Jag kommer att implementera djup-först-sökning (DFS) för ett rutnät och en graf i den här handledningen. Djup-först-sökning är en oinformerad sökalgoritm eftersom den inte använder någon heuristik för att vägleda sökningen. DFS används för att hitta en väg från en startpunkt till en målpunkt, längden på sökvägen kan också beräknas.
Djup-först-sökning startar från en rotnod och expanderar grannnoder på djupet tills det att en målnod har hittats, detta kan implementeras genom att använda en LIFO-kö (sist in först ut). Djup-först-sökningen kan hamna i en oändlig loop om sökutrymmet är oändligt och målnoden inte är i den aktuella sökvägen. En DFS-algoritm kan ignorera många noder om den når slutet på ett djup av ett träd och denna algoritm är därför mer minneseffektiv än en bredd-först-sökning i vissa fall.
En djup-först-sökning är inte garanterad att hitta den optimala lösningen och den är väldigt tidskrävande i värsta fall. Tidskomplexiteten är O(n) i ett rutnät och O(b^d) i en graf 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. DFS och varianter av algoritmen används i AI-sökningar eftersom den är minneseffektiv jämfört med andra sökalgoritmer.
Rutnätsproblem (labyrint)
Jag har skapat en enkel labyrint (ladda ner) med en startpunkt, en målpunkt och väggar. DFS används för att hitta en väg till målet, algoritmen använder en Node-klass. DFS-algoritmen har en lista för öppna noder och en lista för stängda noder, algoritmen kommer att loopa tills den hittar en målnod eller tills listan med öppna noder är tom. Koden och utdata från körningen visas nedan.
# This class represent 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
# Depth-first search (DFS)
def depth_first_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:
# Get the last node (LIFO)
current_node = open.pop(-1)
# 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
# Everything is green, add the node if it not is in open
if (neighbor not in open):
open.append(neighbor)
# Return None, no path is found
return None
# 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('annytab\\ai_search_algorithms\\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 = depth_first_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
Detta grafproblem handlar om att hitta den kortaste vägen från en stad till en annan stad, en karta har använts för att skapa förbindelser mellan städer. DFS-algoritmen använder en Graph-klass och en Node-klass, den har en lista med öppna noder och en lista med stängda noder. DFS-algoritmen hittar en väg till destinationen, men det är inte den kortaste vägen.
# 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.position, self.f))
# Depth-first search (DFS)
def depth_first_search(graph, 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:
# Get the last node (LIFO)
current_node = open.pop(-1)
# 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
# Check if neighbor is in open list and if it has a lower f value
if(neighbor in open):
continue
# Calculate cost so far
neighbor.g = current_node.g + graph.get(current_node.name, neighbor.name)
# Everything is green, add neighbor to open list
open.append(neighbor)
# Return None, no path is found
return None
# 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()
# Run search algorithm
path = depth_first_search(graph, 'Frankfurt', 'Ulm')
print(path)
print()
# Tell python to run main method
if __name__ == "__main__": main()['Frankfurt: 0', 'Mannheim: 85', 'Karlsruhe: 152', 'Stuttgart: 216', 'Ulm: 323']