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

Введение

Этот документ продолжает тему задачи коммивояжёра. Мы обсудим различные эвристические алгоритмы, которые не гарантируют получения точного решения, однако, иногда дают кратчайший путь или близкий к нему. Первые два метода (жадный алгоритм и метод шнурка), обычно, используются для получения первого приближения к решению задачи. Затем его можно улучшить остальными эвристиками, описанными в документе.

Вообще, эффективность эвристических методов повышается при их комбинировании. Если первые два метода не зависят от "предыстории" поиска, то последовательность остальных методов важна и при удачном их сочетании результат может существенно улучшиться.

Полученный при помощи эвристик путь, в дальнейшем используется как стартовый для поиска с возвратом. При этом возможно не только его улучшение, но и доказательство оптимальности (если поиск закончит свою работу).

Жадный алгоритм

Идея этого алгоритма очень проста. При выборе очередного города берётся ближайший город в котором мы ещё не были. Такой подход, по понятным причинам называется "жадным". К сожалению, если в начале путь получается коротким, то в конце часто возникает очень большой прирост его длины.

В жадном алгоритме принципиально какой город выбирается в качестве стартового. Чтобы улучшить результат, будем по очереди делать стартовым каждый город, выбирая тот вариант, который даст кратчайший путь. В начале следующей итерации вспомогательный массив way заполняется номерами городов: way = [0,1,2,3,...,N-1] и на первое место ставится город j=0,1,2,...N-1. Для этого он меняется местами с нулевым элементом массива. Затем ищется ближайший к нему город и ставится на первое место (снова при помощи перестановки элементов массива функцией swap). Эти действия продолжаются, пока не сформируется полный путь:

Salesman.prototype.greedy = function ()
{
   this.minLen = Infinity;
   for(var j=0; j < this.N; j++){                 // выбираем лучший стартовый город
      for(var i=0; i < this.N; i++ )
         this.way[i] = i;                         // все города
      Salesman.swap(this.way, 0, j);              // j-тый город ставим первым
 
      var last = j, lf = 1, d = 0;                // last - последний посещённый город
      while(lf < this.N){                         // пока не перебрали оставшиеся города
         var minD = this.dists[last][this.way[lf]];
         for(var i=lf+1; i < this.N; i++)         // ищем ближайший к last город
            if(this.dists[last][this.way[i]] < minD){
               minD = this.dists[last][this.way[i]];
               Salesman.swap(this.way, lf, i);    // ближайший переносим в начало
            }
         d += minD;                               // суммируем общую длину пути
         last = this.way[lf++];                   // берём "первый" как ближайший
      }
      d +=  this.dists[last][j];                  // финальный отрезок
      if(this.minLen > d){                        // если длина пути лучшая,
         this.minLen = d;                         // запоминаем её и путь:
         this.minWay = Salesman.copy(this.minWay, this.way);
      }
   }
}

Приведём длину пути, сам путь и карту городов в конце каждого цикла по стартовому городу j для карты городов, созданной функцией create(100,100, 7, lcg, true) (картинки увеличены в scale = 2.2 раза):

В этом случае города 1, 6 и 7, в качестве стартовых, привели к точному (и единственному) решению с длиной пути 305. Самым неудачным оказался бы старт с города 3, который приводит (при "простом" жадном выборе очередного горорда) к пути длиной 378.

Жадный алгоритм (с перебором стартового города) имеет кубическое время работы T ~ N3. Поэтому для большого числа городов N стоит переписать функцию greed для вызова её в таймере. Соответствующий код (функции greedInit и greedTimer) можно найти в исходниках класса salesman.js.

Метод шнурка

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

Затем в таймере, в каждый сегмент полученного контура вставляется "промежуточный" город, который минимальным образом увеличивает общий путь.

Нажми на кнопку

Для охватывания точек на плоскости выпуклым полигоном, воспользуемся алгоритмом Джарвиса. Сначала найдём самую верхнюю из самых левых точек cur (верхний левый угол - ось y вниз!). Выше это город номер 18, и он, очевидно, лежит на охватывающем полигоне. Затем ищем ближайшую к cur точку nxt, такую, что вектор в остальные точки i лежит слева от вектора проходящего через nxt - cur (если смотреть из точки cur). Это проверяется знаком векторного произведения (nxt - cur) x (i - cur). Если оно равно нулю, это значит, что точки лежат на одной прямой. После этого, точку nxt (выше 59) делаем cur и повторяем вычисления, формируя охватывающий контур против часовой стрелки. Алгоритм останавливается, когда возвращается к исходной точке beg:

Salesman.prototype.laceInit = function()
{
   var time = window.performance.now();           // время в начале функции
   var p = this.pos;                              // точки на плоскости
   this.minWay = [];                              // номера точек, образующих полигон
 
   var beg = 0;                                   // номер самой верхней из самых левых
   for (var i = 1; i < p.length; i++)
      if (p[i].x < p[beg].x || (p[i].x === p[beg].x && p[i].y < p[beg].y))
         beg = i;
 
   var cur = beg, prv=-1;                         // cur-текущая точка на полигоне
   do{
      this.minWay.push(cur);                      // добавляем точку в полигон
      var nxt = cur > 0? cur-1: 1;                // любая, отличная от cur
      for (var i = 0; i < p.length; i++)          // ищем следующую точку
         if ( i!==prv ){
            var nx = p[nxt].x - p[cur].x, ny = p[nxt].y - p[cur].y;
            var ix = p[i].x   - p[cur].x, iy = p[i].y   - p[cur].y;
            var s = nx*iy - ny*ix;                // векторное произведение n x i
            if(s === 0 && Salesman.isInArray(this.minWay, i))
               continue;                          // cur, nxt, i на одной линии и i была
            if (s > 0 || (s === 0 && ix*ix+iy*iy < nx*nx+ny*ny) )
               nxt = i;                           // справа или ближайшая
         }
      prv = cur;
      cur = nxt;
   }
   while (cur !== beg);                           // пока не вернулись в начало
 
   this.was = new Array(this.N);                  // пройден путь через точку или нет
   for(var i=0; i < this.minWay.length; i++)
      this.was[this.minWay[i]] = true;
   this.minLen = this.distance(this.minWay);      // длина контура будет расти
 
   this.timeTot = window.performance.now() - time;// время вычислений
   this.outInfo();
}
Функция isInArray (статическая) проверяет, есть ли в массиве minWay значение i. В конце подготавливается массив was, i-й элемент которого равен true, если i-й город уже находится в пути.

Дальнейшие вычисления проводятся в таймере и они достаточно незатейливые. Выбирается сегмент [i1, i2] и город i, добавление которого между i1 и i2 увеличивает длину пути минимальным образом:

Salesman.prototype.laceTimer = function()
{
   var num = this.loops;                          // итераций за один "тик" таймера
   var time = window.performance.now();           // время в начале функции
   do{
      if(this.minWay.length === this.N ){         // все города уже в пути
         this.stop();                             // убиваем таймер
         break;                                   // прекращаем итерации
      }
 
      var minD = Infinity, minI1, minI2, minI;
      for(var i1=0;i1 < this.minWay.length; i1++){// бежим по уже существующим сегментам
         var i2 = (i1+1 < this.minWay.length)? i1+1: 0;
         var d12 = this.dists[this.minWay[i1]][this.minWay[i2]];
         for(var i=0; i < this.N; i++){           // перебераем все города,
            if(this.was[i])                       // которые не попали пока в путь
               continue;
            var d = this.dists[this.minWay[i1]][i]// на сколько изменится длина пути
                  + this.dists[i][this.minWay[i2]]// при добавлении города i в сегмент
                  - d12;
            if( d < minD ){                       // наименьшее изменение запоминаем
               minD = d;
               minI1 = i1; minI2 = i2; minI = i;
            }
            if(minD === 0)                        // точка i лежит на прямой i1-i2
               break;
         }
      }
      this.was[minI] = true;                      // помечаем, что в этом городе были
      this.minWay.splice(minI2, 0, minI);         // вставляем перед minI2
 
   } while(--num);
   this.timeTot += window.performance.now() - time;
 
   this.minLen = this.distance(this.minWay);
   this.outInfo(", N: "+this.minWay.length);
}

Перестановка соседей

Перейдём теперь к эвристикам которые, обычно, позволяют улучшить найденный предыдущими двумя методами путь. Простейшей из них является перестановка двух соседних городов в пути. Если такая перестановка приводит к уменьшению общей длины пути, то она запоминается. Этот приём позволяет "распутывать маленькие петли":

Перестановка соседей имеет квадратичное время работы, поэтому сделаем её "не таймерной":

Salesman.prototype.turn = function ()
{
   var beg=0, end=1, nxt=2, prv=this.N-1, cnt=0, totCnt=0;
   while(true){                                 // длина до переворота и после:
      var oldD = this.dists[this.minWay[prv]][this.minWay[beg]]
               + this.dists[this.minWay[beg]][this.minWay[end]]
               + this.dists[this.minWay[end]][this.minWay[nxt]];
      var newD = this.dists[this.minWay[prv]][this.minWay[end]]
               + this.dists[this.minWay[end]][this.minWay[beg]]
               + this.dists[this.minWay[beg]][this.minWay[nxt]];
      if(oldD > newD){                          // длина пути уменьшилась
         Salesman.swap(this.minWay, beg, end);  // меняем местами
         this.minLen -= oldD-newD;              // уменьшаем длину пути
         cnt++; totCnt++;                       // переворотов на круге и всего
      }
      prv = beg;  beg = end;  end = nxt;  nxt = this.next(nxt);
 
      if(beg===0){                              // сделали полный круг
         if(!cnt)                               // не было ни одного переворота
            break;                              // оканчиваем работу
         cnt = 0;                               // иначе делаем ещё один круг
      }
   }
   this.outInfo(" cnt:"+totCnt);                // дополнительно выводим число переворотов
}
Выше использована функция next получения следующего индекса, с учётом перодичности движения по массиву minWay:
Salesman.prototype.next = function(i) {  return ++i >= this.N ? 0: i;        }
Salesman.prototype.prev = function(i) {  return --i <  0      ? this.N-1: i; }

Поэкспериментировать с этой эвристикой можно на страничке сравнения различных методов (метод "перевороты"). Лучше её запускать после жадного алгоритма или метода шнурка.

Перестановка пар

В этой эвристике берутся две пары соседних узлов и проверяется, уменьшится ли расстояние, если переставить местами по одному городу из каждой пары. Ниже одна пара - это узлы b1 и b2, а вторая пара - узлы e1 и e2. Пунктирными линиями обозначены остальные участки пути (с не нарисованными на них узлами) и стрелками - направление движения. Понятно, что если после города b1 пойти не в b2, а в e1, то общая длина пути уменьшится (второй рисунок). При такой замене необходимо также обратить последовательность прохождения участка пути A (см. направление стрелок):



  [B] b1b2 [A] e1e2 [B] b1e1 [A]inv b2e2        

Эвристика перестановки пар в классе Salesman сделана "таймерной" (функции swapInit и swapTimer). Алгоритм начинается с индексов beg1=0, beg2=1 (в массиве minWay), а для второй пары берутся соседние города с индексами end1=2 и end2=3. Затем в таймерной функции вторая пара начинает скользить вдоль пути в поисках возможных перестановок. Если они произошли, увеличивается счётчик числа перестановок cntSwaps "на круге". Если при полном обходе второй парой пути не произошло ни одной перестановки, то первая пара сдвигается на один индекс. Вторая опять становится после неё и всё повторяется.

На результат работы этой эвристики можно посмотреть на страничке сравнения методов (метод swap).

Частичный перебор

Ещё одна эвристика обобщает метод "перестановки соседей". В ней выбирается небольшой участок пути ("окно перестановок"). Ниже на рисунке приведено окно шириной в четыре города между узлами b и e (попавшие в него города обведены пунктиром). Города внутри окна переставляются всеми возможными способами. После проведения этих перестановок окно сдвигается вдоль пути на один город. Процедура повторяется до тех пор, пока при полном прохождении окна перестановок вдоль пути не будет найдено ни одного лучшего решения.

Соответствующие функции moveInit и moveTimer есть в исходниках. Эту эвристика, как и остальные, можно запустить на страничке сравнения методов (метод move perm).
Класс Salesman <
> Нижняя граница длины оптимального пути