Класс Salesman для задачи коммивояжёра

Класс Salesman

В следующих документах мы рассмотрим различные методы решения задачи коммивояжёра. Сейчас же подготовим необходимую "базу" в виде класса Salesman. Его конструктор создаёт массивы, необходимые для N городов:

function Salesman(n)
{
   this.N      = n;                               // число городов
   this.minWay = new Array(this.N);               // лучший путь (массив номеров городов)
   this.minLen = Infinity;                        // лучшее расстояние

   this.dists = new Array(this.N);                // двумерная матрица расстояний
   for(var j=0; j < this.N; j++)                  // размерности N x N
      this.dists[j] = new Array(this.N);

   this.pos = new Array(this.N);                  // положение {x,y} городов на плоскости
   this.way = new Array(this.N);                  // временный путь для различных алгоритмов

   this.method = "perm";                          // метод поиска пути  ( см. init() )
   this.timerPeriod = 10;                         // период (ms) вызова из таймера
   this.timeTot = this.timeMin = 0;               // время общее и до лучшего решения
}

Генератор расстояний

Для наглядности, заполним матрицу dists евклидовыми расстояниями между точками на плоскости (плоская, евклидовая задача коммивояжёра). Функция create создаёт города на карте размером w×h в случайных местах. При этом используется генератор случайных чисел rnd с затравочным значением seed (будем использовать линейный конгруэнтный генератор lcg):

Salesman.prototype.create = function (w, h, seed, rnd, round)
{
   this.w = w;  this.h = h;                       // ширина и высота карты с городами

   rnd.seed(seed);                                // номер случайной последовательности
   for(var k=0; k < this.N; k++)
      this.pos[k] = {x:rnd.rand(w),y:rnd.rand(h)};// случайное положение городов

   this.setDists(round);                          // вычисляем матрицу расстояний
}

Salesman.prototype.setDists = function (round)
{
   for(var j=0; j < this.N; j++){                 // вычисляем попарные расстояния
      this.dists[j][j] = -1;                      // сам с собой город дорогой не связан
      for(var i=0; i < j; i++){
         var dx = this.pos[i].x - this.pos[j].x;
         var dy = this.pos[i].y - this.pos[j].y;  // евклидово расстояние:
         var d  = Math.sqrt(dx*dx+dy*dy);
         this.dists[j][i] = this.dists[i][j] = round? Math.round(d): d;
      }
   }

   for(var i=0; i < this.N; i++)
      this.minWay[i] = this.way[i] = i;           // пока лучший путь 0,1,2,...,N-1
   this.minLen = this.distance(this.minWay);      // пока лучшее расстояние
}

Salesman.prototype.distance = function (way)
{
   var d = 0, i = 1;
   for(; i < way.length; i++)
      d += this.dists[way[i-1]][way[i]];          // из города way[i-1] в город way[i]
   return d + this.dists[way[i-1]][way[0]];       // замыкающее расстояние в город way[0]
}

Карта городов

Для рисования городов и пути коммивояжёра будем использовать класс draw, который предоставляет методы рисования как на канвасе, так и в виде svg-картинки. Следующая функция возвращает svg-картинку, которую можно непосредственно вставить в html-страницу:

Salesman.prototype.getSVG = function (way)
{
   if(!way) way = this.minWay;                    // по умолчанию минимальный путь
   var draw = new Draw(), rect = {};              // объект рисования из draw.js
   var pos  = this.getMap(rect);                  // отмасштабированный массив координат

   if(!this.noWay)
      draw.polygon(pos, false, way);              // рисуем замкнутый полигон пути way

   var r = this.N <= 50 ? 8: (this.N <= 100? 6:3);// выбираем радиус узла
   if(this.noNames) r = 3;                        // не будем выводить имя города
   if(this.radius !== undefined) r = this.radius; // радиус задан извне
   draw.colorFill('#ffa');                        // цвет заливки города
   if(r > 0 && !this.noCites)
      for(var j=0; j < this.N; j++)               // точки городов с координатами {x,y}
          draw.circleFill(pos[j], r);             // окружность с жёлтой сердцевиной

   if(!this.noNames && r > 3){                    // выводим номера городов вдоль пути!
      draw.colorText('#00a');                     // цвет текста
      draw.sizeText(r===8 ? 12 : 8);              // размер шрифта
      for(var i=0; i < way.length; i++)
         draw.text(way[i], pos[way[i]].x, pos[way[i]].y+1);
   }

   draw.transformAll(2*r, 2*r);                   // возвращаем рисунок как svg - текст:
   return draw.getSVG(rect.w+4*r, rect.h+4*r);
}

Salesman.prototype.getMap = function (rect)
{
   var min = {x:Infinity, y:Infinity}, max = {x:0, y:0};
   for(var i=0; i < this.pos.length; i++){        // минимальные и максимальные координаты
      var p = this.pos[i];
      if(p.x < min.x) min.x = p.x;  if(p.x > max.x) max.x = p.x;
      if(p.y < min.y) min.y = p.y;  if(p.y > max.y) max.y = p.y;
   }

   var pos = new Array(this.pos.length);          // сдвинутые и сжатые координаты
   for(var i=0; i < pos.length; i++)
      pos[i] = {x: (this.pos[i].x-min.x)*this.scale,
                y: (this.pos[i].y-min.y)*this.scale};
   rect.w = (max.x-min.x)*this.scale;  rect.h = (max.y-min.y)*this.scale;
   return pos;
}

Протестируем, что получилось, написав следующий скрипт (результат работы приведен справа):

var sm = new Salesman(8);                         // 8 городов
sm.create(200, 200, 4, lcg);                      // карта 120 x 120

document.write(sm.getSVG(),'
');               // как svg-картинку
document.write("distance = "+sm.distance(sm.minWay).toFixed(2));

Длительные вычисления

Метод грубой силы и более "интеллектуальные" алгоритмы, при большом числе городов, занимают длительное время. Поэтому имеет смысл использовать таймер, при каждом вызове которого производится только часть вычислений. Запускать и останавливать таймера будем нажатием кнопки, так как это было описано при обсуждении "грубой силы". При нажатии кнопки вызывается следующая функция:

Salesman.prototype.run = function(btn)
{
   if(this.timerID === undefined){                // создаём таймер:
      this.timerID = setInterval(this.timer.bind(this), this.timerPeriod);
      btn.value = "stop";                         // меняем надпись на кнопке
      this.btn  =  btn;                           // запоминаем кнопку
      this.init();                                // функция инициализации
      this.timer();                               // сразу запускаем вычисление
   }
   else
      this.stop();                                // таймер уже запущен, убиваем  его
}

Salesman.prototype.stop = function()
{
   this.timerID = clearInterval(this.timerID);    // убиваем  таймер, timerID=undefined
   this.btn.value = "run";                        // меняем надпись на кнопке
}

Salesman.prototype.timer = function()
{
   switch(this.method){
      case "perm":  this.permTimer();  break;     // полный перебор
      case "bound": this.boundInit();  break;     // метод ветвей и границ
      ...
   }
}

Salesman.prototype.init = function()
{
   this.cntWays  = 0;                             // число просмотренных путей
   this.cntNode  = 0;                             // число сформированных узлов
   this.cntCuts  = 0;                             // число отсечений неподходящих веток
   this.timeTot  = this.timeMin = 0;              // общее время и время до минимума

   if(this.minWay.length !== this.N){             // на всякий случай, иначе не меняем
      this.minWay   = new Array(this.N);          // лучший путь
      this.way      = new Array(this.N);          // вспомогательный путь
      for(var i=0; i < this.N; i++)               // заполняем их
         this.minWay[i] = this.way[i] = i;        // начальным порядком 0,1,2,...
      this.minLen = this.distance(this.minWay);   // вычисляем длину этого пути
   }
   this.maxLen  = 0;                              // максимальное расстояние

   switch(this.method){                           // инициализируем конкретный метод
      case "perm" : this.permInit();   break;     // полный перебор
      case "bound": this.boundTimer(); break;     // метод ветвей и границ
      ...
   }
}

Полный перебор

Полный перебор был подробно описан ранее, поэтому приведём соответствующие функции без особых пояснений. Инициализация:

Salesman.prototype.permInit = function()
{
   this.cntSol  = 0;                              // число оптимальных решений
   this.total = Salesman.factorial(this.N-1);     // число необходимых перестановок
   for(var i=0; i < this.N; i++) this.way[i] = i; // все города для перестановок
}

Salesman.prototype.permTimer = function()
{
   var num = this.loops;                          // итераций за один "тик" таймера
   var time = window.performance.now();           // время в начале функции
   do{
      this.cntWays++;                             // число просмотренных путей
      var len = this.distance(this.way);          // вычисляем длину пути
      if(len === this.minLen) this.cntSol++;      // число оптимальных решений
      if(len < this.minLen){                      // нашли более короткий путь
         this.minLen = len;                       // запоминаем кратчайшее растояние
         this.minWay = Salesman.copy(this.minWay, this.way);
         this.cntSol = 1;                         // первое оптимальное решение
         this.timeMin = this.timeTot + (window.performance.now() - time);
      }
      if(len > this.maxLen) this.maxLen=len;      // запоминаем максимальное расстояние

   }
   while(Salesman.permNxt(this.way, 1, this.N-1) && --num);
   this.timeTot += window.performance.now() - time;

   if(num)                                        // while был прерван permNxt
      this.stop();                                // убиваем таймер (перестановки окончены)

   this.outInfo(", countSol = " + this.cntSol);   // выводим результаты
}

Salesman.prototype.outInfo = function(st)
{
   if(this.outTXT)
      this.outTXT.innerHTML =  "len: "+this.minLen.toFixed(2)+"
"+this.minWay
         + "
ms min,tot:" + this.timeMin.toFixed(0)
         + " " + this.timeTot.toFixed(0) + " "
         + (this.maxLen? "maxDist = " + this.maxLen.toFixed(2): "")
         + (this.cntWays? ", ways: " +this.cntWays
         + " ("+(100*this.cntWays/this.total).toFixed(2) + "%)":"")
         + (this.cntNode? ", nodes: " + this.cntNode: "")
         + (this.cntCuts? ", cuts: " + this.cntCuts: "")
         + (st? st:"");

   if(this.outSVG)
      this.outSVG.innerHTML = this.getSVG();
}

Вставка в html-страницу

Чтобы увидеть результат работы полного перебора всех путей, вставим в html-страницу следующий текст:

<input type="button"  value="Создать" style="width:5em" onClick="create()">
<input type="text" id="nID" value="8" style="width:2em">
городов на карте размером:
<b class="norm">w =</b>     <input type="text" id="wID"  value="200" style="width:2em">,
<b class="norm">h =</b>     <input type="text" id="hID"  value="200" style="width:2em"> и
<b class="norm">seed =</b>  <input type="text" id="sID"  value="4"   style="width:1em;">.<br>

<input type="button" value="run" style="width:5em" onClick="run(this);">
period: <input type="text" id="permTID" value="1" style="width:3em;">,
loops:  <input type="text" id="permLID" value="1000" style="width:3em;"><br>

<b id="pathID">Нажми на кнопку</b><br>
<div id="svgID">svg</div>

var man;                                                        // экземпляр класса

function create()
{
   var n    = Number(document.getElementById('nID').value);     // число городов
   var w    = Number(document.getElementById('wID').value);     // ширина карты
   var h    = Number(document.getElementById('hID').value);     // высота карты
   var seed = Number(document.getElementById('sID').value);     // номер случайной последовательности

   man  = new Salesman(n);
   man.create(w, h, seed, lcg);                                  // создаём случайную карту
   man.outTXT = document.getElementById('pathID');               // задаём где выводить путь
   man.outSVG = document.getElementById('svgID');                // задаём где рисовать карту
   man.outSVG.innerHTML = man.getSVG();                          // рисуем карту
}

function run(btn)
{
   man.period = Number(document.getElementById('permTID').value); // период таймера
   man.loops  = Number(document.getElementById('permLID').value); // число циклов в таймере
   man.method = 'perm';                                           // метод вычислений
   man.run(btn);                                                  // запуск перебора
}

create();