Dont copy from chegg Complete all 3 parts in details please

Don\'t copy from chegg. Complete all 3 parts in details please

For the above weighted graph, use the Brute Force Algorithm to find an optimal Hamilton Circuit stating at Vertex C. You work at UPS and the company has decided to add a new truck route that will cover 9 cities in Japan. Assume each city is connected to each city. You want to design the route in the most efficient way so that the truck will never have to visit a city more than once, except for Tokyo (where the headquarters is located.) Your boss wants the optimal route. Which algorithm should you use to answer your boss\'s question?] Suppose you are planning a trip around the world. Below is a table of the distances (in miles) between the cities you want to visit. Assume that you will start and end your trip in New York City. Find the nearest-neighbor tour with New York as the starting city.

Solution

(a)

THE BRUTE FORCE ALGORITHM

TRYING DIFFERENT circuits

1. C-B-A-D-C

weight=8+13+5+15=41

2. C-A-D-B-C

weight=10+5+14+8=37

Similarly trying every possible circuit with every vertex being visited once starting with C and ending at C

The circuit with minimum weight will be C-A-D-B-C with weight=37.

(b) Brute force algorithm will be most suitable as it produces least weight path and that too visiting each city only once except the headquarter. And it is best in case of small graphs. It always gives the one with least weight.

(c)Nearest Neighbor Algorithm- start at home and follow the cheapest choices from each vertex

1. Pick a vertex as the starting point

2. From the starting vertex, go to the vertex for which the corresponding edge has the smallest weight

3. Continue building the circuit, one vertex at a time.

• Do not go to a vertex that has already been visited

• Do not go to a vertex if it creates a small circuit

4. From the last vertex, return to the start.

Following above algorithm starting from New York, the nearest city is London. Now from London the nearest one is Istanbul. Moving on from Istanbul the closest one is Moscow. From Moscow Istanbul is the nearest but its already been visited then its London which is also visited then next nearest city is Shanghai. From Shanghai it will be Buence Aires as this the only city not visited still. From Buence Aires we\'ll go back to to New York as all the cities are visited.

So, the order will be

New York-London-Istanbul-Moscow-Shanghai-Buence Aires-New York