New Memory bounded A* Algorithm

 def astar(start, goal):

    opened = [[start, 0]]  # List of open nodes

    closed = []  # List of closed nodes

    visited = set()  # Set of visited nodes


    while opened:

        val, min_cost = opened.pop(0)

        

        if val == goal:

            break

        

        visited.add(val)

        

        for neighbor, cost in nodes[val]:

            if neighbor not in visited:

                new_cost = min_cost + cost

                opened.append([neighbor, new_cost])

            else:

                continue

        

        opened.sort(key=lambda x: x[1])  # Sort open nodes by cost

        closed.append(val)


    return closed, min_cost


# Define nodes before using the astar function

nodes = {

    'A': [('B', 5), ('C', 10)],

    'B': [('D', 3), ('E', 8)],

    'C': [('F', 6), ('G', 9)],

    'D': [('H', 7), ('I', 3)],

    'E': [('J', 4)],

    'F': [('K', 2)],

    'G': [('L', 5)],

    'H': [('M', 6)],

    'I': [('N', 2)],  # Adding node 'N' with its neighbor and cost

    'J': [('O', 1)],

    'N': [],  # Adding node 'N' without any neighbors initially

}


# Start-'A', Goal = 'J'

print(astar('A', 'J'))




Comments

Popular posts from this blog

Pos using Seq to seq