A* search algorithm: Difference between revisions
Content added Content deleted
(Change in the way to write the path in "printSolution".) |
|||
| Line 2,587: | Line 2,587: | ||
</pre> |
</pre> |
||
=={{header|Python}}== |
<nowiki>'''''=={{header|Python}}== |
||
<lang python>from __future__ import print_function |
<lang python>from __future__ import print_function |
||
| Line 2,595: | Line 2,595: | ||
#Define a class board like grid with two barriers |
#Define a class board like grid with two barriers |
||
def __init__(self): |
#def __init__(self): |
||
# self.barriers = [] |
|||
self.barriers.append([(2,4),(2,5),(2,6),(3,6),(4,6),(5,6),(5,5),(5,4),(5,3),(5,2),(4,2),(3,2)]) |
self.barriers.append([(2,4),(2,5),(2,6),(3,6),(4,6),(5,6),(5,5),(5,4),(5,3),(5,2),(4,2),(3,2)]) |
||
# |
|||
def heuristic(self, start, goal): |
#def heuristic(self, start, goal): |
||
# #Use Chebyshev distance heuristic if we can move one square either |
|||
#adjacent or diagonal |
#adjacent or diagonal |
||
# D = 1 |
|||
D2 = 1 |
D2 = 1 |
||
# dx = abs(start[0] - goal[0]) |
|||
dy = abs(start[1] - goal[1]) |
dy = abs(start[1] - goal[1]) |
||
return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy) |
return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy) |
||
| Line 2,695: | Line 2,695: | ||
<pre>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>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)] |
||
cost 11</pre> |
cost 11</pre> |
||
'''''</nowiki> |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |
||