[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

New thinking cap question(s)





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