What is a more efficient way to choose/sort the best node in an A* search?

Question

I am using an A* search and a Breadth First search to find a winning game state in an 8 puzzle. The winning state looks like this

123
456
780

and stored as a list like such

[1,2,3,4,5,6,7,8,9,0]

I used a heuristic function to score each node (based on its state), but I believe my method of prioritizing the best scored nodes is slowing my program down a lot. So much so actually that the breadth first search algorithm I made vastly outperforms the A* algorithm (even though most of the the inner workings are identical).

I believe the main thing slowing my A* search down is that I'm using the position in the fringe (the list holding my nodes) to indicate the next node to prioritize.

def aStartSort(node):
    if not fringe:
        fringe.append(node)
    else:
        fl = len(fringe)
        if node.score >= fringe[fl-1].score:
            fringe.append(node)
        else:
            for i in range(fl):
                if node.score < fringe[i].score:
                    fringe.insert(i, node)

So as you can see, every time a node is added to the fringe, it looks for a node that is scored worse than it, and then inserts itself in front of it. This ensures that I get a least a tie for the best scored node when I do fringe.pop(0). But inserting items into the middle of a giant list isn't a very fast action is it? What would be a better alternative?

I also considered not ordering the fringe list, but that seems just as bad or worse (because the entire list would have to be searched each time a node is popped out.

Answer 1

To answer your specific question, assuming your scores are integers, create a dictionary of lists, mapping scores to nodes with that score. That makes inserts O(1), and since you can iterate over the possible score range, retrieval should be fast as well.