Jag kommer att visa dig hur man implementerar en A* (A-stjärna) sökalgoritm i den här handledningen, algoritmen kommer att användas för att lösa ett rutnätsproblem och ett grafproblem i Python. Sökalgoritmen A* använder den totala sökkostnaden som heuristik, kostnaden från startnoden plus den uppskattade kostnaden till målnoden.
A* är en informerad algoritm eftersom den använder en heuristik för att vägleda sökningen. Algoritmen startar från en initial startnod, expanderar grannar och uppdaterar den totala sökvägskostnaden för varje granne. Algoritmen väljer grannen med lägst kostnad och fortsätter tills den hittar en målnod, detta kan implementeras med en prioriteringskö eller genom att sortera listan med öppna noder i stigande ordning. Det är viktigt att välja en bra heuristik för att göra A* snabb i sökningar, en bra heuristik bör vara nära den faktiska kostnaden men inte högre än den faktiska kostnaden.
En A*-sökning är komplett och optimal, den hittar den kortaste vägen till målet. En bra heuristik kan göra sökningen mycket snabb, men det kan ta lång tid och konsumera mycket minne i ett stort sökutrymme. Tidskomplexiteten är O(n) i ett rutnät och O(b^d) i en graf eller ett träd med en förgreningsfaktor (b) och ett djup (d) . Förgreningsfaktorn är det genomsnittliga antalet grannnoder som kan utökas från varje nod och djupet är det genomsnittliga antalet nivåer i en graf eller ett träd.
Rutnätsproblem (labyrint)
Jag har skapat en enkel labyrint (ladda ner) med väggar, en startpunkt (@) och ett mål ($). Målet med A*-algoritmen är att hitta den kortaste vägen från startpunkten till målpunkten, detta gärna så snabbt som möjligt. Den fulla sökvägskostnaden (f) för varje nod beräknas som avståndet till startnoden (g) plus avståndet till målnoden (h). Avstånd beräknas som manhattanavståndet (taxigeometri) mellan noder.
# This class represents a node
class Node:
# Initialize the class
def __init__(self, position:(), parent:()):
self.position = position
self.parent = parent
self.g = 0 # Distance to start node
self.h = 0 # Distance to goal node
self.f = 0 # Total cost
# Compare nodes
def __eq__(self, other):
return self.position == other.position
# Sort nodes
def __lt__(self, other):
return self.f < other.f
# Print node
def __repr__(self):
return ('({0},{1})'.format(self.position, self.f))
# Draw a grid
def draw_grid(map, width, height, spacing=2, **kwargs):
for y in range(height):
for x in range(width):
print('%%-%ds' % spacing % draw_tile(map, (x, y), kwargs), end='')
print()
# Draw a tile
def draw_tile(map, position, kwargs):
# Get the map value
value = map.get(position)
# Check if we should print the path
if 'path' in kwargs and position in kwargs['path']: value = '+'
# Check if we should print start point
if 'start' in kwargs and position == kwargs['start']: value = '@'
# Check if we should print the goal point
if 'goal' in kwargs and position == kwargs['goal']: value = '$'
# Return a tile value
return value
# A* search
def astar_search(map, start, end):
# Create lists for open nodes and closed nodes
open = []
closed = []
# Create a start node and an goal node
start_node = Node(start, None)
goal_node = Node(end, None)
# Add the start node
open.append(start_node)
# Loop until the open list is empty
while len(open) > 0:
# Sort the open list to get the node with the lowest cost first
open.sort()
# Get the node with the lowest cost
current_node = open.pop(0)
# Add the current node to the closed list
closed.append(current_node)
# Check if we have reached the goal, return the path
if current_node == goal_node:
path = []
while current_node != start_node:
path.append(current_node.position)
current_node = current_node.parent
#path.append(start)
# Return reversed path
return path[::-1]
# Unzip the current node position
(x, y) = current_node.position
# Get neighbors
neighbors = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
# Loop neighbors
for next in neighbors:
# Get value from map
map_value = map.get(next)
# Check if the node is a wall
if(map_value == '#'):
continue
# Create a neighbor node
neighbor = Node(next, current_node)
# Check if the neighbor is in the closed list
if(neighbor in closed):
continue
# Generate heuristics (Manhattan distance)
neighbor.g = abs(neighbor.position[0] - start_node.position[0]) + abs(neighbor.position[1] - start_node.position[1])
neighbor.h = abs(neighbor.position[0] - goal_node.position[0]) + abs(neighbor.position[1] - goal_node.position[1])
neighbor.f = neighbor.g + neighbor.h
# Check if neighbor is in open list and if it has a lower f value
if(add_to_open(open, neighbor) == True):
# Everything is green, add neighbor to open list
open.append(neighbor)
# Return None, no path is found
return None
# Check if a neighbor should be added to open list
def add_to_open(open, neighbor):
for node in open:
if (neighbor == node and neighbor.f >= node.f):
return False
return True
# The main entry point for this module
def main():
# Get a map (grid)
map = {}
chars = ['c']
start = None
end = None
width = 0
height = 0
# Open a file
fp = open('data\\maze.in', 'r')
# Loop until there is no more lines
while len(chars) > 0:
# Get chars in a line
chars = [str(i) for i in fp.readline().strip()]
# Calculate the width
width = len(chars) if width == 0 else width
# Add chars to map
for x in range(len(chars)):
map[(x, height)] = chars[x]
if(chars[x] == '@'):
start = (x, height)
elif(chars[x] == '$'):
end = (x, height)
# Increase the height of the map
if(len(chars) > 0):
height += 1
# Close the file pointer
fp.close()
# Find the closest path from start(@) to end($)
path = astar_search(map, start, end)
print()
print(path)
print()
draw_grid(map, width, height, spacing=1, path=path, start=start, goal=end)
print()
print('Steps to goal: {0}'.format(len(path)))
print()
# Tell python to run main method
if __name__ == "__main__": main()#################################################################################
#.#...#....$....#...................#...#.........#.......#.............#.......#
#.#.#.#.###+###.#########.#########.#.#####.#####.#####.#.#.#######.###.#.#####.#
#...#.....#+++#.#.........#.#.....#.#...#...#...#.......#.#.#.......#.#.#.#...#.#
#############+#.#.#########.#.###.#.###.#.###.#.#.#######.###.#######.#.#.#.#.#.#
#+++++++++++#+#...#.#.....#...#...#...#.#.#.#.#...#...#.......#.......#.#.#.#.#.#
#+#########+#+#####.#.#.#.#.###.#####.#.#.#.#.#####.#.#########.###.###.###.#.#.#
#+#........+#+++#...#.#.#.#...#.....#.#.#.#...#.#...#.......#.....#.#...#...#...#
#+#########+#.#+###.#.#.#####.###.#.#.#.#.#.###.#.#########.#####.#.#.###.#####.#
#+#+++++++#+#.#+++#...#.#.....#.#.#.#...#.#.....#.#.....#.#...#...#.......#...#.#
#+#+#####+#+#.###+#####.#.#####.#.#.###.#.#######.###.#.#.###.#.###########.#.#.#
#+++#+++#+#+#...#+++++#.#.......#.#.#...#.....#...#...#.....#.#.#...#...#...#...#
#####+#+#+#+#########+#.#######.#.###.#######.#.###.#########.###.#.#.#.#.#######
#+++++#+++#+#+++++++++#.......#.#...#.#.#.....#.#.....#.......#...#.#.#.#.#.....#
#+#########+#+#########.###.###.###.#.#.#.###.#.#.###.#.#######.###.#.###.#.###.#
#+++#.#+++++#+++#.....#.#.#...#.#.#.....#...#.#.#...#.#...#...#...#.#.#...#...#.#
###+#.#+#####.#+#.#.###.#.###.#.#.#####.###.###.#####.###.#.#.#.###.#.#.#####.#.#
#+++#+++#.....#+#.#.#...#...#.....#...#.#...#...........#.#.#...#...#.......#.#.#
#+###+#########+#.#.#.###.#.#####.#.#.###.###.###########.#.#####.#########.###.#
#+#..+++++++++++#.#.......#.#...#.#.#...#.#...#.#.......#.......#.#...#.....#...#
#+#.#############.#########.#.#.###.###.#.#.###.#.#####.#.#######.#.#.#.#####.#.#
#+#.#+++++++++++#.#.#.#.....#.#.....#...#.#.....#...#.#.#.#.#...#.#.#.#.#.....#.#
#+###+#########+#.#.#.#######.#######.###.#####.###.#.#.#.#.###.#.#.#.#.#####.#.#
#+++++#+++#+++++#...#.........#.....#...#.....#...#...#.#.....#.#...#.#.#.....#.#
#.#####+#+#+#######.###########.#######.#.#######.###.#.###.###.#####.#.#.#####.#
#.....#+#+#+++#...#.#+++++++#.........#.#...#.......#.#.#...#...#.....#.#.#...#.#
#######+#+###+#.###.#+#####+#.#####.###.#.#.#.#######.#.#####.###.#####.#.###.#.#
#+++++++#+#+++#.....#+#...#+#...#.#.....#.#.#.#.#.....#...#...#...#.....#...#.#.#
#+#######+#+#.#####.#+###.#+###.#.#######.#.#.#.#.#######.#.###.#.###.#####.#.#.#
#+#.#+++++#+#.#+++#.#+++#.#+++#...#.#...#.#...#.#.....#.#...#...#...#.......#...#
#+#.#+#####+#.#+#+#####+#.###+###.#.#.#.#.#####.#####.#.#####.#####.#########.###
#+#..+#..+++#.#+#+#+++#+++#.#+#...#...#.#.#...#.....#...#.#...#...#.....#...#.#.#
#+###+###+#.###+#+#+#+###+#.#+#.#######.#.#.#.#####.###.#.#.###.#.#####.###.#.#.#
#+++#+++#+#.#+++#+#+#+++#+#.#+#.#.......#...#.........#.#...#...#.#...#...#.#...#
#.#+###+#+#.#+###+#+###+#+#.#+#.###.###.###########.###.#.###.###.###.###.#.###.#
#.#+++#+#+#.#+++#+++#+++#+#.#+#.....#...#...#.....#.#...#.....#.....#.#...#...#.#
#.###+#+#+#####+#####+#.#+#.#+#######.###.#.#####.#.#.#############.#.#.###.#.#.#
#...#+#+++#+++#+++++#+#.#+#.#+#+++#...#.#.#.......#.#.#...#...#...#...#.#.#.#...#
###.#+#####+#+#####+#+###+#.#+#+#+#.###.#.#########.#.#.#.#.#.#.#.#####.#.#.#####
#...#+++++++#+++++++#+++++..#+++#+++++++@...........#...#...#...#.......#.......#
#################################################################################
Steps to goal: 339Grafproblem
Målet med detta grafproblem är att hitta den kortaste vägen mellan en startplats och destinationsplats. En karta har använts för att skapa en graf med faktiska avstånd mellan platser. A*-algoritmen använder en Graph-klass, en Node-klass och heuristik för att hitta den kortaste vägen på ett snabbt sätt. Heuristiken mäts som raka sträckor (flyg-avstånd) mellan platser, flyg-avståndet kommer aldrig att vara större än det faktiska avståndet.
# This class represent a graph
class Graph:
# Initialize the class
def __init__(self, graph_dict=None, directed=True):
self.graph_dict = graph_dict or {}
self.directed = directed
if not directed:
self.make_undirected()
# Create an undirected graph by adding symmetric edges
def make_undirected(self):
for a in list(self.graph_dict.keys()):
for (b, dist) in self.graph_dict[a].items():
self.graph_dict.setdefault(b, {})[a] = dist
# Add a link from A and B of given distance, and also add the inverse link if the graph is undirected
def connect(self, A, B, distance=1):
self.graph_dict.setdefault(A, {})[B] = distance
if not self.directed:
self.graph_dict.setdefault(B, {})[A] = distance
# Get neighbors or a neighbor
def get(self, a, b=None):
links = self.graph_dict.setdefault(a, {})
if b is None:
return links
else:
return links.get(b)
# Return a list of nodes in the graph
def nodes(self):
s1 = set([k for k in self.graph_dict.keys()])
s2 = set([k2 for v in self.graph_dict.values() for k2, v2 in v.items()])
nodes = s1.union(s2)
return list(nodes)
# This class represent a node
class Node:
# Initialize the class
def __init__(self, name:str, parent:str):
self.name = name
self.parent = parent
self.g = 0 # Distance to start node
self.h = 0 # Distance to goal node
self.f = 0 # Total cost
# Compare nodes
def __eq__(self, other):
return self.name == other.name
# Sort nodes
def __lt__(self, other):
return self.f < other.f
# Print node
def __repr__(self):
return ('({0},{1})'.format(self.name, self.f))
# A* search
def astar_search(graph, heuristics, start, end):
# Create lists for open nodes and closed nodes
open = []
closed = []
# Create a start node and an goal node
start_node = Node(start, None)
goal_node = Node(end, None)
# Add the start node
open.append(start_node)
# Loop until the open list is empty
while len(open) > 0:
# Sort the open list to get the node with the lowest cost first
open.sort()
# Get the node with the lowest cost
current_node = open.pop(0)
# Add the current node to the closed list
closed.append(current_node)
# Check if we have reached the goal, return the path
if current_node == goal_node:
path = []
while current_node != start_node:
path.append(current_node.name + ': ' + str(current_node.g))
current_node = current_node.parent
path.append(start_node.name + ': ' + str(start_node.g))
# Return reversed path
return path[::-1]
# Get neighbours
neighbors = graph.get(current_node.name)
# Loop neighbors
for key, value in neighbors.items():
# Create a neighbor node
neighbor = Node(key, current_node)
# Check if the neighbor is in the closed list
if(neighbor in closed):
continue
# Calculate full path cost
neighbor.g = current_node.g + graph.get(current_node.name, neighbor.name)
neighbor.h = heuristics.get(neighbor.name)
neighbor.f = neighbor.g + neighbor.h
# Check if neighbor is in open list and if it has a lower f value
if(add_to_open(open, neighbor) == True):
# Everything is green, add neighbor to open list
open.append(neighbor)
# Return None, no path is found
return None
# Check if a neighbor should be added to open list
def add_to_open(open, neighbor):
for node in open:
if (neighbor == node and neighbor.f > node.f):
return False
return True
# The main entry point for this module
def main():
# Create a graph
graph = Graph()
# Create graph connections (Actual distance)
graph.connect('Frankfurt', 'Wurzburg', 111)
graph.connect('Frankfurt', 'Mannheim', 85)
graph.connect('Wurzburg', 'Nurnberg', 104)
graph.connect('Wurzburg', 'Stuttgart', 140)
graph.connect('Wurzburg', 'Ulm', 183)
graph.connect('Mannheim', 'Nurnberg', 230)
graph.connect('Mannheim', 'Karlsruhe', 67)
graph.connect('Karlsruhe', 'Basel', 191)
graph.connect('Karlsruhe', 'Stuttgart', 64)
graph.connect('Nurnberg', 'Ulm', 171)
graph.connect('Nurnberg', 'Munchen', 170)
graph.connect('Nurnberg', 'Passau', 220)
graph.connect('Stuttgart', 'Ulm', 107)
graph.connect('Basel', 'Bern', 91)
graph.connect('Basel', 'Zurich', 85)
graph.connect('Bern', 'Zurich', 120)
graph.connect('Zurich', 'Memmingen', 184)
graph.connect('Memmingen', 'Ulm', 55)
graph.connect('Memmingen', 'Munchen', 115)
graph.connect('Munchen', 'Ulm', 123)
graph.connect('Munchen', 'Passau', 189)
graph.connect('Munchen', 'Rosenheim', 59)
graph.connect('Rosenheim', 'Salzburg', 81)
graph.connect('Passau', 'Linz', 102)
graph.connect('Salzburg', 'Linz', 126)
# Make graph undirected, create symmetric connections
graph.make_undirected()
# Create heuristics (straight-line distance, air-travel distance)
heuristics = {}
heuristics['Basel'] = 204
heuristics['Bern'] = 247
heuristics['Frankfurt'] = 215
heuristics['Karlsruhe'] = 137
heuristics['Linz'] = 318
heuristics['Mannheim'] = 164
heuristics['Munchen'] = 120
heuristics['Memmingen'] = 47
heuristics['Nurnberg'] = 132
heuristics['Passau'] = 257
heuristics['Rosenheim'] = 168
heuristics['Stuttgart'] = 75
heuristics['Salzburg'] = 236
heuristics['Wurzburg'] = 153
heuristics['Zurich'] = 157
heuristics['Ulm'] = 0
# Run the search algorithm
path = astar_search(graph, heuristics, 'Frankfurt', 'Ulm')
print(path)
print()
# Tell python to run main method
if __name__ == "__main__": main()['Frankfurt: 0', 'Wurzburg: 111', 'Ulm: 294']