Том 11. Карты метро и нейронные сети. Теория графов - [12]
* * *
В предыдущем разделе мы говорили о гамильтоновых циклах — путях, которые содержат каждую вершину графа ровно один раз, причем начальная и конечная вершина этих путей совпадают. В большинстве практических задач ребрам графа соответствуют некоторые значения; это может быть стоимость перевозки, расстояние и другие параметры. Следовательно, встает вопрос о поиске цикла, для которого стоимость, время или расстояние будут наименьшими.
Почтальон хочет обойти всех адресатов так, чтобы пройти за день как можно меньше. Точно так же действуете и вы, когда планируете отпуск: вы ищете самый короткий маршрут или же более длинный, но при этом самый дешевый, и так далее. В главе 5 мы покажем, что этот вопрос является ключевым в линейном программировании.
* * *
АЛГОРИТМ БЛИЖАЙШЕГО СОСЕДА
Допустим, что А, B, С и D — города, числа на ребрах графа — расстояние между городами в километрах. Вы находитесь в городе А и можно выбрать одну из трех дорог длиной в 300 км, 500 км и 600 км. Вы выбираете ближайший город D. Из города D ведут две дороги длиной 350 и 400 км. Вы снова выбираете ближайший город, на этот раз B. Из города В вы едете в С, затем возвращаетесь в А. Этот алгоритм относится к так называемым «жадным» алгоритмам, так как мы выбираем оптимальное решение на каждом шаге: наименьшие затраты, минимальное время или расстояние (так называемый «жадный» выбор). Этот алгоритм не гарантирует, что конечное решение всегда будет оптимальным. Альтернативой является алгоритм сортировки ребер графа, который также не гарантирует оптимальность решения. В этом алгоритме на каждом шаге выбирается ребро с наименьшим весом, если они не препятствуют построению гамильтонова цикла.
* * *
Решить задачу путешественника на больших графах очень сложно. По этой причине она является классическим примером так называемых NP-полных задач, то есть задач, для которых невозможно найти «быстрый» алгоритм поиска оптимальных решений. В информатике под быстротой алгоритма понимается скорость выполнения компьютерных программ, реализующих этот алгоритм.
* * *
АЛГОРИТМ КРУСКАЛА
Джозеф Бернард Крускал (1928–2010), выпускник Принстонского университета и специалист по комбинаторике из компании Bell Laboratories, в 1950-е годы разработал замечательный алгоритм. Этот алгоритм позволяет получить минимальное остовное дерево (то есть соответствующее наименьшим общим затратам) путем последовательного добавления к нему ребер графа, упорядоченных по возрастанию веса.
* * *
Во множестве реальных ситуаций используются не обыкновенные графы, а орграфы, то есть ориентированные графы. В этих графах к ребрам добавляются стрелки, указывающие направление. Орграф, изображенный на первом рисунке снизу, может соответствовать, например, маршруту по улицам с односторонним движением. На втором рисунке снизу тот же орграф может представлять последовательность задач (А, В, С, D, Е) и порядок, в котором нужно выполнить эти задачи.
В виде орграфов можно представить энергосети, транспортные потоки, телефонные сети, схемы промышленного производства, порядок действий при ремонте и многое другое. Как можно увидеть из второго рисунка, узлы А, В, С, D, Е обозначены не точками, а кругами или прямоугольниками, внутри которых указаны задачи (разгрузка, покраска, установка и прочее), а также соответствующие им веса (1000 евро, 12 минут и так далее). На ребрах ориентированного графа, которые называются дугами, также указаны веса — это оценки затрат финансов, времени и других ресурсов, которые требуются для выполнения соответствующего действия.
Именно в таких сложных случаях требуется найти критические пути, оптимальные с точки зрения затрат или сроков. На предыдущем рисунке сумма а, Ь, е равна 34 дням, сумма а, с, d — 45 дням. Критическим путем является ABDE. Если критический путь не пройден до конца, хотя другие операции выполнены, проект не может считаться полностью завершенным.
* * *
ОПТИМИЗАЦИЯ ВРЕМЕНИ ПРЕБЫВАНИЯ САМОЛЕТОВ В АЭРОПОРТУ
Авиакомпании стремятся сократить время между приземлением и следующим взлетом самолета. После остановки самолета выполняются следующие действия:
А. Высадка пассажиров.
В. Выгрузка багажа.
С. Уборка салона.
D. Загрузка еды и напитков.
Е. Осмотр самолета.
F. Заправка горючим.
G. Загрузка нового багажа.
Н. Посадка новых пассажиров.
Некоторые из этих действий могут выполняться параллельно (например, А и В, С и D, Е и F), другие — последовательно. К примеру, С нельзя начать, пока не закончится A, G можно выполнить только после В и так далее. Завершающим действием является Н. К этому моменту действие F уже выполнено, действие
