Метод грубой силы

Задача коммивояжёра

5 3 8 7 3 9 1 6 4 2 0 1 2 3 4
Есть N городов, соединённых между собой дорогами. Между ними необходимо проложить кратчайший замкнутый маршрут, проходящий через каждый город только один раз. Справа нарисован граф, состоящий из пяти узлов (городов), соединённых рёбрами (дорогами). Длины дорог приведены рядом с ребрами. Это полносвязный граф, в котором каждый узел соединён с любым другим. Рёбра графа ненаправленные и перемещение по ним от узла к узлу возможно в любом направлении. Обозначим расстояние между городами i и j через Dij. Обычно предполагается, что: 
                                  Dij ≥ 0,          Dij = Dji.

Вообще говоря, Dij - не обязательно "физическая длина" дороги. Это может быть время перемещения, стоимость билета или произвольно заданное неотрицательное число. Тем не менее, во всех этих случаях, Dij будет называться расстоянием.

01234
0-5892
15-334
283-76
3937-1
42461-
Запишем расстояния между городами в виде матрицы (таблица справа). Например, расстояние из города 2 в город 3 (и из 3 в 2) равно 7. Так как граф ненаправленный, эта матрица симметрична. Прочерками отмечены "запрещённые" переходы из города в него же.

Искомый путь замкнут, поэтому любой город можно выбрать в качестве начального (и конечного). Пусть таковым будет нулевой город. Тогда любая перестановка чисел от 1 до 4, окруженная нулями, символизирует некоторый путь, проходящий через каждый город один раз. Например, 0,1,3,2,4,0, означает, что стартуя из города 0, мы перемещаемся в город 1, затем в город 3 и т.д. На последнем шаге из города 4 возвращаемся в стартовую точку - город 0. Длина этого пути равна 5+3+7+6+2 = 23 и он не самый короткий. В данном случае есть две перестановки длиной 17. Это 0,2,1,3,4,0 и 0,4,3,1,2,0. На самом деле это один и тот же путь, который проходится в "прямом" или "обратном" направлении. Подобные перестановки, отличающиеся обращением пути, считаются тождественными. В дальнейшем финальный город будет опускаться и подразумевается, что он всегда совпадает со стартовым. Таким образом, на приведенном выше графе существует единственное оптимальное решение 0,2,1,3,4 с длиной пути равной 17.

Пусть один из N городов фиксирован. Тогда остальные N-1 городов можно переставить (N-1)! способами. Половина из них является обращением пути (циклической перестановкой). Поэтому существует (N-1)!/2 вариантов различных путей, среди которых необходимо найти хотя бы один путь минимальной длины.

Если расстояния между любыми тремя городами i,j и k удовлетворяют неравенству треугольника: 

                                        Dij + Djk  ≥ Dik,
задачу коммивояжёра называют метрической. Её частным случаем является задача соединения замкнутой ломаной линией точек на плоскости ("дороги" между городами считаются прямыми с евклидовым расстоянием в качестве их длины). Ниже приведены решения такой задачи для 20 и 50 городов:

Факториал в выражении (N-1)!/2 растёт очень быстро и уже при N > 15 перебрать все пути проблематично. Поэтому задача коммивояжёра служит хорошей моделью для тестирования непереборных алгоритмов, обладающих "зачатками интеллекта". Эти алгоритмы содержат те или иные эвристические соображения, делающие поиск решения более направленным (осмысленным). Однако в этом документе рассматривается метод "грубой силы", т.е. перебор. В дальнейшем мы неоднократно вернёмся к задаче коммивояжёра.

Генерация перестановок

Напишем рекурсивную функцию, создающую перестановки n чисел. Решим чуть более общую задачу: переставим всеми возможными способами элементы массива, начиная с индекса lf и вправо от него. Для этого, поочерёдно поставим на место элемента ar[lf] все элементы ar[i] c i ≥ lf (переставляя их местами) и рекурсивно повторим действия для массива меньшего размера, начиная с индекса lf+1:
function perm(ar, lf)
{
   if(lf >= ar.length){                           // перестановки окончены
      print(ar, dist(ar, dists));                 // выводим перестановку
      return;
   }
 
   perm(ar, lf+1);                                // перестановки элементов справа от lf
   for(var i=lf+1; i < ar.length; i++){           // теперь каждый элемент ar[i], i > lf
      swap(ar, lf, i);                            // меняем местами с ar[lf]
      perm(ar, lf+1 );                            // и снова переставляем всё справа
      swap(ar, lf, i);                            // возвращаем элемент ar[i] назад
   }
}
Функция dist в дальнейшем будет вычислять длину пути по матрице расстояний dists. Сам путь и его длина выводятся функцией print. Третья вспомогательная функция swap переставляет ar[i] и ar[j] местами:
function dist (ar, dists){ return 0; }
function print(ar, d)    { document.write(ar, '<br>'); }
function swap (ar, i, j) { var a=ar[i]; ar[i]=ar[j]; ar[j]=a; }
Протестируем функцию perm, написав следующий код (результат его работы приведен справа):
var ar = [1,2,3,4];                               // массив из 4-х элементов
perm(ar, 0);                                      // запускаем перебор перестановок
1,2,3,4
1,2,4,3
1,3,2,4
1,3,4,2
1,4,3,2
1,4,2,3
2,1,3,4
2,1,4,3
2,3,1,4
2,3,4,1
2,4,3,1
2,4,1,3
3,2,1,4
3,2,4,1
3,1,2,4
3,1,4,2
3,4,1,2
3,4,2,1
4,2,3,1
4,2,1,3
4,3,2,1
4,3,1,2
4,1,3,2
4,1,2,3
Теперь перейдём к вычислению расстояния.

Запускаем перебор

Определим массив dists[j][i] расстояний между городами j и i. Для простоты, будем задавать расстояния только в одну сторону, а обратные расстояния установим в цикле:

var dists = [
    [          ], // 0
    [5         ], // 1
    [8, 3      ], // 2
    [9, 3, 7   ], // 3
    [2, 4, 6, 1], // 4
];
for(var j=0; j < dists.length; j++){              // бежим по строкам вниз
   dists[j][j]=-1;                                // диагональные элементы
   for(var i=j+1; i < dists.length; i++)          // вправо от диагонали
      dists[j][i]=dists[i][j];                    // заполняем "дырки" в матрице
}
JavaScript
Двумерный массив
Элементами массива dists являются 5 массивов. Поэтому, например, dists[4] - это пятый массив (нумерация идёт с нуля), а его второй элемент (равный 4) - это dists[4][1]. Таким образом получился двумерный массив. Отметим также, что при задании значения элемента массива за пределами его длины, он (массив) автоматически увеличивает свою длину. Например, если var ar = []; (пустой массив нулевой длины) и затем ar[2]=1, то теперь ar.length становится равной 3. 

0,1,2,3,4 dist=17
0,1,2,4,3 dist=23
0,1,3,2,4 dist=22
0,1,3,4,2 dist=22
0,1,4,3,2 dist=24
0,1,4,2,3 dist=30
0,2,1,3,4 dist=16
0,2,1,4,3 dist=24
0,2,3,1,4 dist=23
0,2,3,4,1 dist=24
0,2,4,3,1 dist=22
0,2,4,1,3 dist=29
0,3,2,1,4 dist=24
0,3,2,4,1 dist=30
0,3,1,2,4 dist=22
0,3,1,4,2 dist=29
0,3,4,1,2 dist=24
0,3,4,2,1 dist=23
0,4,2,3,1 dist=22
0,4,2,1,3 dist=22
0,4,3,2,1 dist=17
0,4,3,1,2 dist=16
0,4,1,3,2 dist=23
0,4,1,2,3 dist=24
Осталось переопределить функцию вычисления длины пути dist и запустить перебор (результат которого приведен справа):
function dist(ar, dists)
{
   var d = dists[0][ar[0]] + dists[ar[ar.length-1]][0]; // начало и конец
   for(var i=1; i < ar.length; i++)
      d += dists[ar[i-1]][ar[i]];                 // между ar[i-1] и ar[i]
   return d;                                      // длина пути перестановки ar
}
 
function print(ar, d){ document.write(ar, ' dist='+d+'<br>'); }
 
ar = new Array(dists.length);                     // перестановки городов 1,...,n-1
for(var i = 0; i < ar.length; i++) ar[i]=i;       // ar = [0, 1, 2, ...]
 
perm(ar, 1);                                      // запускаем перебор перестановок

Рекурсивный способ перебора всех путей (перестановок чисел) достаточно прост. Однако для больших N, поиск оптимального решения занимает очень много времени, html - страница будет "подвисать", а мы не увидим процесса вычислений. Поэтому, создадим нерекурсивную функцию получения перестановок, а затем, "включим" таймер, и в каждом его "тике" будем проводить только часть вычислений, выводя промежуточные результаты поиска кратчайшего пути.

Не рекурсивный способ

Будем порождать перестановки в лексикографическом порядке. Например: (1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1). Этот порядок означает, что перестановка (a1,a2,...,an) меньше перестановки (b1,b2,...,bn), если существует такое k ≥ 1, что все ai == bi для i < k и ak < bk. Другими словами начала перестановок совпадают и меньше та, у которой меньше первое не совпадающее число.

Алгоритм генерации перестановок в лексикографическом порядке следующий. Начинаем с последовательности (1,2,...,n). На каждом шаге, предыдущую перестановку (a1,a2,...,an) просматриваем справа налево и ищем самый правый ak, меньший следующего за ним: ak < ak+1. Затем находим наименьшее число aj, стоящее справа от ai (и большее его). Эти два числа переставляем местами и после этого переворачиваем последовательность чисел (ai+1,...,an).

Справа приведены перестановки четырёх чисел. Красным отмечено число ai, а синим - aj. С отступом выведен результат их перестановки (очевидно, что число в лексикографическом смысле стало больше, т.к. до перестановки ai < aj). Затем, всё правее красной цифры переворачивается и оказывается упорядоченным по возрастанию. Тем самым получается не просто лексикографически большая перестановка, а минимально большая (следующая).

Перейдём к реализации этого алгоритма. Введём функцию, которая генерит одну (следующую) перестановку и возвращающую true, если перестановки не закончились и false, если закончились. В дальнейшем массив ar будет содержать номера городов вдоль пути коммивояжёра. Поэтому будем переставлять числа в массиве, начиная с первого, а не нулевого элемента (там будет город 0). В общем случае, кроме массива ar в функцию передаётся номер первого lf элемента массива, который участвует в перестановке:

function permNxt(ar, lf)
{
   var  rt=ar.length-1, i=rt-1;
   while( i >= lf && ar[i] >= ar[i+1]) i--;       // ищем справа ar[i] < ar[i+1]
   if(i < lf)                                     // такого нет?
      return false;                               // перестановки окончены
 
   var j = rt;                                    // ищем ar[j],
   while(ar[i] >= ar[j]) j--;                     // наименьший справа от ar[i]
   swap(ar, i, j);                                // переставляем их местами
 
   var lf = i+1;                                  // переворачиваем последовательность
   while(lf < rt)
      swap(ar, lf++, rt--);
 
   return true;                                   // перестановки не закончились
}

Протестируем эту функцию:

var ar = [1,2,3,4];                               // массив из 4-х элементов
 
do   { document.write(ar, '<br>'); }              // печатаем массив
while( permNxt(ar, 0) );                          // пока есть перестановка

1,2,3,4
   1,2,4,3
1,2,4,3
   1,3,4,2
1,3,2,4
   1,3,4,2
1,3,4,2
   1,4,3,2
1,4,2,3
   1,4,3,2
1,4,3,2
   2,4,3,1
2,1,3,4
   2,1,4,3
2,1,4,3
   2,3,4,1
2,3,1,4
   2,3,4,1
2,3,4,1
   2,4,3,1
2,4,1,3
   2,4,3,1
2,4,3,1
   3,4,2,1
3,1,2,4
   3,1,4,2
3,1,4,2
   3,2,4,1
3,2,1,4
   3,2,4,1
3,2,4,1
   3,4,2,1
3,4,1,2
   3,4,2,1
3,4,2,1
   4,3,2,1
4,1,2,3
   4,1,3,2
4,1,3,2
   4,2,3,1
4,2,1,3
   4,2,3,1
4,2,3,1
   4,3,2,1
4,3,1,2
   4,3,2,1
4,3,2,1

JavaScript
Цикл do ... while
Перестановки выводятся в цикле do{ ... } while(условие). Он похож на цикл while(условие){ ... }, однако первая итерация выполняется в любом случае, независимо от истинности условия. Следующая итерация будет проведена, если условие (проверяемое после предыдущей итерации) оказывается истинным. Благодаря использованию такого цикла, сначала выводится стартовая последовательность 1,2,3,4, а затем в функции permNxt начинают проводиться перестановки.

Создаём таймер

Чтобы создать таймер, запускаемый нажатием кнопки, вставим в html страницу следующий код:

<input id="btnID" type="button" value="run" onclick="run(this)" style="width:4em">
<b id="outID" style="font-family:monospace; color:green;">Нажми на кнопку</b>
Первая строка создаёт кнопку (type="button") на которой написано "run" (value="run"). При нажатии на неё вызовется функция run (onClick="run(this)"), которую мы определим ниже. Кроме этого, кнопка имеет собственное имя "btnID" (id="btnID"), которое позволит "добираться" к ней из скрипта. При помощи стиля, кнопке также задаётся фиксированная ширина в 4 символа.

Вторая строка - это "жирный текст" (окружённый тегами <b>...</b>). Этот текст ("внутренность" между тегами), как и кнопка, имеет собственное имя (id="outID"). Для красоты, при помощи стиля, для текста задаётся моноширинный шрифт и зелёный цвет.

Определим функцию run, вызываемую при нажатии на кнопку:

var timerID;                                      // номер таймера
 
function run(btn)
{
   if(timerID === undefined){
      timerID = setInterval(timer, 100);          // создаём таймер на 100 ms, в timerID - его номер
      btn.value = "stop";                         // меняем надпись на кнопке
   }
   else{
      timerID = clearInterval(timerID);           // убиваем таймер, timerID будет undefined
      btn.value = "run";                          // меняем надпись на кнопке
   }
}

JavaScript
setInterval
clearInterval
В ней анализируется значение глобальной переменной timerID. Если она не определена (как есть в начале), при помощи функции setInterval создаётся таймер, который будет вызывать функцию timer (мы определим её далее) с частотой один раз в 100 ms. Затем меняется надпись на кнопке (вызывая run(this), кнопка в указателе this передаёт себя в эту функцию как объект, поэтому можно изменить любое её свойство). При повторном нажатии на кнопку сработает второй блок условного оператора if (переменная timerID уже определена и равна номеру созданного таймера). В этом блоке происходит убивание таймера функцией clearInterval. На самом деле она не возвращает значений, поэтому переменная timerID снова становится undefined и всё приходит к исходному состоянию.

Осталось написать собственно функцию timer и её окружение:

var ar = new Array(6);                            // массив из 6-ти элементов
for(var i = 0; i < ar.length; i++) ar[i]=i;       // в начале ar = 0,1,2,3,4,5
 
var count = 0;                                    // количество просмотренных перестановок
 
function timer()
{
   var num = 1;                                   // количество итераций за один "тик" таймера
   do{
      count++;                                    // тут обрабатываем перестановку
      document.getElementById('outID').innerHTML = count + ": " + ar;
   }
   while(permNxt(ar, 1) && --num);                // 0-город фиксирован, остальные меняем местами
 
   if(num){                                       // while был прерван permNxt
      timerID = clearInterval(timerID);           // убиваем таймер, timerID будет undefined
      document.getElementById('btnID').value="run"// меняем надпись на кнопке
   }
}
В этой функции num раз получается очередная перестановка (permNxt), массив которой выводится в текст тега <b>...</b> с именем outID. Доступ к этому тексту даёт функция document.getElementById, аргументом которой является поле id текста, а innerHTML - это собственно текст, который мы меняем. Если перестановок больше нет, цикл while не доберётся по переменной num до нуля. В этом случае происходит уничтожение таймера (конец вычислений) и смена надписи на кнопке. Нажав ниже на кнопку (можно несколько раз), стоит посмотреть что у нас получилось. Для перезапуска "вычислений" с самого начала, необходимо обновить страницу.

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

Воспроизводимые случайные числа

JavaScript
Math.random()
Расстояния между городами будем задавать целыми псевдослучайными числами от нуля до некоторого n (не включая его). В JavaScript объект Math предоставляет функцию Math.random(), которая возвращает вещественное случайное число в интервале [0...1), не включая 1. Поэтому, при помощи функции отбрасывания целой части floor, несложно получить целые случайные числа:
function rand(n) { return Math.floor(Math.random()*n); }
Впрочем, у этого способа есть один недостаток: последовательности случайных чисел будут различными при каждом обновлении страницы. Для воспроизводимости результатов, хотелось бы иметь генератор случайных чисел, которому можно задавать фиксированный "номер" случайной последовательности, обычно, называемый "seed" (затравка). Для этого напишем простой линейный конгруэнтный генератор (другие генераторы можно найти здесь):
var lcg = (function() {
     var z=1, a=1664525, b=1013904223, m = 4294967296; // = 2^32
  return {
     seed   : function(val)   { z = val || Math.round(Math.random() * m); },
     rand   : function(bound) { return (z = (a*z + b) % m) % bound; },
     random : function()      { return (z = (a*z + b) % m) / m; }
  };
}());
В этом коде используется ряд новых понятий, поэтому сначала покажем как пользоваться генератором:
lcg.seed(10);                                     // задаём seed 10
for(var i=50; i--; ) document.write(lcg.rand(10),',');
document.write('<br>');
lcg.seed();                                       // задаём случайный seed
for(var i=50; i--; ) document.write(lcg.rand(10),',');
3,6,5,8,5,4,5,4,3,8,7,2,7,0,3,4,1,4,9,6,3,8,9,8,9,0,9,0,1,4,9,8,1,2,5,4,5,0,9,6,1,6,7,4,3,0,1,0,3,6,
2,1,8,3,4,9,2,5,8,3,6,7,2,9,4,3,8,3,0,1,6,7,6,9,2,3,4,9,0,5,8,5,4,3,4,5,4,3,4,3,8,5,8,9,8,3,2,9,8,7,
Стоит несколько раз обновить страницу. Первая строка меняться не будет, тогда как вторая каждый раз даёт новый набор случайных чисел.

Теперь немного о сути кода. В JavaScript любая функция хранится в некоторой памяти, на которую можно получить ссылку. Например, возможен следующий скрипт:

var sqr = function(x) { return x*x; }
document.write( sqr(2) );

JavaScript
Функции как указатели
Он напечатает 4. В этом примере ссылка на память, где хранится безымянная функция возведения x в квадрат, передаётся переменной sqr. Так как JavaScript "знает", что это функция, с переменной можно обращаться как с функцией, передавая ей в круглых скобках аргумент и ожидая результата вычислений. Так, если написать var f = sqr, то f(5) даст 25, и т.д. В генераторе, в переменную lcg присваивается результат работы функции, которая возвращает объект (фигурные скобки после return). Его тремя полями (свойствами) являются указатели на три функции: seed - инициализация случайной последовательности, rand(bound) - генератор случайного целого неотрицательного числа, меньшего bound и random - генератор вещественного числа в диапазоне от 0 до 1. Хотя безымянная функция вернула результат, она сама остаётся в памяти, где также хранятся переменные z, a, b, m, доступные в функциях seed, rand и random. Тем самым реализуется механизм введения приватных (скрытых) переменных.

JavaScript
Логическое "или": a||b
В функции seed, при присвоении начального значения z, использовано логическое "или" (||). Если величина слева от него определена (есть аргумент val) и отлична от нуля, то операция || считается выполненной и её результатом будет val. В противном случае возвращается значение второго аргумента операции, которое является встроенным генератором, выдающим "случайную" затравку для последовательности. Например, 0 || 2 === 2, а 1 || 2 === 1.

Матрица расстояний

Создадим матрицу расстояний для произвольного числа городов. Для наглядности будем рассматривать метрическую задачу. Города случайным образом расположим на карте шириной w, высотой h и попарно соединим прямыми дорогами. Кроме кнопки с надписью "Создать", на html-страницу добавим 4 поля редактирования (стили опускаем):

<input type="button"  value="Создать"  onClick="create()">      <!-- кнопка запуска -->
 
<input type="text"    value="12"       id="nID">                <!-- число городов  -->
<input type="text"    value="256"      id="wID">                <!-- ширина карты   -->
<input type="text"    value="256"      id="hID">                <!-- высота карты   -->
<input type="text"    value="1"        id="seedID">             <!-- номер последовательности  -->
Доступ к полям ввода, как обычно, осуществляется по id при помощи функции document.getElementById.

Объявим следующие глобальные переменные, которые потребуются для вычислений:

var dists = [];                                   // матрица расстояний
var path  = [];                                   // путь (массив перестановок)
var minWay =[], minDist = Infinity, maxDist=0;    // лучший путь, его длина и максимальная длина
var countPath = 0;                                // число просмотренных путей
var countSol  = 0;                                // число оптимальных решений
var timerPathID;                                  // номер таймера
var timeTot, timeBest;                            // общее время и время до лучшего решения
var total;                                        // число перестановок
var pos;                                          // массив координат городов
Их уже стало многовато и в дальнейшем подобные переменные будут прятаться в объект, а все вычисления оформляться в виде класса. Константа Infinity означает наибольшее число поддерживаемое браузером. Им инициализируется кратчайший путь, в предположении, что реальные пути будут всегда короче.

Ниже приведена функция, создающая случайно расположенные города и вычисляющая евклидовы расстояния между ними:

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('seedID').value); // номер случайной последовательности
 
   pos = new Array(n);
   lcg.seed(seed);                                // инициализируем случайную последовательность
   for(var j = 0; j < n; j++)                     // для каждого города
      pos[j] = { x:lcg.rand(w), y:lcg.rand(h) };  // задаём случайное положение
 
   dists = new Array(n);                          // массив расстояний
   for(var j=0; j < n; j++)
      dists[j] = new Array(n);                    // расстояния к каждому городу от j-того
 
   for(var j = 0; j < n; j++){
      dists[j][j] = -1;                           // диагональные элементы
      for(var i = 0; i < j; i++ ){
         var dx = pos[i].x - pos[j].x;            // вычисляем евклидово расстояние
         var dy = pos[i].y - pos[j].y;
         dists[j][i] = dists[i][j] = Math.sqrt(dx*dx+dy*dy);
      }
   }
 
   minDist = Infinity; maxDist = 0;               // наименьшая и наибольшая длина пути
   countPath = 0;  countSol = 0;                  // число просмотренных путей и оптимальных решений
 
   path = new Array(dists.length);                // собственно путь
   for(var i=0; i < path.length; i++) path[i]=i;  // 0,1,2,3,...
 
   timeTot = timeBest = 0;                        // общее время и время до лучшего решения
   total = fac(n-1);                              // число перестановок (n-1)! (Recursion.html)
}

Обратим внимание, что свойство value текстового поля является строкой, поэтому к нему применяется функция Number, которая переводит строку в число. Кроме этого расстояние между городами округляется (Math.round), поэтому длина пути всегда будет целым числом.

Рисуем на канвасе

Чтобы нарисовать города и путь между ними, добавим в html-страницу тег канваса:

<canvas id="canID" width="10" height="10"></canvas>
и следующую функцию:
function show(pos, path, w, h)
{
   var canvas = document.getElementById('canID'); // получаем объект канваса
   var ctx = canvas.getContext('2d');             // у него есть свойство - контекст рисования
   var x0 = 10, y0 = 10;                          // положение левого верхнего угла карты
   canvas.width = w+2*x0; canvas.height = h+2*y0; // меняем размеры канваса (чуть больше, чем w x h)
 
   ctx.beginPath();                               // начало рисования ломаной линии
   ctx.moveTo(x0+pos[path[0]].x,y0+pos[path[0]].y)// переходим на 0-й город
   for(var i=1; i < path.length; i++)             // рисуем отрезки пути к i-тому городу
      ctx.lineTo(x0+pos[path[i]].x, y0+pos[path[i]].y);
   ctx.closePath();                               // соединяем последнюю и первую точку
   ctx.stroke();                                  // собственно рисуем линию
 
   ctx.fillStyle = '#FFA';                        // цвет заливки круга
   for(var i=0; i < pos.length; i++){
      ctx.beginPath();
      ctx.arc(x0+pos[i].x,  y0+pos[i].y, 10, 0, Math.PI*2, true);
      ctx.stroke();                              // рисуем окружность
      ctx.fill();                                // рисуем круг
   }
 
   ctx.font         = "12pt Consolas";            // моноширинный шрифт
   ctx.textAlign    = "center";                   // текст центрован по горизонтали
   ctx.textBaseline = "middle";                   // и по вертикали
   ctx.fillStyle    = '#000';                     // цвет текста
   for(var i=0; i < pos.length; i++)
      ctx.fillText(i, x0+pos[i].x, y0+pos[i].y);  // выводим текст (номер города)
}

Пример результата вызова функции приведен справа. Смысл команд рисования должен быть ясен из их названия и комментариев в коде. Сначала рисуется замкнутая ломаная линия (путь коммивояжёра). Затем - окружности городов и поверх них - номера городов. Работа с канавасом в JavaScript несколько громоздка и в дальнейшем мы будем использовать класс draw, который эту работу упрощает и одновременно позволяет получать картинки в svg-формате.

Перебор в таймере

Реализация переборного алгоритма поиска кратчайшего пути в таймере не представляет труда. Для сохранения лучшего пути в массиве minWay, напишем функцию копирования значений элементов массива src в массив des:

function  copy(des, src)
{
   if(des.length !== src.length)
      des = new Array(src.length);
   for(var i=0; i < src.length; i++)
      des[i] = src[i];
   return des;
}

JavaScript
assign
Напомним, что переменные типа строка, массив или объект являются указателями на память, где хранятся соответствующие данные. Поэтому присвоение массива типа minWay = path не приведёт к сохранению текущих значений массива path (которые всё время будут меняться). Для хранения лучшего пути, необходимо создать отдельную память и скопировать туда содержимое массива. В принципе, это можно сделать при помощи встроенного объекта Object и его метода assign следующим образом: minWay = Object.assign([], path). Первый аргумент этой функции объявляет новую память (пустой массив), в которую затем копируются данные из памяти path. Возвращает функция указатель на новую память и на неё будет ссылаться переменная minWay. Однако, в "Internet Explore" и некоторых мобильных браузерах функция assign объекта Object не определена. Поэтому мы будем пользоваться функцией copy.

Обратим внимание на ещё один момент. Функция copy возвращает ссылку на копируемый массив, которую мы присваиваем в minWay. Если это не сделать, то при первом её вызове, когда minWay=[], произойдёт выделение памяти под новый массив (в if-ниже), о чём minWay ни чего не знает. Записывая minWay = copy(minWay, path) мы устраняем эту неприятность.

Функция, вызываемая в таймере имеет вид:

function timerPath()
{
   var time =  window.performance.now();          // время в начале функции
   var num = 1000000;                             // количество итераций за один "тик" таймера
   do{
      countPath++;                                // тут обрабатываем перестановку
      var d = dist(path, dists);                  // вычисляем длину пути
 
      if(d === minDist)  countSol++;              // число оптимальных решений
      if(d < minDist){                            // нашли более короткий путь
         minDist = d;                             // запоминаем кратчайшее расстояние
         minWay = copy(minWay, path);             // запоминаем путь
         countSol = 1;                            // первое оптимальное решение
         timeBest = timeTot;                      // время до этого решения
      }
      if(d > maxDist) maxDist = d;                // запоминаем максимальное расстояние
   }
   while(permNxt(path, 1) && --num);              // пока есть перестановки и итерации
   timeTot +=  window.performance.now() - time;   // время вычислений
 
   document.getElementById('outPathID').innerHTML = "minDist: " + minDist.toFixed(2)
                           + ", path: "   + minWay
                           + "<br>time: " + timeBest.toFixed(0) + " ms, "
                           + "maxDist = " + maxDist.toFixed(2)
                           + ", countSol = " + countSol
                           + ", total: " + timeTot.toFixed(0) + " ms, "
                           + "iters: " +(100*countPath/total).toFixed(2) + "%";
 
   if(num){                                       // while был прерван permNxt
      timerPathID = clearInterval(timerPathID);   // убиваем таймер, timerPathID будет undefined
      document.getElementById('btnPathID').value="run";
   }
 
}

Результат

Ниже, при нажатии кнопки "Создать", генерится массив расстояний между городами. Их число, ширина, высота карты и "номер" последовательности можно менять. Результат представлен svg-картинкой и таблицей. Для запуска полного перебора, нажимаем на кнопку "run":

городов на карте w = , h = и seed = , показывать распределение длин

полный перебор
Нажми на кнопку

svg
01234567891011
0-2815642412391027582137156130
128-13720372111185273122128112
2156137-14717214316286195288226
34220147-262061386154134126122
4413717226-2291438641158151147
5239211143206229-29017122616885152
6102118162138143290-126184134206142
77552866186171126-112748561
882731955441226184112-186156172
91371222813415816813474186-9820
1015612882126151852068515698-79
1113011226122147152142611722079-

Распределение (в процентах) вариантов различных длин (доля путей с данной длиной):

В браузере Google Chrome, на процессоре Intel Core i5-2300 2.8 GHz, 4 Gb полный перебор занимает следующее чистое время (без учёта вывода промежуточных результатов):

N 10 11 12 13 14 15 ... 20
time, tN 41 ms 331 ms 4s 48 s 12 m 3 h ~ 600 лет
tN/tN-1 8.1 11.4 12.7 15.2 14.7

Понятно, что задача с всего лишь 20-ю городами, имеющая 6·1016 вариантов путей, методом перебора не решается и необходимо использовать другие подходы, которые будут рассмотрены в дальнейшем.

Рекурсия <
> Списки