-
-
Notifications
You must be signed in to change notification settings - Fork 1.4k
Expand file tree
/
Copy pathExamplesTSP.html
More file actions
336 lines (334 loc) · 27.8 KB
/
Copy pathExamplesTSP.html
File metadata and controls
336 lines (334 loc) · 27.8 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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
<!-- HTML header for doxygen 1.13.1-->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en-US">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=11"/>
<meta name="generator" content="Doxygen 1.13.1"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>Taskflow: A General-purpose Task-parallel Programming System: Travelling Salesman Problem</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<script type="text/javascript" src="clipboard.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="cookie.js"></script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
<link href="custom.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr id="projectrow">
<td id="projectlogo"><img alt="Logo" src="taskflow_logo.png"/></td>
<td id="projectalign">
<div id="projectname"><a href="https://github.com/taskflow/taskflow" style="color:inherit; text-decoration:none;">Taskflow: A General-purpose Task-parallel Programming System</a>
</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.13.1 -->
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
var searchBox = new SearchBox("searchBox", "search/",'.html');
/* @license-end */
</script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(function() { codefold.init(0); });
/* @license-end */
</script>
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(function() {
initMenu('',true,false,'search.php','Search',true);
$(function() { init_search(); });
});
/* @license-end */
</script>
<div id="main-nav"></div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
<div id="nav-tree">
<div id="nav-tree-contents">
<div id="nav-sync" class="sync"></div>
</div>
</div>
<div id="splitbar" style="-moz-user-select:none;"
class="ui-resizable-handle">
</div>
</div>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(function(){initNavTree('ExamplesTSP.html',''); initResizable(true); });
/* @license-end */
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>
<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<div id="MSearchResults">
<div class="SRPage">
<div id="SRIndex">
<div id="SRResults"></div>
<div class="SRStatus" id="Loading">Loading...</div>
<div class="SRStatus" id="Searching">Searching...</div>
<div class="SRStatus" id="NoMatches">No Matches</div>
</div>
</div>
</div>
</div>
<div><div class="header">
<div class="headertitle"><div class="title">Travelling Salesman Problem</div></div>
</div><!--header-->
<div class="contents">
<div class="toc"><h3>Table of Contents</h3>
<ul>
<li class="level1">
<a href="#TSPIntroduction">What is the Travelling Salesman Problem?</a>
</li>
<li class="level1">
<a href="#TSPWalkthrough">Concrete Walkthrough</a>
</li>
<li class="level1">
<a href="#TSPImplementation">Implementation</a>
</li>
<li class="level1">
<a href="#TSPDesignPoints">Design Points</a>
</li>
</ul>
</div>
<div class="textblock"><p>We implement a parallel branch-and-bound solver for the Travelling Salesman Problem (TSP) using <a class="el" href="classtf_1_1TaskGroup.html" title="class to create a task group from a task">tf::TaskGroup</a> for recursive task parallelism. This example demonstrates how a combinatorial search algorithm with a dynamically growing task tree maps naturally onto Taskflow's cooperative task group model.</p>
<h1><a class="anchor" id="TSPIntroduction"></a>
What is the Travelling Salesman Problem?</h1>
<p>The Travelling Salesman Problem asks: given a set of cities and the distance between every pair of cities, what is the shortest route that visits every city exactly once and returns to the starting city?</p>
<div class="image">
<img src="tsp_example.png" alt=""/>
</div>
<p>It is one of the most studied problems in computer science and operations research. Despite its simple statement, TSP is NP-hard: no known algorithm solves it in polynomial time for arbitrary inputs. The only way to guarantee an optimal solution is exhaustive search, which explores all possible tours. For <code>N</code> cities there are <code></code>(N-1)!/2 distinct tours, which grows astronomically: 10 cities have 181,440 tours, 15 cities have over 43 billion.</p>
<p>This is precisely why parallelism matters. Each branch of the search tree is independent of every other branch and can be explored on a separate CPU core simultaneously. Branch and bound makes the search tractable by pruning branches that cannot possibly improve the best solution found so far, but the remaining work is still substantial and benefits greatly from parallel execution.</p>
<h1><a class="anchor" id="TSPWalkthrough"></a>
Concrete Walkthrough</h1>
<p>Consider four cities A, B, C, D with the following symmetric distance matrix:</p>
<div class="fragment"><div class="line"> A B C D</div>
<div class="line">A [ 0 10 15 20 ]</div>
<div class="line">B [ 10 0 35 25 ]</div>
<div class="line">C [ 15 35 0 30 ]</div>
<div class="line">D [ 20 25 30 0 ]</div>
</div><!-- fragment --><p>Starting from city A, the algorithm builds partial tours by choosing which city to visit next at each step. At each node it computes a lower bound on the best possible completion of the current partial tour. If the lower bound is greater than or equal to the best complete tour found so far, the entire subtree rooted at that node is pruned — there is no point exploring it further. The lower bound used here is:</p>
<div class="fragment"><div class="line">lb = cost_so_far</div>
<div class="line"> + min outgoing edge from current city to any unvisited city</div>
<div class="line"> + sum of min outgoing edge from each remaining unvisited city</div>
</div><!-- fragment --><p>This is a valid lower bound because any completion of the tour must include at least one edge out of the current city and at least one edge incident to each unvisited city. The figure below shows the full search tree for this 4-city instance. Peach nodes are explored, red nodes are pruned (their lower bound already exceeds the best known cost), and the green node is the optimal tour:</p>
<div class="dotgraph">
<iframe scrolling="no" frameborder="0" src="dot_tsp_tree.svg" width="906" height="428"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
<p>The algorithm finds <code>A->B->C->D->A</code> with cost 95 first, then improves to <code>A->B->D->C->A</code> with cost 80 (the optimum). With <code>best_cost</code> equal to 80 established, all four remaining branches are pruned because their lower bounds of 80 or 95 cannot improve on 80. Only 5 of the 9 possible interior nodes are actually evaluated.</p>
<h1><a class="anchor" id="TSPImplementation"></a>
Implementation</h1>
<p>We represent the distance matrix as a flat vector and implement the branch-and-bound search as a recursive function. Each recursive call creates a <a class="el" href="classtf_1_1TaskGroup.html" title="class to create a task group from a task">tf::TaskGroup</a> to spawn one async task per unvisited city (the "include this city next" branch) while computing one branch directly on the current worker. After spawning, <code>tg.corun()</code> cooperatively waits for all spawned branches to complete without blocking the worker thread.</p>
<p>A global <code>std::atomic<int></code> tracks the best tour cost found so far. Any branch whose lower bound is at or above this value is pruned immediately by returning without spawning children. When a better complete tour is found, the atomic is updated with <code>compare_exchange_weak</code> so that all workers immediately see the tighter bound on their next pruning check.</p>
<div class="fragment"><div class="line"><span class="preprocessor">#include <taskflow/taskflow.hpp></span></div>
<div class="line"> </div>
<div class="line"><a class="code hl_class" href="classtf_1_1Executor.html">tf::Executor</a> executor;</div>
<div class="line"><span class="keyword">const</span> <span class="keywordtype">int</span> INF = std::numeric_limits<int>::max();</div>
<div class="line">std::atomic<int> best_cost{INF};</div>
<div class="line"> </div>
<div class="line"><span class="comment">// ── distance matrix (4 cities: A=0, B=1, C=2, D=3) ───────────────────────</span></div>
<div class="line"><span class="keyword">const</span> <span class="keywordtype">int</span> N = 4;</div>
<div class="line"><span class="keyword">const</span> <span class="keywordtype">int</span> dist[N][N] = {</div>
<div class="line"> { 0, 10, 15, 20 },</div>
<div class="line"> { 10, 0, 35, 25 },</div>
<div class="line"> { 15, 35, 0, 30 },</div>
<div class="line"> { 20, 25, 30, 0 },</div>
<div class="line">};</div>
<div class="line"> </div>
<div class="line"><span class="comment">// ── lower bound ──────────────────────────────────────────────────────────────</span></div>
<div class="line"><span class="comment">//</span></div>
<div class="line"><span class="comment">// The key insight: any valid completion of the partial tour must include</span></div>
<div class="line"><span class="comment">// at least one edge leaving the current city (to reach the next unvisited</span></div>
<div class="line"><span class="comment">// city) and at least one edge touching each remaining unvisited city</span></div>
<div class="line"><span class="comment">// (to enter or leave it).</span></div>
<div class="line"><span class="comment">//</span></div>
<div class="line"><span class="comment">// We do not know which edges those will be, but we know they cannot be</span></div>
<div class="line"><span class="comment">// shorter than the cheapest available option for each city.</span></div>
<div class="line"><span class="comment">// So the cheapest possible completion is at minimum:</span></div>
<div class="line"><span class="comment">//</span></div>
<div class="line"><span class="comment">// (1) the shortest edge from the current city to any unvisited city</span></div>
<div class="line"><span class="comment">// (2) for each unvisited city, its shortest outgoing edge to any other city</span></div>
<div class="line"><span class="comment">//</span></div>
<div class="line"><span class="comment">// Adding these minimum costs to the cost already spent gives a floor: the</span></div>
<div class="line"><span class="comment">// final tour cannot possibly cost less than this bound, regardless of how</span></div>
<div class="line"><span class="comment">// the remaining cities are visited.</span></div>
<div class="line"><span class="comment">// If this floor already meets or exceeds the best complete tour found so</span></div>
<div class="line"><span class="comment">// far, the entire subtree can be pruned safely.</span></div>
<div class="line"><span class="comment">//</span></div>
<div class="line"><span class="comment">// Example: at partial tour A->C (cost=15) with best_cost=80:</span></div>
<div class="line"><span class="comment">// (1) min edge from C to unvisited {B,D}: min(35,30) = 30</span></div>
<div class="line"><span class="comment">// (2) min edge from B to anywhere: min(10,35,25) = 10</span></div>
<div class="line"><span class="comment">// min edge from D to anywhere: min(20,25,30) = 20</span></div>
<div class="line"><span class="comment">// lb = 15 + 30 + 10 + 20 = 75 < 80 => not pruned yet</span></div>
<div class="line"><span class="comment">//</span></div>
<div class="line"><span class="comment">// Later at A->C->B (cost=50):</span></div>
<div class="line"><span class="comment">// (1) min edge from B to unvisited {D}: 25</span></div>
<div class="line"><span class="comment">// (2) min edge from D to anywhere: 20</span></div>
<div class="line"><span class="comment">// lb = 50 + 25 + 20 = 95 >= 80 => PRUNED</span></div>
<div class="line"><span class="comment">//</span></div>
<div class="line"><span class="keywordtype">int</span> lower_bound(<span class="keywordtype">int</span> current, <span class="keyword">const</span> std::vector<bool>& visited, <span class="keywordtype">int</span> cost_so_far) {</div>
<div class="line"> <span class="keywordtype">int</span> bound = cost_so_far;</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// (1) cheapest edge we can take out of the current city</span></div>
<div class="line"> <span class="comment">// to reach any city we have not yet visited</span></div>
<div class="line"> <span class="keywordtype">int</span> min_curr = INF;</div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keywordtype">int</span> v = 0; v < N; v++) {</div>
<div class="line"> <span class="keywordflow">if</span>(!visited[v]) min_curr = std::min(min_curr, dist[current][v]);</div>
<div class="line"> }</div>
<div class="line"> <span class="keywordflow">if</span>(min_curr == INF) <span class="keywordflow">return</span> bound; <span class="comment">// no unvisited cities: tour is complete</span></div>
<div class="line"> bound += min_curr;</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// (2) for each unvisited city, add the cost of its cheapest outgoing edge</span></div>
<div class="line"> <span class="comment">// to any other city (visited or not, as long as it is not the city itself).</span></div>
<div class="line"> <span class="comment">// This accounts for the fact that we must enter or leave each unvisited city</span></div>
<div class="line"> <span class="comment">// at some point, and the cheapest way to do so is via its minimum edge.</span></div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keywordtype">int</span> u = 0; u < N; u++) {</div>
<div class="line"> <span class="keywordflow">if</span>(visited[u]) <span class="keywordflow">continue</span>;</div>
<div class="line"> <span class="keywordtype">int</span> min_u = INF;</div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keywordtype">int</span> v = 0; v < N; v++) {</div>
<div class="line"> <span class="keywordflow">if</span>(v != u) min_u = std::min(min_u, dist[u][v]);</div>
<div class="line"> }</div>
<div class="line"> bound += min_u;</div>
<div class="line"> }</div>
<div class="line"> <span class="keywordflow">return</span> bound;</div>
<div class="line">}</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">void</span> branch_and_bound(</div>
<div class="line"> <span class="keywordtype">int</span> current,</div>
<div class="line"> std::vector<bool> visited,</div>
<div class="line"> <span class="keywordtype">int</span> cost_so_far,</div>
<div class="line"> <span class="keywordtype">int</span> depth</div>
<div class="line">) {</div>
<div class="line"> <span class="comment">// compute a lower bound on the best possible tour through this node.</span></div>
<div class="line"> <span class="comment">// if the bound already meets or exceeds the best complete tour found so</span></div>
<div class="line"> <span class="comment">// far by any worker, this entire subtree cannot improve on the best known</span></div>
<div class="line"> <span class="comment">// solution and can be safely discarded.</span></div>
<div class="line"> <span class="keywordtype">int</span> lb = lower_bound(current, visited, cost_so_far);</div>
<div class="line"> <span class="keywordflow">if</span>(lb >= best_cost.load(std::memory_order_relaxed)) <span class="keywordflow">return</span>;</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// all N cities have been visited: close the tour by returning to city 0.</span></div>
<div class="line"> <span class="comment">// try to update best_cost if this tour is cheaper than any found so far.</span></div>
<div class="line"> <span class="comment">// compare_exchange_weak retries if another worker concurrently updates</span></div>
<div class="line"> <span class="comment">// best_cost, ensuring only the true minimum is stored.</span></div>
<div class="line"> <span class="keywordflow">if</span>(depth == N) {</div>
<div class="line"> <span class="keywordtype">int</span> total = cost_so_far + dist[current][0];</div>
<div class="line"> <span class="keywordtype">int</span> cur = best_cost.load(std::memory_order_relaxed);</div>
<div class="line"> <span class="keywordflow">while</span>(total < cur &&</div>
<div class="line"> !best_cost.compare_exchange_weak(cur, total,</div>
<div class="line"> std::memory_order_relaxed, </div>
<div class="line"> std::memory_order_relaxed));</div>
<div class="line"> <span class="keywordflow">return</span>;</div>
<div class="line"> }</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// create a task group for parallel branching.</span></div>
<div class="line"> <span class="comment">// task_group() is valid here because this function always runs inside a</span></div>
<div class="line"> <span class="comment">// worker thread of the executor (either the root executor.async task or</span></div>
<div class="line"> <span class="comment">// a tg.silent_async task spawned by a parent call).</span></div>
<div class="line"> <span class="keyword">auto</span> tg = executor.<a class="code hl_function" href="classtf_1_1Executor.html#a8858a119b9ad697748293c4bb1408853">task_group</a>();</div>
<div class="line"> </div>
<div class="line"> <span class="keywordtype">bool</span> first = <span class="keyword">true</span>;</div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keywordtype">int</span> v = 0; v < N; v++) {</div>
<div class="line"> <span class="keywordflow">if</span>(visited[v]) <span class="keywordflow">continue</span>;</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// prepare the state for the branch where we visit city v next</span></div>
<div class="line"> std::vector<bool> new_visited = visited;</div>
<div class="line"> new_visited[v] = <span class="keyword">true</span>;</div>
<div class="line"> <span class="keywordtype">int</span> new_cost = cost_so_far + dist[current][v];</div>
<div class="line"> </div>
<div class="line"> <span class="keywordflow">if</span>(first) {</div>
<div class="line"> <span class="comment">// run the first unvisited branch directly on the current worker.</span></div>
<div class="line"> <span class="comment">// this avoids task creation overhead for at least one branch per node</span></div>
<div class="line"> <span class="comment">// and keeps the current worker busy without yielding to the scheduler.</span></div>
<div class="line"> first = <span class="keyword">false</span>;</div>
<div class="line"> branch_and_bound(v, new_visited, new_cost, depth + 1);</div>
<div class="line"> }</div>
<div class="line"> <span class="keywordflow">else</span> {</div>
<div class="line"> <span class="comment">// spawn the remaining branches as independent async tasks in the group.</span></div>
<div class="line"> <span class="comment">// each task explores a different city as the next stop in the tour.</span></div>
<div class="line"> <span class="comment">// all spawned tasks share the same best_cost atomic, so a good solution</span></div>
<div class="line"> <span class="comment">// found in any branch immediately tightens the pruning bound for all others.</span></div>
<div class="line"> tg.silent_async([=]() {</div>
<div class="line"> branch_and_bound(v, new_visited, new_cost, depth + 1);</div>
<div class="line"> });</div>
<div class="line"> }</div>
<div class="line"> }</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// cooperatively wait for all spawned branches to finish.</span></div>
<div class="line"> <span class="comment">// corun() does not block the worker thread: it re-enters the executor's</span></div>
<div class="line"> <span class="comment">// work-stealing loop, executing other pending tasks while waiting.</span></div>
<div class="line"> <span class="comment">// this prevents worker starvation and avoids deadlock in deep recursion.</span></div>
<div class="line"> tg.<a class="code hl_function" href="classtf_1_1TaskGroup.html#a1f481dc466e3107a08346d1a124677bc">corun</a>();</div>
<div class="line">}</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main() {</div>
<div class="line"> </div>
<div class="line"> std::vector<bool> visited(N, <span class="keyword">false</span>);</div>
<div class="line"> visited[0] = <span class="keyword">true</span>; <span class="comment">// start from city A (index 0)</span></div>
<div class="line"> </div>
<div class="line"> <span class="comment">// the root call must run inside a worker so that task_group() is valid</span></div>
<div class="line"> executor.<a class="code hl_function" href="classtf_1_1Executor.html#af960048056f7c6b5bc71f4f526f05df7">async</a>([&]() {</div>
<div class="line"> branch_and_bound(0, visited, 0, 1);</div>
<div class="line"> }).get();</div>
<div class="line"> </div>
<div class="line"> <span class="keyword">const</span> <span class="keywordtype">char</span>* names[] = {<span class="stringliteral">"A"</span>, <span class="stringliteral">"B"</span>, <span class="stringliteral">"C"</span>, <span class="stringliteral">"D"</span>};</div>
<div class="line"> printf(<span class="stringliteral">"Optimal tour cost: %d\n"</span>, best_cost.load());</div>
<div class="line"> </div>
<div class="line"> <span class="keywordflow">return</span> 0;</div>
<div class="line">}</div>
<div class="ttc" id="aclasstf_1_1Executor_html"><div class="ttname"><a href="classtf_1_1Executor.html">tf::Executor</a></div><div class="ttdoc">class to create an executor</div><div class="ttdef"><b>Definition</b> executor.hpp:62</div></div>
<div class="ttc" id="aclasstf_1_1Executor_html_a8858a119b9ad697748293c4bb1408853"><div class="ttname"><a href="classtf_1_1Executor.html#a8858a119b9ad697748293c4bb1408853">tf::Executor::task_group</a></div><div class="ttdeci">TaskGroup task_group()</div><div class="ttdoc">creates a task group that executes a collection of asynchronous tasks</div><div class="ttdef"><b>Definition</b> task_group.hpp:875</div></div>
<div class="ttc" id="aclasstf_1_1Executor_html_af960048056f7c6b5bc71f4f526f05df7"><div class="ttname"><a href="classtf_1_1Executor.html#af960048056f7c6b5bc71f4f526f05df7">tf::Executor::async</a></div><div class="ttdeci">auto async(P &&params, F &&func)</div><div class="ttdoc">creates a parameterized asynchronous task to run the given function</div></div>
<div class="ttc" id="aclasstf_1_1TaskGroup_html_a1f481dc466e3107a08346d1a124677bc"><div class="ttname"><a href="classtf_1_1TaskGroup.html#a1f481dc466e3107a08346d1a124677bc">tf::TaskGroup::corun</a></div><div class="ttdeci">void corun()</div><div class="ttdoc">corun all tasks spawned by this task group with other workers</div><div class="ttdef"><b>Definition</b> task_group.hpp:725</div></div>
</div><!-- fragment --><p>The program output is:</p>
<div class="fragment"><div class="line">Optimal tour cost: 80</div>
</div><!-- fragment --><p>which corresponds to the tour <code>A->B->D->C->A</code>.</p>
<h1><a class="anchor" id="TSPDesignPoints"></a>
Design Points</h1>
<p>There are a few important design points worth noting for this example, which also apply generally to parallel search algorithms:</p>
<ul>
<li>TaskGroup per recursive call: Each invocation of <code>branch_and_bound</code> creates its own <code>tg</code> via <code>executor.task_group()</code>. This is valid because every invocation runs inside a worker thread of the executor — either as the root <code>executor.async</code> task or as a <code>tg.silent_async</code> task spawned by a parent invocation. Attempting to call <code>executor.task_group()</code> from outside a worker thread throws an exception.</li>
<li>First branch on the current worker: Rather than spawning all branches as async tasks, the first unvisited city is explored directly on the current worker. This avoids task creation overhead for at least one branch per node and keeps the worker busy without yielding back to the scheduler. The remaining branches are spawned via <code>tg.silent_async</code>.</li>
<li>Atomic <code>best_cost</code> for pruning: All workers share a single <code>std::atomic<int></code> <code>best_cost</code>. When any worker finds a better complete tour, it updates <code>best_cost</code> with <code>compare_exchange_weak</code> so that all other workers immediately see the tighter bound on their next pruning check. This is the key mechanism that makes parallel branch and bound more efficient than running independent serial searches: workers continuously share information about the best solution found so far, tightening the pruning bound for the entire parallel search.</li>
<li>Cooperative execution via corun: <code>tg.corun()</code> does not block the calling worker thread. Instead, the worker participates in the executor's work-stealing loop, executing other tasks while waiting for its spawned branches to complete. This prevents worker starvation when the search tree is deep and avoids the deadlock that would result from a blocking wait inside an executor worker.</li>
</ul>
<dl class="section note"><dt>Note</dt><dd>For larger instances, the <code>visited</code> vector copy on each recursive call becomes a bottleneck. A bitmask (<code>uint32_t</code> or <code>uint64_t</code>) is more efficient for up to 32 or 64 cities respectively. For production TSP solvers, more sophisticated bounding functions such as the Held-Karp lower bound or minimum spanning tree bound deliver much tighter pruning and dramatically reduce the search tree size. </dd></dl>
</div></div><!-- contents -->
</div><!-- PageDoc -->
</div><!-- doc-content -->
<!-- HTML footer for doxygen 1.13.1-->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
<ul>
<li class="navelem"><a class="el" href="Examples.html">Learning from Examples</a></li>
<li class="footer">
Maintained by <a href="https://tsung-wei-huang.github.io/">Dr. Tsung-Wei Huang</a>
—
Generated by <a href="https://www.doxygen.org/index.html"><img class="footer" src="doxygen.svg" width="104" height="31" alt="doxygen"/></a> 1.13.1
</li>
</ul>
</div>