Поиск гамильтонова цикла в большом графе

1. Постановка задачи

Полный взвешенный граф из 500 вершин задан матрицей смежности.
Необходимо найти гамильтонов цикл в этом графе как можно меньшей суммарной стоимости.

2. Решение

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

Тут все просто, запускаемся из любой вершины, выбираем минимальную стоимость ребра из тех, по которым можно идти, переходим в вершину x, нашу вершину вычеркиваем, в вершине х делаем тоже самое и т.д.
Просто и быстро.
Однако ответ может быть очень и очень далеким от правды.
Жадина хорошо работает на случайном графе, однако тут мы ничего про граф не знаем.
Поэтому идем дальше.

2. Честный перебор

Задача коммивояжера, она же поиск гамильтонова цикла минимальной суммарной стоимости — NP-полная, так что полный перебор для такого графа может продлиться вечность, поэтому данная идея не подходит.

3. Метод ветвей и границ

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

Один из наиболее эффективных алгоритмов такого рода является метод ветвей и границ («поиск с возвратом», «backtracking»), разработанный Литтлом, Мерти, Суини, Кэрелом в 1963 г.

Пусть S(0) — множество всех допустимых замкнутых маршрутов задачи о коммивояжере с n городами и матрицей затрат c.
Метод Литтла основан на разбиении множества на два непересекающихся подмножества и на вычислении оценок каждого из них. Далее подмножество с минимальной оценкой (стоимостью) разбивается на два подмножества и вычисляются их оценки. На каждом шаге выбирается подмножество с наименьшей из всех полученных на этом шаге оценок и производится его разбиение на два подмножества. В конце концов получаем подмножество, содержащее один цикл (замкнутый маршрут, удовлетворяющий наложенным ограничениям), стоимость которого минимальна.

Алгоритм состоит из двух этапов:

Первый этап

Приведение матрицы затрат и вычисление нижней оценки стоимости маршрута r.

1. Вычисляем наименьший элемент в каждой строке(константа приведения для строки)
2. Переходим к новой матрице затрат, вычитая из каждой строки ее константу приведения
3. Вычисляем наименьший элемент в каждом столбце(константа приведения для столбца)
4. Переходим к новой матрице затрат, вычитая из каждого столбца его константу приведения.
Как результат имеем матрицу затрат, в которой в каждой строчке и в каждом столбце имеется хотя бы один нулевой элемент.
5. Вычисляем r как сумму констант приведения для столбцов и строк.

Второй (основной) этап

1.Вычисление штрафа за неиспользование для каждого нулевого элемента приведенной матрицы затрат.
Штраф за неиспользование означает элемента с индексом (h,k) в матрице, означает, что это ребро не включается в наш маршрут, а значит минимальная стоимость «неиспользования» этого ребра равна сумме минимальных элементов в строке h и столбце k.

а) Ищем все нулевые элементы в приведенной матрице
б) Для каждого из них считаем его штраф за неиспользование.
в) Выбираем элемент, которому соответствует максимальный штраф

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

2. Теперь наше множество S(0) разбиваем на два — Sw(содержащие ребро h,k) и Sw/o(не содержащие ребро h,k)
3. Вычисление оценок затрат для маршрутов, входящих в каждое из этих множеств.
а) Для множества Sw/o все просто: раз мы не берем ребро (h,k), то для него оценка затрат равна оценки затрат множества S(0) + штраф за неиспользование ребра (h,k)
б) При вычислении затрат для множества Sw примем во внимание, что раз ребро (h,k) входит в маршрут, то значит ребро (k,h) в маршрут входить не может, поэтому в матрице затрат пишем c(k,h)=infinity, а так как из пункта h мы «уже ушли», а в пункт k мы «уже пришли», то ни одно ребро, выходящее из h, и ни одно ребро, приходящее в k, уже использоваться не могут, поэтому вычеркиваем из матрицы затрат строку h и столбец k. После этого приводим матрицу, и тогда оценка затрат для Sw равна сумме оценки затрат для S(0) и r(h,k), где r(h,k) — сумма констант приведения для измененной матрицы затрат.
4. Из множеств Sw и Sw/o выбирается то, которое имеет наибольшую оценку.

Так продолжаем, пока в матрице затрат не останется одна невычеркнутая строка и один один невычеркнутый столбец.

Теперь результаты.
Если на каждом шаге выбирать только из двух множеств(Sw и Swo) то алгоритм работает вполне вменяемое время, однако точность просто ужасна ( проигрывает ОЧЕНЬ много жадине из п.4)

Если же на каждом шаге выбирать лучшее множество из всех, полученных к этому шагу и не использовавшихся до этого,
то для маленьких графов(порядка 40-50) вершин, получается хорошая точность, но 500 вершин дождаться не удалось.

Поэтому в голову приходит следующая идея:

4. Метод ветвей и границ с эвристикой

Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (x,y) или нет, и вешаем двух детей — Sw(x,y) и Sw/o(x,y). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.

Первый и самый простой вариант эвристики cost=mark — k*depth. k подбираем в зависимости от среднего веса ребра так, чтобы все-таки глубина не играла определяющей роли. Так же добавим, например, что depth равно минимум b, т.е. если наша вершина находиться на расстоянии q от корня, и q<b, то depth=b, иначе depth=q. В качестве b выбираем такое число, что до такой глубины честный алгоритм ветвей и границ ( без эвристики ) доходит за адекватное время. В моем случае было b=30.

Запускаем, ждем.

За ночь работы получаем ответ, который выигрывает у жадного алгоритма ~2%.
Мало, очень мало, учитывая, что жадный алгоритм работает пару секунд и пишется за 5 минут.

И теперь победитель:

Жадный алгоритм с локальным методом границ и ветвей

Алгоритм такой:

1.Запускаем жадный алгоритм, получаем некоторый маршрут.
2. Делим маршрут на несколько частей.
3.В каждой части делаем фиктивное ребро — из последней вершины маршрута в первую, которое трогать запрещается
4. На каждой из этих частей запускаем метод ветвей и границ, без эвристики.
5. Объединяем части, оптимизированные методом ветвей и границ, размыкая фиктивные ребра и соединяя последнюю вершину n-1 части с первой n части.

Как легко понять, этот алгоритм имеет несколько плюсов.

— честный метод ветвей и границ, без использования эвристики;
— легко параллелится, выигрываем во времени работы;
— жадный алгоритм говорит нам лишь части разбиений, после объединения мы используем только NUMBER_OF_PARTS-1 ребер, данных нам жадным алгоритмом, и не оптимизированных методом ветвей и границ.

Результат.
Время работы на 25 частях — 3 минуты, выигрываем у жадины ~7%
10 частей — 4 часа, выигрыш ~15%