taralino

Der Handlungsreisende

Das Problem des Handlungsreisenden (englisch Traveling Salesperson Problem oder kurz TSP) besteht darin, eine feste Anzahl von Orten jeweils genau einmal zu besuchen und anschließend zum Ausgangsort zurückzukehren. Dabei ist die Reihenfolge der besuchten Orte derart zu wählen, sodass die Wegstrecke bzw. Rundtour zu kurz wie möglich ist.

Die Abbildung zuvor veranschaulicht das Problem: Gegeben sind 24 Orte (blaue Punkte) und in Rot ist eine geeignete Rundtour dargestellt, die unter Verwendung eines genetischen Algorithmus bestimmt wurde.

Bevor wir uns mit weiteren Eigenschaften es Problems beschäftigen, kannst du zunächst in folgender Anwendung selber versuchen, eine optimale Rundtour zu finden.

Anwendung

Klicke auf die Punkte, um eine Rundtour zu definieren.

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <script src="taralino.js"></script>
</head>
<body>
<script>


var n = 16;

var T = [];
var x = [];
var s = [];



function distance(A, B) {
  return Math.sqrt((A[0]-B[0])*(A[0]-B[0]) + (A[1]-B[1])*(A[1]-B[1]));
};


function f(x) {
  var h = 0;
  var n = x.length;
  for (var k = 0; k < n; k++) h += distance(T[x[k]], T[x[(k+1)%n]]);
  return h;
};


function nearest(Z) {
  var i = -1;
  var h = 1e6;
  for (var k = 0; k < T.length; k++) if (T[k][2] == -1) {
    var t = distance(Z, T[k]);
    if (t < h) { h = t; i = k; };
  };
  return i;
};


function init() {
  T = [];
  x = [];
  s = [];
  while (T.length < n) {
    var p = [random(0,100), random(0,100), -1];
    var h = 1e6;
    for (var i = 0; i < T.length; i++) h = Math.min(h, distance(p, T[i]));
    if (h > 10) T.push(p);
  };
};


function draw() {
  Canvas.clear();

  for (var k = 0; k < s.length-1; k++) Canvas.line(T[s[k]][0], T[s[k]][1], T[s[k+1]][0], T[s[k+1]][1], {stroke:"red"});
  if (s.length == n) Canvas.line(T[s[k]][0], T[s[k]][1], T[s[0]][0], T[s[0]][1], {stroke:"red"});

  if (x.length == n) {
    for (var k = 0; k < T.length; k++) {
      var a = [T[x[k]][0], T[x[k]][1]];
      var b = [T[x[(k+1)%n]][0], T[x[(k+1)%n]][1]];
      var c = [b[0]-a[0], b[1]-a[1]];
      var d = Math.sqrt(c[0]*c[0]+c[1]*c[1]);
      c = [c[0]/d, c[1]/d];
      var h = 2;
      while (distance(a, b) > h) {
        Canvas.circle(a[0], a[1], 0.6, {fill:"yellow"});
        a = [a[0] + h*c[0], a[1] + h*c[1]];
      };
    };
  };

  if (s.length == n) {
    if (Math.abs(f(s)-f(x)) < 1e-3) {
      Canvas.circle(50, -18, 5, {fill:"yellow"});
      Canvas.text(50, -18, "=");
    } else {
      if (f(s) < f(x)) {
        Canvas.circle(25, -18, 16, {fill:"yellow"});
      } else {
        Canvas.circle(75, -18, 16, {fill:"yellow"});
      };
    };

    Canvas.text(25, -15, "Deine Tour:");
    Canvas.text(25, -21, f(s).toFixed(3));
    Canvas.text(75, -15, "Algorithmus:");
    Canvas.text(75, -21, f(x).toFixed(3));
  };

  for (var k = 0; k < T.length; k++) Canvas.circle(T[k][0], T[k][1], 1.8, {fill:"blue", stroke:(T[k][2] == -1 ? "none" : "red")});
};


function setup() {
  Canvas.init([-10,110], [-30,110], {background:"lightgrey", width:400});
  init();
  draw();
  Button.add("restart", "Neue Punkte");
  Button.add("retour", "Neue Tour");
};


function on_mouse_up(x, y) {
  var i = nearest([x,y]);
  if (i != -1) {
    s.push(i);
    T[i][2] = 0;
  };
  if (s.length == n) solve();
  draw();
};



function solve() {
  var options = {iterations:400, population:20, children:20, mutation_rate:0};
  x = GeneticAlgorithm.permutation(f, n, options);
  for (var k = 0; k < 10; k++) {
    var y = GeneticAlgorithm.permutation(f, n, options);
    if (f(y) < f(x)) x = y;
  };
  draw();
};


function on_click(id) {
  if (id == "restart") {
    init();
    draw();
  };
  if (id == "retour") {
    for (var k = 0; k < T.length; k++) T[k][2] = -1;
    x = [];
    s = [];
    draw();
  };
};


</script>
</body>
</html>

Vorschau Download Kopie speichern

Aufgabe

Kannst du das Problem des Handlungsreisenden besser lösen als der Algorithmus? Nutze die Anwendung zuvor, definiere eine Rundtour und vergleiche deine Tour mit der Lösung des Algorithmus. Führe dies mehrfach durch und protokolliere die Ergebnisse als Strichliste:

Eigenschaften des Problems

Angenommen, es sind Orte gegeben (wobei eine ganze Zahl ist). Als mathematisches Modell werden die Orte nun von 1 bis durchnummeriert und die Aufgabe besteht darin, eine Reihenfolge der Orte festzulegen, sodass die Rundtour möglichst kurz ist. Eine derartige Reihenfolge ist beispielsweise

bei einem Problem mit Orten (bzw. Punkten). Eine derartige (beliebige) Reihenfolge der Zahlen 1 bis wird auch als Permutation bezeichnet.

Obwohl das Problem zunächst sehr einfach klingt, ist es dennoch extrem komplex: Selbst bei nur neun Orten gibt es 20 160 unterschiedliche Rundtouren, von denen im Allgemeinen nur eine einzige tatsächlich die kürzeste ist. Bei 16 Orten gibt es bereits über 653 Milliarden mögliche Rundtouren.

Aufgrund dieser enormen Komplexität ist bis heute kein Verfahren bekannt, welches das Problem des Handlungsreisenden für eine beliebige Anzahl an Orten in einer vertretbaren Rechenzeit exakt löst (also tatsächlich die mit Sicherheit kürzeste Rundtour bestimmt). Selbst wenn eine Rundtour gegeben wird ist es nicht einmal möglich zu prüfen, ob es sich dabei um die kürzeste Rundtour handelt oder nicht.

Grundsätzlich ist man daher auf Näherungsverfahren angewiesen, auf sogenannte Heuristiken: Dies sind Verfahren, welche ein sehr komplexes Problem in vertretbarer Zeit näherungsweise lösen. Beim Problem des Handlungsreisenden bedeutet dies, dass auch in kurzer Zeit eine Rundtour gefunden werden kann, welche (möglicherweise) nicht am kürzesten ist, jedoch dennoch eine sehr gute Lösung darstellt.

In der Anwendung zuvor kam mit einem genetischen Verfahren eine spezielle Heuristiken zum Einsatz. Du hast daher sicher bereits erste Erfahrungen damit gesammelt, dass das Verfahren durchaus sehr gute Lösungen bestimmt hat.