Автор: Андрей
Гамильтонов цикл - это частная постановка задачи коммивояжёра. В общей постановке необходимо найти кратчайший путь, связывающий любые два узла. |
|
У меня есть забавная, но слишком сырая индейка по поводу оптимизации поиска короткого пути в произвольном неориентированном нагруженном графе между любыми двумя точками с использованием одноагентного(последовательного) вычислителя. Она может сыграть даже в решении транспортных задач, хотя в них условие неориентированности (как, впрочем, и постоянной структуры)графа в любой момент времени не применимо. К сожалению, нет пока ни полного решения ни методики оценки сложности.
Начинается алгоритм так:
1. Удаляем все петли и обособленные вершины. Называем результат нормализованным графом первого порядка. Если удалилась хотя бы одна целевая вершина, пишем, что пути нет или что путь есть, если начало и конец пути совпадают.
2. Удаляем все вершины второй степени с заменой двух рёбер на одно суммарное (что делать, если одна из вершин назначения попалась?) и кратные рёбра с заменой всех рёбер на наименьшее(а если они соединяют целевые вершины?). Обзываем граф нормальным второго порядка. Куда засунуть вершины первой степени пока не придумал. Может, не трогать их вообще.
Какой должна быть нормализация третьего порядка, быстро поймёт любой, знакомый с электротехникой.
Ну, и т.д.