Поиск с возвратом: Salesman

Функция backInit

Решение задачи коммивояжёра, найденное эвристическими методами, можно улучшить при помощи поиска в глубину с возвратами. Для этого добавим в класс Salesman функцию инициализации метода:

Salesman.prototype.backInit = function()
{
   this.close = new List();                       // менеджер памяти узлов
   this.cntN1 = 0;                                // число узлов на глубине 1
 
   this.open  = new List();                       // список узлов для анализа
   for(var i=1; i < this.N; i++)                  // помещаем лучший путь и его варианты
      for(var j = this.N-1; j>i; j--){            // спереди будет лучший путь
         var n = {n:i+1, way:Salesman.copy([],this.minWay), len:0 };
         Salesman.swap(n.way, i, j);
         n.len = this.subDistance(n.way, n.n);
         this.open.unshift(n);                    // помещаем в очередь
         if(n.n === 2) this.cntN1++;              // число узлов глубины 1
      }
}
0 1 2 3 4 2 3 4 3 4 4
В этой функции создаётся список список частичных путей, в основу которых будет положен лучший к настоящему моменту путь из массива minWay. Каждый элемент списка - это структура, хранящая путь way, число посещённых городов n и длину len, пройденного пути.

Пусть minWay = [0,1,2,3,4] (на рисунке - жёлтые узлы). Тогда в самом начале очереди должен находится участок пути way = [0,1,2,4], затем [0,1,3] и [0,1,4] и после них: [0,2],[0,3], [0,4]. Помещение в список open таких участков производится в циклах по i и j, путём обмена i-го и j-го городов местами. Функция subDistance вычисляет длину не законченного пути, без его "закольцевания". Переменная cntN1 служит для подсчёта оставшихся в списке open вариантов глубины 1, а дополнительный список close хранит массивы, выступая в качестве менеджера памяти (чтобы не выделять всё время память для новых узлов дерева).

Функция backTimer

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

Salesman.prototype.backTimer = function()
{
   var num = this.loops;                          // итераций за один "тик" таймера
   var time = window.performance.now();           // время в начале функции
   do{
      if( this.open.empty() ){                    // очередь пустая
         this.stop();                             // убиваем таймер
         break;
      }
      var n = this.open.shift();                  // берём узел из начала списка
      if(n.n === 2) this.cntN1--;
      if(n.len + this.supDistance(n.way, n.n) >= this.minLen){
         this.cntCuts++;                          // уже есть путь короче
         if(this.close.length < 1000)
            this.close.push(n.way);
         continue;                                // обрываем ветку !!!
      }
 
      if(n.n === this.N){                         // сформировали полный путь
         this.cntWays++;
         var len = n.len + this.dists[n.way[n.n-1]][n.way[0]];
         if( len < this.minLen){
            this.minLen = len;                    // запоминаем кратчайшее расстояние
            this.minWay = Salesman.copy(this.minWay, n.way);
            this.timeMin = this.timeTot + (window.performance.now() - time);
         }
         continue;                                // новых потомков не будет
      }
 
      var ar = new Array(this.N-n.n);             // создаём новых потомков:
      for(var i = 0; i < ar.length; i++){
         var way = Salesman.copy(this.close.length? this.close.shift():[], n.way);
         Salesman.swap(way, n.n, n.n+i);
         ar[i] = {  n  : n.n+1,  way: way,
                    len: n.len + this.dists[n.way[n.n-1]][way[n.n]]
                 };
      }                                           // и сортируем их:
      ar.sort( function(a,b){ return a.len < b.len? -1:(a.len > b.len)? 1:0 });
 
      for(var i=ar.length; i--; ) {               // помещаем в open новых потомков
         this.cntNode++;
         this.open.unshift( ar[i] );
      }
      if(n.n===1)
         this.cntN1 += ar.length;                 // сколько добавили узов глубины 1
 
   } while(--num);
   this.timeTot += window.performance.now() - time;
   this.outInfo(", open: " + this.open.length+' n1:'+this.cntN1);
}
Ключевой является проверка n.len + this.supDistance(n.way, n.n) >= this.minLen, в которой вызывается функция supDistance вычисления нижней границы оставшегося пути. Если накопленная длина пути n.len и нижняя граница оставшегося пути не меньше длины minLen кратчайшего (пока) пути, то дальнейший анализ этой ветки смысла не имеет. Именно в этом месте происходит отсечение неперспективных путей и существенное сокращения пространства поиска.

При создании нового массива, память для него выделяется по-новой, или берётся из массива close (см. выше в функции backTimer строку var way = Salesman.copy ...).

Нижняя граница длины пути <
> Метод ветвей и границ