В задаче коммивояжёра перебор возможных путей ведёт к очень "ветвистому" дереву.
Например, пусть коммивояжёр начинает движение из города 0
и есть ещё 4-е города. Вторым он может посетить один из городов 1,2,3,4.
Если выбран путь 0 → 1, далее можно попасть в 2,3 или 4
и т.д.:
Такой перебор, вообще говоря, задваивает число путей,
так как не учитывается возможность движения по замкнутому пути в любую сторону
(0,1,2,3,4 эквивалентен 0,4,3,2,1).
В результате, вместо (N-1)!/2 вариантов, их просматривается в 2 раза больше.
Впрочем, проблема не в этом, а в общей ветвистости дерева, которое при больших N
не позволяет использовать поиск в ширину
(для N городов на глубине d имеем (N-1)(N-2)...(N-d) узлов).
При направленном поиске и не слишком "агрессивной" эвристике движения в глубину,
мы также рискуем получить очередь open не помещающуюся в памяти компьютера.
Построение бинарного дерева
Существенно менее ветвистым является бинарное дерево.
Пусть на данном этапе известно, что город j ещё не пройден, а в город i
коммивояжёр ещё не вошёл. Построим две ветви.
На всех потомках левой ветви будем перебирать пути в которых присутствует
переход j → i, а на правой, в которых переход j → iзапрещен.
Рассмотрим, например, матрицу расстояний для 5 городов, приведенную ниже в первой таблице.
Нижняя граница длины оптимального пути для этой таблицы
равна 10 + 1 = 11.
Для её получения, необходимо вычесть минимальные значение из каждой строки (2+3+3+1+1=10, вторая таблица),
а затем из каждого столбца (только 1 в первом столбике, см. вторую таблицу):
0
1
2
3
4
0
-
5
8
9
2
1
5
-
3
3
4
2
8
3
-
7
6
3
9
3
7
-
1
4
2
4
6
1
-
0
1
2
3
4
0
-
3
6
7
0
1
2
-
0
0
1
2
5
0
-
4
3
3
8
2
6
-
0
4
1
3
5
0
-
0
1
2
3
4
0
-
3
6
7
0
1
1
-
0
0
1
2
4
0
-
4
3
3
7
2
6
-
0
4
0
3
5
0
-
Любой ноль в последней таблице является потенциально "хорошим перемещением".
Выберем, например, переход 1 → 2.
Тогда пространство решений можно разбить на два класса - содержащих переход
1 → 2 (левая ветвь) и не содержащих его (правая ветвь):
0
1
3
4
0
-
3
7
0
2
4
-
4
3
3
7
2
-
0
4
0
3
0
-
0
1
3
4
0
-
1
7
0
2
1
-
1
0
3
7
0
-
0
4
0
1
0
-
0
1
2
3
4
0
-
3
1
7
0
1
1
-
-
0
1
2
4
0
-
4
3
3
7
2
1
-
0
4
0
3
0
0
-
0
1
2
3
4
0
-
3
6
7
0
1
1
-
-
0
1
2
4
0
-
4
3
3
7
2
6
-
0
4
0
3
5
0
-
Для левой ветви выкинем из таблицы расстояний строку 1 (из этого города уже переходить нельзя)
и столбец 2 (в этот город уже зашли). Кроме этого,
заблокируем обратный переход 2 → 1, который теперь запрещён.
Получится первая таблица выше. В ней снова вычтем минимальные значения из строк и столбцов,
увеличив нижнюю границу на 3+2=5 (вторая таблица).
Для правой ветви ставим прочерк в переходе 1 → 2 (четвёртая таблица)
и, вычитая минимумы, также увеличим нижнюю границу на 5 (третья таблица).
Выбор перехода
Какой лучше выбрать ноль в таблице расстояний для создания очередных двух ветвей?
Поиск оптимального решения будет происходить в основном в глубину, сначала по левым ветвям с уменьшающимися матрицами
(удлиняющимся путём).
Поэтому при выборе перехода j → i
берётся такой ноль, для которого правая ветвь (содержащая большую матрицу)
получает наибольший прирост в нижней границе расстояния.
Для этого временно блокируется по очереди каждый ноль (заменяя его на прочерк)
и производится минимизация строк и столбцов.
На левой ветви, после вычёркивания строки и столбца, всегда блокируется обратный
переход. При этом необходимо учесть, что по мере спуска по дереву могут
возникать несвязные участки пути. Их следует склеивать, как только появляется такая возможность.
Например, если были выбран переход 1 → 2, а в одном из дочерних узлов
переход 2 → 3, то их необходимо объединить в один участок
пути 1 → 2 → 3.
Если мы хотя бы один раз добрались до дна дерева, т.е. сформировали полный путь,
то уже известна его некоторая длина (возможно пока не минимальная).
В дальнейшем, двигаясь по дереву, необходимо отсекать очередную ветку, если она
оценивает нижнюю границу как большую или равную лучшей длины пути к текущему моменту.
Перейдём к деталям реализации алгоритма ветвей и границ на JavaScript.
Узел бинарного дерева Salesway
Метод ветвей и границ в модуле salesman.js
использует дополнительный класс Salesway, экземпляры
которого являются узлами бинарного дерева:
functionSalesway(num, cities)
{
this.num = num; // размерность матриц расстояний
this.dists = newArray(num*num); // оставшиеся варианты расстояний
this.src = newArray(num); // города из которых можно ещё перейти
this.des = newArray(num); // города в которые можно ещё перейти
this.frw = newArray(cities); // участки пути в одну сторону
this.rev = newArray(cities); // участки пути в обратную сторону
}
Заголовки строк и столбцов (номера городов) матрицы расстояний для
оставшихся городов находятся в массивах src и des
соответственно. Для экономии памяти, матрица расстояний dists
хранится в одномерном массиве. Он содержит в себе кроме расстояний между оставшимися городами, информацию
о заблокированных переходах (прочерки), расстояния которых считаются равными -1.
Корневой узел бинарного дерева инициализируется по исходной матрице расстояний между городами dists
следующим образом:
Salesway.prototype.init = function(dists)
{
for(varj=0, k=0; j < dists.length; j++){
for(vari=0; i < dists.length; i++)
this.dists[k++] = dists[j][i]; // квадратная матрица в линейном массиве
this.src[j] = this.des[j] = j; // в именах строк и колонок все города
this.frw[j] = this.rev[j] = -1; // пока нет участков пути
}
this.boundLen = this.value = 0; // накопленная оценка снизу и её ценность
}
Работу с квадратной матрицей размерности num x num, хранящейся в линейном массиве dists,
проиллюстрируем на примере функции, которая находит минимальное значение в i-той строке или i-той колонке
(если есть параметр col и он не нулевой):
Salesway.prototype.getMin = function(i, col)
{
varmin = Infinity; // минимум разрешённых расстояний
if(m > 0 && m < min) min = m; // только не отрицательные расстояния
}
returnmin;
}
Получение нижней границы оставшегося пути
Для получении нижней границы оставшейся длины пути коммивояжёра,
необходимо вычесть минимальные значения
расстояний из каждой строки и каждого столбца.
Минимизацию строк провводит функция minimizeRows:
Salesway.prototype.minimizeRows = function()
{
varsum = 0;
for(varj=0; j < this.num; j++){
varmin = this.getMin(j); // ищем минимум в строке
if(min < Infinity){
sum += min;
for(vari=0; i < this.num; i++) // вычитаем его из элементов строки
if( this.dists[j*this.num+i] >=0 )
this.dists[j*this.num+i] -= min;
}
}
returnsum;
}
а колонок - функция minimizeCols:
Salesway.prototype.minimizeCols = function()
{
varsum = 0;
for(vari=0; i < this.num; i++){
varmin = this.getMin(i, true); // ищем минимум в колонке
if(min < Infinity){
sum += min;
for(varj=0; j < this.num; j++) // вычитаем его из элементов столбика
Она не только вычисляет нижнюю границу пути boundLen, но и задаёт
параметр value по которому будет сортировать узлы приоритетная
очередь (см. ниже).
Чтобы более активно опускаться вниз дерева, нижняя граница умножается на размерность матрицы
(число городов в оставшемся пути).
Выбор очередного перехода
При выборе очередного перехода ищется такой ноль в матрице расстояний,
блокировка которого приводит к наибольшему росту нижней оценки оставшегося пути:
Salesway.prototype.selectPair = function()
{
varii=0, jj=1, minI, minJ, max=-1;
for(varj=0; j < this.num; j++)
for(vari=0; i < this.num; i++){ // бежим по всем ячейкам матрицы,
if(this.dists[j*this.num+i]) continue; // которые равны нулю
this.dists[j*this.num+i]=-1; // временно блокируем этот переход
varmJ = this.getMin(j); // получаем минимум в строке j
Функция возвращает объект,
свойствами которого является прирост нижней границы max,
индексы jj, ii строки и столбца в матрице расстояний,
где стоит "лучший" ноль и минимумы minJ и minI
в этой строке и столбце (после блокирования нуля).
Этот объект res = way.selectPair()
используется далее для блокировки перехода:
Salesway.prototype.blockWay = function(res)
{
this.dists[res.jj*this.num+res.ii] = -1; // блокируем путь jj-ii
if(res.minJ) // если минимум в строке не нулевой
for(vari=0; i < this.num; i++) if(this.dists[res.jj*this.num+i] > 0)
Для сшивки отдельных участков пути, прямые и обратные переходы хранятся в двух массивах:
frw и rev.
Значение frw[j] означает номер города в который идёт переход из города j
(или -1, если перехода ещё нет), rev[i] - означает номер города
который предшествует городу i (или -1, если его ещё нет).
Например, пусть для восьми городов зафиксированы два участка пути: 0 → 5 → 2 и
3 → 4 → 7 → 6. Тогда массивы имеют следующие элементы:
Приведём пример работы с этими массивами в функции, возвращающей
массив массивов с участками сформированного пути:
Salesway.prototype.getPath = function()
{
varres = []; // результирующий массив массивов
for(vark=0; k < this.rev.length; k++){ // по массиву с обратными путями
if(this.rev[k] >= 0 || this.frw[k] < 0)
continue; // ищем начало последовательности
varar = [k];
varn = k;
while( this.frw[n] >= 0 ){
n = this.frw[n];
ar.push(n);
}
res.push(ar); // добавляем цепочку городов
}
returnres;
}
Когда путь сформирован полностью, результирующий массив
будет состоять из одного элемента, являющегося массивом списка городов.
Создание нового участка пути
Левая ветвь бинарного дерева получается в результате добавления
к уже частично построенному пути перехода
wj -> wi, где wj,wi - положение в оставшейся матрице расстояний:
