Using min() to get minimum value or sort the array and then pop the first value in Python when implementing open set in A* (A star) algorithm?

user_5225862 0
Viewed 550

I'm implementing A* (A star) algorithm in Python.

As you know we have have "open set" which consists a list of nodes we plan to explore.

In the algorithm we get the node with lowest F(n) value (estimated total cost) from open set.

We often use PriorityQueue, but for some reason which I don't understand why PriorityQueue doens't get the node with lowest value.

So rather I made an array list (regular list in Python) named "frontier" and keep the "open set" there.

There are two ways to use that like PriorityQueue.

currentNode = min(frontier)

to get the minimum value from the open set.

Or we can sort the array everytime we add new node into it, and just use "pop" to get the lowest value.

#adding a node
frontier.append(someNode)
sorted(frontier)

#taking out the node
currentNode = frontier.pop(0)

Which one is faster?

Using min() or first sorting and then using pop() ?

What algorithm does "min()" in Python use to get the minimum value from an array?

min algorithm python
1 Answers

There are three operations that this data structure s needs to perform, these are

  • Get the element with lowest F(n)
  • Add an element
  • Remove an element

The easiest way to implement would be to have a plain list and use min(s) to get the min value or min(range(len(values)), key=s.__getitem__) to get the index.

This runs in O(n) because it looks at every element once. Adding an element to the end of the list runs in O(1) and removing from an arbitrary index runs in O(n) because all successive elements need to be shifted.

The idea to sort the array every time is slightly worse, as sorting runs in O(n log n). You save some time by sorting the min element to the end of the list, where it can be removed in O(1), but in total it will be slower.

The best solution is to have a heap or priority queue. It maintains the min element at the top where it can be retrieved in O(1) and allows inserting and removing elements in O(log n).

user_57106370
Related