-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathtravling-salesman-trolley-problem.html
More file actions
308 lines (275 loc) · 21.3 KB
/
travling-salesman-trolley-problem.html
File metadata and controls
308 lines (275 loc) · 21.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
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
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<!-- 2022-W11-4 02:12 -->
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>A Possibly Correct Solution to the Travling Salseman Trolly Problem</title>
<meta name="author" content="Inanna" />
<meta name="description" content="Backtracking and travling salseman with linear programming." />
<meta name="generator" content="Org Mode" />
<link href="/site.css" rel="stylesheet" type="text/css" /><link href="images/website-icon.png" rel="icon" />
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
displayAlign: "center",
displayIndent: "0em",
"HTML-CSS": { scale: 100,
linebreaks: { automatic: "false" },
webFont: "TeX"
},
SVG: {scale: 100,
linebreaks: { automatic: "false" },
font: "TeX"},
NativeMML: {scale: 100},
TeX: { equationNumbers: {autoNumber: "AMS"},
MultLineWidth: "85%",
TagSide: "right",
TagIndent: ".8em"
}
});
</script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS_HTML"></script>
</head>
<body>
<div id="preamble" class="status">
<div><a href="/index.html"><img alt="An abstract logo representing a series of three assembly line stamping machines with the words CONS, DEV, and embalzoned in white on each machine." id="site-logo" src="/images/website-logo.png" /></a></div>
</div>
<div id="content" class="content">
<h1 class="title">A Possibly Correct Solution to the Travling Salseman Trolly Problem</h1>
<div id="table-of-contents" role="doc-toc">
<h2>Table of Contents</h2>
<div id="text-table-of-contents" role="doc-toc">
<ul>
<li><a href="#org22c4dcd">Introduction</a></li>
<li><a href="#org6b30d69">Algorithm Description</a></li>
<li><a href="#org66e610a">Implementation</a>
<ul>
<li><a href="#org47311bd">Defining the Graph</a></li>
<li><a href="#orge504c99">Traversing the Graph</a>
<ul>
<li><a href="#org382239d">Edge Less Than</a></li>
</ul>
</li>
</ul>
</li>
</ul>
</div>
</div>
<div id="outline-container-org22c4dcd" class="outline-2">
<h2 id="org22c4dcd">Introduction</h2>
<div class="outline-text-2" id="text-org22c4dcd">
<p>
While on discord I saw this meme.
</p>
<div id="orgb217042" class="figure">
<p><img src="images/travling-salesman-trolley-problem.png" alt="travling-salesman-trolley-problem.png" />
</p>
</div>
<p>
I decided to write an optimal solution for it because I was bored. I also decided to add this to my website because why not. I have yet to formally prove that it actually works, and I probably should do that, but it seems that it should in fact work just fine. Basically I take the problem to be finding the optimal route through the graph with free backtracking.
</p>
</div>
</div>
<div id="outline-container-org6b30d69" class="outline-2">
<h2 id="org6b30d69">Algorithm Description</h2>
<div class="outline-text-2" id="text-org6b30d69">
<p>
In the case of an undirected graph you first consider a node, obtain the weights of the edges going from it and sort them in a list. Then you traverse along the lowest weighted edge in your list. Once you have reached this new edge you discard the previous edge, get the new edges, discard any edges that go to a visited node in both of your lists, sort them, and then merge them. You then proceed to again choose the lowest weighted edge from your list and visit the node that goes through that edge. You continue this until all nodes have been visited
</p>
<p>
So long as the graph is not fully connected I the time complexity should tend towards \(O(n\ log(n))\), should it be more fully connected I think the time complexity will be more similar to \(O(n^2)\) for the optimal solution.
</p>
<p>
The proof is trivial and left as an exercise to the reader.<label class="sidenote-number" for="1"><sup>1</sup></label><input checked="checked" id="1" style="display:none" type="checkbox" /><span class="sidenote"><span class="sidenote-number"> 1</span> I am lazy. I might prove it eventually. Please talk to me later</span>
</p>
</div>
</div>
<div id="outline-container-org66e610a" class="outline-2">
<h2 id="org66e610a">Implementation</h2>
<div class="outline-text-2" id="text-org66e610a">
<p>
So to accompany the above description let's have a quick implementation in Clojure.
</p>
</div>
<div id="outline-container-org47311bd" class="outline-3">
<h3 id="org47311bd">Defining the Graph</h3>
<div class="outline-text-3" id="text-org47311bd">
<p>
So to start I use the graph I defined in my <a href="impl-graphs.html#ID-7f4d867c-294d-460d-915b-5363b945662d">implementing graphs</a> tutorial and define the graph using it. So we just import it from the shared library I have in the public section of my wiki.
</p>
<div class="org-src-container">
<pre class="src src-clojure"><span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">ns</span> <span style="color: #E53935;">tstp</span>
<span style="color: #bbb;">(</span><span style="color: #E53935;">:require</span> mylibs.graphs <span style="color: #E53935;">:refer</span> <span style="color: #494949;">[</span>graph edge dot-repr<span style="color: #494949;">]</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
</pre>
</div>
<p>
But before we define the graph we must first look at the problem itself and come up with a series of names for the nodes so that a graph can be made for it.
</p>
<div id="org981097c" class="figure">
<p><img src="images/travling-salesman-trolley-problem-numbered.png" alt="travling-salesman-trolley-problem-numbered.png" />
</p>
</div>
<p>
Below is the code that implements it. As you can see, it's actually pretty long.
</p>
<div class="org-src-container">
<pre class="src src-clojure" id="org668217a"><span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">def</span> <span style="font-style: italic;">tstp-graph</span>
<span style="color: #bbb;">(</span><span style="color: #E53935; font-style: italic;">-></span> <span style="color: #494949;">(</span>apply graph <span style="color: #bbb;">(</span>range 29<span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">0</span>
<span style="color: #494949;">(</span>edge 0 1 10<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>edge 0 6 15<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">1</span>
<span style="color: #494949;">(</span>edge 1 2 6<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">2</span>
<span style="color: #494949;">(</span>edge 2 3 1<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>edge 2 8 1<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>edge 2 7 10<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">3</span>
<span style="color: #494949;">(</span>edge 3 4 1<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">4</span>
<span style="color: #494949;">(</span>edge 4 5 0<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>edge 4 10 1<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">5</span>
<span style="color: #494949;">(</span>edge 5 11 0<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">6</span>
<span style="color: #494949;">(</span>edge 6 7 1<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>edge 6 12 5<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">7</span>
<span style="color: #494949;">(</span>edge 7 8 10<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>edge 7 14 10<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>edge 7 13 1<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">8</span>
<span style="color: #494949;">(</span>edge 8 9 5<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>edge 8 14 1<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>edge 8 15 10<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">9</span>
<span style="color: #494949;">(</span>edge 9 10 0<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>edge 9 17 1<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">10</span>
<span style="color: #494949;">(</span>edge 10 11 1<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">11</span>
<span style="color: #494949;">(</span>edge 11 18 5<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">12</span>
<span style="color: #494949;">(</span>edge 12 13 2<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>edge 12 26 5<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>edge 12 28 1<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">13</span>
<span style="color: #494949;">(</span>edge 13 24 10<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">14</span>
<span style="color: #494949;">(</span>edge 14 24 1<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">15</span>
<span style="color: #494949;">(</span>edge 15 16 1<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>edge 15 21 1<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>edge 15 22 4<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">16</span>
<span style="color: #494949;">(</span>edge 16 17 1<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>edge 16 20 5<span style="color: #494949;">)</span>
<span style="color: #494949;">(</span>edge 16 21 5<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">17</span>
<span style="color: #494949;">(</span>edge 17 18 0<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">18</span>
<span style="color: #494949;">(</span>edge 18 19 5<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">19</span>
<span style="color: #494949;">(</span>edge 19 20 0<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">20</span>
<span style="color: #494949;">(</span>edge 20 21 1<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">22</span>
<span style="color: #494949;">(</span>edge 22 23 1<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">23</span>
<span style="color: #494949;">(</span>edge 23 24 5<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">24</span>
<span style="color: #494949;">(</span>edge 24 25 0<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">25</span>
<span style="color: #494949;">(</span>edge 25 26 0<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">26</span>
<span style="color: #494949;">(</span>edge 26 27 1<span style="color: #494949;">)</span>
<span style="color: #a4a4a4; font-style: italic;">;; </span><span style="color: #a4a4a4; font-style: italic;">27</span>
<span style="color: #494949;">(</span>edge 27 28 1<span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
</pre>
</div>
<p>
Using our DOT code we can also check that our graph is correct visually by obtaining the DOT representation (plus the DOT representation is prettier and more clear than the previous one).
</p>
<div class="org-src-container">
<pre class="src src-clojure" id="org6c7277c"><span style="color: #494949;">(</span>dot-repr tstp-graph<span style="color: #494949;">)</span>
</pre>
</div>
<div id="orgf2d6ecb" class="figure">
<p><img src="./images/graph_39d0b492-a701-4d8d-a7de-d854f3eda883.png" alt="graph_39d0b492-a701-4d8d-a7de-d854f3eda883.png" />
</p>
</div>
<p>
It doesn't look exactly like the original, but honestly that doesn't matter, it contains all the nodes of the original.
</p>
<p>
Given how <i>nice</i> it was to just get a DOT representation of a clojure datastructure I think I might end up writing some code to automatically spit out DOT code for various Clojure objects. I think it will, by default, probably just spit out DOT code, but it will also allow you to define custom handling code for different datastructures.
</p>
</div>
</div>
<div id="outline-container-orge504c99" class="outline-3">
<h3 id="orge504c99">Traversing the Graph</h3>
<div class="outline-text-3" id="text-orge504c99">
<p>
So next we create some functions to traverse this graph and implement our algorithm. First we want an algorithm that, given some set of nodes, will then return the least weighted edge of the set of nodes. Secondarily we want.
</p>
</div>
<div id="outline-container-org382239d" class="outline-4">
<h4 id="org382239d">Edge Less Than</h4>
<div class="outline-text-4" id="text-org382239d">
<p>
So first we want to have a predicate that compares the edges and returns true should the first edge be less than the second, which will be fed into our mergesort function.
</p>
<div class="org-src-container">
<pre class="src src-clojure"><span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">defn</span> <span style="font-weight: bold; font-style: italic;">edge-less-than?</span> a b<span style="color: #494949;">)</span>
</pre>
</div>
<p>
We then we want to create a predicate that compares the weight of two edges, returning.
</p>
<div class="org-src-container">
<pre class="src src-clojure"><span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">defn</span> <span style="font-weight: bold; font-style: italic;">merge</span>
<span style="color: #bbb;">(</span><span style="color: #494949;">[</span>left right<span style="color: #494949;">]</span> <span style="color: #494949;">(</span>merge < left right<span style="color: #494949;">)</span><span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span><span style="color: #494949;">[</span>comp <span style="color: #bbb;">[</span>left-head & left-rest <span style="color: #E53935;">:as</span> left<span style="color: #bbb;">]</span> <span style="color: #bbb;">[</span>right-head & right-rest <span style="color: #E53935;">:as</span> right<span style="color: #bbb;">]</span><span style="color: #494949;">]</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">cond</span> <span style="color: #bbb;">(</span>nil? right-head<span style="color: #bbb;">)</span> left
<span style="color: #bbb;">(</span>nil? left-head<span style="color: #bbb;">)</span> right
<span style="color: #bbb;">(</span>comp left-head right-head<span style="color: #bbb;">)</span> <span style="color: #bbb;">(</span>cons left-head <span style="color: #494949;">(</span>merge left-rest right<span style="color: #494949;">)</span><span style="color: #bbb;">)</span>
<span style="color: #E53935;">:else</span> <span style="color: #bbb;">(</span>cons right-head <span style="color: #494949;">(</span>merge left right-rest<span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">defn</span> <span style="font-weight: bold; font-style: italic;">mergesort</span>
<span style="color: #bbb;">(</span><span style="color: #494949;">[</span>coll<span style="color: #494949;">]</span> <span style="color: #494949;">(</span>mergesort < coll<span style="color: #494949;">)</span><span style="color: #bbb;">)</span>
<span style="color: #bbb;">(</span><span style="color: #494949;">[</span>comp coll<span style="color: #494949;">]</span>
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">let</span> <span style="color: #bbb;">[</span>left <span style="color: #494949;">(</span>take <span style="color: #bbb;">(</span>/ <span style="color: #494949;">(</span>count coll<span style="color: #494949;">)</span> 2<span style="color: #bbb;">)</span> coll<span style="color: #494949;">)</span>
right <span style="color: #494949;">(</span>drop <span style="color: #bbb;">(</span>count left<span style="color: #bbb;">)</span> coll<span style="color: #494949;">)</span><span style="color: #bbb;">]</span>
<span style="color: #bbb;">(</span>apply merge comp
<span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">if</span> <span style="color: #bbb;">(</span>> <span style="color: #494949;">(</span>count coll<span style="color: #494949;">)</span> 2<span style="color: #bbb;">)</span>
<span style="color: #bbb;">[</span><span style="color: #494949;">(</span>mergesort left<span style="color: #494949;">)</span> <span style="color: #494949;">(</span>mergesort right<span style="color: #494949;">)</span><span style="color: #bbb;">]</span>
<span style="color: #bbb;">[</span>left right<span style="color: #bbb;">]</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span><span style="color: #bbb;">)</span><span style="color: #494949;">)</span>
</pre>
</div>
<div class="org-src-container">
<pre class="src src-clojure"><span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">defn</span> <span style="font-weight: bold; font-style: italic;">sort-edges</span><span style="color: #494949;">)</span>
</pre>
</div>
<p>
We also want a function to merge the edges from each new node onto this list of edges sorted by weight, using the same function from our <a href="impl-mergesort.html#ID-b5540a6b-30a3-46b2-99f2-bffe4080f1b3">merge sort</a> tutorial.
</p>
<div class="org-src-container">
<pre class="src src-clojure"><span style="color: #494949;">(</span><span style="color: #E53935; font-style: italic;">defn</span> <span style="font-weight: bold; font-style: italic;">merge-edges</span><span style="color: #494949;">)</span>
</pre>
</div>
<p>
As we can see
</p>
</div>
</div>
</div>
</div>
<!-- Footnotes --><!--
<div class="footdef"><sup><a id="fn.1" class="footnum" href="#fnr.1" role="doc-backlink">1</a></sup> <div class="footpara" role="doc-footnote"><p class="footpara">I am lazy. I might prove it eventually. Please talk to me later</p></div></div>
--></div>
<div id="postamble" class="status">
<p class="date">Last Modified: 2022-W01-5 11:16</p><p class="creator">Generated Using: <a href="https://www.gnu.org/software/emacs/">Emacs</a> 27.2 (<a href="https://orgmode.org">Org</a> mode 9.4.6)</p><p class="license">Except where otherwise noted content on <a href="https://cons.dev">cons.dev</a> is licensed under a <a href="https://creativecommons.org/licenses/by-sa/4.0/" rel="license">Creative Commons Attribution-ShareAlike 4.0 International License</a>.</p>
</div>
</body>
</html>