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

Question

Допустим, нам дано 7 городов A, B, C, D, E, F, G, и у нас есть начальное состояние ABCDEFGA с некоторой стоимостью 'x', я не понимаю, какими будут дочерние элементы этого узла. будет ли проходить вторая итерация алгоритма восхождения на гору?

Будет ли узел ABCDEFGA, который является начальным состоянием, иметь 6 детей? Как в бы то

вторая итерация: ACBDEFGA, ADCBEFGA, AECDBFGA, AFCDEBGA, AGCDEFBA?

Третья итерация. Допустим, во второй итерации выбран ADCBEFGA, тогда будет ли третья итерация заменять город 'C' на все остальные города и т. Д.?

Я просто хотел бы знать, правильно ли я понимаю алгоритм.

Answer 1

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

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

Простая замена второго города другим городом дает вам следующее:

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

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

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

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