Question

You are renting a limousine that charges certain rates to visit each of the following cities. You need to visit each city once and you need to start in Athens and end in Athens. Use the "Brute Force" Algorithm to find the cheapest route to visit each city and return home again to Athens.

Answer 1

Answer:

The cheapest route to visit each city and return home again to Athens is:

A→B→C→D→A  or A→D→C→B→A.

Step-by-step explanation:

The Algorithm of Brute Force

1. List of all possible routes
2. Calculate the charge of each route found in Step 1
3. Pick the route which has the cheapest route.

Let Athens ⇒A , Buford ⇒B , Cuming ⇒ C , Dacula ⇒ D

There are 6 routes to visit each city and return home again to Athens.

Route 1: A→B→C→D→A = 70 + 25 + 30 + 60 = $185

Route 2: A→B→D→C→A = 70 + 70 + 30 + 50 = $220

Route 3: A→C→B→D→A = 50 + 25 + 70 + 60 = $205

Route 4: A→C→D→B→A = 50 + 30 + 70 + 70 = $220

Route 5: A→D→B→C→A = 60 + 70 + 25 + 50 = $205

Route 6: A→D→C→B→A = 60 + 30 + 25 + 70 = $185

By checking the previous routes:

The cheapest charge will be $185 and it will be for the route

A→B→C→D→A  or A→D→C→B→A.