Получить точное решение этой задачи труднее, чем для исходной задачи о разбиении. Если бы существовал простой способ решения задачи в общем случае, то его можно было бы использовать для решения исходной задачи. В этом случае можно было бы просто найти два подмножества, удовлетворяющих условиям, а затем проверить, совпадают ли суммы значений элементов в них.
Для решения общего случая задачи можно использовать метод ветвей и границ, примерно так же, как он использовался для решения частного случая задачи, чтобы избежать поиска по всему дереву. Можно также использовать при этом эвристический подход. Например, можно проверять элементы в порядке убывания их значения, помещая очередной элемент в подмножество с меньшей суммой значений элементов. Также можно было бы легко использовать случайный поиск, метод последовательных приближений, или метод отжига для поиска приближенного решения этого общего случая задачи.
Если задана сеть, то Гамильтоновым путем (Hamiltonian path) для нее называется путь, обходящий все узлы в сети только один раз и затем возвращающийся в начальную точку.
На рис. 8.9 показана небольшая сеть и Гамильтонов путь для нее, нарисованный жирной линией.
Задача поиска Гамильтонова пути формулируется так: если задана сеть, существует ли для нее Гамильтонов путь?
==============219
@Рис. 8.9. Гамильтонов путь
Так как Гамильтонов путь обходит все узлы в сети, то не нужно определять, какие из узлов попадают в него, а какие нет. Необходимо установить только порядок, в котором их нужно обойти для создания Гамильтонова пути.
Для моделирования этой задачи при помощи дерева, предположим, что ветви соответствуют выбору следующего узла в пути. Корневой узел тогда будет содержать N ветвей, соответствующих началу пути в каждом из N узлов. Каждый из узлов первого уровня будет иметь N – 1 ветвей, по одной ветви для каждого из оставшихся N – 1 узлов. Узлы на следующем уровне дерева будут иметь N – 2 ветвей, и так далее. Нижний уровень дерева будет содержать N! листьев, соответствующих N! возможных путей. Всего в дереве будет находиться порядка O(N!) узлов.
Каждый лист соответствует Гамильтонову пути, но число листьев может быть разным для различных сетей. Если два узла в сети не связаны друг с другом, то в дереве будут отсутствовать ветви, которые соответствуют переходам между этими двумя узлами. Это уменьшает число путей в дереве и соответственно, число листьев.
Так же, как и в задачах о выполнимости и о разбиении, для задачи поиска Гамильтонова пути нельзя получить приближенное решение. Путь может либо являться Гамильтоновым, либо нет. Это означает, что эвристический подход и метод ветвей и границ не помогут при поиске Гамильтонова пути. Что еще хуже, дерево решений для задачи поиска Гамильтонова пути содержит порядка O(N!) узлов. Это намного больше, чем порядка O(2N) узлов, которые содержат деревья решений для задач о выполнимости и разбиении. Например, 220 примерно равно 1 * 10 6, тогда как 20! составляет около 2,4 * 1018 — в миллион раз больше. Из‑за очень большого размера дерева решений задачи нахождения Гамильтонова пути, поиск в нем можно выполнить только для задач очень небольшого размера.
Задача коммивояжера (traveling salesman problem) тесно связана с задачей поиска Гамильтонова пути. Она формулируется так: найти самый короткий Гамильтонов путь для сети.
========220
Эта задача имеет примерно такое же отношение к задаче поиска Гамильтонова пути, как обобщенный случай задачи о разбиении к простой задаче о разбиении. В первом случае возникает вопрос о существовании решения. Во втором — какое приближенное решение будет наилучшим. Если бы существовало простое решение второй задачи, то его можно было бы использовать для решения первого варианта задачи.
Обычно задача коммивояжера возникает только в сетях, содержащих большое число Гамильтоновых путей. В типичном примере, коммивояжеру требуется посетить несколько клиентов, используя кратчайший маршрут. В случае обычной сети улиц, любые две точки в сети связаны между собой, поэтому любой маршрут представляет собой Гамильтонов путь. Задача заключается в том, чтобы найти самый короткий из них.
Так же как и в случае поиска Гамильтонова пути, дерево решений для этой задачи содержит порядка O(N!) узлов. Так же, как и в обобщенной задаче о разбиении, для отсечения ветвей дерева и ускорения поиска решения задач средних размеров можно использовать метод ветвей и границ.
Существует также несколько хороших эвристических методов последовательных приближений для задачи коммивояжера. Например, использование стратегии пар путей, при которой перебираются пары отрезков маршрута. Программа проверяет, станет ли маршрут короче, если удалить пару отрезков и заменить их двумя новым, так чтобы маршрут при этом оставался замкнутым. На рис. 8.10 показано как изменяется маршрут, если отрезки X1 и X2 заменить отрезками Y1 и Y2. Аналогичные стратегии последовательных приближений рассматривают замену трех или более отрезков пути одновременно.
Обычно такие шаги последовательного приближения повторяются многократно или до тех пор, пока не будут проверены все возможные пары отрезков пути. После того, как дальнейшие шаги не приводят к улучшениям, можно сохранить результат и начать работу снова, случайным образом выбрав другой исходный маршрут. После проверки достаточно большого числа различных случайных исходных маршрутов, вероятно будет найден достаточно короткий путь.
Задача о пожарных депо (firehouse problem) формулируется так: если задана сеть, некоторое число F, и расстояние D, то существует ли способ размесить F пожарных депо таким образом, чтобы все узлы сети находились не дальше, чем на расстоянии D от ближайшего пожарного депо?
@Рис. 8.10. Последовательное приближение при решении задачи коммивояжера
========221
Эту задачу можно смоделировать при помощи дерева решений, в котором каждая ветвь определяет местоположение соответствующего пожарного депо в сети. Корневой узел будет иметь N ветвей, соответствующих размещению первого пожарного депо в одном из N узлов сети. Узлы на следующем уровне дерева будут иметь N – 1 ветвей, соответствующих размещению второго пожарного депо в одном из оставшихся N – 1 узлов. Если всего существует F пожарных депо, то высота дерева решений будет равна F, и оно будет содержать порядка O(NF) узлов. В дереве будет N * (N – 1) * … * (N – F) листьев, соответствующих разным вариантам размещения пожарных депо в сети.
Так же, как и в задачах о выполнимости, разбиении, и поиске Гамильтонова пути, в этой задаче нужно дать положительный или отрицательный ответ на вопрос. Это означает, что при проверке дерева решений нельзя использовать частичные или приближенные решения.
Можно, тем не менее, использовать разновидность метода ветвей и границ, если на ранних этапах решения определить, какие из вариантов размещения пожарных депо не приводят к решению. Например, бессмысленно помещать очередное депо между двумя другими, расположенными рядом. Если все узлы на расстоянии D от нового пожарного депо уже находятся в пределах этого расстояния от другого депо, значит, новое депо нужно поместить в какое‑то другое место. Тем не менее, такого рода вычисления также отнимают достаточно много времени, и задача все еще остается очень сложной.
Так же, как и для задач о разбиении и поиске Гамильтонова пути, существует обобщенный случай задачи о пожарных депо. В обобщенном случае задача формулируется так: если задана сеть и некоторое число F, в каких узлах сети нужно поместить F пожарных депо, чтобы наибольшее расстояние от любого узла до пожарного депо было минимальным?
Так же, как и обобщенных случаях других задач, для поиска частичного и приближенного решений этой задачи можно использовать метод ветвей и границ и эвристический подход. Это несколько упрощает проверку дерева решений. Хотя дерево решений все еще остается огромным, можно по крайней мере найти приблизительные решения, даже если они и не являются наилучшими.
Во время чтения предыдущих параграфов вы могли заметить, что существует два варианта многих сложных задач. Первый вариант задачи задает вопрос: «Существует ли решение задачи, удовлетворяющее определенным условиям?». Второй, более общий случай дает ответ на вопрос: «Какое решение задачи будет наилучшим?»
Обе задачи при этом имеют одинаковое дерево решений. В первом случае дерево решений просматривается до тех пор, пока не будет найдено какое‑либо решение. Так как для этих задач не существует частичного или приближенного решения, то обычно нельзя использовать для уменьшения объема работы эвристический подход или метод ветвей и границ. Обычно всего лишь несколько путей в дереве ведут к решению, поэтому решение этих задач — очень трудоемкий процесс.
При решении же обобщенного случая задачи, часто можно использовать частичные решения и применить метод ветвей и границ. Это не облегчает поиск наилучшего решения задачи, поэтому не поможет получить точное решение для частной задачи. Например, сложнее найти самый короткий Гамильтонов путь в сети, чем найти произвольный Гамильтонов путь для той же сети.
==========222
С другой стороны, эти вопросы обычно относятся к различным входным данным. Обычно вопрос о существовании Гамильтонова пути возникает, если сеть разрежена, и сложно сказать, существует ли такой путь. Вопрос о кратчайшем Гамильтоновом пути возникает обычно, если сеть достаточно плотная и существует множество таких путей. В этом случае легко найти частичные решения, и метод ветвей и границ может сильно упростить решение задачи.