Составители:
Рубрика:
100
метод Кенига). Для крупных городов США перебором найден цикл об
лета этих городов с минимизацией времени облета.
Известна еще одна задача, очень похожая по постановке на две пре
дыдущие. Эта задача больше подходит к проблемам российской дей
ствительности. Называется она «Задача о минимальной сети дорог».
Путешествуя со студенческими строительными отрядами по Ленин
градской области, авторы встречали некоторые населенные пункты в
принципе недоступные большую часть года. Так, между городами Тих
вином и Будогощью имеется некая деревушка, в которую можно про
браться по тропинкам через болота летом, если месяц не было дождей,
или зимой, если долго стояли морозы. Да и то только на гусеничном
тракторе. В остальное время деревню можно посетить только пешком,
пробираясь с кочки на кочку через болота. Однако на большинстве карт
дорога между Будогощью и Тихвином показана как дорога республи
канского значения. Говорят, что эта ошибка сыграла хорошую служ
бу во время Великой Отечественной войны. Немцы отступали от Тих
вина в сторону Будогощи. Увидев на карте дорогу республиканского
значения, решили, что это дорога с хорошим покрытием, и взяли всю
тяжелую технику с собой. Между двумя городами вся эта техника на
вечно завязла в болотах.
Изложенные соображения приводят к новой постановке задачи для
российской действительности. Имеется n городов и заданы попарные
расстояния между ними. Построить граф типа «дерево» минимальной
суммарной длины (рис. 5.6). В отличие от предыдущих двух задач ал
горитм построения минимальной сети дорог прост и всегда приводит к
решению. Для этого нужно из таблицы попарных расстояний выбрать
минимальное расстояние и провести эту дорогу. Затем перейти к рас
смотрению следующего минимального расстояния. Если имеются два
или более минимальных расстояния, можно брать любое. На каждом
Рис 5.6. Минимальная сеть дорог
Страницы
- « первая
- ‹ предыдущая
- …
- 98
- 99
- 100
- 101
- 102
- …
- следующая ›
- последняя »
