[Из песочницы] Решение задачи коммивояжера с помощью метода ветвей и границ
Алгоритм состоит из двух этапов: Первый этап Приведение матрицы затрат и вычисление нижней оценки стоимости маршрута r. 1. Вычисляем наименьший элемент в каждой строке (константа приведения для строки)2. Переходим к новой матрице затрат, вычитая из каждой строки ее константу приведения3. Вычисляем наименьший элемент в каждом столбце (константа приведения для столбца)4. Переходим к новой матрице затрат, вычитая из каждого столбца его константу приведения.Как результат имеем матрицу затрат, в которой в каждой строчке и в каждом столбце имеется хотя бы один нулевой элемент.5. Вычисляем границу на данном этапе как сумму констант приведения для столбцов и строк (данная граница будет являться стоимостью, меньше которой невозможно построить искомый маршрут)Второй (основной) этап 1.Вычисление штрафа за неиспользование для каждого нулевого элемента приведенной матрицы затрат.Штраф за неиспользование элемента с индексом (h, k) в матрице, означает, что это ребро не включается в наш маршрут, а значит минимальная стоимость «неиспользования» этого ребра равна сумме минимальных элементов в строке h и столбце k.а) Ищем все нулевые элементы в приведенной матрицеб) Для каждого из них считаем его штраф за неиспользование.в) Выбираем элементы, которым соответствует максимальный штраф
2. Теперь наше множество S разбиваем на множества — содержащие ребро с максимальным штрафом (Swi) и не содержащие эти ребра (Swi/o).3. Вычисление оценок затрат для маршрутов, входящих в каждое из этих множеств.а) Для множеств Swi/o все просто: раз мы не берем соответствующее ребро c максимальным штрафом (hi, ki), то для него оценка затрат равна оценки затрат множества S + штраф за неиспользование ребра (hi, ki)б) При вычислении затрат для множества Swi примем во внимание, что раз ребро (hii, ki) входит в маршрут, то значит ребро (ki, hi) в маршрут входить не может, поэтому в матрице затрат пишем c (ki, hi)=infinity, а так как из пункта hi мы «уже ушли», а в пункт ki мы «уже пришли», то ни одно ребро, выходящее из hi, и ни одно ребро, приходящее в ki, уже использоваться не могут, поэтому вычеркиваем из матрицы затрат строку hi и столбец ki. После этого приводим матрицу, и тогда оценка затрат для Sw равна сумме оценки затрат для S и r (hi, ki), где r (hi, ki) — сумма констант приведения для измененной матрицы затрат.4. Из всех неразбитых множеств выбирается то, которое имеет наименьшую оценку.
Так продолжаем, пока в матрице затрат не останется одна не вычеркнутая строка и один не вычеркнутый столбец.
Небольшая оптимизация — подключаем эвристику
Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (hi, ki) или нет, и вешаем двух и более детей — Sw (hi, ki) и Sw/o (hi, ki). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.
