У вашей проблемы есть классическое название в литературе, это минимальная проблема гамильтоновой ходьбы .Остерегайтесь не путать ее с проблемой минимального гамильтонова пути, ее «двоюродным братом», потому что она намного более известна и намного, намного сложнее (найти гамильтонову блуждание можно за полиномиальное время, а найти гамильтоновый путь - NP-полная),Проблема коммивояжера - это другое название задачи о минимальном гамильтоновом пути (путь, а не прогулка).
Существует очень мало ресурсов по этой проблеме, но, тем не менее, вы можете взглянуть на статью под названием «Алгоритм нахождения короткого обходного обхода в графе», написанную Такамидзавой, Нишизеки и Сайто с 1980 года.предоставить полиномиальный алгоритм для нахождения такого пути.
Если документ немного сложен для чтения или алгоритм слишком сложен для реализации, то я предложу перейти к алгоритму christofides , потому что он работает за полиномиальное время и каким-то образом эффективен (если я хорошо помню, это 2-аппроксимация).
Другой возможный подход - использовать жадный алгоритм, как ближайший непосещенный соседАлгоритм (начните где-нибудь, перейдите к ближайшему узлу, который еще не в прогулке, повторяйте, пока все в прогулке).
На самом деле, я думаю, что самое простое и, возможно, лучшее простое решение - пойти жадным.