Skip to content

Commit 9c79f69

Browse files
thuva4thuva4
authored
Merge branch 'master' into master
2 parents 0211239 + 4f1b9d5 commit 9c79f69

File tree

41 files changed

+2762
-520
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

41 files changed

+2762
-520
lines changed

‎A*Search/python/astar.py‎

Lines changed: 147 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,147 @@
1+
# Copyright (c) 2008 Mikael Lind
2+
#
3+
# Permission is hereby granted, free of charge, to any person obtaining a copy
4+
# of this software and associated documentation files (the "Software"), to deal
5+
# in the Software without restriction, including without limitation the rights
6+
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7+
# copies of the Software, and to permit persons to whom the Software is
8+
# furnished to do so, subject to the following conditions:
9+
#
10+
# The above copyright notice and this permission notice shall be included in
11+
# all copies or substantial portions of the Software.
12+
#
13+
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14+
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15+
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16+
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17+
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18+
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
19+
# SOFTWARE.
20+
21+
22+
from heapq import heappush, heappop
23+
from sys import maxint
24+
25+
26+
# Represent each node as a list, ordering the elements so that a heap of nodes
27+
# is ordered by f = g + h, with h as a first, greedy tie-breaker and num as a
28+
# second, definite tie-breaker. Store the redundant g for fast and accurate
29+
# calculations.
30+
31+
F, H, NUM, G, POS, OPEN, VALID, PARENT = xrange(8)
32+
33+
34+
def astar(start_pos, neighbors, goal, start_g, cost, heuristic, limit=maxint,
35+
debug=None):
36+
37+
"""Find the shortest path from start to goal.
38+
Arguments:
39+
start_pos - The starting position.
40+
neighbors(pos) - A function returning all neighbor positions of the given
41+
position.
42+
goal(pos) - A function returning true given a goal position, false
43+
otherwise.
44+
start_g - The starting cost.
45+
cost(a, b) - A function returning the cost for moving from one
46+
position to another.
47+
heuristic(pos) - A function returning an estimate of the total cost
48+
remaining for reaching goal from the given position.
49+
Overestimates can yield suboptimal paths.
50+
limit - The maximum number of positions to search.
51+
debug(nodes) - This function will be called with a dictionary of all
52+
nodes.
53+
The function returns the best path found. The returned path excludes the
54+
starting position.
55+
"""
56+
57+
# Create the start node.
58+
nums = iter(xrange(maxint))
59+
start_h = heuristic(start_pos)
60+
start = [start_g + start_h, start_h, nums.next(), start_g, start_pos, True,
61+
True, None]
62+
63+
# Track all nodes seen so far.
64+
nodes = {start_pos: start}
65+
66+
# Maintain a heap of nodes.
67+
heap = [start]
68+
69+
# Track the best path found so far.
70+
best = start
71+
72+
while heap:
73+
74+
# Pop the next node from the heap.
75+
current = heappop(heap)
76+
current[OPEN] = False
77+
78+
# Have we reached the goal?
79+
if goal(current[POS]):
80+
best = current
81+
break
82+
83+
# Visit the neighbors of the current node.
84+
for neighbor_pos in neighbors(current[POS]):
85+
neighbor_g = current[G] + cost(current[POS], neighbor_pos)
86+
neighbor = nodes.get(neighbor_pos)
87+
if neighbor is None:
88+
89+
# Limit the search.
90+
if len(nodes) >= limit:
91+
continue
92+
93+
# We have found a new node.
94+
neighbor_h = heuristic(neighbor_pos)
95+
neighbor = [neighbor_g + neighbor_h, neighbor_h, nums.next(),
96+
neighbor_g, neighbor_pos, True, True, current[POS]]
97+
nodes[neighbor_pos] = neighbor
98+
heappush(heap, neighbor)
99+
if neighbor_h < best[H]:
100+
101+
# We are approaching the goal.
102+
best = neighbor
103+
104+
elif neighbor_g < neighbor[G]:
105+
106+
# We have found a better path to the neighbor.
107+
if neighbor[OPEN]:
108+
109+
# The neighbor is already open. Finding and updating it
110+
# in the heap would be a linear complexity operation.
111+
# Instead we mark the neighbor as invalid and make an
112+
# updated copy of it.
113+
114+
neighbor[VALID] = False
115+
nodes[neighbor_pos] = neighbor = neighbor[:]
116+
neighbor[F] = neighbor_g + neighbor[H]
117+
neighbor[NUM] = nums.next()
118+
neighbor[G] = neighbor_g
119+
neighbor[VALID] = True
120+
neighbor[PARENT] = current[POS]
121+
heappush(heap, neighbor)
122+
123+
else:
124+
125+
# Reopen the neighbor.
126+
neighbor[F] = neighbor_g + neighbor[H]
127+
neighbor[G] = neighbor_g
128+
neighbor[PARENT] = current[POS]
129+
neighbor[OPEN] = True
130+
heappush(heap, neighbor)
131+
132+
# Discard leading invalid nodes from the heap.
133+
while heap and not heap[0][VALID]:
134+
heappop(heap)
135+
136+
if debug is not None:
137+
# Pass the dictionary of nodes to the caller.
138+
debug(nodes)
139+
140+
# Return the best path as a list.
141+
path = []
142+
current = best
143+
while current[PARENT] is not None:
144+
path.append(current[POS])
145+
current = nodes[current[PARENT]]
146+
path.reverse()
147+
return path

‎A*Search/python/astar.pyc‎

2.68 KB
Binary file not shown.

0 commit comments

Comments
 (0)