Question 1161123: Is it C? I want to check my answer.
Which of the following is the cheapest route to visit each city using the "Brute Force Method" starting from A and ending at A.
A. ABCDA
B. ADCBA
C. ABDCA
D. None of the Above
The question is provided in the link here: https://i.imgur.com/r9Xe37R.png
Answer by greenestamps(13203)   (Show Source):
You can put this solution on YOUR website!
The answer is NOT C.
The brute force method determines the cheapest route by examining ALL POSSIBLE routes. ABCDA is not the cheapest route.
In a relatively simple graph like this, the cheapest route will be one that does NOT follow the most expensive edge.
In this graph, edge CD is the most expensive. Answer choices A, B, and C all use edge CD (or DC), so the answer is D none of the above.
This graph is small enough it is not very difficult to list all possible circuits and find the cost of each.
ABCDA
ABDCA
ACBDA
ACDBA
ADBCA
ADCBA
Note that this list of all 6 circuits is actually 3 different circuits, each listed twice, in opposite orders.
The cheapest route is either of the two that do not use edge CD: ACBDA or ADBCA -- which again are the same circuit in opposite directions.
|
|
|
