{"id":200723,"date":"2025-03-14T02:54:45","date_gmt":"2025-03-14T02:54:45","guid":{"rendered":"https:\/\/learnexams.com\/blog\/?p=200723"},"modified":"2025-03-14T02:54:49","modified_gmt":"2025-03-14T02:54:49","slug":"a-salesman-needs-to-visit-five-cities-a-b-c-d-and-e-starting-from-city-a","status":"publish","type":"post","link":"https:\/\/www.learnexams.com\/blog\/2025\/03\/14\/a-salesman-needs-to-visit-five-cities-a-b-c-d-and-e-starting-from-city-a\/","title":{"rendered":"A salesman needs to visit\u00a0five cities (A, B, C, D, and E), starting from\u00a0City A"},"content":{"rendered":"\n

A salesman needs to visit five cities (A, B, C, D, and E)<\/strong>, starting from City A<\/strong>. The distances between the cities (in hundreds of kilometers<\/strong>) are given in the table below.<\/p>\n\n\n\n

From\/To<\/th>A<\/th>B<\/th>C<\/th>D<\/th>E<\/th><\/tr><\/thead>
A<\/strong><\/td>–<\/td>7<\/td>6<\/td>8<\/td>4<\/td><\/tr>
B<\/strong><\/td>7<\/td>–<\/td>8<\/td>6<\/td>8<\/td><\/tr>
C<\/strong><\/td>6<\/td>8<\/td>–<\/td>5<\/td>6<\/td><\/tr>
D<\/strong><\/td>8<\/td>6<\/td>5<\/td>–<\/td>7<\/td><\/tr>
E<\/strong><\/td>4<\/td>8<\/td>6<\/td>7<\/td>–<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Objective:<\/h3>\n\n\n\n

Find the shortest possible route<\/strong> starting from City A<\/strong> that allows the salesman to visit each city exactly once<\/strong> and return to City A<\/strong>, minimizing the total distance traveled.<\/p>\n\n\n\n

The correct answer and explanation is:<\/mark><\/strong><\/p>\n\n\n\n

The optimal route for the salesman to visit all cities and return to City A, while minimizing the total distance traveled, is:<\/p>\n\n\n\n

A \u2192 B \u2192 D \u2192 C \u2192 E \u2192 A<\/strong>
Total Distance: 2800 km<\/strong><\/p>\n\n\n\n

Explanation:<\/h3>\n\n\n\n

This problem is a classic example of the Traveling Salesman Problem (TSP)<\/strong>, where we need to determine the shortest possible route that visits each city exactly once before returning to the starting point.<\/p>\n\n\n\n

Step 1: Understanding the Distance Matrix<\/strong><\/h4>\n\n\n\n

The given distance matrix provides the travel distances between each pair of cities. The objective is to find the shortest route covering all cities.<\/p>\n\n\n\n

Step 2: Generating All Possible Routes<\/strong><\/h4>\n\n\n\n

Since the salesman starts at City A, we generate all possible orders for visiting the remaining cities: B, C, D, and E<\/strong>. Using permutations, we list all possible sequences of these four cities and calculate the total round-trip distance for each.<\/p>\n\n\n\n

Step 3: Calculating Total Distance for Each Route<\/strong><\/h4>\n\n\n\n

For each route, the total travel distance is calculated by summing the corresponding distances from the matrix.<\/p>\n\n\n\n

For example, in our optimal route A \u2192 B \u2192 D \u2192 C \u2192 E \u2192 A<\/strong>:<\/p>\n\n\n\n

    \n
  • A \u2192 B = 700 km<\/li>\n\n\n\n
  • B \u2192 D = 600 km<\/li>\n\n\n\n
  • D \u2192 C = 500 km<\/li>\n\n\n\n
  • C \u2192 E = 600 km<\/li>\n\n\n\n
  • E \u2192 A = 400 km<\/li>\n<\/ul>\n\n\n\n

    Total Distance = 2800 km<\/strong><\/p>\n\n\n\n

    Step 4: Choosing the Optimal Route<\/strong><\/h4>\n\n\n\n

    Among all possible routes, A \u2192 B \u2192 D \u2192 C \u2192 E \u2192 A<\/strong> yields the shortest total distance<\/strong> of 2800 km<\/strong>, making it the best solution.<\/p>\n\n\n\n

    Visualization<\/strong><\/h4>\n\n\n\n

    The diagram illustrates the optimal path, with nodes representing cities and edges indicating travel distances.<\/p>\n\n\n\n

    By following this route, the salesman minimizes fuel consumption, travel time, and overall cost, making the journey as efficient as possible. \ud83d\ude97\ud83d\udca8<\/p>\n\n\n\n

    \"\"<\/figure>\n","protected":false},"excerpt":{"rendered":"

    A salesman needs to visit five cities (A, B, C, D, and E), starting from City A. The distances between the cities (in hundreds of kilometers) are given in the table below. From\/To A B C D E A – 7 6 8 4 B 7 – 8 6 8 C 6 8 – 5 6 D 8 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[25],"tags":[],"class_list":["post-200723","post","type-post","status-publish","format-standard","hentry","category-exams-certification"],"_links":{"self":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/posts\/200723","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/comments?post=200723"}],"version-history":[{"count":0,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/posts\/200723\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/media?parent=200723"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/categories?post=200723"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/tags?post=200723"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}