Задача 14.
Следующая фигура показывает запутанную сеть дорог района города. Представьте, что мусорная машина должна пройти по всем дорогам хотя бы один раз, чтобы собрать мусор. Число на каждой стороне показывает время, которое должна потратить мусорная машина, чтобы проехать этот интервал. На перекрестках машина должна ждать время, равное числу пересекающихся дорог.
Составьте программу, показывающую как выбрать необходимый путь для сбора мусора в кратчайшее время.
Есть 11 остановок.
от 1 до 2 путь 10 мин.
от 1 до 3 4
от 1 до 4 8
от 2 до 3 8
от 2 до 5 6
от 3 до 4 4
от 3 до 5 7
от 4 до 7 7
от 4 до 6 10
от 4 до 8 7
от 8 до 6 7
от 8 до 10 6
от 10 до 6 11
от 6 до 9 4
от 10 до 9 12
от 6 до 11 5
от 6 до 4 8
от 5 до 4 8
от 4 до 11 13
от 9 до 11 5
|
Решение задачи 14.
Так как сеть дорог определяет некоторый граф, то определим в этом графе множество вершин с нечетной степенью. Понятно, что количество таких вершин четно (так как сумма степеней вершин графа четна). Определим на этом множестве взвешенный граф (граф, на ребрах которого определены веса или расстояния) по следующему правилу. Вес ребра (i,j) равен кратчайшему расстоянию между вершинами, соответствующими i и j в исходном графе. Построим в этом графе совершенное сочетание минимального веса. Паросочетанием называется множество попарно несмежных ребер (не имеющих общих вершин). Паросочетание называется совершенным, если оно покрывает все вершины. Весом паросочетания называется суммарный вес входящих в него ребер. Существуют эффективные алгоритмы поиска совершенного сочетания минимального веса. Однако они очень трудны. Поэтому при малом количестве вершин в графе можно воспользоваться перебором всех возможных совершенных паросочетаний. При добавлении к исходному графу ребер совершенного паросочетания получится граф, у которого все степени вершин четны. Найдем в нем цикл, проходящий по каждому ребру графа ровно один раз. Этот цикл и является решением задачи. Заметим при этом, что каждое ребро (i,j) паросочетания должно быть заменено последовательностью дорог исходного графа, которая определяет кратчайшее расстояние между вершинами i и j в исходном графе.
|
