-
Notifications
You must be signed in to change notification settings - Fork 1
/
BFS.pl
97 lines (76 loc) · 2.72 KB
/
BFS.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
%connected(+Start, +Goal, -Weight)
connected(1,7,1).
connected(1,8,1).
connected(1,3,1).
connected(7,4,1).
connected(7,20,1).
connected(7,17,1).
connected(8,6,1).
connected(3,9,1).
connected(3,12,1).
connected(9,19,1).
connected(4,42,1).
connected(20,28,1).
connected(17,10,1).
connected2(X,Y,D) :- connected(X,Y,D).
connected2(X,Y,D) :- connected(Y,X,D).
next_node(Current, Next, Path) :-
connected2(Current, Next, _),
not(member(Next, Path)).
depth_first( Start, Goal, Path):-
depth_first( Start, Goal, [Start], Path).
consed(A,B,[B|A]).
bfs(Goal, [Visited|Rest], Path) :- % take one from front
Visited = [Start|_],
Start \== Goal,
findall(X,
(connected2(X,Start,_),not(member(X,Visited))),
[T|Extend]),
maplist( consed(Visited), [T|Extend], VisitedExtended), % make many
append(Rest, VisitedExtended, UpdatedQueue), % put them at the end
bfs( Goal, UpdatedQueue, Path ).
bfs(Goal, [[Goal|Visited]|_], Path):-
reverse([Goal|Visited], Path).
breadth_first( Start, Goal, Path):- bfs( Goal, [[Start]], Path).
state_record(State, Parent, [State, Parent]).
go(Start, Goal) :-
empty_queue(Empty_open),
state_record(Start, nil, State),
add_to_queue(State, Empty_open, Open),
empty_set(Closed),
path(Open, Closed, Goal).
path(Open,_,_) :- empty_queue(Open),
write('graph searched, no solution found').
path(Open, Closed, Goal) :-
remove_from_queue(Next_record, Open, _),
state_record(State, _, Next_record),
State = Goal,
write('Solution path is: '), nl,
printsolution(Next_record, Closed).
path(Open, Closed, Goal) :-
remove_from_queue(Next_record, Open, Rest_of_open),
(bagof(Child, moves(Next_record, Open, Closed, Child), Children);Children = []),
add_list_to_queue(Children, Rest_of_open, New_open),
add_to_set(Next_record, Closed, New_closed),
path(New_open, New_closed, Goal),!.
moves(State_record, Open, Closed, Child_record) :-
state_record(State, _, State_record),
mov(State, Next),
% not (unsafe(Next)),
state_record(Next, _, Test),
not(member_queue(Test, Open)),
not(member_set(Test, Closed)),
state_record(Next, State, Child_record).
printsolution(State_record, _):-
state_record(State,nil, State_record),
write(State), nl.
printsolution(State_record, Closed) :-
state_record(State, Parent, State_record),
state_record(Parent, _, Parent_record),
member(Parent_record, Closed),
printsolution(Parent_record, Closed),
write(State), nl.
add_list_to_queue([], Queue, Queue).
add_list_to_queue([H|T], Queue, New_queue) :-
add_to_queue(H, Queue, Temp_queue),
add_list_to_queue(T, Temp_queue, New_queue).