Класс 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);                          // вычисляем матрицу расстояний
}
Собственно матрица расстояний dists между городами вычисляется функцией:
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);      // пока лучшее расстояние
}
Если параметр round = true, то расстояние округляется до целых. Длина любого пути way вычисляется в функции:
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);
}
Иногда (особенно при использовании реальных городов) карта получается очень большая. Для "вписывания" её в окне браузера, служит масштабный коэффициент scale. В принципе, можно было не создавать нового массива координат pos, а применить масштабное преобразования в самом конце. Однако линии при этом становятся слишком тонкими. Поэтому, мы пересчитываем координаты в функции getMap и заполняем поля структуры rect = {w, h} шириной и высотой результирующей карты:
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;
}

Обратим также внимание на свойство noNames в функции getSVG. По умолчанию оно не определено. Если задать ему любое не нулевое значение, номера городов выводиться не будут. Аналогично свойством noWay (если оно задано) можно заблокировать рисование пути. Задание радиуса города (в том числе нулевого) можно сделать "руками" при помощи свойства radius.

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

var sm = new Salesman(8);                         // 8 городов
sm.create(200, 200, 4, lcg);                      // карта 120 x 120
 
document.write(sm.getSVG(),'<br>');               // как svg-картинку
document.write("distance = "+sm.distance(sm.minWay).toFixed(2));
Напомним, что класс Salesman должен быть описан внутри html-страницы (в любом месте). Его можно также подключить из внешнего файла, написав в заголовке страницы: <script src="salesman.js"></script>

Естественно, заданный по умолчанию путь 0,1,2,... чаще всего оказывается не оптимальным, что и получилось на рисунке. В данном случае кратчайший путь легко провести без каких-либо вычислений (1,2,4,6,0,7,5,3) и его длина равна 528.29.

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

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

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();                                // таймер уже запущен, убиваем  его
}
Она (при первом нажатии) создаёт таймер (функция setInterval) и передаёт ему функцию timer (см. ниже). Так как это не "обычная функция", а метод класса, она передаётся при помощи дополнительного вызова bind (см. выше). При повторном нажатии на кнопку будет вызвана функция stop, которая уничтожит таймер:
Salesman.prototype.stop = function()
{
   this.timerID = clearInterval(this.timerID);    // убиваем  таймер, timerID=undefined
   this.btn.value = "run";                        // меняем надпись на кнопке
}
Так как алгоритмов поиска пути несколько, введём свойство method класса Salesman, которое необходимо задать перед запуском таймера. Сам таймер просто вызывает из себя тот или иной метод вычислений:
Salesman.prototype.timer = function()
{
   switch(this.method){
      case "perm":  this.permTimer();  break;     // полный перебор
      case "bound": this.boundInit();  break;     // метод ветвей и границ
      ...
   }
}
Перед запуском таймера вызывается функция init, задающая общие и специфические для каждого метода начальные значения переменных:
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);   // выводим результаты
}
Функция permNxt(ar, lf, rt) получения следующей перестановки в массиве ar в диапазоне [lf ... rt] приведена в документе, посвящённом методу грубой силы. Она, функция копирования copy и перестановки двух элементов массива местами swap сделаны статическими. Кроме этого, определена функция вывода информации о процессе вычисления:
Salesman.prototype.outInfo = function(st)
{
   if(this.outTXT)
      this.outTXT.innerHTML =  "len: "+this.minLen.toFixed(2)+"<br>"+this.minWay
         + "<br>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();
}

Свойство outTXT является объектом html-страницы в который при помощи поля innerHTML можно выводить информацию о процессе вычислений. Аналогично свойство outSVG служит для вывода svg-картинки с городами и путём между ними.

Вставка в 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>
и напишем скрипт (в тегах script), который вычитывает параметры карты городов и создаёт экземпляр класса Salesman:
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();
Вот результат этих манипуляций:

городов на карте размером: w = , h = и seed = .
period: , loops:
Нажми на кнопку
svg

Задача коммивояжёра <
> Эвристики в задаче коммивояжёра