{"id":2795,"date":"2025-06-01T08:44:17","date_gmt":"2025-06-01T08:44:17","guid":{"rendered":"https:\/\/diznr.com\/?p=2795"},"modified":"2025-06-01T08:44:17","modified_gmt":"2025-06-01T08:44:17","slug":"traveling-salesman-problem-using-dynamic-programming-with-practical-example","status":"publish","type":"post","link":"https:\/\/www.reilsolar.com\/pdf\/traveling-salesman-problem-using-dynamic-programming-with-practical-example\/","title":{"rendered":"Traveling Salesman Problem Using Dynamic Programming With Practical Example"},"content":{"rendered":"<p>Traveling Salesman Problem Using Dynamic Programming With Practical Example<\/p>\n<p>[fvplayer id=&#8221;116&#8243;]<\/p>\n<h3 data-start=\"0\" data-end=\"71\"><strong data-start=\"4\" data-end=\"69\">\u00a0Traveling Salesman Problem (TSP) Using Dynamic Programming<\/strong><\/h3>\n<p data-start=\"73\" data-end=\"338\">The <strong data-start=\"77\" data-end=\"113\">Traveling Salesman Problem (TSP)<\/strong> is one of the most famous <strong data-start=\"140\" data-end=\"165\">optimization problems<\/strong> in computer science and operations research. The goal is to <strong data-start=\"226\" data-end=\"262\">find the shortest possible route<\/strong> that visits each city <strong data-start=\"285\" data-end=\"301\">exactly once<\/strong> and returns to the starting point.<\/p>\n<h3 data-start=\"345\" data-end=\"374\"><strong data-start=\"348\" data-end=\"372\">\u00a0Problem Statement<\/strong><\/h3>\n<p data-start=\"375\" data-end=\"567\">Given a set of <strong data-start=\"390\" data-end=\"402\">N cities<\/strong> and the <strong data-start=\"411\" data-end=\"429\">cost to travel<\/strong> between each pair of cities, find the <strong data-start=\"468\" data-end=\"495\">shortest possible route<\/strong> that visits every city exactly once and returns to the starting city.<\/p>\n<h3 data-start=\"574\" data-end=\"610\"><strong data-start=\"577\" data-end=\"608\">\u00a0Why Dynamic Programming?<\/strong><\/h3>\n<p data-start=\"611\" data-end=\"757\"><strong data-start=\"613\" data-end=\"680\">Brute force solution (O(N!) complexity) is too slow for large N<\/strong><br data-start=\"680\" data-end=\"683\" \/><strong data-start=\"685\" data-end=\"755\">Dynamic Programming (DP) approach reduces complexity to O(2^N * N)<\/strong><\/p>\n<h3 data-start=\"764\" data-end=\"822\"><strong data-start=\"767\" data-end=\"820\">\u00a0Approach &#8211; Dynamic Programming with Bitmasking<\/strong><\/h3>\n<ul data-start=\"823\" data-end=\"1028\">\n<li data-start=\"823\" data-end=\"870\">Use <strong data-start=\"829\" data-end=\"843\">Bitmasking<\/strong> to track visited cities.<\/li>\n<li data-start=\"871\" data-end=\"927\">Use <strong data-start=\"877\" data-end=\"892\">Memoization<\/strong> to store results of subproblems.<\/li>\n<li data-start=\"928\" data-end=\"1028\">Define <strong data-start=\"937\" data-end=\"952\">dp[mask][i]<\/strong> as the minimum cost to visit all cities in <strong data-start=\"996\" data-end=\"1004\">mask<\/strong> ending at city <strong data-start=\"1020\" data-end=\"1025\">i<\/strong>.<\/li>\n<\/ul>\n<h3 data-start=\"1035\" data-end=\"1052\"><strong data-start=\"1038\" data-end=\"1052\">\u00a0Example<\/strong><\/h3>\n<p data-start=\"1053\" data-end=\"1094\">Let\u2019s take <strong data-start=\"1064\" data-end=\"1076\">4 cities<\/strong>: <strong data-start=\"1078\" data-end=\"1092\">A, B, C, D<\/strong><\/p>\n<h3 data-start=\"1096\" data-end=\"1142\"><strong data-start=\"1100\" data-end=\"1142\">Distance Matrix (Graph Representation)<\/strong><\/h3>\n<table data-start=\"1143\" data-end=\"1286\">\n<thead data-start=\"1143\" data-end=\"1164\">\n<tr data-start=\"1143\" data-end=\"1164\">\n<th data-start=\"1143\" data-end=\"1147\"><\/th>\n<th data-start=\"1147\" data-end=\"1151\">A<\/th>\n<th data-start=\"1151\" data-end=\"1155\">B<\/th>\n<th data-start=\"1155\" data-end=\"1159\">C<\/th>\n<th data-start=\"1159\" data-end=\"1164\">D<\/th>\n<\/tr>\n<\/thead>\n<tbody data-start=\"1187\" data-end=\"1286\">\n<tr data-start=\"1187\" data-end=\"1211\">\n<td>A<\/td>\n<td>0<\/td>\n<td>10<\/td>\n<td>15<\/td>\n<td>20<\/td>\n<\/tr>\n<tr data-start=\"1212\" data-end=\"1236\">\n<td>B<\/td>\n<td>10<\/td>\n<td>0<\/td>\n<td>35<\/td>\n<td>25<\/td>\n<\/tr>\n<tr data-start=\"1237\" data-end=\"1261\">\n<td>C<\/td>\n<td>15<\/td>\n<td>35<\/td>\n<td>0<\/td>\n<td>30<\/td>\n<\/tr>\n<tr data-start=\"1262\" data-end=\"1286\">\n<td>D<\/td>\n<td>20<\/td>\n<td>25<\/td>\n<td>30<\/td>\n<td>0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p data-start=\"1288\" data-end=\"1374\">We start from city <strong data-start=\"1307\" data-end=\"1323\">A (0th city)<\/strong> and find the shortest route covering all cities.<\/p>\n<h3 data-start=\"1381\" data-end=\"1419\"><strong data-start=\"1384\" data-end=\"1419\">\u00a0Dynamic Programming Solution<\/strong><\/h3>\n<div class=\"contain-inline-size rounded-md border-[0.5px] border-token-border-medium relative bg-token-sidebar-surface-primary dark:bg-gray-950\">\n<div class=\"overflow-y-auto p-4\" dir=\"ltr\">\n<p><code class=\"!whitespace-pre language-python\"><span class=\"hljs-keyword\">import<\/span> sys<\/code><\/p>\n<p><span class=\"hljs-comment\"># Number of cities<\/span><br \/>\nN = <span class=\"hljs-number\">4<\/span><br \/>\n<span class=\"hljs-comment\"># Distance matrix<\/span><br \/>\ndist = [<br \/>\n[<span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">10<\/span>, <span class=\"hljs-number\">15<\/span>, <span class=\"hljs-number\">20<\/span>],<br \/>\n[<span class=\"hljs-number\">10<\/span>, <span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">35<\/span>, <span class=\"hljs-number\">25<\/span>],<br \/>\n[<span class=\"hljs-number\">15<\/span>, <span class=\"hljs-number\">35<\/span>, <span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">30<\/span>],<br \/>\n[<span class=\"hljs-number\">20<\/span>, <span class=\"hljs-number\">25<\/span>, <span class=\"hljs-number\">30<\/span>, <span class=\"hljs-number\">0<\/span>]<br \/>\n]<\/p>\n<p><span class=\"hljs-comment\"># Memoization table (stores results of subproblems)<\/span><br \/>\ndp = [[-<span class=\"hljs-number\">1<\/span>] * (<span class=\"hljs-number\">1<\/span> &lt;&lt; N) <span class=\"hljs-keyword\">for<\/span> _ <span class=\"hljs-keyword\">in<\/span> <span class=\"hljs-built_in\">range<\/span>(N)]<\/p>\n<p><span class=\"hljs-comment\"># Function to find the shortest route using DP + Bitmasking<\/span><br \/>\n<span class=\"hljs-keyword\">def<\/span> <span class=\"hljs-title function_\">tsp<\/span>(<span class=\"hljs-params\">mask, pos<\/span>):<br \/>\n<span class=\"hljs-comment\"># Base case: If all cities are visited, return cost to return to starting city<\/span><br \/>\n<span class=\"hljs-keyword\">if<\/span> mask == (<span class=\"hljs-number\">1<\/span> &lt;&lt; N) &#8211; <span class=\"hljs-number\">1<\/span>:<br \/>\n<span class=\"hljs-keyword\">return<\/span> dist[pos][<span class=\"hljs-number\">0<\/span>] <span class=\"hljs-comment\"># Return to start city<\/span><\/p>\n<p><span class=\"hljs-comment\"># If already computed, return stored result<\/span><br \/>\n<span class=\"hljs-keyword\">if<\/span> dp[pos][mask] != &#8211;<span class=\"hljs-number\">1<\/span>:<br \/>\n<span class=\"hljs-keyword\">return<\/span> dp[pos][mask]<\/p>\n<p><span class=\"hljs-comment\"># Try visiting the next unvisited city<\/span><br \/>\nmin_cost = sys.maxsize<br \/>\n<span class=\"hljs-keyword\">for<\/span> city <span class=\"hljs-keyword\">in<\/span> <span class=\"hljs-built_in\">range<\/span>(N):<br \/>\n<span class=\"hljs-keyword\">if<\/span> (mask &amp; (<span class=\"hljs-number\">1<\/span> &lt;&lt; city)) == <span class=\"hljs-number\">0<\/span>: <span class=\"hljs-comment\"># If city not visited<\/span><br \/>\nnew_cost = dist[pos][city] + tsp(mask | (<span class=\"hljs-number\">1<\/span> &lt;&lt; city), city)<br \/>\nmin_cost = <span class=\"hljs-built_in\">min<\/span>(min_cost, new_cost)<\/p>\n<p><span class=\"hljs-comment\"># Store result in DP table<\/span><br \/>\ndp[pos][mask] = min_cost<br \/>\n<span class=\"hljs-keyword\">return<\/span> min_cost<\/p>\n<p><span class=\"hljs-comment\"># Start from city 0 with only city 0 visited (mask = 1)<\/span><br \/>\nmin_route_cost = tsp(<span class=\"hljs-number\">1<\/span>, <span class=\"hljs-number\">0<\/span>)<br \/>\n<span class=\"hljs-built_in\">print<\/span>(<span class=\"hljs-string\">&#8220;Minimum Traveling Cost:&#8221;<\/span>, min_route_cost)<\/p>\n<\/div>\n<\/div>\n<h3 data-start=\"2528\" data-end=\"2561\"><strong data-start=\"2531\" data-end=\"2561\">\u00a0Explanation of the Code<\/strong><\/h3>\n<p data-start=\"2562\" data-end=\"2914\"><strong data-start=\"2566\" data-end=\"2576\"><code data-start=\"2568\" data-end=\"2574\">mask<\/code><\/strong> keeps track of visited cities using bitmasking.<br data-start=\"2624\" data-end=\"2627\" \/><strong data-start=\"2631\" data-end=\"2640\"><code data-start=\"2633\" data-end=\"2638\">pos<\/code><\/strong> represents the last visited city.<br data-start=\"2674\" data-end=\"2677\" \/><strong data-start=\"2681\" data-end=\"2694\">Base Case<\/strong>: If all cities are visited, return cost to return to the start.<br data-start=\"2758\" data-end=\"2761\" \/><strong data-start=\"2765\" data-end=\"2783\">Recursive Case<\/strong>: Try visiting all unvisited cities and take the minimum cost.<br data-start=\"2845\" data-end=\"2848\" \/><strong data-start=\"2852\" data-end=\"2880\">Memoization (<code data-start=\"2867\" data-end=\"2871\">dp<\/code> table)<\/strong> avoids recomputing subproblems.<\/p>\n<h3 data-start=\"2921\" data-end=\"2937\"><strong data-start=\"2924\" data-end=\"2937\">\u00a0Output<\/strong><\/h3>\n<div class=\"contain-inline-size rounded-md border-[0.5px] border-token-border-medium relative bg-token-sidebar-surface-primary dark:bg-gray-950\">\n<div class=\"overflow-y-auto p-4\" dir=\"ltr\"><code class=\"!whitespace-pre\"><span class=\"hljs-attr\">Minimum Traveling Cost:<\/span> <span class=\"hljs-number\">80<\/span><br \/>\n<\/code><\/div>\n<\/div>\n<p data-start=\"2974\" data-end=\"3036\"><strong data-start=\"2976\" data-end=\"2992\">Optimal Path<\/strong>: <code data-start=\"2994\" data-end=\"3017\">A -&gt; B -&gt; D -&gt; C -&gt; A<\/code> with cost <strong data-start=\"3028\" data-end=\"3034\">80<\/strong><\/p>\n<h3 data-start=\"3043\" data-end=\"3068\"><strong data-start=\"3046\" data-end=\"3068\">\u00a0Time Complexity<\/strong><\/h3>\n<p data-start=\"3069\" data-end=\"3113\"><strong data-start=\"3072\" data-end=\"3086\">O(2^N * N)<\/strong> (Much better than O(N!))<\/p>\n<h3 data-start=\"3120\" data-end=\"3149\"><strong data-start=\"3123\" data-end=\"3149\">\u00a0Applications of TSP<\/strong><\/h3>\n<p data-start=\"3150\" data-end=\"3285\"><strong data-start=\"3152\" data-end=\"3189\">Logistics &amp; Delivery Optimization<\/strong>\u00a0<br data-start=\"3192\" data-end=\"3195\" \/><strong data-start=\"3197\" data-end=\"3232\">Route Planning for Salespersons<\/strong>\u00a0<br data-start=\"3235\" data-end=\"3238\" \/><strong data-start=\"3240\" data-end=\"3280\">Network Routing &amp; Data Communication<\/strong><\/p>\n<p data-start=\"3292\" data-end=\"3382\" data-is-last-node=\"\" data-is-only-node=\"\">Would you like a <strong data-start=\"3309\" data-end=\"3332\">Graph Visualization<\/strong> or another approach (e.g., Genetic Algorithm)?<\/p>\n<h3 data-start=\"3292\" data-end=\"3382\"><a href=\"https:\/\/www.cvs.edu.in\/upload\/DAA%20travelling%20salesman.pdf\" target=\"_blank\" rel=\"noopener\">Traveling Salesman Problem Using Dynamic Programming With Practical Example<\/a><\/h3>\n<h3 class=\"LC20lb MBeuO DKV0Md\"><a href=\"https:\/\/sdiopr.s3.ap-south-1.amazonaws.com\/2024\/Jun\/7-Jun-24_2nd%20time\/2024_AJPAS_118144\/Revised-ms_AJPAS_118144_v1.pdf\" target=\"_blank\" rel=\"noopener\">travelsalesman problem using dynamic programming<\/a><\/h3>\n<p>Here\u2019s a complete and student-friendly explanation of the <strong>Traveling Salesman Problem (TSP)<\/strong> using <strong>Dynamic Programming<\/strong>, with a <strong>practical example<\/strong>, ideal for <strong>B.Tech, GATE, BCA, or computer science interviews<\/strong>.<\/p>\n<hr \/>\n<h2>\ud83d\ude9a <strong>Traveling Salesman Problem (TSP) Using Dynamic Programming<\/strong><\/h2>\n<hr \/>\n<h3>\ud83d\udd0d <strong>What is TSP?<\/strong><\/h3>\n<p>The <strong>Traveling Salesman Problem (TSP)<\/strong> asks:<\/p>\n<blockquote><p>&#8220;Given a set of cities and the distances between every pair, what is the shortest possible route that visits every city exactly once and returns to the starting city?&#8221;<\/p><\/blockquote>\n<p>\u2705 It\u2019s a <strong>combinatorial optimization problem<\/strong><br \/>\n\u2705 TSP is an <strong>NP-hard problem<\/strong><br \/>\n\u2705 Useful in <strong>logistics, circuit design, planning, etc.<\/strong><\/p>\n<hr \/>\n<h3>\u2699\ufe0f <strong>Dynamic Programming Approach (Bitmasking + DP)<\/strong><\/h3>\n<p>We use a <strong>bitmask<\/strong> to represent visited cities and <strong>memoization<\/strong> to store subproblem solutions.<\/p>\n<hr \/>\n<h2>\ud83d\udcd8 <strong>Basic Idea:<\/strong><\/h2>\n<p>Let\u2019s say:<\/p>\n<ul>\n<li><code>n<\/code> = number of cities<\/li>\n<li><code>dp[mask][i]<\/code> = minimum cost to reach city <code>i<\/code> after visiting cities in <code>mask<\/code><\/li>\n<\/ul>\n<hr \/>\n<h3>\ud83d\udd23 <strong>Recurrence Relation:<\/strong><\/h3>\n<p><span class=\"katex\">dp[mask][i]=min\u2061j\u2209mask(dp[mask\u2223(1&lt;&lt;j)][j]+dist[i][j])dp[mask][i] = \\min_{j \\notin mask} \\left( dp[mask | (1 &lt;&lt; j)][j] + dist[i][j] \\right)<\/span><\/p>\n<ul>\n<li><code>mask<\/code> is a binary number representing visited cities<\/li>\n<li>Base case:<\/li>\n<\/ul>\n<p><span class=\"katex\">dp[1&lt;&lt;i][i]=dist[0][i](if\u00a0we\u00a0start\u00a0from\u00a0city\u00a00)dp[1 &lt;&lt; i][i] = dist[0][i] \\quad \\text{(if we start from city 0)}<\/span><\/p>\n<hr \/>\n<h2>\ud83e\uddea <strong>Practical Example:<\/strong><\/h2>\n<p>Let\u2019s solve for <strong>4 cities<\/strong> (0, 1, 2, 3) with the distance matrix:<\/p>\n<pre><code>     0   1   2   3\n0 |  0   10  15  20\n1 | 10   0   35  25\n2 | 15  35   0   30\n3 | 20  25  30   0\n<\/code><\/pre>\n<p>Goal: Start from city 0, visit all cities exactly once, and return to 0.<\/p>\n<hr \/>\n<h2>\u2705 <strong>Using DP (Bitmasking Approach)<\/strong><\/h2>\n<p>There are <span class=\"katex\">2n\u00d7n2^n \\times n<\/span> states<br \/>\nFor n=4 \u21d2 16 x 4 = 64 states<\/p>\n<hr \/>\n<h3>\ud83d\udda5\ufe0f <strong>Code (C++ Style Pseudocode):<\/strong><\/h3>\n<pre><code class=\"language-cpp\">int tsp(int mask, int pos, vector&lt;vector&lt;int&gt;&gt; &amp;dist, vector&lt;vector&lt;int&gt;&gt; &amp;dp) {\n    int n = dist.size();\n\n    if (mask == (1 &lt;&lt; n) - 1)\n        return dist[pos][0]; \/\/ return to start\n\n    if (dp[mask][pos] != -1)\n        return dp[mask][pos];\n\n    int ans = INT_MAX;\n\n    for (int city = 0; city &lt; n; city++) {\n        if ((mask &amp; (1 &lt;&lt; city)) == 0) {\n            int newAns = dist[pos][city] + tsp(mask | (1 &lt;&lt; city), city, dist, dp);\n            ans = min(ans, newAns);\n        }\n    }\n\n    return dp[mask][pos] = ans;\n}\n<\/code><\/pre>\n<hr \/>\n<h3>\ud83e\udde0 <strong>Initial Call:<\/strong><\/h3>\n<pre><code class=\"language-cpp\">int n = 4;\nvector&lt;vector&lt;int&gt;&gt; dp(1 &lt;&lt; n, vector&lt;int&gt;(n, -1));\nint result = tsp(1, 0, dist, dp);\n<\/code><\/pre>\n<hr \/>\n<h2>\ud83e\uddfe <strong>Output for This Example:<\/strong><\/h2>\n<p>The <strong>minimum cost<\/strong> path is:<\/p>\n<pre><code class=\"language-text\">0 \u2192 1 \u2192 3 \u2192 2 \u2192 0\n<\/code><\/pre>\n<p>With total cost = <strong>80<\/strong><\/p>\n<hr \/>\n<h2>\u23f1\ufe0f <strong>Time Complexity:<\/strong><\/h2>\n<p><span class=\"katex\">O(n2\u22c52n)O(n^2 \\cdot 2^n)<\/span><\/p>\n<p>Space: <span class=\"katex\">O(n\u22c52n)O(n \\cdot 2^n)<\/span><\/p>\n<p>\u2705 Efficient for <strong>n \u2264 16<\/strong><\/p>\n<hr \/>\n<h2>\ud83c\udfaf <strong>TSP Recap:<\/strong><\/h2>\n<table>\n<thead>\n<tr>\n<th>Feature<\/th>\n<th>Description<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>Technique<\/td>\n<td>Bitmasking + Memoization (DP)<\/td>\n<\/tr>\n<tr>\n<td>Complexity<\/td>\n<td><span class=\"katex\">O(n2\u22c52n)O(n^2 \\cdot 2^n)<\/span><\/td>\n<\/tr>\n<tr>\n<td>Input<\/td>\n<td>Distance matrix<\/td>\n<\/tr>\n<tr>\n<td>Output<\/td>\n<td>Shortest tour covering all cities<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<hr \/>\n<h2>\ud83d\udce6 <strong>Want These?<\/strong><\/h2>\n<ul class=\"contains-task-list\">\n<li class=\"task-list-item\"> Python or Java implementation?<\/li>\n<li class=\"task-list-item\"> Step-by-step animated explanation?<\/li>\n<li class=\"task-list-item\"> PDF notes with trace table?<\/li>\n<li class=\"task-list-item\"> Hindi explanation video?<\/li>\n<\/ul>\n<p>Just say the word \u2014 I\u2019ll deliver what you need for your exam or project!<\/p>\n<h3><a href=\"https:\/\/repub.eur.nl\/pub\/101691\/ERS-2017-011-LIS_v01.pdf\" target=\"_blank\" rel=\"noopener\">Traveling Salesman Problem Using Dynamic Programming With Practical Example<\/a><\/h3>\n","protected":false},"excerpt":{"rendered":"<p>Traveling Salesman Problem Using Dynamic Programming With Practical Example [fvplayer id=&#8221;116&#8243;] \u00a0Traveling Salesman Problem (TSP) Using Dynamic Programming The Traveling Salesman Problem (TSP) is one of the most famous optimization problems in computer science and operations research. The goal is to find the shortest possible route that visits each city exactly once and returns to [&hellip;]<\/p>\n","protected":false},"author":71,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-2795","post","type-post","status-publish","format-standard","hentry","category-algorithm-analysis-and-design"],"_links":{"self":[{"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/posts\/2795","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/users\/71"}],"replies":[{"embeddable":true,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/comments?post=2795"}],"version-history":[{"count":0,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/posts\/2795\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/media?parent=2795"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/categories?post=2795"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/tags?post=2795"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}