A machine is going to navigate through a series of cave connected by straight tunnels(Please see image). It starts navigating from the A to the last cave G. Some tunnels can only be navigated in one direction. Arrows are showing which cave can be reached from which other cave. For example from cave D to B is possible, however from cave B to D is not possible. All the coordinates ar given in the picture.

 

a. Which algorithm is best  to use in order to find shortest route and why? Show the calculations. 

 

b. Which other 2 algorithms can be use to solve this problem? Show the calculations. Comparatively evaluate each of the two algorithms against the algorithm described in a (to find the shortest route)?

 

c. If the problem were to change so that instead of finding the shortest route we needed to find the lowest cost route and the problem is no-longer related to the distance travelled.  If we add some difficulties between the caves, for example  some tunnels could be bulky, or there are any other cost related difficulties between the caves such as some tunnels need to be cleared of various harmful animals, etc.  How will this affect our choice of algorithm?

Transcribed Image Text:

A(2,8) D(7,6) F(11,6) C(14,5) B(3,2) E(11,2) G(14,1) A(2,8) D(7,6) F(11,6) C(14,5) B(3,2) E(11,2) G(14,1)

Answer rating: 100% (QA)

A Algorithm A search algorithm is a combination of both uniform cost search and greedy bestfirst sea... View the full answer