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