A company is using a drone with a camera for surveillance purposes. Suppose the drone is at node $1$ and it needs to visit nodes $2,3,$ and $4,$ and then return to node $1.$ The travelling cost between each node pair is given in Table Q$1-1.$

Table Q$1-1.$ Distance between nodes

$\backslash$table$[[$Distance$,$To Node $1,$To Node $2,$To Node $3,$To Node $4],[$From Node $1,--,4,8,5],[$From Node $2,4,--,6,5],[$From Node $3,7,5,--,9],[$From Node $4,5,6,7,--]]$

Q$1\mathrm{.}1$: Use the nearest unvisited heuristic to find a tour for the drone and calculate the distance of the tour.

Solution:

Stage $0$: Unvisited nodes: $1,2,3,$ and $4$; Home node: $1$; Current node: $1$;

Stage $1$: Current node: $1$; Unvisited nodes: $2,3,$ and $4$; Nearest node: Move to node $2$;

Stage $2$: Current node: $2$; Unvisited nodes: $,$ Nearest node: $4$; Move to node $4$;

Stage $3$: Current node: $4$; Unvisited nodes: ; Nearest node: $,$ Move to node

Stage $4$: Current node: $3$; NO unvisited nodes; Move to home node $1$

Q$1\mathrm{.}2$: Suppose that the distances from Node $1$ to Node $4$ and from Node $4$ to Node $1$ are both shortened to $3.$ Use the nearest unvisited heuristic to find a tour for the drone and calculate the distance of the tour.