A* search algorithm: Difference between revisions
Content added Content deleted
m (Correct a parenthesis in CL code) |
No edit summary |
||
Line 3,728: | Line 3,728: | ||
Cost: 11 |
Cost: 11 |
||
Route: (0, 0), (1, 1), (2, 2), (3, 1), (4, 1), (5, 1), (6, 2), (7, 3), (6, 4), (7, 5), (6, 6), (7, 7) |
Route: (0, 0), (1, 1), (2, 2), (3, 1), (4, 1), (5, 1), (6, 2), (7, 3), (6, 4), (7, 5), (6, 6), (7, 7) |
||
</pre> |
|||
=={{header|Python}}== |
|||
<lang Picat>% An A*-like algorithm is used in tabling |
|||
% |
|||
main => |
|||
Maze = new_array(8,8), |
|||
Obs = [(2,4), (2,5), (2,6), (3,6), (4,6), (5,6), (5,5), (5,4), (5,3), (5,2), (4,2), (3,2)], |
|||
foreach ((R0,C0) in Obs) |
|||
Maze[R0+1,C0+1] = 100 |
|||
end, |
|||
foreach (R in 1..8, C in 1..8) |
|||
(var(Maze[R,C]) -> Maze[R,C] = 1; true) |
|||
end, |
|||
search((1,1),(8,8),Maze,Cost,Path), |
|||
writeln(cost=Cost), |
|||
println([(R0,C0) : (R1,C1) in Path, R0 = R1-1, C0 = C1-1]). |
|||
table (+,+,+,min,-) |
|||
search(G,G,_Maze,Cost,Path) => Cost = 0, Path = [G]. |
|||
search(S@(R,C),G,Maze,Cost,Path) => |
|||
neibs(R,C,Neibs), |
|||
member(S1,Neibs), |
|||
S1 = (R1,C1), |
|||
search(S1,G,Maze,Cost1,Path1), |
|||
Cost = Cost1+Maze[R1,C1], |
|||
Path = [S|Path1]. |
|||
neibs(R,C,Neibs) => |
|||
Neibs = [(R1,C1) : Dr in [-1,0,1], Dc in [-1,0,1], R1 = R+Dr, C1 = C+Dc, |
|||
R1 >= 1, R1 <= 8, C1 >= 1, C1 <= 8, (R,C) != (R1,C1)]. |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
cost = 11 |
|||
[(0,0),(1,0),(2,0),(3,0),(4,0),(5,1),(6,2),(6,3),(6,4),(6,5),(6,6),(7,7)] |
|||
</pre> |
</pre> |
||