@iliareznik
Начинающий

Можно ли единожды обойти все вершины связного неориентированного графа и вернуться в начальную вершину?

Какой алгоритм можно использовать для обхода всех вершин графа по одному разу с возвращением в начальную вершину.
Граф связный, неориентированный.
  • Вопрос задан
  • 168 просмотров
Пригласить эксперта
Ответы на вопрос 2
@antonksa
Можно ли обойти все вершины графа и вернуться в начальную?

Можно.
Ответ написан
wataru
@wataru
Судя по описанию, вам нужен Гамильтонов путь.

Эта задача NP-полна - следовательно, простого и быстрого алгоритма человечеству не известно. Можно делать полный перебор с отсечениями и эвристиками. Какие-нибудь методы имитации отжига или генетические алгоритмы могут работать быстрее, но это не точно и нужно долго и мучительно ковыряться, что бы оно заработало.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Big Data Solutions Санкт-Петербург
от 100 000 до 160 000 руб.
O.Vision Санкт-Петербург
от 200 000 до 280 000 руб.