$3.[5$ pts$]$: Consider the following graph. Do a Branch and Bound Depth First Search on this graph, where the depth bound is not measured in terms of number of edges $($as in the inclass exercises$)$ but in terms of the total distance to the nearest goal node as measured by edge lengths. I have set up the graph so that there all edges outgoing from a given node have different costs, so there are no ties to be broken.

List the nodes you visit in order to find the nearest goal node, showing your return paths.

Solution:

Appendix A: Sample ID$-$DFS with edge lengths. This page shows the solution I am looking for, and the next page explains it$.$

Suppose the start node is S and the goal node is T $.$

The initial depth bound and the depth bound increment are both $4.$

somun:;

$1^($st $)$ iteration, depth bound $4$:S$->$B

$2^($nd $)$ iteration, depth bound $8$: S$->$B$->$C$(->$B$)->$E$(->$B$)(->$S$)->$A$(->$S$)$

$3^($rd $)$ iteration, depth bound $12$:S$->$B$->$C$->$D$(->$C$)(->$B$)->$E$(->$B$)(->$S$)->$A$->$D$(->$A$)(->$S$)4^($th $)$ iteration, depth bound $16$:S$->$B$->$C$->$D$->$T done Explanation of solution.

Solution:

First iteration. denth bound $4$: S$->$B

Explanation:

I go S$->$B and stop because I reached the depth bound. Failure. $($I can't go to A because it's

further away than the depth bound.$)$

Second iteration, depth bound $8$: S$->$B$->$C$(->$B$)->$E$(->$B$)(->$S$)->$A

Explanation:

I go S$->$B$->$C before hitting the depth bound, then back to B then go to E before hitting the

depth bound then back to B then back to S $.$ Then I go S$->$A before hitting the depth bound. I

could go to B $,$ but I already have a shorter path to B so I don't go there again. Failure. Third iteration, depth bound $12$: S$->$B$->$C$->$D$(->$C$)(->$B$)->$E$(->$B$)(->$S$)->$A$->$D$->$E

Expianazion:

I go S$->$B$->$C$->$D before hitting the depth bound, then back to C then back to B then go to E

before hitting the depth bound then back to B then back to S $.$ Then I go S$->$A$.$ From A $,$ I don't

go to B because I already have a shorter path to B$,$ and I don't go to C because I have a shorter

path to C $.$ So I go to D before I reach the depth bound. I don't go to E from D because there is

a shortest path to E already.

Fourth iteration, depth bound $16$:S$->$B$->$C$->$D$->$T

Expianation:

I go S$->$B$->$C$->$D$->$T before hitting the depth bound, so I am done.