taramath: Problem des Handlungsreisenden

Beispiel

Im folgenden Beispiel lösen wir das Problem des Handlungsreisenden mit Orten, welche zufällig in der Ebene verteilt werden. Anschließend wird das Ergebnis graphisch dargestellt.

Tipp: Verändere die Anzahl der Orte. Dabei ist darauf zu achten, dass die Laufzeit zur Lösung des Problems exponentiell in wächst. Bereits für Probleme mit etwa kann die Rechenzeit unangenehm groß sein.

<!DOCTYPE html>
<html>

<head>
  <script src="taramath.js"></script>
</head>

<body>

<div id="plot"></div>

<script>

////////////////////////////////////
//          Eingabedaten          //
////////////////////////////////////

  // Anzahl Orte
  var m = 7;

  // Orte zufaellig verteilen
  var P = new Array(m);
  for (var i = 0; i < m; i++) {
    P[i] = [10+Math.round(80*Math.random()), 10+Math.round(80*Math.random())];
  };


////////////////////////////////////
//        Hilfsfunktionen         //
////////////////////////////////////

  // Euklidischer Abstand zwischen zwei Punkten
  function distance (A, B) {
    return Math.sqrt((A[0]-B[0])*(A[0]-B[0]) + (A[1]-B[1])*(A[1]-B[1]));
  };


  // Die Funktion findet die Subtour beginnend mit Knoten 0.
  function find_subtour (x, m) {
    var n = x.length;
    // Tabelle T aufstellen
    var T = new Array(m);
    for (var i = 0; i < m; i++) T[i] = [];
    var j = 0;
    for (var k = 0; k < m-1; k++) for (var s = k+1; s < m; s++) {
      if (x[j] == 1) { T[s].push(k); T[k].push(s); }
      j++;
    };
    // Subtour unter Verwendung von T berechnen
    var C = [0, T[0][0]];
    var prev = C[0];
    var next = C[1];
    while (next != 0) {
      if (T[next][0] != prev) {
        prev = next;
        next = T[next][0];
        C.push(next);
      } else if (T[next][1] != prev) {
        prev = next;
        next = T[next][1];
        C.push(next);
      };
    };
    // Ergebnis ausgeben
    return C;
  };


  // Die Funktion generiert Nebenbedingung zur Subtour C.
  function subtour_constraint (C, n) {
    var a = new Array(n);
    for (var j = 0; j < n; j++) a[j] = 0;
    for (var u = 0; u < C.length-1; u++) {
      var imin = Math.min(C[u],C[u+1]);
      var imax = Math.max(C[u],C[u+1]);
      var j = 0;
      for (var k = 0; k < m-1; k++) for (var s = k+1; s < m; s++) {
        if ((k == imin) && (s == imax)) a[j] = 1;
        j++;
      };
    };
    return a;
  };


  // Darstellung der Loesung
  function plot_result (id, x) {
    Svg.init(id, 320, 320);
    Svg.resize(-5, 105, -5, 105);
    Svg.clear("#f0f0f0");
    var j = 0;
    for (var k = 0; k < m-1; k++) for (var s = k+1; s < m; s++) {
      if (x[j] == 1) Svg.line(P[k][0], P[k][1], P[s][0], P[s][1], "#999999");
      j++;
    };
    for (var i = 0; i < m; i++) Svg.disc(P[i][0], P[i][1], 1.2, "#0000ff");
    Svg.draw();
  };


////////////////////////////////////
//         Problem loesen         //
////////////////////////////////////

  // Aufstellen des ganzzahligen Programms (ohne Subtour-Constraints)
  var n = Math.round((m-1)*m/2);
  var c = new Array(n);
  var j = 0;
  for (var k = 0; k < m-1; k++) for (var s = k+1; s < m; s++) {
    c[j] = distance(P[k], P[s]);
    j++;
  };
  var t = new Array(n);
  for (var j = 0; j < n; j++) t[j] = "b";
  var A = new Array(m);
  for (var i = 0; i < m; i++) A[i] = new Array(n);
  for (var i = 0; i < m; i++) {
    var j = 0;
    for (var k = 0; k < m-1; k++) for (var s = k+1; s < m; s++) {
      A[i][j] = ((k == i) || (s == i) ? 1 : 0);
      j++;
    };
  };
  var b = new Array(m);
  for (var i = 0; i < m; i++) b[i] = 2;
  var s = new Array(m);
  for (var i = 0; i < m; i++) s[i] = 0;


  // Loesen des ganzzahligen Programms unter Hinzufuegen von Subtour-Constraints
  var S = [];
  var x = [];
  do {
    S = IntegerProgramming.minimize(c, t, A, b, s);
    x = S[0];
    var C = find_subtour(x, m);
    if (C.length < m-1) {
      var a = subtour_constraint(C, n);
      A.push(a);
      b.push(C.length-2);
      s.push(-1);
    };
  } while (C.length < m-1);

  // Loesung graphisch darstellen
  plot_result("plot", x);


</script>

</body>
</html>

Vorschau aktualisieren

Problem des Handlungsreisenden

formuliert als ganzzahliges Programm