World's most popular travel blog for travel bloggers.

Why to implement Open list in Heuristic search with priority queue

, , No Comments
Problem Detail: 

I don't understand why do we need to implement Open list using priority queue? There could be other data structure.

I understand the usage of priority queues from this example clearly. The newly discovered node would always be inserted at the head of the Open List. Then why do we need priority queue?

This article has mentioned everything about open list.

Usually Open Set contains the states. Its more convenient to assume Open Set as a list. However, the when we were to implement it in some programming language, we use priority queue as data structure.

By states, I mean assume rubix cube of 6 faces. When we rotate it we could have 3 possibilities: 90, 180, 270 degree rotations.

Total states 6x3 = 18

Asked By : Abhimanyu Aryan

Answered By : adrianN

Your question is not perfectly clear to me, so maybe I answer a different question from what you intended. The article you linked talks about A* as a search algorithm that uses a heuristic to speed up searching, so I'll talk about this.

In a naive search you explore a graph for example in breadth first order: You start at some node, then visit its neighbors, then the neighbors of the neighbors and so on until you reach your goal state (or there is nothing more to explore).

Now suppose you had some function (the "heuristic") that can tell you more or less accurately how close a particular node is to your goal node. Then you can speed up your search by visiting nodes that are closer to your goal first. Now it depends on the quality of your heuristic how you should do that.

If your heuristic is perfect, that is, it tells you the distance to the goal accurately for every node, then you can just look at the neighbors of your start node and proceed to the node with the smallest distance to the goal. From there again you look at the neighbors and proceed to the one with the smallest distance to the goal. You don't need to keep any memory of possible alternative routes, because your heuristic exactly tells you which node you have to go to.

If the heuristic is not perfect however, the picture changes. Say your heuristic is optimistic, that is, it always underestimates the distance to the goal. Then can't assume that the neighbor with the smallest heuristic distance to the goal is always the correct node to which to proceed, because it might turn out that the true distance is much larger than what your heuristic told you. So you have to remember some alternative routes.

You can do that as follows: Maintain a set of nodes to which you could proceed (the neighbors of all nodes that you have already seen but not visited). This is you open set. In each step you continue searching from the node in the open set where the distance from the start plus the heuristic distance to the goal is smallest.

Now how do you find this node in the open set? You could store the open set as a list look at all nodes in each step to find it, but that is inefficient. Instead you could maintain the open set as a heap, where finding the minimum is cheap.

So this is why you want to use a heap in a heuristic search. It speeds up finding the next node from which to proceed with your search.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54431

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback