Поиск с возвратом: 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 } }
Пусть 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 ...).