1. Your friend was doing an iterative deepening uniform cost search on a graph representing the
distances between various landmarks in town (presumably to find optimal paths between any pair of
landmarks). Originally he had a graph where all the road distances were measured in multiples of integral
miles (i.e. each edge cost was an integer). After a while, your friend decided to represent the distances
more accurately and so went and found all distances correct to four decimal places. All of a sudden he found that
the efficiency of his search worsened quite dramatically. He was perplexed at this since the underlying graph
topology was the same and distances were just more accurate. Can you explain what happened?
2. What, if any, are the differences between uniform cost search algorithm as we described in the class and "Dijkstra's algorithm" on
graphs that you have probably learned in CSE310?
Rao
3 comments:
2.
Dijkstra's algorithm keeps track of the current shortest distance from the source to every other node in the graph, at any point during the search.
On the other hand, Uniform Cost Search simply inserts all vertices resulted from an expanded node to the priority queue along with the cost along a specific path.
As a consequence, a vertex with two distinct paths will be inserted twice into the queue in the order of their costs in case of UCS, while the same node will be updated with the new best path in case of Dijkstra's algorithm.
Good answer.
The follow-up question is
is one of these ideas significantly better--in terms of time complexity--than the other or do they offer complementary tradeoffs?
rao
When the distances becomes more accurately, the difference between two IDUC seachs is also become small. That is, we may search the same subgraph for several times
Post a Comment