% A-Star Search
% COMP3411/9414/9814 Artificial Intelligence, UNSW,
Copyright By PowCoder代写 加微信 powcoder
% solve(Start, Solution, G, N)
% Solution is a path (in reverse order) from the start node to a goal state.
% G is the length of the path, N is the number of nodes expanded.
solve(Start, Solution, G, N) :-
consult(pathsearch), % insert_legs(), head_member(), build_path()
h(Start,H),
astar([[Start,Start,0,H]], [], Solution, G, 1, N).
% astar(Generated, Expanded, Solution, L, N)
% Generated = [[Node1,Prev1,G1,H1],[Node2,Prev2,G2,H2],…,[Start,Start,0,H0]]
% Expanded = [[Node1,Prev1],[Node2,Prev2],…,[Start,Start]]
% Store the steps generated but not yet expanded in a queue
% sorted in increasing order of G+H.
% If the next leg to be expanded begins with a goal node,
% stop searching, build the path and return it.
astar([[Node,Pred,G,_H]|_Generated], Expanded, Path, G, N, N) :-
goal(Node),
build_path([[Node,Pred]|Expanded], Path).
% Extend the leg at the head of the queue by adding the
% successors of its head node.
% Add these newly created legs to the end of the queue
astar([[Node,Pred,G,_H]| Generated], Expanded, Solution, G1, L, N) :-
extend(Node, G, Expanded, NewLegs),
M is L + 1,
insert_legs(Generated, NewLegs, Generated1),
astar(Generated1, [[Node,Pred]|Expanded], Solution, G1, M, N).
% find all successor nodes to this node, and check in each case
% that the new node has not previously been expanded
extend(Node, G, Expanded, NewLegs) :-
% write(Node),nl, % print nodes as they are expanded
findall([NewNode, Node, G1, H], (s(Node, NewNode, C)
, not(head_member(NewNode, Expanded))
, G1 is G + C
, h(NewNode, H)
), NewLegs).
% base case: insert one leg into an empty list.
insert_one_leg([], Leg, [Leg]).
% If we already knew a shorter path to the same node, discard the new one.
insert_one_leg([Leg1|Generated], Leg, [Leg1|Generated]) :-
Leg = [Node,_Pred, G, _H],
Leg1 = [Node,_Pred1,G1,_H1],
G >= G1, ! .
% Insert the new leg in its correct place in the list (ordered by G+H).
insert_one_leg([Leg1|Generated], Leg, [Leg,Leg1|Generated]) :-
Leg = [_Node, _Pred, G, H ],
Leg1 = [_Node1,_Pred1,G1,H1],
F1 is G1 + H1,
F is G + H,
F < F1, ! .
% Search recursively for the correct place to insert.
insert_one_leg([Leg1|Generated], Leg, [Leg1|Generated1]) :-
insert_one_leg(Generated, Leg, Generated1).
% Breadth First Search, using Dijkstras Algorithm
% COMP3411/9414 Artificial Intelligence, UNSW,
% This is a memory-efficient implementation of BFS, which is a
% special case of Dijkstras algorithm. It is designed to find
% only one solution (which is guaranteed to be the shortest path).
% solve(Start, Solution, D, N)
% Solution is a path (in reverse order) from start node to a goal state.
% D is the depth of the path, N is the number of nodes expanded.
solve(Start, Solution, D, N) :-
consult(pathsearch), % head_member(), build_path()
bfsdijkstra([[Start,Start]], [], Solution, 1, N),
length(Solution, D1),
D is D1 - 1.
% bfsdijkstra(Generated, Expanded, Solution, L, N)
% The algorithm builds a list of generated "legs" in the form
% Generated = [[Node1,Prev1],[Node2,Prev2],...,[Start,Start]]
% sorted in increasing order of path length from the start node.
% Expanded nodes are moved to a separate list.
% If the next leg to be expanded reaches a goal node,
% stop searching, build the path and return it.
bfsdijkstra([[Node,Pred]|_Generated], Expanded, Path, N, N) :-
goal(Node),
build_path([[Node,Pred]|Expanded], Path).
% Take the the leg at the head of the queue and extend it,
% by generating the successors of its destination node.
% Append these new legs to the back of the queue, and keep searching.
bfsdijkstra([[Node,Pred]|Generated], Expanded, Solution, L, N) :-
extend(Node, Generated, Expanded, NewLegs),
M is L + 1,
append(Generated, NewLegs, Generated1),
bfsdijkstra(Generated1, [[Node,Pred]|Expanded], Solution, M, N).
% Find all successor nodes to this node, and check in each case
% that the new node has not previously been generated or expanded.
extend(Node, Generated, Expanded, NewLegs) :-
% write(Node),nl, % print nodes as they are expanded
findall([NewNode,Node], (s(Node, NewNode, _)
, not(head_member(NewNode, Generated))
, not(head_member(NewNode, Expanded))
), NewLegs).
% breadthfirst.pl
% Breadth First Search
% COMP3411/9414/9814 Artificial Intelligence, UNSW,
% solve(Start, Solution, D, N)
% Solution is a path (in reverse order) from start node to a goal state.
% D is the depth of the path, N is the number of nodes expanded.
solve(Start, Solution, D, N) :-
breadthfirst([[Start]], Solution, 1, N),
length(Solution, D1),
D is D1 - 1.
% breadthfirst([Path1, Path2, ...], Solution, L, N)
% Store the paths generated but not yet expanded in a queue,
% sorted in order of increasing path depth (number of nodes).
% Each path is a list of nodes in reverse order,
% with the start node at the back end of the list.
% If the next path to be expanded reaches a goal node,
% return this path.
breadthfirst([[Node|Path]|_], [Node|Path], N, N) :-
goal(Node).
% Take the path at the front of the queue and extend it,
% by adding successors of its head node. Append these newly
% created paths to the back of the queue, and keep searching.
breadthfirst([Path|Paths], Solution, L, N) :-
extend(Path, NewPaths),
M is L + 1,
append(Paths, NewPaths, Paths1),
breadthfirst(Paths1, Solution, M, N).
% Find all successor nodes to this node, and check in each case
% that the new node does not already occur along the path.
extend([Node|Path], NewPaths) :-
% write(Node),nl, % print nodes as they are expanded
findall([NewNode,Node|Path], (s(Node, NewNode, _)
, not(member(NewNode, [Node|Path])) % exclude repeated states
), NewPaths).
% Depth First Search
% COMP3411/9414/9814 Artificial Intelligence, UNSW,
% solve(Node, Solution, D, N)
% Solution is a path (in reverse order) from start node to a goal state.
% D is the depth of the path, N is the number of nodes expanded.
solve(Node, Solution, D, N) :-
nb_setval(counter,0),
depthfirst([], Node, Solution),
nb_getval(counter,N),
length(Solution, D1),
D is D1 - 1.
% depthfirst(Path, Node, Solution)
% Use depth first search to find a solution recursively.
% If the next node to be expanded is a goal node, add it to
% the current path and return this path.
depthfirst(Path, Node, [Node|Path]) :-
goal(Node).
% Otherwise, use Prolog backtracking to explore all successors
% of the current node, in the order returned by s.
depthfirst(Path, Node, Sol) :-
nb_getval(counter, N),
N1 is N + 1,
nb_setval(counter, N1),
write(Node),nl,
s(Node, Node1, _), % Ignore cost
not(member(Node1, Path)), % Prevent a cycle
depthfirst([Node|Path], Node1, Sol).
% generate.pl
generate(Node, 0, Node).
generate(Start, N, Final) :-
N1 is N - 1,
findall( NextNode, (s(Start,NextNode,_C)), NodeList),
length(NodeList, Num),
K is random(Num),
nth0(K, NodeList, Node1),
generate(Node1, N1, Final).
% Greedy ( ) Search
% COMP3411/9414/9814 Artificial Intelligence, UNSW,
% solve(Start, Solution, G, N)
% Solution is a path (in reverse order) from start node to a goal state.
% G is the length of the path, N is the number of nodes expanded.
solve(Start, Solution, D, N) :-
consult(pathsearch), % insert_legs(), head_member(), build_path()
h(Start,H),
greedy([[Start,Start,H]], [], Solution, 1, N),
length(Solution, D1),
D is D1 - 1.
% greedy(Generated, Expanded, Solution, L, N)
% The algorithm builds a list of generated "legs" in the form
% Generated = [[Node1,Prev1,H1],[Node2,Prev2,H2],...,[Start,Start,H]]
% The heuristic H is stored with each leg,
% and the legs are listed in increasing order of H.
% The expanded nodes are moved to another list (H is discarded)
% Expanded = [[Node1,Prev1],[Node2,Prev2],...,[Start,Start]]
% If the next leg to be expanded reaches a goal node,
% stop searching, build the path and return it.
greedy([[Node,Pred,_H]|_Generated], Expanded, Path, N, N) :-
goal(Node),
build_path([[Node,Pred]|Expanded], Path).
% Extend the leg at the head of the queue by generating the
% successors of its destination node.
% Insert these newly created legs into the list of generated nodes,
% keeping it sorted in increasing order of H; and continue searching.
greedy([[Node,Pred,_H]|Generated], Expanded, Solution, L, N) :-
extend(Node, Generated, Expanded, NewLegs),
M is L + 1,
insert_legs(Generated, NewLegs, Generated1),
greedy(Generated1, [[Node,Pred]|Expanded], Solution, M, N).
% Find all successor nodes to this node, and check in each case
% that the new node has not previously been generated or expanded.
extend(Node, Generated, Expanded, NewLegs) :-
% write(Node),nl, % print nodes as they are expanded
findall([NewNode, Node, H], (s(Node, NewNode, _C)
, not(head_member(NewNode, Generated))
, not(head_member(NewNode, Expanded))
, h(NewNode, H)
), NewLegs).
% base case: insert one leg into an empty list.
insert_one_leg([], Leg, [Leg]).
% Insert the new leg in its correct place in the list (ordered by H).
insert_one_leg([Leg1|Generated], Leg, [Leg,Leg1|Generated]) :-
Leg = [_Node, _Pred, H ],
Leg1 = [_Node1,_Pred1,H1],
H < H1, ! .
% Search recursively for the correct place to insert.
insert_one_leg([Leg1|Generated], Leg, [Leg1|Generated1]) :-
insert_one_leg(Generated, Leg, Generated1).
% Iterative Deepening A-Star Search
% COMP3411/9414/9814 Artificial Intelligence, UNSW,
% solve(Start, Solution, G, N)
% Solution is a path (in reverse order) from Node to a goal state.
% G is the length of the path, N is the number of nodes expanded.
solve(Start, Solution, G, N) :-
nb_setval(counter,0),
idastar(Start, 0, Solution, G),
nb_getval(counter,N).
% Perform a series of depth-limited searches with increasing F_limit.
idastar(Start, F_limit, Solution, G) :-
depthlim([], Start, 0, F_limit, Solution, G).
idastar(Start, F_limit, Solution, G) :-
write(F_limit),nl,
F_limit1 is F_limit + 2, % suitable for puzzles with parity
idastar(Start, F_limit1, Solution, G).
% depthlim(Path, Node, Solution)
% Use depth first search (restricted to nodes with F <= F_limit)
% to find a solution which extends Path, through Node.
% If the next node to be expanded is a goal node, add it to
% the current path and return this path, as well as G.
depthlim(Path, Node, G, _F_limit, [Node|Path], G) :-
goal(Node).
% Otherwise, use Prolog backtracking to explore all successors
% of the current node, in the order returned by s.
% Keep searching until goal is found, or F_limit is exceeded.
depthlim(Path, Node, G, F_limit, Sol, G2) :-
nb_getval(counter, N),
N1 is N + 1,
nb_setval(counter, N1),
% write(Node),nl, % print nodes as they are expanded
s(Node, Node1, C),
not(member(Node1, Path)), % Prevent a cycle
G1 is G + C,
h(Node1, H1),
F1 is G1 + H1,
F1 =< F_limit,
depthlim([Node|Path], Node1, G1, F_limit, Sol, G2).
% Iterative Deepening (Depth First) Search
% COMP3411/9414/9814 Artificial Intelligence, UNSW,
% solve(Node, Solution, D, N)
% Solution is a path (in reverse order) from Start to a goal state
% D is the depth of the path, N is the number of nodes expanded.
solve(Node, Solution, D, N) :-
nb_setval(counter,0),
ideepsearch([], Node, 0, Solution),
nb_getval(counter,N),
length(Solution, D1),
D is D1 - 1.
% Perform a series of depth-limited searches with increasing depth.
ideepsearch(Path, Node, D, Solution) :-
depthlim(Path, Node, D, Solution).
ideepsearch(Path, Node, D, Solution) :-
D1 is D + 1,
write(D1),nl,
ideepsearch(Path, Node, D1, Solution).
% depthlim(Path, Node, D, Solution)
% Use depth first search to look for a solution recursively,
% up to the specified depth limit (D).
% If the next node to be expanded is a goal node, append it to
% the current path and return this path.
depthlim(Path, Node, _D, [Node|Path]) :-
goal(Node).
% Otherwise, use Prolog backtracking to explore all successors
% of the current node, in the order returned by s.
% Keep searching until goal is found, or depth limit is reached.
depthlim(Path, Node, D, Sol) :-
D1 is D - 1,
nb_getval(counter, N),
N1 is N + 1,
nb_setval(counter, N1),
% write(Node),nl, % print nodes as they are expanded
s(Node, Node1, _),
not(member(Node1, Path)), % Prevent a cycle
depthlim([Node|Path], Node1, D1, Sol).
% pathsearch.pl
% COMP3411/9414/9814 Artificial Intelligence, UNSW,
% This file provides code for insert_legs(), head_member() and build_path()
% used by bfsdijkstra(), ucsdijkstra(), greedy() and astar().
% insert_legs(Generated, Legs, Generated1).
% insert new legs into list of generated legs,
% by repeatedly calling insert_one_leg()
% base case: no legs to be inserted
insert_legs(Generated, [], Generated).
% Insert the first leg using insert_one_leg(); and continue.
insert_legs(Generated, [Leg|Legs], Generated2) :-
insert_one_leg(Generated, Leg, Generated1),
insert_legs(Generated1, Legs, Generated2).
% head_member(Node, List)
% check whether Node is the head of a member of List.
% base case: node is the head of first item in list.
head_member(Node,[[Node,_]|_]).
% otherwise, keep searching for node in the tail.
head_member(Node,[_|Tail]) :-
head_member(Node,Tail).
% build_path(Expanded, [[Node,Pred]], Path).
% build_path(Legs, Path)
% Construct a path from a list of legs, by joining the ones that match.
% base case: join the last two legs to form a path of one step.
build_path([[Next,Start],[Start,Start]], [Next,Start]).
% If the first two legs match, add to the front of the path.
build_path([[C,B],[B,A]|Expanded],[C,B,A|Path]) :-
build_path([[B,A]|Expanded],[B,A|Path]), ! .
% If the above rule fails, we skip the next leg in the list.
build_path([Leg,_SkipLeg|Expanded],Path) :-
build_path([Leg|Expanded],Path).
% Problem-specific procedures for 8-Puzzle and 15-Puzzle
% Refer to Bratko Figure 12.3.
/* Problem-specific procedures for the 8-Puzzle
Current state is represented as a list of positions of tiles
in the form R/C, with the first item corresponding to the
position of "empty" and the rest to those of the tiles 1-8.
State Representation
+-----------+
1 | 1 2 3 |
2 | 4 5 6 | [3/3, 1/1, 1/2, 1/3, 2/1, 2/2, 2/3, 3/1, 3/2]
3 | 7 8 |
+-----------+
Moves are handled by swapping the positions of "empty" and one of its
neighbours.
The 15-Puzzle is represented in an analogous way, with 4 rows and columns.
% s(Node, SuccessorNode, Cost)
s([Empty|Tiles], [Tile|Tiles1], 1) :- % All arc costs are 1
swap(Empty, Tile, Tiles, Tiles1). % Swap Empty and Tile in Tiles
swap(Empty, Tile, [Tile|Ts], [Empty|Ts]) :- % Swap allowed if Man Dist = 1
mandist(Empty, Tile, 1).
swap(Empty, Tile, [T1|Ts], [T1|Ts1]) :-
swap(Empty, Tile, Ts, Ts1).
mandist(X/Y, X1/Y1, D) :- % D is Manhattan Dist between two positions
dif(X, X1, Dx),
dif(Y, Y1, Dy),
D is Dx + Dy.
dif(A, B, D) :- % D is |A-B|
D is A-B, D >= 0, !.
dif(A, B, D) :- % D is |A-B|
goal(Pos) :-
length(Pos,9),
goal3(Pos).
goal(Pos) :-
length(Pos,16),
goal4(Pos).
goal3([3/3,1/1,1/2,1/3,2/1,2/2,2/3,3/1,3/2]).
goal4([4/4,1/1,1/2,1/3,1/4,2/1,2/2,2/3,2/4,3/1,3/2,3/3,3/4,4/1,4/2,4/3]).
% Display a solution path as a list of board positions
showsol([]).
showsol([P|L]) :-
showsol(L),
nl, write(‘—-‘),
showpos(P).
% Display a board position for the 8-Puzzle (3×3)
showpos([S0,S1,S2,S3,S4,S5,S6,S7,S8]) :-
member(R, [1,2,3]), nl, % Order to display Row
member(C, [1,2,3]), % Order to display Col
member(Tile-R/C, % Tile currently at position R/C
[‘ ‘-S0,1-S1,2-S2,3-S3,4-S4,5-S5,6-S6,7-S7,8-S8]),
write(Tile),
fail % Backtrack to next position
true. % All positions displayed
% Display a board position for the 15-Puzzle (4×4)
showpos([S0,S1,S2,S3,S4,S5,S6,S7,S8,S9,S10,S11,S12,S13,S14,S15]) :-
member(R, [1,2,3,4]), nl, % Order to display Row
member(C, [1,2,3,4]), % Order to display Col
member(Tile-R/C, % Tile currently at position R/C
[‘ ‘-S0,’A’-S1,’B’-S2, ‘C’-S3, ‘D’-S4, ‘E’-S5, ‘F’-S6, ‘G’-S7,
‘H’-S8,’I’-S9,’J’-S10,’K’-S11,’L’-S12,’M’-S13,’N’-S14,’O’-S15]),
write(Tile),
fail % Backtrack to next position
true. % All positions displayed
% Start positions, named according to the minimum number of moves
start10([4/4,1/1,1/2,1/3,1/4,2/1,2/2,2/3,2/4,4/2,3/2,3/3,3/4,3/1,4/1,4/3]). % N= 29
start12([4/4,1/1,1/2,1/3,1/4,2/1,2/3,3/2,2/4,3/1,3/3,3/4,4/3,4/1,2/2,4/2]). % N= 21
start20([3/1,1/1,1/3,2/3,1/4,2/2,1/2,3/3,2/4,2/1,3/2,4/2,3/4,4/3,4/1,4/4]). % N= 952
start30([3/3,1/2,1/4,1/3,2/4,4/1,1/1,2/3,3/4,4/2,2/1,2/2,4/4,3/2,3/1,4/3]). % N= 17297
start40([1/3,2/1,2/2,1/4,3/3,2/4,2/3,4/1,4/3,3/1,1/1,3/4,4/4,1/2,3/2,4/2]). % N= 112571
start50([2/2,4/2,2/3,1/1,3/1,1/3,4/4,2/4,2/1,1/2,1/4,3/3,3/4,4/1,3/2,4/3]). % N= 14642512
start60([3/1,1/4,4/4,1/3,4/3,3/3,2/3,4/1,4/2,3/2,2/1,1/2,3/4,2/2,2/4,1/1]). % N= 321252368
start64([1/1,4/4,4/2,2/1,4/1,3/4,2/3,2/2,3/2,3/3,1/2,1/3,1/4,4/3,2/4,3/1]). % N=1209086782
% Example query: ?- start10(Pos), solve(Pos, Sol, G, N), showsol(Sol).
% ——————————————————————–
% The rest is needed only for A*Search (To compute the heuristic)
% ——————————————————————–
% Heuristic estimate h is the sum of distances of each tile
% from its “home” position.
h(Pos, H) :-
length(Pos, 9),
h3(Pos,H).
h(Pos, H) :-
length(Pos, 16),
h4(Pos,H).
h3([_Empty|Tiles], H) :-
goal3([_Empty1|GoalPositions]),
totdist(Tiles, GoalPositions, D), % Total dist from home positions
h4([_Empty|Tiles], H) :-
goal4([_Empty1|GoalPositions]),
totdist(Tiles, GoalPositions, D), % Total dist from home positions
totdist([], [], 0).
totdist([Tile|Tiles], [Position|Positions], D) :-
mandist(Tile, Position, D1),
totdist(Tiles, Positions, D2),
D is D1 + D2.
% romania.pl
goal(bucharest).
s(arad,sibiu,140).
s(arad,timisoara,118).
s(arad,zerind,75).
s(bucharest,fagaras,211).
s(bucharest,giurgiu,90).
s(bucharest,pitesti,101).
s(bucharest,urziceni,85).
s(craiova,dobreta,120).
s(craiova,pitesti,138).
s(craiova,rimnicu_vilcea,146).
s(dobreta,craiova,120).
s(dobreta,mehadia,75).
s(eforie,hirsova,86).
s(fagaras,bucharest,211).
s(fagaras,sibiu,99).
s(giurgiu,bucharest,90).
s(hirsova,eforie,86).
s(hirsova,urziceni,98).
s(iasi,neamt,87).
s(iasi,vaslui,92).
s(lugoj,mehadia,70).
s(lugoj,timisoara,111).
s(mehadia,dobreta,75).
s(mehadia,lugoj,70).
s(neamt,iasi,87).
s(oradea,sibiu,151).
s(oradea,zerind,71).
s(pitesti,bucharest,101).
s(pitesti,craiova,138).
s(pitesti,rimnicu_vilcea,97).
s(rimnicu_vilcea,craiova,146).
s(rimnicu_vilcea,pitesti,97).
s(rimnicu_vilcea,sibiu,80).
s(sibiu,arad,140).
s(sibiu,fagaras,99).
s(sibiu,oradea,151).
s(sibiu,rimnicu_vilcea,80).
s(timisoara,arad,118).
s(timisoara,lugoj,111).
s(urziceni,bucharest,85).
s(urziceni,hirsova,98).
s(urziceni,vaslui,142).
s(vaslui,iasi,92).
s(vaslui,urziceni,142).
s(zerind,arad,75).
s(zerind,oradea,71).
h(arad,366).
h(bucharest,0).
h(craiova,160).
h(dobreta,242).
h(eforie,161).
h(fagaras,178).
h(giurgiu,77).
h(hirsova,151).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com