Алгоритм, чтобы найти путь ко всем городам

Question

Я надеюсь, что алгоритм прямой прямой есть как решение этого, но не уверен, что называется этим типом проблемы, и поэтому, где искать решение. Это в некотором роде похоже на проблему коммивояжера, но я думаю, что это должно быть намного проще. Главным отличием проблемы является Ограниченное количество соединений (от 3 до 6 городов) между городами. Путь не нужно возвращать к началу, только то, что оно посещает каждый город только один раз. Также соединения имеют одинаковую длину, поэтому полная длина пути всегда будет одинаковой (НЕ БОЛЬШАЯ ПРОБЛЕМА РАССТОЯНИЯ). Есть 84 цитаты, и поэтому конечный путь всегда будет 87 единиц. В основном я ищу любое решение, которое может от случайного начала, добраться до всех городов только один раз. Я надеюсь на «случайное» решение, которое не будет выглядеть упорядоченным. Любые предложения о том, что называется этим типом проблемы, и где я могу найти алгоритм. Спасибо.

Answer 1

Вы ищете Hamiltonian Path. К сожалению, эта проблема NP-Complete, хотя тот факт, что вершины на вашем графике имеют ограниченную степень, с ее помощью. Дополнительную информацию о решении этой проблемы вы можете найти на связанной странице Википедии или в this answer.