A* search algorithm implementation in python-CodePudding

I am trying to build a very simple A* Search Algorithm in Python 3. Given the following distances for each node (considering S is the starting node and G the end one)

further_cost = {'s': 11.2, 'a': 9, 'b': 9.3, 'd': 6.2, 'c': 6.7, 'e': 4.2, 'f': 2.1, 'g': 0}

previous_cost = {'s': 0, 'a': 2, 'b': 2.5, 'c': 4, 'd': 3, 'e': 3, 'f': 2.5, 'g': 2}

I want to write a function that finds the best path based on total cost (i.e., f(n) for those familiar with the terminology) for the following search space:

sp = {'s': ['a', 'b'],
      'a': ['b', 'd', 's'],
      'b': ['a', 'e', 'c'],
      'c': ['b'],
      'd': ['s', 'a', 'e'],
      'e': ['d', 'b', 'f'],
      'f': ['e', 'g']}

This is what I have written so far. The issue is that I cannot seem to implement dynamic programming. In other words, I cannot make it so that the algorithm selects the path having the lower f(n).

def extend(queue, state_space):
    current_path = queue[0]
    current_state = current_path[-1]
    extensions = state_space[current_state]
    newpaths = []
    for ext in extensions:
        if not ext in current_path: # check for and don't add loops
            newpaths.append(current_path   ext)
    return newpaths

def a_search(goal, state_space=sp, heuristic=further_cost, a = previous_cost, strategy='best', queue=['s']):




    print (queue)
           
    if not queue:
        print('Search failed')
        return False
    elif queue[0][-1] == 'g':
        print('Goal found with path {}'.format(queue[0]))
        return True
        
    else:
        
        new_paths = extend(queue, state_space)
        
        cost = {}
        for path in new_paths:
            cost[path] = 0
            for node in path:
                if node == path[-1]:
                    cost[path]  = further_cost.get(node)   previous_cost.get(node)
                else:
                    cost[path]  = previous_cost.get(node)

            
        if strategy == 'best':
            
            
            #new_queue = sorted(new_paths   queue[1:], key=lambda x: cost[x[-1]])
            new_queue = new_paths   queue[1:]
            new_queue = sorted(new_queue, key=cost.get)

            print(new_queue, cost)
            
        else:
            print('Unknown search algorithm')
            return False
        
    a_search(goal, state_space, heuristic, a, strategy, new_queue)

The function returns the following error:

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-105-dfe3fabe38db> in <module>
----> 1 a_search(['g'], sp, further_cost, previous_cost, 'best', ['s'])

<ipython-input-104-f872f8359edc> in a_search(goal, state_space, heuristic, a, strategy, queue)
     40             return False
     41 
---> 42     a_search(goal, state_space, heuristic, a, strategy, new_queue)

<ipython-input-104-f872f8359edc> in a_search(goal, state_space, heuristic, a, strategy, queue)
     32             #new_queue = sorted(new_paths   queue[1:], key=lambda x: cost[x[-1]])
     33             new_queue = new_paths   queue[1:]
---> 34             new_queue = sorted(new_queue, key=cost.get)
     35 
     36             print(new_queue, cost)

TypeError: '<' not supported between instances of 'NoneType' and 'float'

I suspect I may be making some conceptual mistake here. Ay help would be appreciated!

CodePudding user response：

Apparently you have some values in your cost dictionary that are of type None. Perhaps the previous_cost.get call returned None for some early value.

I might suggest a different approach. Rather than having separate collections for each piece of data used by A*, you should group them into objects. Make a node object that overrides __lt__ and pass in your f and g scores and your parent to its constructor.