Please, help me to answer these questions. 1. In Dijkstar, how is the fringe set
ID: 3698674 • Letter: P
Question
Please, help me to answer these questions.
1. In Dijkstar, how is the fringe set related to the closed set (aka visited set)?
2. In a binary min heap, when the current minimum is removed what actions are taken to restore the
heap.
3. Like Dijkstar the standard backtracking path finding algorithm does not use the position of the
goal. How could you modify that algorithm to use the goal information in a way that can often
(and definitely not always) make the algorithm find the goal faster?
4. Explain why D* plots the path from the goal to the start.
5. When should one check the contact manifold?
Explanation / Answer
Solution:
The first four subparts have been answered as per Chegg guidelines, please repost others.
1. In Dijkstar, how is the fringe set related to the closed set (aka visited set)?
In Dijkstra's, there is a field named predecessor which is maintained after every relaxation to see which visited vertex is the predecessor of the one to provide the shortest path from the source.
2. In a binary min heap, when the current minimum is removed what actions are taken to restore the
heap.
The removal is done, by replacing the root with the rightmost element in the last level and after that from the leaf the root (min value) is removed, then again heapify procedure is called to maintain the binary min-heap.
3)
In this case, we can use greedy approach, then it will make the goal to find faster. We should choose the smallest adjacent path which leads to the goal at every step and we will reach the goal faster.
4)
It uses bottom-up approach and maintains NEW, OPEN, CLOSED, RAISE, LOWER.
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)