Эвристические алгоритмы

Рассмотрим одну знаменитую задачу. Коммивояжер должен посетить N городов и возвратиться в исходный пункт, при этом требуется минимизировать общую протяженность путешествия. Переезжая из города i в город j, он преодолевает расстояние C_ij.

Эта задача коммивояжера может, например, ставиться, когда требуется определить маршрут лиц, занимающихся выемкой монет из таксофонов. Длиной дуги в этом случае может быть расстояние или время в пути между двумя таксофонами на маршруте. В общем случае матрица расстояний несимметрична, но часто рассматривают симметричную матрицу расстояний.

Для решения задачи проще всего организовать поиск в глубину на заданном графе, но это крайне трудоемко при большой размерности графа. Можно использовать метод ветвей и границ, возвращаясь всякий раз, когда длина текущего частного решения превосходит длину лучшего решения, найденного до сих пор. Эта проверка устраняет просмотр некоторых частей дерева решений, но на самом деле она достаточно слабая. Более того, произвольный фиксированный порядок городов является причиной того, что много времени теряется, например, на исследование путей, которые начинаются с маршрута 1 – 2, когда города 1 и 2 отделяет большое расстояние. Имеет смысл начинать исследование с пары ближайших городов. Но и это соображение не спасает положения, как и некоторые другие подходы в рамках метода ветвей и границ.

Для таких трудных с вычислительной точки зрения проблем один из подходов состоит в том, чтобы ослабить требование, что алгоритм должен давать оптимальный результат, и требовать лишь, чтобы результат был разумно близким к оптимальному. Ослабление ограничений на оптимальность приводит к более эффективным приближенным алгоритмам.

Часто такие алгоритмы строятся на основе некоторых разумных предложений, которые называют эвристиками, а сами алгоритмы – эвристическими. Обычно невозможно доказать, что эвристический алгоритм всегда находит решение близкое к оптимальному. Качество эвристического алгоритма проверяется на практике.

Рассмотрим некоторые эвристические алгоритмы для решения задачи коммивояжера. Наиболее известный из них - алгоритм ближайшего соседа. В качестве начальной точки произвольно выбираем один из городов. Среди всех еще не посещавшихся городов в качестве следующего выбираем ближайший к только что выбранному. Так продолжаем, пока не придем в последний город, после чего возвращаемся в исходный город. Алгоритм ближайшего соседа можно реализовать за время, пропорциональное N².

Есть более эффективные алгоритмы, использующие идеи алгоритмов Прима и Крускала построения остовного дерева графа. Алгоритм включения ближайшего города на каждом шаге добавляет город, еще не вошедший в маршрут, но ближайший к некоторому городу, уже принадлежащему маршруту. Новый город включается после того города из маршрута, который был ближайшим к нему. Этот алгоритм сложнее предыдущего, но также может быть реализован за время O(N²). Доказано, что если матрица симметрична и удовлетворяет неравенству треугольника (C_ij = C_ji и C_ij ≤ C_ik + C_kj для любых i, j, k), то найденный путь не более, чем в 2 раза длиннее оптимального.

В “жадном” алгоритме, как и в алгоритме Крускала, сначала рассматриваются самые короткие ребра. Очередное ребро принимается в том случае, если не приводит к появлению вершины со степенью 3 и более и не образует цикл, за исключением присутствия в цикле всех вершин. Совокупности ребер, выбранных в соответствии с этими критериями, образуют множества несоединенных путей. Такое положение сохраняется до последнего шага, когда единственный путь замыкается, образуя маршрут.

Рассмотрим для примера шесть “городов” A, B, C, D, E, F, заданных координатами A(0, 0), B(4, 3), C(1, 7), D(15, 7), E(15, 4), F(18, 0). Сначала выбирается ребро DE, имеющее кратчайшую длину 3. Затем включаются ребра AB, BC, EF, имеющие длину 5. Следующим кратчайшим ребром является AC, длина которого 7.08. Однако это ребро образует цикл с ребрами AB и BC, поэтому отвергается. Следующее ребро BE повышает степени вершин B и E до 3, поэтому тоже отвергается, как и ребро BD. Затем рассматривается и принимается ребро CD. Образовался путь A, B, C, D, E, F. Завершая маршрут, выбираем ребро AF.

Дата добавления: 2014-01-11