Главная Промышленная автоматика.

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

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

Пример 10.8. Вспомните задачу коммивояжера, которую мы рассмотрели в одном из предыдущих разделов. В связи с этой задачей мы описали так называемый "жадный алгоритм", позволяющий найти хороший, хотя и необязательно оптимальный, маршрут. Посмотрим, как можно было бы найти оптимальный маршрут путем систематического просмотра всех маршрутов. Это можно было бы сделать, рассмотрев все перестановки узлов и определив маршрут, который проходит через узлы в соответствующей последовательности, учитывая наилучший из найденных до сих пор маршрутов. Время, которое потребуется на реализацию такого подхода на графе с п узлами, равняется 0(п!), поскольку необходимо рассмотреть (п - 1)! различных перестановок, а оценка каждой перестановки занимает время 0(п).

Все маршруты

Маршруты с (а. Ь)

Маршруты без (а, Ь)

Маршруты с

{а. Ь) и (а, с)

Маршруты

с (а, Ь) и без (а, с)

Маршруты с (а, Ь), (а, с), но без (а, d)

Маршруты с [а, Ь) без (а. с) или (а, d)

Маршруты с

(э, Ь) и (э, d), но без (а, с)

Маршруты

с (а, с) без (а, Ь)

Маршруты без (а, Ь) и (а, с

Маршруты с

(а, с) без (а, Ь) или (а, d)

Маршруты с (а, с) и (а, d) но без (а, Ь)

Маршруты без (а, Ь). (а, с) или (а, d)

Маршрутыс (а, d) и без (а, Ь) или (а, с

Рис. 10.15. Начало дерева решений для задачи коммивояжера

Мы рассмотрим несколько иной подход, который в наихудшем случае оказывается ничуть не лучше описанного выше, однако в среднем - в сочетании с методом ветвей и границ, который мы далее кратко рассмотрим, - позволяет получить ответ

Обратите внимание: нам не нужно рассматривать все п! перестановок, поскольку исходный пункт маршрута не имеет значения. Следовательно, мы можем рассматривать только те перестановки, которые начинаются с 1.



намного быстрее, чем метод "перебора всех перестановок". Построение дерева начинается с корня, который представляет все маршруты. Маршруты соответствуют уже упоминавшимся выше "конфигурациям". Каждый узел имеет двух сыновей, и маршруты, которые представляет узел, делятся этими сыновьями на две группы: которые содержат определенное ребро и у которых такого ребра нет. Например, на рис. 10.15 показаны фрагменты дерева для задачи коммивояжера из рис. 10.11.

Будем проходить ребра дерева решений из рис. 10.15 в лексикографическом порядке: (а, Ь), (а, с), ... , (a,f), (Ь, с), ... , (b,f), (с, d) и т.д. Можно, разумеется, выбрать любой другой порядок. Учтите, что не у каждого узла в этом дереве есть два сына. Некоторых сыновей можно удалить, поскольку выбранные ребра не образуют часть маршрута. Таким образом, не сушествует узлов для маршрутов, содержащих ребра (а, Ь), (а, с) и (а, d), так как вершина а имела бы степень 3 и полученный результат не был бы маршрутом. Точно так же, спускаясь вниз по дереву, можно удалить некоторые узлы, поскольку какой-то город будет иметь степень меньше 2. Например, нет ни одного узла для маршрутов без (а, 6), (а, с), (а, d) или (а, е). П

Ограничения эвристических алгоритмов

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

Пример 10.9. Обсудим один из способов определения нижней границы для определенных совокупностей решений задачи коммивояжера, причем эти совокупности представлены узлами на дереве решений в соответствии с рис. 10.15. Прежде всего, допустим, что требуется определить нижнюю границу для всех решений данной задачи коммивояжера. Примем во внимание, что стоимость любого маршрута можно вычислить как половину суммы по всем узлам га стоимости пар ребер этого маршрута, инцидентных с узлом га. Из этого замечания можно вывести следующее правило. Сумма стоимости двух ребер, инцидентных узлу га и входящих в маршрут, не может быть меньше суммы двух ребер наименьшей стоимости, инцидентных узлу п. Таким образом, ни один из маршрутов не может стоить меньше, чем половина суммы по всем узлам я стоимости двух ребер наименьшей стоимости, инцидентных узлу га.

Рассмотрим, например, задачу коммивояжера, граф для которой представлен на рис. 10.16. В отличие от примера, показанного на рис. 10.11, здесь мера расстояний между вершинами не является евклидовой, т.е. она никоим образом не связана с расстоянием на плоскости между городами, соединенными ребром. Такой мерой стоимости может служить, например, время в пути или плата за проезд. В данном случае ребрами с наименьшей стоимостью, инцидентными узлу а, являются (а, d) и (а, Ь) с суммарной стоимостью 5. Для узла Ь такими ребрами являются (а, Ъ) и (Ь, е) с суммарной стоимостью, равной 6. Аналогично, суммарная стоимость двух ребер с наименьшей стоимостью, инцидентных узлам с, due, равняется соответственно 8, 7 и 9. Нижняя граница стоимости маршрута составит, таким образом, (5-1-6+8-1-7-Ь9)/2=17.5.

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



обусловливающее наличие этого ребра в каком-либо маршруте, необходимо включить между двумя выбранными ребрами независимо от того, имеют ли они наименьщую стоимость или стоимость, ближайщую к наименьшей/ Аналогично, ребро, на которое накладывается ограничение, исключающее его из маршрута, выбрать нельзя, даже если у него наименьщая стоимость.


Рис. 10.16. Граф для задачи коммивояжера

Таким образом, если ограничения обязывают включить в марщрут ребро (а, с) и исключить ребро (Ь, с), то двумя ребрами для узла а будут (а, а) и (а, с), общая стоимость которых равна 9. Для узла Ь мы выбираем ребра (а, Ь) и (6, с), общая стоимость которых, как и раньще, равняется 6. Для узла с мы не можем выбрать ребро (Ь, с) и поэтому выбираем ребра (а, с) и (с, d), общая стоимость которых равна 9. Для узла d мы, как и раньще, выбираем ребра (а, d) и (с, d), тогда как для узла с мы должны выбрать ребро (а, с) и еще выбираем ребро (Ь, с). Таким образом, нижняя граница при ограничениях равняется {9-i-6-i-9-i-7-i-10)/2 = 20.5. □

Построим дерево поиска вдоль путей, предложенных в примере 10.8. Как и в примере, будем рассматривать ребра в лексикографическом порядке. Каждый раз, когда есть разветвление для двух сыновей какого-либо узла, мы пытаемся принять дополнительные рещения относительно того, какие ребра необходимо включить или исключить из маршрутов, представленных соответствующими узлами. Ниже перечислены правила, которые будем использовать для принятия этих рещении.

1. Если исключение ребра (х, у) приводит к тому, что у верщины х или у нет других инцидентных ребер на данном маршруте, тогда ребро (х, у) необходимо включить.

2. Если включение ребра (х, у) приводит к тому, что у вершины х или у будет более двух ребер на данном маршруте или образуется цикл (не совпадающий с маршрутом) с ранее включенными ребрами, тогда ребро (х, у) необходимо исключить.

При разветвлении вычисляем нижние границы для обоих сыновей. Если нижняя граница для какого-нибудь из сыновей оказывается не ниже, чем у найденного на данный момент маршрута с наименьшей стоимостью, мы можем отсечь этого сына и не рассматривать его потомков. Интересно отметить, что бывают ситуации, когда нижняя граница для узла га оказывается ниже, чем наилучшее из найденных на

Правила построения дерева поиска предусматривают исключение любой совокупности ограничений, которая не позволяет получить какой-либо маршрут (например, по той причине, что этому маршруту должны принадлежать три ребра, инцидентных одному узлу).





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 [95] 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0034