📄 tsp.htm
字号:
<html>
<head>
<meta http-equiv=Content-Type content="text/html; charset=windows-1253">
<link rel=Edit-Time-Data href="./TSP_files/editdata.mso">
<link rel=OLE-Object-Data href="./TSP_files/oledata.mso">
<title>Analysis of TSP</title>
<style><!--
.Normal
{font-size:10.0pt;
font-family:Arial;}
.Normal2
{text-align:justify;
font-size:12.0pt;
font-family:Arial;}
-->
</style>
</head>
<body lang=EN-GB link=blue vlink=purple class="Normal" bgcolor="#ffffff">
<p class=Normal2 align=center style='text-align:center'><b><span lang=EN-US
style='font-size:14.0pt;'>TSP (TRAVELING SALESMAN PROBLEM)</span></b></p>
<p class=Normal2 align=center style='text-align:center'><b><span lang=EN-US>By
GrMikeD</span></b></p>
<p class=Normal2 align=center style='text-align:center'><b><span lang=EN-US>E-mail:
</span></b><b><span
lang=EL><a href="mailto:GrMikeD@usa.net"><span
lang=EN-US>GrMikeD@usa.net</span></a></span></b><b><span
lang=EN-US></span></b></p>
<p class=Normal2 align=center style='text-align:center'><b><span lang=EN-US>Web
Page: </span></b><b><span
lang=EL><a
href="http://students.ceid.upatras.gr/~miatidis"><span lang=EN-US>http://students.ceid.upatras.gr/~miatidis</span></a></span></b><b><span
lang=EN-US></span></b></p>
<p class=Normal2><b><span lang=EN-US>Introduction</span></b></p>
<p class=Normal2><span lang=EN-US>The TSP (Traveling Salesman Problem) is considered
as one of the most difficult to solve problems and belongs to the category of
the NP Complete problems. The situation it deals with is as follows:</span></p>
<p class=Normal2><span lang=EN-US>A salesman has to visit n cities, each one exactly
once. He starts from one of them (base city) and after visiting all the other,
he returns to his base. We know the transport cost between any two of the cities.
We want to find the optimal path for his visits. When we say the optimal we
mean the path with the lowest cost.</span></p>
<p class=Normal2><span lang=EN-US>This is a famous problem of the graph theory
where the vertices of the graph represent the cities and the nodes, represent
the paths between them. When there is no node connecting two vertices, it means
that there is no way to reach one city from the other. Here, we assume that
only one path can connect two cities and no more (the graph is simple).</span></p>
<p class=Normal2><span lang=EN-US>For this problem we have implemented two algorithms.
One is the <u>heuristic</u> and the other is the <u>exhaustive</u>. The heuristic
algorithm does not always give us the best solution but is very quick and low
costing. Contrary to the heuristic algorithm, the exhaustive always gives us
the best solution but is very slow and resource - consuming. For example if
we use 20 cities as input and run the exhaustive algorithm on the most powerful
and modern computing system, it will spend 770 centuries to give us the solution!
In practice, we find that for input n>=10, the algorithm is very slow. </span></p>
<p class=Normal2><b><span lang=EN-US>Analysis of the Heuristic Algorithm</span></b><b><span
lang=EN-US></span></b></p>
<p class=Normal2>This algorithm is based on the 揼reedy method⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -