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