I have the following DFS2 pseudo-code, which is used in the pseudo-code of IDA*, from my teacher’s book, but I cannot understand why it’s correct:
DFS2(N0, f, threshold): PQInit(PQ) // PQ means Priority Queue, for a pair (c, p) in PQ it represents a path from N0 to c. PQ.offer(null, N0) while isEmpty(PQ) is FALSE do current, parent := PQ.poll() R := next(current, parent) // return the next child of parent if R is null then continue PQ.offer(R) Let P be the path from N0 to R. if f(P) > threshold then continue if isGoal(R) then return success if R in PQ then continue PQ.offer(null, R) return fail
if I substitute the
PQ to a Stack
S in the code above, then it’s just a non-recursive DFS which I can understand and prove its correctness. Even more I think I have a better version (reordering of the continue-conditions) of the non-recursive DFS:
StackInit(S) if isGoal(N0) then return success markVisited(N0) S.push(null, N0) while isEmpty(S) is FALSE do current, parent := S.pop() R := next(current, parent) if R is null then continue S.push(R,parent) if isVisited(R) then // if it's visited then it cannot be goal continue markVisited(R) if isGoal(R) then // if it's goal then no need to check its children return success Let P be the path from N0 to R if f(P) > threshold then continue S.push(null, R) return fail
I thought this would be perfect since any visited node would not be visited again, but then I realized that revisiting of nodes (In CLRS this is called RELAXING weights of nodes.) is required to achieve A*. Can anyone explain for me why the A*(DFS2) pseudo-code I provided above is correct? And could anyone teach me how to improve my second DFS pseudo-code to make it a thresholded-A*?
In my current understand the nature of A*, which can be seen as a generalization of Dijkstra-shortest path algorithm, is BFS. So given a DONE set (A set of nodes which are already labeled with the shortest/smallest accumulated weight) I choose the shortest adjacent edge(Greedy) of this DONE set then I will find the next node which labeled shortest path weight. In DFS2 not all adjacent edges are discovered since it’s Depth-First, so how can I prove it that the path found is indeed optimal when it