Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· OpenAIAi2 WildChat-4.8M (AI2)

Can you write a code for IDA* algorithm with python class declaration and with following…

  1. User

    Can you write a code for IDA* algorithm with python class declaration and with following graph and heuristic fucntions:

    graph = { 'Bhubaneswar Airport': {'Lingraj Temple': 30, 'Udhayagiri &Kandhagiri': 48}, 'Lingraj Temple': {'Bhubaneswar Airport': 30, 'Shanthi Stupa': 25, 'Udhayagiri &Kandhagiri': 28, 'Mukteshwar temple': 5}, 'Shanthi Stupa': {'Lingraj Temple': 25, 'Tribal Museum': 50, 'Mukteshwar temple': 45}, 'Tribal Museum': {'Shanthi Stupa': 50, 'Mukteshwar temple': 15}, 'Udhayagiri &Kandhagiri': {'Lingraj Temple': 28, 'Mukteshwar temple': 22, 'Raja Rani temple': 18, 'Bhubaneswar Airport': 48}, 'Raja Rani temple': {'Udhayagiri &Kandhagiri': 48, 'Mukteshwar temple': 20}, 'Mukteshwar temple': {'Raja Rani temple': 20, 'Udhayagiri &Kandhagiri': 22, 'Lingraj Temple': 5, 'Tribal Museum': 15, 'Shanthi Stupa': 45} }

    coordinates = { 'Bhubaneswar Airport': (0, 0), 'Lingraj Temple': (10, 10), 'Shanthi Stupa': (20, 20), 'Tribal Museum': (30, 10), 'Udhayagiri &Kandhagiri': (40, 0), 'Raja Rani temple': (40, 20), 'Mukteshwar temple': (50, 10) }

    class Heuristic: def init(self, coordinates): self.coordinates = coordinates

    def calculate(self, node1, node2):
        """Calculate the heuristic value (straight-line distance) between two nodes."""
        # print('--'*50)
        # print(f'node1 : {node1}')
        # print(f'node2 : {node2}')
        # print(f'coordinates are: \n{self.coordinates}')
        # print(f'node2 val : \n{self.coordinates[node2]}')
        # print('--'*50)
        x1, y1 = self.coordinates[node1]
        x2, y2 = self.coordinates[node2]
        return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
    

    Kindly write the code accordingly ?

  2. Assistant

    Sure! Here's the code implementing the IDA* algorithm using the provided graph and heuristic functions:

    import math
    
    graph = {
        'Bhubaneswar Airport': {'Lingraj Temple': 30, 'Udhayagiri &Kandhagiri': 48},
        'Lingraj Temple': {'Bhubaneswar Airport': 30, 'Shanthi Stupa': 25, 'Udhayagiri &Kandhagiri': 28, 'Mukteshwar temple': 5},
        'Shanthi Stupa': {'Lingraj Temple': 25, 'Tribal Museum': 50, 'Mukteshwar temple': 45},
        'Tribal Museum': {'Shanthi Stupa': 50, 'Mukteshwar temple': 15},
        'Udhayagiri &Kandhagiri': {'Lingraj Temple': 28, 'Mukteshwar temple': 22, 'Raja Rani temple': 18, 'Bhubaneswar Airport': 48},
        'Raja Rani temple': {'Udhayagiri &Kandhagiri': 48, 'Mukteshwar temple': 20},
        'Mukteshwar temple': {'Raja Rani temple': 20, 'Udhayagiri &Kandhagiri': 22, 'Lingraj Temple': 5, 'Tribal Museum': 15, 'Shanthi Stupa': 45}
    }
    
    coordinates = {
        'Bhubaneswar Airport': (0, 0),
        'Lingraj Temple': (10, 10),
        'Shanthi Stupa': (20, 20),
        'Tribal Museum': (30, 10),
        'Udhayagiri &Kandhagiri': (40, 0),
        'Raja Rani temple': (40, 20),
        'Mukteshwar temple': (50, 10)
    }
    
    class Heuristic:
        def __init__(self, coordinates):
            self.coordinates = coordinates
    
        def calculate(self, node1, node2):
            """Calculate the heuristic value (straight-line distance) between two nodes."""
            x1, y1 = self.coordinates[node1]
            x2, y2 = self.coordinates[node2]
            return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
    
    class Node:
        def __init__(self, state, parent=None, action=None, g=0, h=0):
            self.state = state
            self.parent = parent
            self.action = action
            self.g = g  # Path cost from start node to current node
            self.h = h  # Heuristic value of current node
    
        def __repr__(self):
            return f"Node({self.state})"
    
        def __lt__(self, other):
            return self.g + self.h < other.g + other.h
    
    def ida_star_search(initial_state, goal_state, heuristic):
        bound = heuristic.calculate(initial_state, goal_state)
        path = [initial_state]
    
        while True:
            result = dfs_with_bound(Node(initial_state), goal_state, bound, heuristic, path)
            if result == 'FOUND':
                return path
            if result == float('inf'):
                return None
            bound = result
    
    def dfs_with_bound(node, goal_state, bound, heuristic, path):
        state = node.state
        if state == goal_state:
            return 'FOUND'
    
        f = node.g + heuristic.calculate(state, goal_state)
        if f > bound:
            return f
    
        successors = graph[state]
        min_f = float('inf')
    
        for successor_state in successors:
            g = node.g + successors[successor_state]
            h = heuristic.calculate(successor_state, goal_state)
            child_node = Node(successor_state, node, successors[successor_state], g, h)
            path.append(successor_state)
            result = dfs_with_bound(child_node, goal_state, bound, heuristic, path)
            path.pop()
    
            if result == 'FOUND':
                return 'FOUND'
            if result < min_f:
                min_f = result
    
        return min_f
    
    # Example usage:
    heuristic = Heuristic(coordinates)
    path = ida_star_search('Bhubaneswar Airport', 'Tribal Museum', heuristic)
    print(path)
    

    This code defines a Heuristic class to calculate the straight-line distance between two nodes based on their coordinates, and a Node class to represent the search nodes. The main function ida_star_search implements the IDA* algorithm using a depth-first search with a given bound. The dfs_with_bound function recursively explores successors until the goal state is found or the bound is exceeded. The path variable stores the found path from the initial state to the goal state.

    The example usage at the end demonstrates how to use the ida_star_search function with the provided graph and heuristic. It searches for a path from 'Bhubaneswar Airport' to 'Tribal Museum' and prints the resulting path.