Bredd-först-sökning i Python

Jag kommer att implementera bredd-först-sökning (BFS) för ett rutnät och en graf i den här handledningen. Bredd-först-sökning är en algoritm som används i inom AI-området för att hitta en sökväg från en punkt till en annan.

Bredd-först-sökning är en oinformerad algoritm, den söker blint mot ett mål på bredden. BFS startar från en initial nod (start) och expanderar grannnoder på bredden, detta implementeras genom att använda en FIFO-kö (först in först ut). BFS är komplett eftersom det inte kommer att fastna i en oändlig loop om det finns en målnod i sökutrymmet.

En bredd-först sökning är garanterad att hitta den optimala lösningen, men det kan ta tid och konsumera mycket minne. 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. BFS är inte så minneseffektiv som djup-först-sökning i träd. BFS kan användas om sökutrymmet inte är för stort, när det är viktigt att hitta en optimal lösning.

Rutnätsproblem (labyrint)

Jag har skapat en enkel labyrint (ladda ner) med väggar, en startpunkt och ett mål. BFS används för att hitta den kortaste vägen till målet, algoritmen använder en Node-klass. BFS-algoritmen har en lista för öppna noder och en lista för stängda noder, den kommer att loopa tills den hittar en målnod eller tills listan med öppna noder är tom.

# 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 

# Breadth-first search (BFS)
def breadth_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 first node (FIFO)
        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

            # 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 = breadth_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: 339

Grafproblem

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äderna. BFS-algoritmen använder en Graph-klass och en Node-klass, den har en lista med öppna noder och en lista med stängda noder. BFS-algoritmen hittar den kortaste vägen till målet.

# 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))

# Breadth-first search (BFS)
def breadth_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 first node (FIFO)
        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

            # 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 = breadth_first_search(graph, 'Frankfurt', 'Ulm')
    print(path)
    print()

# Tell python to run main method
if __name__ == "__main__": main()
['Frankfurt: 0', 'Wurzburg: 111', 'Ulm: 294']
Etiketter:

Lämna ett svar

E-postadressen publiceras inte. Obligatoriska fält är märkta *