Алгоритм Литтла - метод решения задачи коммивояжера

[hclubmk]

Прошу помощи у коммунити.
Окончательно зашел в тупик, при решении топик-задачи, хочется однозначного понимания, дает ли вышеупомянутый метод оптимальное решение, или всё таки решение данным методом правильное, но не является оптимальным.
Алгоритм брал здесь:Алгоритм Литтла (уже упоминал этот ресурс), тестировал там-же. Решая задачу, описанную здесь, получаю результат, явно не соответствующий оптимальному (как ни странно, полученному решением "жадным" методом). Контрольный пример могу привести. У кого есть возможность помочь - с меня пиво.

[Евгений Машеров]

Алгоритм Литтла даёт оптимальное решение.
Так что либо задача не та решается, либо алгоритм неверен. Во всяком случае, то, что описано по ссылке - это точно не алгоритм Литтла, хотя и "нечто по мотивам". Он вообще не "ветвей и границ", в нём ничего не ветвится и, соответственно, не нужны границы отсечения.

(Оффтоп)

Жил был на свете один добрый мальчик. И пошел он как-то в лес погулять. Ходит он, любуется деревьями, птичками и цветочками. И вдруг видит маленького ежика под кустом. Ежик был очень хилым и голодным. Стало мальчику его жалко и решил он его взять с собой. Принес его домой, напоил молоком, накормил сметаной, смастерил домик с теплой ватой и опилками. И так мальчик ухаживал тщательно и с любовью за ежиком месяц. Все что только ежику было нужно - все мальчик ему предоставил.
Но через месяц ежик стал меняться: у него отвалились иголки, вместо симпатичной мордочки отросла пасть с огромными клыками, язык вытянулся и стал раздвоенным как у змеи, ноги вытянулись и покрылись чешуей, между пальцев выросли плавательные перепонки, вырос лопатообразный хвост, как у бобра и выросли большие оперенные крылья, а на голове у него выросли оленьи рога...
Неожиданно мальчик понял, что принес он домой не ежика, а ФИГ ЗНАЕТ ЧТО!

Вот более вменяемое описание
http://www.lib.tsu.ru/mminfo/000349342/ ... 20-078.pdf

[hclubmk]

Спасибо,пошел учиться

[Евгений Машеров]

Очень краткое и поверхностное описание алгоритма:
Это метод класса "ветвей и границ". То есть в нём делаются ветвления, в данном случае выбирается включать ли в маршрут переход i->j или не включать, что порождает две ветви, которые затем тоже делятся, и в худшем случае число ветвей растёт экспоненциально, но при этом для каждой ветви строится оценка "снизу", и если она оказывается хуже уже достигнутого решения, данная ветка сразу исключается без дальнейшего ветвления. Обход делается так, чтобы быстро получить некое "хорошее" решение, что позволит исключать ветки, для которых оценка хуже. В качестве оценки используется сумма минимальных значений по строкам и минимальных (после вычитания минимума по строкам) значений по столбцам, поскольку при любом обходе меньше названной величины не получится. Для поиска "хорошего" решения используется некоторая эвристика: для включения в обход выбирается тот элемент, для которого сумма минимумов в содержащих его строке и столбце максимальна (то есть если на самом деле надо было включать другой элемент, то его вклад будет не меньше этой суммы, так что если она максимальна, то шанс, что надо было брать иной нулевой элемент - минимален). Выбрав такой элемент - ветвимся, одна ветвь с переходом i->j, в ней мы можем сразу убрать всю i-тую строку и j-тый столбец, а также запретить переход j->i, вторая ветвь - в которой запрещён только переход i->j. Обход делаем "в глубину", всё время выбирая левую ветвь, пока не получим допустимое (и, надеемся, хорошее) решение, а потом начинаем обходить остаток дерева, отсекая те ветви, где оценка хуже уже достигнутого решения, а где получено решение лучше достигнутого ("рекорда") - используем новый "рекорд". Пока всё дерево не обойдём - не будем уверены в том, что нашли оптимум.
Алгоритм, который по Вашей ссылке - часть настоящего. Собственно, это движение по одной ветке в глубину, а отсечения и перебора не видать.

[hclubmk]

Евгений Машеров
Большое спасибо за разъяснения и потраченное время. Буду разбираться, поскольку решение действительно необходимо. По результату разбирательства отпишусь здесь, или буду докучать вопросами...
Ещё раз спасибо.

[Евгений Машеров]

Да, и вдогонку.
Запрет делается присвоением данному переходу "бесконечной стоимости" (обычно используют не IEEE-шный +INF, а просто очень большое, заведомо большее всех стоимостей реальных переходов число).
В связи с этим вызывает сомнение рекомендация в алгоритме по Вашей ссылке - вычислять длину пути i->j и её принимать за значение для запрета. Вообще совершенно неадекватное описание алгоритма (и возникает сомнения в том, что прочие алгоритмы на сайте изложены без фатальных ошибок).

[hclubmk]

Да, теперь понятно, что ветвление не реализовано во взятом за основу алгоритме, и обход велся только по левой ветви.
В приведенном примере, к сожалению, не встретился момент, когда оценочное значение 2-й (правой) ветви будет предпочтительнее, чем левой. Не ясно, что делать, если на n-ом шаге в матрице, после запрета i->j перехода, оценочное значение будет меньше ,а следовательно - предпочтительнее (оно ведь может быть меньше, иначе теряется суть обхода по правой ветви). Нужно вернуться к (n-1)-му шагу, i->j переход не включать в порядок обхода, а искать новый (при этом оставляя запрет i->j перехода)?
Если что-то не то говорю, уж не взыщите...

[Евгений Машеров]

Сравнивать надо не оценочные значения ветвей, левой и правой, а оценочное значение каждой ветви с рекордом. Если для данной ветви оценочное значение лучше рекорда (если хуже - её сразу можем "зарубить"), то, идя по этой ветви далее, мы можем придти к лучшему решению, а можем и не придти. То есть по ней надо ветвиться. Опять выбирать включаемый переход k->l и делать две ветки - с включением его и с запретом. И так далее.
Обычный обход дерева, поиск в глубину. Просто надо обходить не все мыслимые ветви дерева, некоторые удаётся обрубить без ветвления. Но если оснований рубить нет, оценка для этой ветви лучше рекорда, то рубить мы не вправе. Надо ветвиться, в надежде найти лучшее решение (и уточнить рекорд) или обрубить плохие ветки (в худшем случае - обойти всё дерево).

[hclubmk]

Хорошо. Предположим, запретив переход i->j в правой ветви, вычисляем оценочное значение, и оно лучше рекорда. Каким образом будет строиться обход этой ветви?

[Евгений Машеров]

Точно так же. Поскольку оценка лучше рекорда, зарубить ветку сразу мы не может. Поэтому её ветвим. Точно так же находим кандидата на ветвление k->l, и строим две подветки - в одной путь k->l используется, в другой запрещён. И так далее.

[Евгений Машеров]

Могу подкинуть популярную книжку Мудрова (из "Знаниевской" серии брошюр), где довольно подробно расписаны шаги. Куда бросать?

-- 26 авг 2014, 11:10 --

Ну, или есть:
Введение в прикладное дискретное программирование.Модели и вычислительные алгоритмы Сигал И.Х., Иванова А.П.
Тоже подробно расписано.

[hclubmk]

[e-mail]
будет здорово получить подробное рассмотрение хоть нескольких примеров с ветвлением и по правой части дерева.
Спасибо, буду ждать.

[Евгений Машеров]

Отправлено.

[hclubmk]

Это было увлекательно!
Хочу поблагодарить за книги и за подсказки - видно, что Вы - практик.
Мудров очень подробно и доступно описывает методику - хорошая книга, вероятно, ещё кому-то может пригодиться, с Вашего позволения оставлю на нее ссылку
Пришлось, конечно, повозиться с не рекуррентным обходом графа, но это уже не так важно. Метод действительно работает замечательно, как при замкнутом контуре, так и с обозначенными начальной и конечной точкой маршрута. (Конечную точку задаю запретом переходов из нее в любую другую, кроме начальной).
Ну и пара рассчитанных маршрутов как результат реализации метода: замкнутый, разомкнутый
Ещё раз благодарю за содействие.

И, да, я неловко себя чувствую... Куда высылать пиво?

[Евгений Машеров]

Откуда высылать-то собираетесь?