-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathtravelling-salesman.html
More file actions
99 lines (86 loc) · 27.3 KB
/
travelling-salesman.html
File metadata and controls
99 lines (86 loc) · 27.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
<!DOCTYPE html>
<html lang="en-US">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1">
<title>Algorithm - Travelling Salesman</title>
<meta name="generator" content="VuePress 1.8.2">
<link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
<link rel="manifest" href="/site.webmanifest">
<link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png">
<link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5">
<meta name="description" content="Brute Force Algorithm, Dynamic Programming Algorithm">
<meta property="og:site_name" content="DevTut">
<meta property="og:title" content="Algorithm - Travelling Salesman">
<meta property="og:description" content="Brute Force Algorithm, Dynamic Programming Algorithm">
<meta property="og:type" content="article">
<meta property="og:url" content="/algorithm/travelling-salesman.html">
<meta property="og:image" content="/logo.png">
<meta name="twitter:title" content="Algorithm - Travelling Salesman">
<meta name="twitter:description" content="Brute Force Algorithm, Dynamic Programming Algorithm">
<meta name="twitter:url" content="/algorithm/travelling-salesman.html">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="/logo.png">
<meta name="theme-color" content="#ffffff">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<meta name="msapplication-TileImage" content="/mstile-150x150.png">
<meta name="msapplication-TileColor" content="#da532c">
<meta name="google-site-verification" content="76_rKXgwMVIjd-axJC_1zPV9OS4mEjvtgjYOWVkAdnQ">
<link rel="preload" href="/assets/css/0.styles.60619e34.css" as="style"><link rel="preload" href="/assets/js/app.1779e102.js" as="script"><link rel="preload" href="/assets/js/3.2cfa8016.js" as="script"><link rel="preload" href="/assets/js/75.7b814d35.js" as="script">
<link rel="stylesheet" href="/assets/css/0.styles.60619e34.css">
</head>
<body>
<div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">DevTut</span></a> <div class="links"><form id="search-form" role="search" class="algolia-search-wrapper search-box"><input id="algolia-search-input" class="search-query"></form> <nav class="nav-links can-hide"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav> <ul class="sidebar-links"><li><section class="sidebar-group depth-0"><p class="sidebar-heading open"><span>Algorithm</span> <!----></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/algorithm/" aria-current="page" class="sidebar-link">Disclaimer</a></li><li><a href="/algorithm/getting-started-with-algorithm.html" class="sidebar-link">Getting started with algorithm</a></li><li><a href="/algorithm/algorithm-complexity.html" class="sidebar-link">Algorithm Complexity</a></li><li><a href="/algorithm/big-o-notation.html" class="sidebar-link">Big-O Notation</a></li><li><a href="/algorithm/trees.html" class="sidebar-link">Trees</a></li><li><a href="/algorithm/binary-search-trees.html" class="sidebar-link">Binary Search Trees</a></li><li><a href="/algorithm/check-if-a-tree-is-bst-or-not.html" class="sidebar-link">Check if a tree is BST or not</a></li><li><a href="/algorithm/binary-tree-traversals.html" class="sidebar-link">Binary Tree traversals</a></li><li><a href="/algorithm/lowest-common-ancestor-of-a-binary-tree.html" class="sidebar-link">Lowest common ancestor of a Binary Tree</a></li><li><a href="/algorithm/graph.html" class="sidebar-link">Graph</a></li><li><a href="/algorithm/graph-traversals.html" class="sidebar-link">Graph Traversals</a></li><li><a href="/algorithm/dijkstras-algorithm.html" class="sidebar-link">Dijkstra’s Algorithm</a></li><li><a href="/algorithm/a-pathfinding.html" class="sidebar-link">A* Pathfinding</a></li><li><a href="/algorithm/a-pathfinding-algorithm.html" class="sidebar-link">A* Pathfinding Algorithm</a></li><li><a href="/algorithm/dynamic-programming.html" class="sidebar-link">Dynamic Programming</a></li><li><a href="/algorithm/applications-of-dynamic-programming.html" class="sidebar-link">Applications of Dynamic Programming</a></li><li><a href="/algorithm/kruskal-s-algorithm.html" class="sidebar-link">Kruskal's Algorithm</a></li><li><a href="/algorithm/greedy-algorithms.html" class="sidebar-link">Greedy Algorithms</a></li><li><a href="/algorithm/applications-of-greedy-technique.html" class="sidebar-link">Applications of Greedy technique</a></li><li><a href="/algorithm/prim-s-algorithm.html" class="sidebar-link">Prim's Algorithm</a></li><li><a href="/algorithm/bellman-ford-algorithm.html" class="sidebar-link">Bellman–Ford Algorithm</a></li><li><a href="/algorithm/line-algorithm.html" class="sidebar-link">Line Algorithm</a></li><li><a href="/algorithm/floyd-warshall-algorithm.html" class="sidebar-link">Floyd-Warshall Algorithm</a></li><li><a href="/algorithm/catalan-number-algorithm.html" class="sidebar-link">Catalan Number Algorithm</a></li><li><a href="/algorithm/multithreaded-algorithms.html" class="sidebar-link">Multithreaded Algorithms</a></li><li><a href="/algorithm/knuth-morris-pratt-kmp-algorithm.html" class="sidebar-link">Knuth Morris Pratt (KMP) Algorithm</a></li><li><a href="/algorithm/edit-distance-dynamic-algorithm.html" class="sidebar-link">Edit Distance Dynamic Algorithm</a></li><li><a href="/algorithm/online-algorithms.html" class="sidebar-link">Online algorithms</a></li><li><a href="/algorithm/integer-partition-algorithm.html" class="sidebar-link">Integer Partition Algorithm</a></li><li><a href="/algorithm/maximum-path-sum-algorithm.html" class="sidebar-link">Maximum Path Sum Algorithm</a></li><li><a href="/algorithm/maximum-subarray-algorithm.html" class="sidebar-link">Maximum Subarray Algorithm</a></li><li><a href="/algorithm/sliding-window-algorithm.html" class="sidebar-link">Sliding Window Algorithm</a></li><li><a href="/algorithm/sorting.html" class="sidebar-link">Sorting</a></li><li><a href="/algorithm/bubble-sort.html" class="sidebar-link">Bubble Sort</a></li><li><a href="/algorithm/merge-sort.html" class="sidebar-link">Merge Sort</a></li><li><a href="/algorithm/insertion-sort.html" class="sidebar-link">Insertion Sort</a></li><li><a href="/algorithm/bucket-sort.html" class="sidebar-link">Bucket Sort</a></li><li><a href="/algorithm/quicksort.html" class="sidebar-link">Quicksort</a></li><li><a href="/algorithm/counting-sort.html" class="sidebar-link">Counting Sort</a></li><li><a href="/algorithm/heap-sort.html" class="sidebar-link">Heap Sort</a></li><li><a href="/algorithm/cycle-sort.html" class="sidebar-link">Cycle Sort</a></li><li><a href="/algorithm/odd-even-sort.html" class="sidebar-link">Odd-Even Sort</a></li><li><a href="/algorithm/selection-sort.html" class="sidebar-link">Selection Sort</a></li><li><a href="/algorithm/pigeonhole-sort.html" class="sidebar-link">Pigeonhole Sort</a></li><li><a href="/algorithm/radix-sort.html" class="sidebar-link">Radix Sort</a></li><li><a href="/algorithm/shell-sort.html" class="sidebar-link">Shell Sort</a></li><li><a href="/algorithm/pancake-sort.html" class="sidebar-link">Pancake Sort</a></li><li><a href="/algorithm/searching.html" class="sidebar-link">Searching</a></li><li><a href="/algorithm/substring-search.html" class="sidebar-link">Substring Search</a></li><li><a href="/algorithm/breadth-first-search.html" class="sidebar-link">Breadth-First Search</a></li><li><a href="/algorithm/depth-first-search.html" class="sidebar-link">Depth First Search</a></li><li><a href="/algorithm/hash-functions.html" class="sidebar-link">Hash Functions</a></li><li><a href="/algorithm/travelling-salesman.html" aria-current="page" class="active sidebar-link">Travelling Salesman</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/algorithm/travelling-salesman.html#brute-force-algorithm" class="sidebar-link">Brute Force Algorithm</a></li><li class="sidebar-sub-header"><a href="/algorithm/travelling-salesman.html#dynamic-programming-algorithm" class="sidebar-link">Dynamic Programming Algorithm</a></li></ul></li><li><a href="/algorithm/shortest-common-supersequence-problem.html" class="sidebar-link">Shortest Common Supersequence Problem</a></li><li><a href="/algorithm/knapsack-problem.html" class="sidebar-link">Knapsack Problem</a></li><li><a href="/algorithm/equation-solving.html" class="sidebar-link">Equation Solving</a></li><li><a href="/algorithm/longest-common-subsequence.html" class="sidebar-link">Longest Common Subsequence</a></li><li><a href="/algorithm/longest-increasing-subsequence.html" class="sidebar-link">Longest Increasing Subsequence</a></li><li><a href="/algorithm/check-two-strings-are-anagrams.html" class="sidebar-link">Check two strings are anagrams</a></li><li><a href="/algorithm/pascal-s-triangle.html" class="sidebar-link">Pascal's Triangle</a></li><li><a href="/algorithm/algo-print-a-m-n-matrix-in-square-wise.html" class="sidebar-link">Algo:- Print a m*n matrix in square wise</a></li><li><a href="/algorithm/matrix-exponentiation.html" class="sidebar-link">Matrix Exponentiation</a></li><li><a href="/algorithm/polynomial-time-bounded-algorithm-for-minimum-vertex-cover.html" class="sidebar-link">polynomial-time bounded algorithm for Minimum Vertex Cover</a></li><li><a href="/algorithm/dynamic-time-warping.html" class="sidebar-link">Dynamic Time Warping</a></li><li><a href="/algorithm/fast-fourier-transform.html" class="sidebar-link">Fast Fourier Transform</a></li><li><a href="/algorithm/pseudocode.html" class="sidebar-link">Pseudocode</a></li><li><a href="/algorithm/contributors.html" class="sidebar-link">The Contributors</a></li></ul></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="travelling-salesman"><a href="#travelling-salesman" class="header-anchor">#</a> Travelling Salesman</h1> <h2 id="brute-force-algorithm"><a href="#brute-force-algorithm" class="header-anchor">#</a> Brute Force Algorithm</h2> <p>A path through every vertex exactly once is the same as ordering the vertex in some way. Thus, to calculate the minimum cost of travelling through every vertex exactly once, we can brute force every single one of the <code>N!</code> permutations of the numbers from <code>1</code> to <code>N</code>.</p> <p><strong>Psuedocode</strong></p> <div class="language-cpp extra-class"><pre class="language-cpp"><code>minimum <span class="token operator">=</span> INF
<span class="token keyword">for</span> all permutations P
current <span class="token operator">=</span> <span class="token number">0</span>
<span class="token keyword">for</span> i from <span class="token number">0</span> to N<span class="token operator">-</span><span class="token number">2</span>
current <span class="token operator">=</span> current <span class="token operator">+</span> cost<span class="token punctuation">[</span>P<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">[</span>P<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator"><</span><span class="token operator">-</span> Add the cost of going from <span class="token number">1</span> vertex to the next
current <span class="token operator">=</span> current <span class="token operator">+</span> cost<span class="token punctuation">[</span>P<span class="token punctuation">[</span>N<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">[</span>P<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator"><</span><span class="token operator">-</span> Add the cost of going from last vertex to the first
<span class="token keyword">if</span> current <span class="token operator"><</span> minimum <span class="token operator"><</span><span class="token operator">-</span> Update minimum <span class="token keyword">if</span> necessary
minimum <span class="token operator">=</span> current
output minimum
</code></pre></div><p><strong>Time Complexity</strong></p> <p>There are <code>N!</code> permutations to go through and the cost of each path is calculated in <code>O(N)</code>, thus this algorithm takes <code>O(N * N!)</code> time to output the exact answer.</p> <h2 id="dynamic-programming-algorithm"><a href="#dynamic-programming-algorithm" class="header-anchor">#</a> Dynamic Programming Algorithm</h2> <p>Notice that if we consider the path (in order):</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">7</span><span class="token punctuation">)</span>
</code></pre></div><p>and the path</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">7</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">)</span>
</code></pre></div><p>The cost of going from vertex <code>1</code> to vertex <code>2</code> to vertex <code>3</code> remains the same, so why must it be recalculated? This result can be saved for later use.</p> <p>Let <code>dp[bitmask][vertex]</code> represent the minimum cost of travelling through all the vertices whose corresponding bit in <code>bitmask</code> is set to <code>1</code> ending at <code>vertex</code>. For example:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code>dp<span class="token punctuation">[</span><span class="token number">12</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span>
<span class="token number">12</span> <span class="token operator">=</span> <span class="token number">1</span> <span class="token number">1</span> <span class="token number">0</span> <span class="token number">0</span>
<span class="token operator">^</span> <span class="token operator">^</span>
vertices<span class="token operator">:</span> <span class="token number">3</span> <span class="token number">2</span> <span class="token number">1</span> <span class="token number">0</span>
</code></pre></div><p>Since <code>12</code> represents <code>1100</code> in binary, <code>dp[12][2]</code> represents going through vertices <code>2</code> and <code>3</code> in the graph with the path ending at vertex 2.</p> <p>Thus we can have the following algorithm (C++ implementation):</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token keyword">int</span> cost<span class="token punctuation">[</span>N<span class="token punctuation">]</span><span class="token punctuation">[</span>N<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">//Adjust the value of N if needed</span>
<span class="token keyword">int</span> memo<span class="token punctuation">[</span><span class="token number">1</span> <span class="token operator"><<</span> N<span class="token punctuation">]</span><span class="token punctuation">[</span>N<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">//Set everything here to -1</span>
<span class="token keyword">int</span> <span class="token function">TSP</span><span class="token punctuation">(</span><span class="token keyword">int</span> bitmask<span class="token punctuation">,</span> <span class="token keyword">int</span> pos<span class="token punctuation">)</span><span class="token punctuation">{</span>
<span class="token keyword">int</span> cost <span class="token operator">=</span> INF<span class="token punctuation">;</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>bitmask <span class="token operator">==</span> <span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token number">1</span> <span class="token operator"><<</span> N<span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">{</span> <span class="token comment">//All vertices have been explored</span>
<span class="token keyword">return</span> cost<span class="token punctuation">[</span>pos<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">//Cost to go back</span>
<span class="token punctuation">}</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>memo<span class="token punctuation">[</span>bitmask<span class="token punctuation">]</span><span class="token punctuation">[</span>pos<span class="token punctuation">]</span> <span class="token operator">!=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">{</span> <span class="token comment">//If this has already been computed</span>
<span class="token keyword">return</span> memo<span class="token punctuation">[</span>bitmask<span class="token punctuation">]</span><span class="token punctuation">[</span>pos<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">//Just return the value, no need to recompute</span>
<span class="token punctuation">}</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> N<span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span><span class="token punctuation">{</span> <span class="token comment">//For every vertex </span>
<span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>bitmask <span class="token operator">&</span> <span class="token punctuation">(</span><span class="token number">1</span> <span class="token operator"><<</span> i<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">{</span> <span class="token comment">//If the vertex has not been visited</span>
cost <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>cost<span class="token punctuation">,</span><span class="token function">TSP</span><span class="token punctuation">(</span>bitmask <span class="token operator">|</span> <span class="token punctuation">(</span><span class="token number">1</span> <span class="token operator"><<</span> i<span class="token punctuation">)</span> <span class="token punctuation">,</span> i<span class="token punctuation">)</span> <span class="token operator">+</span> cost<span class="token punctuation">[</span>pos<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">//Visit the vertex</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
memo<span class="token punctuation">[</span>bitmask<span class="token punctuation">]</span><span class="token punctuation">[</span>pos<span class="token punctuation">]</span> <span class="token operator">=</span> cost<span class="token punctuation">;</span> <span class="token comment">//Save the result</span>
<span class="token keyword">return</span> cost<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token comment">//Call TSP(1,0)</span>
</code></pre></div><p>This line may be a little confusing, so lets go through it slowly:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code>cost <span class="token operator">=</span> <span class="token function">min</span><span class="token punctuation">(</span>cost<span class="token punctuation">,</span><span class="token function">TSP</span><span class="token punctuation">(</span>bitmask <span class="token operator">|</span> <span class="token punctuation">(</span><span class="token number">1</span> <span class="token operator"><<</span> i<span class="token punctuation">)</span> <span class="token punctuation">,</span> i<span class="token punctuation">)</span> <span class="token operator">+</span> cost<span class="token punctuation">[</span>pos<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
</code></pre></div><p>Here, <code>bitmask | (1 << i)</code> sets the ith bit of <code>bitmask</code> to 1, which represents that the ith vertex has been visited. The <code>i</code> after the comma represents the new <code>pos</code> in that function call, which represents the new "last" vertex. <code>cost[pos][i]</code> is to add the cost of travelling from vertex <code>pos</code> to vertex <code>i</code>.</p> <p>Thus, this line is to update the value of <code>cost</code> to the minimum possible value of travelling to every other vertex that has not been visited yet.</p> <p><strong>Time Complexity</strong></p> <p>The function <code>TSP(bitmask,pos)</code> has <code>2^N</code> values for <code>bitmask</code> and <code>N</code> values for <code>pos</code>. Each function takes <code>O(N)</code> time to run (the <code>for</code> loop). Thus this implementation takes <code>O(N^2 * 2^N)</code> time to output the exact answer.</p> <h4 id="remarks"><a href="#remarks" class="header-anchor">#</a> Remarks</h4> <p>The Travelling Salesman Problem is the problem of finding the minimum cost of travelling through <code>N</code> vertices exactly once per vertex. There is a cost <code>cost[i][j]</code> to travel from vertex <code>i</code> to vertex <code>j</code>.</p> <p>There are 2 types of algorithms to solve this problem:
<strong>Exact Algorithms</strong> and <strong>Approximation Algorithms</strong></p> <p><strong>Exact Algorithms</strong></p> <ol><li>Brute Force Algorithm</li> <li>Dynamic Programming Algorithm</li></ol> <p><strong>Approximation Algorithms</strong></p> <p>To be added</p></div> <footer class="page-edit"><div class="edit-link"><a href="https://github.com/devtut/generate/edit/master/docs/algorithm/travelling-salesman.md" target="_blank" rel="noopener noreferrer">Edit this page on GitHub</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <!----></footer> <div class="page-nav"><p class="inner"><span class="prev">
←
<a href="/algorithm/hash-functions.html" class="prev">
Hash Functions
</a></span> <span class="next"><a href="/algorithm/shortest-common-supersequence-problem.html">
Shortest Common Supersequence Problem
</a>
→
</span></p></div> </main></div><div class="global-ui"><!----></div></div>
<script src="/assets/js/app.1779e102.js" defer></script><script src="/assets/js/3.2cfa8016.js" defer></script><script src="/assets/js/75.7b814d35.js" defer></script>
</body>
</html>