{"id":2168,"date":"2023-08-08T18:10:09","date_gmt":"2023-08-08T12:40:09","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2168"},"modified":"2023-08-17T13:33:48","modified_gmt":"2023-08-17T08:03:48","slug":"travelling-salesman-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/travelling-salesman-problem\/","title":{"rendered":"Travelling Salesman Problem (TSP)"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#example-1-travelling-salesman-problem-\">Example 1: Travelling Salesman Problem <\/a><\/li><li><a href=\"#example-2-travelling-salesman-problem-\">Example 2: Travelling Salesman Problem <\/a><\/li><\/ul><li><a href=\"#1-simple-approach\">1. Simple Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#java-code-implementation\">Java Code Implementation<\/a><\/li><li><a href=\"#python-code-implementation\">Python Code Implementation<\/a><\/li><\/ul><li><a href=\"#2-travelling-salesman-problem-using-dynamic-programming\">2. Travelling Salesman Problem Using Dynamic Programming<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-implementation\">C Code Implementation<\/a><\/li><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#python-code-implementation\">Python Code Implementation<\/a><\/li><li><a href=\"#java-code-implementation\">Java Code Implementation<\/a><\/li><\/ul><li><a href=\"#3-greedy-approach\">3. Greedy Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#-java-code-implementation\"><meta charset=\"utf-8\">Java Code Implementation<\/a><\/li><li><a href=\"#python-code-implementation\">Python Code Implementation<\/a><\/li><\/ul><li><a href=\"#practice-questions\">Practice Questions<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#1-which-algorithm-is-used-for-the-travelling-salesman-problem\">1. Which algorithm is used for the Travelling salesman problem?<\/a><\/li><li><a href=\"#2-what-is-the-complexity-of-the-travelling-salesman-problem\">2. What is the complexity of the Travelling salesman problem?<\/a><\/li><li><a href=\"#3-how-is-this-problem-modelled-as-a-graph-problem\">3. How is this problem modelled as a Graph problem?<\/a><\/li><li><a href=\"#4-what-is-the-difficulty-level-of-the-travelling-salesman-problem\">4: What is the difficulty level of the Travelling salesman problem?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p><strong>Travelling Salesman Problem (TSP)<\/strong>&#8211; Given a set of cities and the distance between every pair of cities as an adjacency matrix, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point. The ultimate goal is to minimize the total distance travelled, forming a closed tour or circuit.<\/p>\n\n\n\n<p>The TSP is referred to as an NP-hard problem, meaning there is no known algorithm to solve it in polynomial time for large instances. As the number of cities increases, the number of potential solutions grows exponentially, making an exhaustive search unfeasible. This complexity is one of the reasons why the TSP remains a popular topic of research. <a rel=\"noreferrer noopener\" href=\"https:\/\/en.wikipedia.org\/wiki\/Travelling_salesman_problem\" target=\"_blank\">Learn More<\/a>.<\/p>\n\n\n\n<iframe loading=\"lazy\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/WIz6PppzYZE\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen=\"\"><\/iframe>\n\n\n\n<h3 id=\"example-1-travelling-salesman-problem-\"><span id=\"example-1-travelling-salesman-problem\">Example 1: Travelling Salesman Problem <\/span><\/h3>\n\n\n\n<p><strong>Input<\/strong> &#8211;<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"320\"  height=\"340\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Input\"  class=\"wp-image-2172 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 320px) 100vw, 320px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/3-2.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/3-2.jpg 320w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/3-2-282x300.jpg 282w\" ><\/figure>\n\n\n\n<p><strong>Output<\/strong> &#8211;<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"314\"  height=\"391\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Output\"  class=\"wp-image-2170 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 314px) 100vw, 314px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/1-6.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/1-6.jpg 314w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/1-6-241x300.jpg 241w\" ><\/figure>\n\n\n\n<p>Here, the TSP Tour is 0-2-1-3-0 and the cost of the tour is 48.<\/p>\n\n\n\n<h3 id=\"example-2-travelling-salesman-problem-\"><span id=\"example-2-travelling-salesman-problem\">Example 2: Travelling Salesman Problem <\/span><\/h3>\n\n\n\n<p><strong>Input &#8211;<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"397\"  height=\"349\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"TSP Input\"  class=\"wp-image-2171 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 397px) 100vw, 397px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/2-5.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/2-5.jpg 397w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/2-5-300x264.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/09\/2-5-380x334.jpg 380w\" ><\/figure>\n\n\n\n<p><strong>Output &#8211;<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"travelling salesman problem-ex-2\"  class=\"wp-image-22872 pk-lazyload\"  width=\"698\"  height=\"747\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 698px) 100vw, 698px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2023\/08\/Travelling-Salesman-Problem-Example-2-1-2-956x1024.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2023\/08\/Travelling-Salesman-Problem-Example-2-1-2-956x1024.png 956w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2023\/08\/Travelling-Salesman-Problem-Example-2-1-2-280x300.png 280w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2023\/08\/Travelling-Salesman-Problem-Example-2-1-2-768x823.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2023\/08\/Travelling-Salesman-Problem-Example-2-1-2-1433x1536.png 1433w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2023\/08\/Travelling-Salesman-Problem-Example-2-1-2-1911x2048.png 1911w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2023\/08\/Travelling-Salesman-Problem-Example-2-1-2-380x407.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2023\/08\/Travelling-Salesman-Problem-Example-2-1-2-550x589.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2023\/08\/Travelling-Salesman-Problem-Example-2-1-2-800x857.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2023\/08\/Travelling-Salesman-Problem-Example-2-1-2-1160x1243.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2023\/08\/Travelling-Salesman-Problem-Example-2-1-2-150x161.png 150w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2023\/08\/Travelling-Salesman-Problem-Example-2-1-2.png 2250w\" ><\/figure>\n\n\n\n<p><strong>Minimum weight Hamiltonian Cycle<\/strong>: EACBDE= 32<\/p>\n\n\n\n<p>Wondering how the <a href=\"https:\/\/www.interviewbit.com\/blog\/hamiltonian-path-problem\/\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>Hamiltonian Cycle Problem<\/strong><\/a> and the Traveling Salesman Problem differ? The Hamiltonian Cycle problem is to find out if there exists a tour that visits each city exactly once. Here, we know that the Hamiltonian Tour exists (due to the graph being complete), and there are indeed many such tours. The problem is to find a minimum weight Hamiltonian Cycle.<\/p>\n\n\n\n<p>There are <strong>various approaches<\/strong> to finding the solution to the travelling salesman problem- simple (na\u00efve) approach, dynamic programming approach, and greedy approach. Let&#8217;s explore each approach in detail:<\/p>\n\n\n\n<h2 id=\"1-simple-approach\">1. Simple Approach<\/h2>\n\n\n\n<ul><li>Consider city 1 as the starting and ending point. Since the route is cyclic, we can consider any point as a starting point.<\/li><li>Now, we will generate all possible permutations of cities which are (n-1)!.<\/li><li>Find the cost of each permutation and keep track of the minimum cost permutation.<\/li><li>Return the permutation with minimum cost.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code-implementation\"><span id=\"c-code-implementation-3\">C++ Code Implementation<\/span><\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/116fbb48229579a62a71 title='Interviewbit Ide snippet\/116fbb48229579a62a71' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h3 id=\"java-code-implementation\"><span id=\"java-code-implementation-2\">Java Code Implementation<\/span><\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/3fe8f99acc42d7aefdfa title='Interviewbit Ide snippet\/3fe8f99acc42d7aefdfa' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h3 id=\"python-code-implementation\"><span id=\"python-code-implementation-2\">Python Code Implementation<\/span><\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/bfafeefa6b10ac6a2439 title='Interviewbit Ide snippet\/bfafeefa6b10ac6a2439' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<ul><li><strong>Time complexity:<\/strong> O(N!), Where N is the number of cities.<\/li><li><strong>Space complexity:<\/strong> O(1).<\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"2-travelling-salesman-problem-using-dynamic-programming\">2. Travelling Salesman Problem Using Dynamic Programming<\/h2>\n\n\n\n<p>In the travelling salesman problem algorithm, we take a subset N of the required cities that need to be visited, the distance among the cities dist, and starting cities s as inputs. Each city is identified by a unique city id which we say like 1,2,3,4,5\u2026\u2026\u2026n<\/p>\n\n\n\n<p>Here we use a dynamic approach to calculate the cost function Cost(). Using recursive calls, we calculate the cost function for each subset of the original problem.<\/p>\n\n\n\n<p>To calculate the cost(i) using <a href=\"https:\/\/www.interviewbit.com\/courses\/programming\/dynamic-programming\/\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>Dynamic Programming<\/strong><\/a>, we need to have some recursive relation in terms of sub-problems.<\/p>\n\n\n\n<p>We start with all subsets of size 2 and calculate C(S, i) for all subsets where S is the subset, then we calculate C(S, i) for all subsets S of size 3 and so on.<\/p>\n\n\n\n<p>There are at most O(n2^n) subproblems, and each one takes linear time to solve. The total running time is, therefore, O(n^22^n). The time complexity is much less than O(n!) but still exponential. The space required is also exponential.<\/p>\n\n\n\n<h3 id=\"c-code-implementation\"><span id=\"c-code-implementation-2\">C Code Implementation<\/span><\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/7eaa91f19c572373f014 title='Interviewbit Ide snippet\/7eaa91f19c572373f014' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h3 id=\"c-code-implementation\"><span id=\"c-code-implementation-4\">C++ Code Implementation<\/span><\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: 700px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/6fa24f02b93e9adf2f27 title='Interviewbit Ide snippet\/5d2ee7cf4db6311fcfbc' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h3 id=\"python-code-implementation\"><span id=\"python-code-implementation-3\">Python Code Implementation<\/span><\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: 700px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/3132dc879fee5648fb55 title='Interviewbit Ide snippet\/3132dc879fee5648fb55' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-scripts allow-same-origin allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h3 id=\"java-code-implementation\">Java Code Implementation<\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/75e6face95a79daac29e title='Interviewbit Ide snippet\/75e6face95a79daac29e' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(N^2*2^N).<\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"3-greedy-approach\">3. Greedy Approach<\/h2>\n\n\n\n<ul><li>First of all, we have to create two primary data holders.<ul><li>First of them is a list that can hold the indices of the cities in terms of the input matrix of distances between cities<\/li><li>And the Second one is the array which is our result<\/li><\/ul><\/li><li>Perform traversal on the given adjacency matrix tsp[][] for all the cities and if the cost of reaching any city from the current city is less than the current cost update the cost.<\/li><li>Generate the minimum path cycle using the above step and return their minimum cost.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code-implementation\">C++ Code Implementation<\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/1e3c57c7c77c537fb6b9 title='Interviewbit Ide snippet\/1e3c57c7c77c537fb6b9' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h3 id=\"-java-code-implementation\"><span id=\"java-code-implementation-3\"><meta charset=\"utf-8\">Java Code Implementation<\/span><\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/1d70a6b210e135ac90c4 title='Interviewbit Ide snippet\/1d70a6b210e135ac90c4' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<h3 id=\"python-code-implementation\">Python Code Implementation<\/h3>\n\n\n\n<iframe style='max-width:100%; border: none; height: 375px; width: {width}px;' height=375 width=700 src=https:\/\/www.interviewbit.com\/embed\/snippet\/e78aa4d8f83c9784cc95 title='Interviewbit Ide snippet\/e78aa4d8f83c9784cc95' loading=\"lazy\" allow=\"clipboard-write\" allowfullscreen referrerpolicy=\"unsafe-url\" sandbox=\"allow-same-origin allow-scripts allow-popups allow-top-navigation-by-user-activation allow-popups-to-escape-sandbox\"><\/iframe>\n\n\n\n<ul><li><strong>Time complexity: <\/strong>O(N^2*logN), Where N is the number of cities.<\/li><li><strong>Space complexity:<\/strong> O(N).<\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-questions\">Practice Questions<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/city-tour\/\" target=\"_blank\">City Tour Problem<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/shortest-common-superstring\/\" target=\"_blank\">Shortest Common Substring<\/a><\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"frequently-asked-questions\">Frequently Asked Questions<\/h2>\n\n\n\n<h3 id=\"1-which-algorithm-is-used-for-the-travelling-salesman-problem\">1. Which algorithm is used for the Travelling salesman problem?<\/h3>\n\n\n\n<p><strong>Ans<\/strong>. Travelling Salesman Problem uses Dynamic programming with a masking algorithm.<\/p>\n\n\n\n<h3 id=\"2-what-is-the-complexity-of-the-travelling-salesman-problem\">2. What is the complexity of the Travelling salesman problem?<\/h3>\n\n\n\n<p><strong>Ans.:<\/strong> The complexity of TSP using Greedy will be O(N^2<em>LogN) and using DP will be O(N^2<\/em>2^N).<\/p>\n\n\n\n<h3 id=\"3-how-is-this-problem-modelled-as-a-graph-problem\">3. How is this problem modelled as a Graph problem?<\/h3>\n\n\n\n<p><strong>Ans<\/strong>.: The TSP can be modelled as a graph problem by considering a complete graph G = (V, E). A tour is then a circuit in G that meets every node. In this context, tours are sometimes called Hamiltonian circuits.<\/p>\n\n\n\n<h3 id=\"4-what-is-the-difficulty-level-of-the-travelling-salesman-problem\">4: What is the difficulty level of the Travelling salesman problem?<\/h3>\n\n\n\n<p><strong>Ans.:<\/strong> It is an NP-hard problem.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Travelling Salesman Problem (TSP)&#8211; Given a set of cities and the distance between every pair of&hellip;\n","protected":false},"author":5,"featured_media":2173,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[368,367],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2168"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2168"}],"version-history":[{"count":36,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2168\/revisions"}],"predecessor-version":[{"id":22875,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2168\/revisions\/22875"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2173"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2168"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2168"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2168"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}