Informed search algorithms

 

Expt No: 2                                           Informed search algorithms

Date:

 

Aim: To write a program to demonstrate informed search algorithms – A* and memory–bound A* algorithms

 

Program

# A* algorithm

 

import heapq

 

class Graph:

    def __init__(self):

        self.nodes = set()

        self.edges = {}

   

    def add_node(self, value):

        self.nodes.add(value)

        if value not in self.edges:

            self.edges[value] = []

   

    def add_edge(self, from_node, to_node, cost):

        self.edges[from_node].append((to_node, cost))

        self.edges[to_node].append((from_node, cost))

   

    def get_neighbors(self, node):

        return self.edges[node]

 

def heuristic(node, goal):

    # Manhattan distance between two nodes

    x1, y1 = node

    x2, y2 = goal

    return abs(x1 - x2) + abs(y1 - y2)

 

 

def astar_search(graph, start, goal):

    frontier = [(0, start)]  # Priority queue (cost, node)

    came_from = {}

    cost_so_far = {start: 0}

   

    while frontier:

        current_cost, current_node = heapq.heappop(frontier)

       

        if current_node == goal:

            break

       

        for next_node, edge_cost in graph.get_neighbors(current_node):

            new_cost = cost_so_far[current_node] + edge_cost

            if next_node not in cost_so_far or new_cost < cost_so_far[next_node]:

                cost_so_far[next_node] = new_cost

                priority = new_cost + heuristic(next_node, goal)

                heapq.heappush(frontier, (priority, next_node))

                came_from[next_node] = current_node

   

    path = []

    current_node = goal

    while current_node != start:

        path.append(current_node)

        current_node = came_from[current_node]

    path.append(start)

    path.reverse()

   

    return path

 

# Create graph and add nodes

 

graph = Graph()

graph.add_node((0, 0))

graph.add_node((1, 0))

graph.add_node((0, 1))

graph.add_node((1, 1))

graph.add_node((2, 1))

graph.add_node((2, 2))

 

# Add edges and assign weights

 

graph.add_edge((0, 0), (0, 1), 1)

graph.add_edge((0, 0), (1, 1), 4)

graph.add_edge((0, 0), (1, 0), 3)

graph.add_edge((0, 1), (2, 2), 2)

graph.add_edge((1, 1), (1, 0), 2)

graph.add_edge((1, 1), (2, 1), 4)

graph.add_edge((1, 1), (2, 2), 3)

graph.add_edge((1, 0), (2, 1), 5)

graph.add_edge((2, 1), (2, 2), 4)

 

 

# Call search algorithm

start_node = (0, 0)

goal_node = (2, 1)

 

path = astar_search(graph, start_node, goal_node)

print("Shortest path:", path)

 

 

 

# Memory–Bound A* algorithm

 

import heapq

 

class Graph:

    def __init__(self):

        self.nodes = set()

        self.edges = {}

   

    def add_node(self, value):

        self.nodes.add(value)

        if value not in self.edges:

            self.edges[value] = []

   

    def add_edge(self, from_node, to_node, cost):

        self.edges[from_node].append((to_node, cost))

        self.edges[to_node].append((from_node, cost)) 

   

    def get_neighbors(self, node):

        return self.edges[node]

 

def heuristic(node, goal):

    # Manhattan distance between two nodes

    x1, y1 = node

    x2, y2 = goal

    return abs(x1 - x2) + abs(y1 - y2)

 

 

def memory_bound_astar_search(graph, start, goal, memory_limit):

    frontier = [(0, start)]

    came_from = {}

    cost_so_far = {start: 0}

   

    while frontier:

        current_cost, current_node = heapq.heappop(frontier)

       

        if current_node == goal:

            break

       

        # Check if the memory limit is exceeded

        if len(cost_so_far) > memory_limit:

            # Discard nodes with the highest cost so far

            max_cost_node = max(cost_so_far, key=cost_so_far.get)

            del cost_so_far[max_cost_node]

       

        for next_node, edge_cost in graph.get_neighbors(current_node):

            new_cost = cost_so_far[current_node] + edge_cost

            if next_node not in cost_so_far or new_cost < cost_so_far[next_node]:

                cost_so_far[next_node] = new_cost

                priority = new_cost + heuristic(next_node, goal)

                heapq.heappush(frontier, (priority, next_node))

                came_from[next_node] = current_node

   

    path = []

    current_node = goal

    while current_node != start:

        path.append(current_node)

        current_node = came_from[current_node]

    path.append(start)

    path.reverse()

   

    return path

 

 

# Create Graph and add nodes

 

graph = Graph()

graph.add_node((0, 0))

graph.add_node((1, 0))

graph.add_node((0, 1))

graph.add_node((1, 1))

graph.add_node((2, 1))

graph.add_node((2, 2))

 

# Add edges and assign weights

 

graph.add_edge((0, 0), (0, 1), 1)

graph.add_edge((0, 0), (1, 1), 4)

graph.add_edge((0, 0), (1, 0), 3)

graph.add_edge((0, 1), (2, 2), 2)

graph.add_edge((1, 1), (1, 0), 2)

graph.add_edge((1, 1), (2, 1), 4)

graph.add_edge((1, 1), (2, 2), 3)

graph.add_edge((1, 0), (2, 1), 5)

graph.add_edge((2, 1), (2, 2), 4)

 

# call search algorithm

 

start_node = (0, 0)

goal_node = (2, 1)

memory_limit = int(input("Enter memory limit : "))

 

path = memory_bound_astar_search(graph, start_node, goal_node, memory_limit)

print("Shortest path:", path)

 

 

 

 

 

 

Result: Thus the program to demonstrate informed search algorithms were written and executed

 

 

 

Input Graph

 

Sample Output

 

# A* algorithm

 

>python Astar.py

Shortest path: [(0, 0), (0, 1), (2, 2), (2, 1)]

 

 

# Memory–Bound A* algorithm

 

>python MAstar.py

Enter memory limit : 5

Shortest path: [(0, 0), (1, 1), (2, 1)]

 

>python MAstar.py

Enter memory limit : 10

Shortest path: [(0, 0), (0, 1), (2, 2), (2, 1)]