Поиск всех циклов может быть нужен, например, когда требуется найти все циклы удовлетворяющие некому условию. При этом само это условие нельзя проверить как-то иначе, скажем выделением множества связанных вершин или еще каким-либо сокращением входного массива данных...
Для решения задачи коммивояжера и похожих задач используется, насколько мне известно симплекс метод (приближенный метод) он выдает варианты решения, но вроде бы без гарантии экстремума на них...
Других применений для задачи поиска гамильтонова цикла мне не встречалось, хотя они наверно есть в каких-то узких областях.
Спасибо всем, если я правильно понял эта задача относится к задачам класса np (поиск всех циклов в графе и поиск гамильтонова цикла). По поводу гамильтоновых циклов была информация, что есть алгоритм их поиска в книге Липского В. "Комбинаторика для программистов", но книгу найти пока не удалось... Вообще если такой алгоритм есть, то как быть с утверждением из источников по сложности алгоритмов о том, что если найдено решение одной np сложной задачи, то все остальные задачи этого класса тоже решаемы...?
И кроме того, интересно насколько решение этих задач практически значимо именно с прикладной точки зрения? Где они используются кроме непосредственно математики и прикладной логистики? Я имею ввиду прикладные химию, физику, ИТ, производство, проектирование и пр. Или всем вполне хватает тех возможностей, которые позволяют найти решения для них при малых числах вершин?
Ищутся элементарные (без повторяющихся в одном цикле вершин) циклы. Без учета циклических сдвигов, т. е. если цикл 12345 найден, то циклы 23451, 34512 искать не нужно. Можно ограничиться конечным графом. Повторюсь: интересует сам факт наличия или отсутствия такого алгоритма, случаи для которых он известен (разрешим) за конечное время. Т.е. практически применимые варианты.
Написано
Войдите на сайт
Чтобы задать вопрос и получить на него квалифицированный ответ.
Для решения задачи коммивояжера и похожих задач используется, насколько мне известно симплекс метод (приближенный метод) он выдает варианты решения, но вроде бы без гарантии экстремума на них...
Других применений для задачи поиска гамильтонова цикла мне не встречалось, хотя они наверно есть в каких-то узких областях.