Поиск гамильтонова цикла в большом графе (задача коммивояжера). Часть 3

В этом небольшом посте я продолжу тему, которую поднимал в своих старых двух постах

Часть 1

Часть 2

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

Так что добро пожаловать под хабракат

Старое решение

Если вы помните, или прочитали первые две части, окончательное мое решение было основано на методе ветвей и границ и хитром подборе эвристик и параметров алгоритма. Можно ли как-то заимпрувить качество работы алгоритма, добавив изменения в сам алгоритм?

Идея

Идея достаточно проста — давайте запоминать всех, с кем нам было хорошо. В стиле «любовь на века».

Что я имею под этим в виду? Давайте то решение, которое на некоем шаге казалось нам очень даже неплохим, сохранять и не выкидывать из рассмотрения, даже если после нескольких шагов оно кажется нам совсем плохим? А потом, если в какой-то момент у нас будет кризис идей и вариантов, вспомним о нем?

Теоретически, зачем это и чем нам это может помочь? Как мне кажется, это поможет избежать ситуаций, что хорошее решение, имеющее всплеск стоимости где-то вначале, будет выкинуто из рассмотрения, потому что есть много решений, которые поначалу очень дешевые, но вот под конец становятся сильно дороже. Тогда идея не забывать и не выкидывать ничего поможет нам в конце увидеть и понять, что это некое решение, дорогое вначале, в конце становится сильно дешевле.

Результаты

Я добавил эту идею в свой алгоритм. Условия были такие — если на каком-то шаге стоимость лучшего решения больше, чем на 30%, ниже остальных текущих решений, то эту ветку решения мы запоминаем. И потом, если мы видим прирост стоимости по лучшему решению достаточно большим(в моей случае это выглядело так — если на одном шаге добавляется больше 5% от суммарной стоимости лучшего решения), то мы делаем rollback, а именно откатываемся, и смотрим, а не даст ли нам сохраненный вариант решение получше.

Так или иначе, это сработало. На том же графе, на котором проверялись алгоритмы первых двух постов, я получил выигрыш 3.5% от лучшего решения.

А что вы думаете по этому поводу?

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.