Алгоритм поиска Hill Climbing Применяется к коммивояжеру

Алгоритм Hill Climbing отлично подходит для поиска локальных оптимумов и работает, изменяя небольшую часть текущего состояния, чтобы получить лучший (в данном случае более короткий) путь.

Как вы реализуете небольшие изменения, чтобы найти лучшее решение, зависит от вас. Допустим, вы хотите просто поменять местами два узла и сохранить результат, только если он лучше вашего текущего решения.

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

# first iteration
start: ABCDEFGA
next: ACBDEFGA, ADCBEFGA, AECDBFGA, AFCDEBGA, AGCDEFBA

# second iteration
start: ADCBEFGA
next: ACDBEFGA, ABCDEFGA, AECBDFGA, AFCBEDGA, AGCBEFDA

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

Вы можете переключить второй город на первой итерации, третий на вторую, четвертый на третью и т. д., но убедитесь, что вы возвращаетесь назад и продолжаете этот стиль замены и не останавливаетесь, когда дойдете до конца. Я бы предложил придерживаться одного места и поменяться местами с другим, но в конечном итоге вы получите разные неоптимальные ответы, независимо от того, как вы справитесь с этим.