How to understand this priority queue depth-first search?

user_5290519 0
Viewed 876

The following is pseudocode implement depth-first search(DFS) with one stack and a large table to mark visited nodes:

DFS(N0):
   StackInit(S)
   S.push((N0, null))
   if isGoal(N0) then do
      return true
   markVisited(N0)
   S.push((null, N0))
   while !isEmpty(S) then do
      (N, parent) := S.pop()
      R := next((N, parent))
      if isNull(R) then do
         continue             // So no new node add to this layer.
      S.push((R, parent))
      if marked(R) then do
         continue
      if isGoal(R) then do    // If it's goal don't have to explore it.
         return true
      markVisited(R)
      if depthMax((R, parent)) then do
         continue
      S.push((null, R))
   return false

The problem I want to solve is a modification from it: it substitutes the stack S with PriorityQueue PQ. This algorithm is used to simulate IDA* algorithm (this is stated in a textbook, which unfortunately not written in English, so I won't provide reference / book title):

DFS2(N0, f, LIMIT):
   PriorityQueueInit(PQ)
   // A node (N, parent) stored in PQ represents a path from `N0` to `N`\
        passing the node `parent`; A node with smaller value on f() is \
        prioritized than those with larger value.
   PQ.push((N0, null))
   if isGoal(N0) then do
      return true
   markVisited(N0)
   PQ.push((null, N0))
   while !isEmpty(PQ) then do     // (1)
      (N, parent) := PQ.poll()
      R := next((N, parent))      // (2)
      if isNull(R) then do
         continue
      PQ.offer((R, parent))
      if marked(R) then do
         continue
      if isGoal(R) then do
         return true
      markVisited(R)
      if f((R, parent)) > LIMIT then do
         continue
      PQ.offer((null, R))
   return false
  • (1): In A* algorithm, a priority queue is used to store nodes which haven't been explored, i.e. open list. While in the first DFS pseudocode I provided, the stack S is close list, so I assume that in the second pseudocode PQ is close list, too. So how can the second pseudocode simulate IDA* algorithm, with a close list?
  • (2): It fetch the current smallest node from PQ, which is probably not a sibling of node N, i.e. It jumps to another subtree from current subtree contains N. What's the purpose of this line?

Can anyone show me the correctness of the second algorithm, i.e. why it can be used in IDA* algorithm?

updated for more information: I have spent many time and effort on this question, but it seems to be very hard because of the following points:

  1. All graphs appear in the textbook are drawn tree-like, i.e. only one parent for each node, to show the concepts. This makes me confused: Does the second algorithm only work for trees?

  2. Considering the line

    if f((R, parent)) > LIMIT then do ...

    If the second one also works for graph, not just tree, then there might be many parents go to R, should I consider all cases or just the current one, parent?

priority-queue depth-first-search search algorithm
1 Answers

There's a lot going on here.

As far as I can tell this code always returns the first goal node that reaches the top of the queue. Under the assumptions below about f and next, this goal node is f-optimal. But I wouldn't call this IDA*.

First, typically both A* and IDA* will open all neighbors of the current node at the same time. This code...doesn't. It uses iterators but only one loop. The first push is for the next sibling of the current node, and the second push is for the child. This is fine, I guess, except that siblings should be enumerated in increasing f-order so that a promising sibling doesn't get hidden after an unpromising one.

Second, unlike A*, IDA* doesn't have a close list. In a sense IDA* always has a search tree, since if it reaches two equivalent nodes, it still treats them as if they are distinct nodes. A* does have a close list, but it's more complicated than what's presented here. The way that A* handles cycles is that, if it discovers a cheaper path to an already closed node, then it reopens the node. This code doesn't, so it's only correct if there is never a need to reopen a node. As a result, this code needs f to be what's called a consistent heuristic (on every path, f never goes down as you follow the path), while A* only needs f to be admissible (f never underestimates the cost to reach a goal state).

user_21446690
Related