Глава 1. Введение в разработку алгоритмов
25
независимо от того, какую точку мы выберем в качестве исходной, алгоритм ближай-
шего соседа обречен на неудачу с некоторыми экземплярами задачи (т. е. с некоторы-
ми множествами точек), и нам нужно искать другой подход. Условие, заставляющее
всегда искать ближайшую точку, является
излишне ограничивающим, т. к. оно прину-
ждает нас выполнять нежелательные переходы. Задачу можно попробовать решить
другим способом — соединяя пары самых близких точек, если такое соединение не
вызывает никаких проблем, например, досрочного завершения цикла. Каждая вершина
рассматривается как самостоятельная одновершинная цепочка. Соединив все вместе,
мы
получим одну цепочку, содержащую все точки. Соединив две конечные точки, мы
получим цикл. На любом этапе выполнения этого эвристического алгоритма ближай-
ших пар у нас имеется множество отдельных вершин и не имеющих общих вершин
цепочек, которые можно соединить. Псевдокод соответствующего алгоритма показан
в листинге 1.3.
Листинг 1.3. Эвристический алгоритм ближайших пар
ClosestPair(P)
Пусть n — количество точек множества Р.
For i = 1 to n — 1 do
d = ∞
For каждой пары точек(s, t), не имеющих общих вершин цепей
if dist(s, t) ≤ d then s
m
= s, t
m
= t и d = dist(s, t)
Соединяем (s
m
,t
m
) ребром
Соединяем
две конечные точки ребром
Для экземпляра задачи, представленного на рис. 1.3, этот алгоритм работает должным
образом. Сначала точка 0 соединяется со своими ближайшими соседями, точками 1
и –1. Потом соединение следующих ближайших пар точек выполняется поочередно вле-
во-вправо, расширяя центральную часть по одному сегменту за проход. Эвристический
алгоритм ближайших пар чуть более сложный и менее эффективный, чем предыдущий,
но, по
крайней мере, для данного экземпляра задачи он дает правильный результат.
Впрочем, это верно не для всех экземпляров. Посмотрите на результаты работы алго-
ритма на рис. 1.4,
а
. Данный входной экземпляр состоит из двух рядов равномерно
расположенных точек. Расстояние между рядами (1 –
e
) несколько меньше, чем рас-
стояние между смежными точками в рядах (1 +
e
). Таким образом, пары наиболее
близких точек располагаются не по периметру, а напротив друг друга. Сперва проти-
воположные
точки соединяются попарно, а затем полученные пары соединяются по-
очередно по периметру. Общее расстояние маршрута алгоритма ближайших пар в этом
случае будет равно
2
2
3(1
) 2(1
)
(1
)
(2 2 )
− +
+ +
−
+ +
e
e
e
e
. Этот маршрут на 20% длин-
нее, чем маршрут на рис. 1.4,
б
, когда
e
≈ 0. Более того, есть входные экземпляры,
дающие значительно худшие результаты, чем этот.
Таким образом, этот алгоритм тоже не годится. Какой из этих двух алгоритмов более
эффективный? На
этот вопрос нельзя ответить, просто посмотрев на них. Но очевидно,
что оба алгоритма могут выдать очень плохие маршруты на некоторых с виду простых
входных экземплярах.
Но каков же правильный алгоритм решения этой задачи? Можно попробовать пере-
числить все возможные перестановки множества точек, а потом выбрать перестановку,