|
VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программированияПри поиске методом ветвей и границ число проверяемых узлов намного меньше, чем при полном переборе. Дерево решений для задачи портфеля с 20 позициями содержит 2.097.151 узел. При полном переборе придется проверить их все, при поиске методом ветвей и границ понадобится проверить только примерно 1.500 из них. @Рис. 8.7. Программа BindB ======200 Число узлов, которые проверяет программа при использовании метода ветвей и границ, зависит от точных значений данных. Если цена позиций высока, то в правильное решение будет входить немного элементов. После помещения нескольких позиций в пробное решение, оставшиеся позиции слишком дорого стоят, чтобы поместиться в портфеле, потому большая часть дерева будет отсечена. С другой стороны, если элементы имеют низкую стоимость, то в правильное решение войдет большое их число, поэтому программе придется исследовать множество комбинаций. В табл. 8.2 приведено число узлов, проверенное программой BindB в серии тестов при различной стоимости позиций. Программа создавала 20 случайных позиций, и полная стоимость решения была равна 100. Эвристики Иногда даже алгоритм ветвей и границ не может провести полный поиск в дереве. Дерево решений для задачи портфеля с 65 позициями содержит более 7 * 1019 узлов. Если алгоритм ветвей и границ проверяет только одну десятую процента этих узлов, и если компьютер проверяет миллион узлов в секунду, то для решения этой задачи потребовалось бы более 2 миллионов лет. В задачах, для которых алгоритм ветвей и границ выполняется слишком медленно, можно использовать эвристический подход. Если качество решения не так важно, то приемлемым может быть результат, полученный при помощи эвристики. В некоторых случаях точность входных данных может быть недостаточной. Тогда хорошее эвристическое решение может быть таким же правильным, как и теоретически «наилучшее» решение. В предыдущем примере метод ветвей и границ использовался для выбора инвестиционных возможностей. Тем не менее, вложения могут быть рискованными, и точные результаты часто заранее неизвестны. Может быть, что заранее будет неизвестен точный доход или даже стоимость некоторых инвестиций. В этом случае, эффективное эвристическое решение может быть таким же надежным, как и наилучшее решение, которое вы может вычислить точно. @Таблица 8.2. Число узлов, проверенных при поиске методами полного перебора и ветвей и границ =======201 В этом разделе обсуждаются эвристики, которые полезны при решении многих сложных задач. Программа Heur демонстрирует каждую из эвристик. Она также позволяет сравнить результаты, полученные при помощи эвристик и методов полного перебора и ветвей и границ. Введите значения минимальной и максимальной стоимости и дохода, а также число позиций и полную стоимость портфеля в соответствующих полях области Parameters (Параметры), чтобы задать параметры создаваемых данных. Затем выберите алгоритмы, которые вы хотите протестировать, и нажмите на кнопку Go. Программа выведет полную стоимость и доход для наилучшего решения, найденного при помощи каждого из алгоритмов. Она также сортирует решения по максимальному полученному доходу и выводит время выполнения для каждого из алгоритмов. Используйте метод ветвей и границ только для небольших задач, а метод полного перебора только для задач еще меньшего объема. На рис. 8.8 показано окно программы Heur после решения задачи формирования портфеля для 20 позиций. Эвристики Fixed1, Fixed2 и No Changes 1, которые будут вскоре описаны, дали наилучшие эвристические решения. Заметьте, что эти решения немного хуже, чем точные решения, которые получены при использовании метода ветвей и границ. Восхождение на холм Эвристика восхождения на холм (hill-climbing) вносит изменения в текущее решение, чтобы максимально приблизить его к цели. Этот процесс называется восхождением на холм, так как он похож на то, как заблудившийся путешественник пытается ночью добраться до вершины горы. Даже если уже слишком темно, чтобы еще можно было разглядеть что-то вдали, путешественник может попытаться добраться до вершины горы, постоянно двигаясь вверх. Конечно, существует вероятность, что путешественник застрянет на вершине меньшего холма и не доберется до пика. Эта проблема всегда может возникать при использовании этой эвристики. Алгоритм может найти решение, которое может оказаться локально приемлемым, но это не обязательно наилучшее возможное решение. В задаче о формировании портфеля, цель заключается в том, чтобы подобрать набор позиций, полная стоимость которых не превышает заданного предела, а общая цена максимальна. На каждом шаге эвристика восхождения на холм будет выбирать позицию, которая приносит наибольшую прибыль. При этом решение будет все лучше соответствовать цели — получению максимальной прибыли. @Рис. 8.8. Программа Heur ========202 Вначале программа добавляет к решению позицию с максимальной прибылью. Затем она добавляет следующую позицию с максимальной прибылью, если при этом полная цена еще остается в допустимых пределах. Она продолжает добавлять позиции с максимальной прибылью до тех пор, пока не останется позиций, удовлетворяющих условиям. Для списка инвестиций из табл. 8.3, программа вначале выбирает позицию A, так как она дает максимальную прибыль — 9 миллионов долларов. Затем программа выбирает следующую позицию C, которая дает прибыль 8 миллионов. В этот момент потрачены уже 93 миллиона из 100, и программа не может приобрести больше позиций. Решение, полученное при помощи эвристики, включает позиции A и C, имеет стоимость 93 миллиона, и приносит 17 миллионов прибыли. @Таблица 8.3. Возможные инвестиции Эвристика восхождения на холм заполняет портфель очень быстро. Если позиции изначально были отсортированы в порядке убывания приносимой прибыли, то сложность этого алгоритма порядка O(N). Программа просто перемещается по списку, добавляя каждую позицию, если под нее есть место. Даже если список не упорядочен, то это алгоритм со сложностью порядка O(N2). Это намного лучше, чем O(2N) шагов, которые требуются для полного перебора всех узлов в дереве. Для 20 позиций эта эвристика требует всего около 400 шагов, метод ветвей и границ — несколько тысяч, а полный перебор — более чем 2 миллиона. Public Sub HillClimbing() Dim i As Integer Dim j As Integer Dim big_value As Integer Dim big_j As Integer ' Многократный обход списка и поиск следующей ' позиции, приносящей наибольшую прибыль, ' стоимость которой не превышает верхней границы. For i = 1 To NumItems big_value = 0 big_j = -1 For j = 1 To NumItems ' Проверить, не находится ли он уже ' в решении. If (Not test_solution(j)) And _ (test_cost + Items(j).Cost Items(j).Cost) Then small_cost = Items(j).Cost small_j = j End If Сбалансированная прибыль Стратегия восхождения на холм не учитывает стоимость добавляемых позиций. Она выбирает позиции с максимальной прибылью, даже если их стоимость велика. Стратегия наименьшей стоимости не учитывает приносимую позицией прибыль. Она выбирает позиции с низкой стоимостью, даже если они приносят мало прибыли. Эвристика сбалансированной прибыли (balanced profit) сравнивает при выборе стоимость позиций и приносимую ими прибыль. На каждом шаге эвристика выбирает позицию с наибольшим отношением прибыль-стоимость. В табл. 8.4 приведены те же данные, что и в табл. 8.3, но в ней добавлена еще одна колонка с отношением прибыль-стоимость. При этом подходе вначале выбирается позиция C, так как она имеет максимальное соотношение прибыль- стоимость — 0,27. Затем к решению добавляется позиция D с отношением 0,26, и позиция B с отношением 0,20. В этой точке, будет потрачено 92 миллиона из 100 возможных, и в решение нельзя будет добавить больше ни одной позиции. Решение будет иметь стоимость 92 миллиона и давать 22 миллиона прибыли. Это на 4 миллиона лучше, чем решение с наименьшей стоимостью и на 5 миллионов лучше, чем решение методом восхождения на холм. В этом случае, это будет также наилучшим возможным решением, и его также можно найти полным перебором или методом ветвей и границ. Метод сбалансированной прибыли тем не менее, является эвристическим, поэтому он не обязательно находит наилучшее возможное решение. Он часто находит лучшее решение, чем методы наименьшей стоимости и восхождения на холм, но это не обязательно так. @Таблица 8.4. Возможные инвестиции с соотношением прибыль-стоимость =========205 Структура программы, реализующей эвристику сбалансированной прибыли, почти идентична структуре программ для восхождения на холм и наименьшей стоимости. Единственное отличие заключается в методе выбора следующей позиции, которая добавляется к решению: If (Not test_solution(j)) And _ (test_cost + Items(j).Cost best_profit Then best_profit = test_profit best_cost = test_cost For i = 1 To NumItems best_solution(i) = test_solution(i) Next i End If ' Сбросить пробное решение и сделать еще одну попытку. test_profit = 0 test_cost = 0 For i = 1 To NumItems test_solution(i) = False Next i Next trial End Sub Private Function AddToSolution() As Boolean Dim num_left As Integer Dim j As Integer Dim selection As Integer ' Определить, сколько осталось позиций, которые ' удовлетворяют ограничению максимальной стоимости. num_left = 0 For j = 1 To NumItems If (Not test_solution(j)) And _ (test_cost + Items(j).Cost trial_profit Then ' Сохранить изменения. trial_profit = test_profit trial_cost = test_cost For i = 1 To NumItems trial_solution(i) = test_solution(i) Next i Else ' Сбросить пробное решение. test_profit = trial_profit test_cost = trial_cost For i = 1 To NumItems test_solution(i) = trial_solution(i) Next i End If Next change ' Если пробное решение лучше предыдущего ' наилучшего решения, сохранить его. If trial_profit > best_profit Then best_profit = trial_profit best_cost = trial_cost For i = 1 To NumItems best_solution(i) = trial_solution(i) Next i End If ' Сбросить пробное решение для ' следующей попытки. test_profit = 0 test_cost = 0 For i = 1 To NumItems test_solution(i) = False Next i Next trial End Sub Private Sub RemoveFromSolution() Dim num_in_solution As Integer Dim j As Integer Dim selection As Integer ' Определить число позиций в решении. num_in_solution = 0 For j = 1 To NumItems If test_solution(j) Then num_in_solution = num_in_solution + 1 Next j If num_in_solution < 1 Then Exit Sub ' Выбрать случайную позицию. selection = Int((num_in_solution) * Rnd + 1) ' Найти случайно выбранную позицию. For j = 1 To NumItems If test_solution(j) Then selection = selection - 1 If selection < 1 Then Exit For End If Next j ' Удалить позицию из решения. test_profit = test_profit - Items(j).Profit test_cost = test_cost - Items(j).Cost test_solution(j) = False End Sub ======209-210 Другая стратегия заключается в том, чтобы вносить изменения до тех пор, пока несколько последовательных изменений не приносят улучшений. Для задачи с N позициями, программа может вносить изменения до тех пор, пока в течение N изменений подряд улучшений не будет. Эта стратегия реализована в подпрограмме MakeChangesNoChange программы Heur. Она повторяет попытки до тех пор, пока определенное число последовательных попыток не даст никаких улучшений. Для каждой попытки она вносит случайные изменения в пробное решение до тех пор, пока после определенного числа изменений не наступит никаких улучшений. Public Sub MakeChangesNoChange(K As Integer, _ max_bad_trials As Integer, max_non_changes As Integer) Dim i As Integer Dim removal As Integer Dim bad_trials As Integer ' Неэффективных попыток подряд. Dim non_changes As Integer ' Неэффективных изменений подряд. ' Повторять попытки, пока не встретится max_bad_trials ' попыток подряд без улучшений. bad_trials = 0 Do ' Выбрать случайное пробное решение для ' использования в качестве начальной точки. Do While AddToSolution() ' All the work is done by AddToSolution. Loop ' Начать с этого пробного решения. trial_profit = test_profit trial_cost = test_cost For i = 1 To NumItems trial_solution(i) = test_solution(i) Next i ' Повторять, пока max_non_changes изменений ' подряд не даст улучшений. non_changes = 0 Do While non_changes < max_non_changes ' Удалить K случайных позиций. For removal = 1 To K RemoveFromSolution Next removal ' Вернуть максимально возможное число позиций. Do While AddToSolution() ' All the work is done by ' AddToSolution. Loop ' Если это улучшает пробное значение, сохранить его. ' Иначе вернуть прежнее значение пробного решения. If test_profit > trial_profit Then ' Сохранить улучшение. trial_profit = test_profit trial_cost = test_cost For i = 1 To NumItems trial_solution(i) = test_solution(i) Next i non_changes = 0 ' This was a good change. Else ' Reset the trial. test_profit = trial_profit test_cost = trial_cost For i = 1 To NumItems test_solution(i) = trial_solution(i) Next i non_changes = non_changes + 1 ' Плохое изменение. End If Loop ' Продолжить проверку случайных изменений. ' Если эта попытка лучше, чем предыдущее наилучшее ' решение, сохранить его. If trial_profit > best_profit Then best_profit = trial_profit best_cost = trial_cost For i = 1 To NumItems best_solution(i) = trial_solution(i) Next i bad_trials = 0 ' Хорошая попытка. Else bad_trials = bad_trials + 1 ' Плохая попытка. End If ' Сбросить тестовое решение для следующей попытки. test_profit = 0 test_cost = 0 For i = 1 To NumItems test_solution(i) = False Next i Loop While bad_trials < max_bad_trials End Sub Локальные оптимумы Если программа заменяет случайно выбранную позицию в пробном решении, то может встретиться решение, которое она не может улучшить, но которое при этом не будет наилучшим из возможных решений. Например, рассмотрим список инвестиций, приведенный в табл. 8.5. Предположим, что алгоритм случайно выбрал позиции A и B в качестве начального решения. Его стоимость будет равно 90 миллионам долларов, и оно принесет 17 миллионов прибыли. Если программа удалит позиции A и B, то стоимость решения будет все еще настолько велика, что программа сможет добавить всего лишь одну позицию к решению. Так как наибольшую прибыль приносят позиции A и B, то замена их другими позициями уменьшит суммарную прибыль. Случайное удаление одной позиции из этого решения никогда не приведет к улучшению решения. Наилучшее решение содержит позиции C, D и E. Его полная стоимость равно 98 миллионам долларов и суммарная прибыль составляет 18 миллионов долларов. Чтобы найти это решение, алгоритму бы понадобилось удалить из решения сразу обе позиции A и B и затем добавить на их место новые позиции. Решения такого типа, для которых небольшие изменения решения не могут улучшить его, называются локальным оптимумом (local optimum). Можно использовать два способа для того, чтобы программа не застревала в локальном оптимуме, и могла найти глобальный оптимум (global optimum). @Таблица 8.5. Возможные инвестиции =============213 Во-первых, можно изменить программу так, чтобы она удаляла более одной позиции во время случайных изменений. В этом примере, программа могла бы найти правильное решение, если бы она одновременно удаляла бы по две случайно выбранных позиции. Тем не менее, для задач большего размера, удаления двух позиций может быть недостаточно. Программе может понадобиться удалять три, четыре, или больше позиций. Второй, более простой способ заключается в том, чтобы делать больше попыток, начиная с разных начальных решений. Некоторые из начальных решений будут приводить к локальным оптимумам, но одно из них позволит достичь глобального оптимума. Программа Heur демонстрирует три стратегии последовательных приближений. При выборе метода Fixed 1 (Фиксированный 1) делается N попыток. Во время каждой попытки выбирается случайно решение, которое программа затем пытается улучшить за 2 * N попыток, случайно удаляя по одной позиции. При выборе эвристики Fixed 2 (Фиксированный 2)делается всего одна попытка. При этом программа выбирает случайное решение и пытается улучшить его, случайным образом удаляя по одной позиции до тех пор, пока в течение N последовательных изменений не будет никаких улучшений. При выборе эвристики No Changes 1 (Без изменений 1) программа выполняет попытки до тех пор, пока после N последовательных попыток не будет никаких улучшений. Во время каждой попытки программа выбирает случайное решение и затем пытается улучшить его, случайным образом удаляя по одной позиции до тех пор, пока в течение N последовательных изменений не будет никаких улучшений. При выборе эвристики No Changes 2 (Без изменений 2)делается одна попытка. При этом программа выбирает случайное решение и пытается улучшить его, случайным образом удаляя по две позиции до тех пор, пока в течение N последовательных изменений не будет никаких улучшений. Названия эвристик и их описания приведены в табл. 8.6. Алгоритм «отжига» Метод отжига (simulated annealing) ведет свое начало из термодинамики. При отжиге металла он нагревается до высокой температуры. Молекулы в нагретом металле совершают быстрые колебания, а при медленном остывании они начинают располагаться упорядоченно, образуя кристаллы. При этом молекулы постепенно переходят в состояние с минимальной энергией. @Таблица 8.6. Стратегии последовательных приближений ===========214 При медленном остывании металла, соседние кристаллы сливаются друг с другом. Молекулы в одном из кристаллов покидают состояние с минимальной энергией и принимают порядок молекул в другом кристалле. Энергия получившегося кристалла большего размера будет меньше, чем сумма энергий двух исходных кристаллов. Если охлаждение происходит достаточно медленно, то кристаллы становятся очень большими. Окончательное распределение молекул представляет состояние с очень низкой энергией, и металл при этом будет очень твердым. Начиная с состояния с высокой энергией, молекулы в конце концов достигают состояния с очень низкой энергией. На пути к конечному положению, они проходят множество локальных минимумов энергии. Каждое сочетание кристаллов образует локальный минимум. Кристаллы могут объединяться друг с другом только за счет временного повышения энергии системы, чтобы затем перейти к состоянию с меньшей энергией. Метод отжига использует аналогичный подход для поиска наилучшего решения задачи. Во время поиска решения программой, она может застрять в локальном оптимуме. Чтобы избежать этого, программа время от времени вносит в решение случайные изменения, даже если очередное изменение и не приводит к мгновенному улучшению результата. Это может помочь программе выйти из локального оптимума и отыскать лучшее решение. Если это изменение не ведет к лучшему решению, то вероятно, через некоторое время программа его отбросит. Чтобы эти изменения не возникали постоянно, алгоритм изменяет вероятность возникновения случайных изменений со временем. Вероятность P возникновения одного из подобных изменений определяется формулой P = 1 / Exp(E / (k * T)), где E — увеличение «энергии» системы, k — некоторая постоянная, и T — переменная, соответствующая «температуре». Вначале температура должна быть высокой, поэтому и вероятность изменений P = 1 / Exp(E / (k * T)) также достаточно велика. Иначе случайные изменения могли бы никогда не возникнуть. С течением времени значение переменной T постепенно снижается, и вероятность случайных изменений также уменьшается. После того, как модель дойдет до точки, в которой она никакие изменения не смогут улучшить решение, и температура T станет достаточно низкой, чтобы вероятность случайных изменений была мала, алгоритм заканчивает работу. Для задачи о формирования портфеля, в качестве прибавки «энергии» E выступает уменьшение прибыли решения. Например, при удалении позиции, которая дает прибыль 10 миллионов, и замене ее на позицию, которая приносит 7 миллионов прибыли, энергия, добавленная к системе, будет равна 3. Заметьте, что если энергия велика, то вероятность изменений P = 1 / Exp(E / (k * T)) мала, поэтому вероятность больших изменений ниже. Алгоритм отжига в программе Heur устанавливает значение постоянной k равным разнице между наибольшей и наименьшей прибылью возможных инвестиций. Начальная температура T задается равной 0,75. После выполнения определенного числа случайных изменений, температура T уменьшается умножением на постоянную 0,95. =========215 Public Sub AnnealTrial(K As Integer, max_non_changes As Integer, _ max_back_slips As Integer) Const TFACTOR = 0.95 Dim i As Integer Dim non_changes As Integer Dim t As Double Dim max_profit As Integer Dim min_profit As Integer Dim doit As Boolean Dim back_slips As Integer ' Найти позицию с минимальной и максимальной прибылью. max_profit = Items(1).Profit min_profit = max_profit For i = 2 To NumItems If max_profit < Items(i).Profit Then max_profit = Items(i).Profit If min_profit > Items(i).Profit Then min_profit = Items(i).Profit Next i t = 0.75 * (max_profit - min_profit) back_slips = 0 ' Выбрать случайное пробное решение ' в качестве начальной точки. Do While AddToSolution() ' Вся работа выполняется в процедуре AddToSolution. Loop ' Использовать в качестве пробного решения. best_profit = test_profit best_cost = test_cost For i = 1 To NumItems best_solution(i) = test_solution(i) Next i ' Повторять, пока в течение max_non_changes изменений ' подряд не будет улучшений. non_changes = 0 Do While non_changes < max_non_changes ' Удалить случайную позицию. For i = 1 To K RemoveFromSolution Next i ' Добавить максимально возможное число позиций. Do While AddToSolution() ' Вся работа выполняется в процедуре AddToSolution. Loop ' Если изменение улучшает пробное решение, сохранить его. ' Иначе вернуть прежнее значение решения. If test_profit > best_profit Then doit = True ElseIf test_profit < best_profit Then doit = (Rnd < Exp((test_profit - best_profit) / t)) back_slips = back_slips + 1 If back_slips > max_back_slips Then back_slips = 0 t = t * TFACTOR End If Else doit = False End If If doit Then ' Сохранить улучшение. best_profit = test_profit best_cost = test_cost For i = 1 To NumItems best_solution(i) = test_solution(i) Next i non_changes = 0 ' Хорошее изменение. Else ' Reset the trial. test_profit = best_profit test_cost = best_cost For i = 1 To NumItems test_solution(i) = best_solution(i) Next i non_changes = non_changes + 1 ' Плохое изменение. End If Loop ' Продолжить проверку случайных изменений. End Sub Сравнение эвристик Различные эвристики по-разному ведут себя в различных задачах. Для задачи о формировании портфеля, эвристика сбалансированной прибыли работает достаточно хорошо, учитывая ее простоту. Стратегии последовательного приближения обычно дают сравнимые результаты, но для больших задач их выполнение занимает намного больше времени. Для других задач наилучшей может быть какая-либо другая эвристика, в том числе из тех, которые не обсуждались в этой главе. ========216-217 Эвристические методы обычно выполняются быстрее, чем метод ветвей и границ. Некоторые из них, например методы восхождения на холм, наименьшей стоимости и сбалансированной прибыли, выполняются очень быстро, так как они рассматривают только одно возможное решение. Они выполняются настолько быстро, что имеет смысл выполнить их все по очереди, и затем выбрать наилучшее из трех полученных решений. Это не гарантирует того, что это решение будет наилучшим, но дает некоторую уверенность, что оно окажется достаточно хорошим. Другие сложные задачи Существует множество очень сложных задач, большинство из которых не имеет решений с полиномиальной вычислительной сложностью. Другими словами, не существует алгоритмов, которые решали бы эти задачи за время порядка O(NC) для любых постоянных C, даже за O(N1000). В следующих разделах кратко описаны некоторые из этих задач. В них также показано, почему они являются сложными в общем случае и насколько большим может оказаться дерево решений задачи. Вы можете попробовать применить метод ветвей и границ или эвристики для решения некоторых из этих задач. Задача о выполнимости Если имеется логическое утверждение, например “(A And Not B) Or C”, то существуют ли значения переменных A, B и C, при которых это утверждение истинно? В данном примере легко увидеть, что утверждение истинно, если A = true, B = false и C = false. Для более сложных утверждений, содержащих сотни переменных, бывает достаточно сложно определить, может ли быть утверждение истинным. При помощи метода, похожего на тот, который использовался при решении задачи о формировании портфеля, можно простроить дерево решений для задачи о выполнимости (satisfiability problem). Каждая ветвь дерева будет соответствовать решению о присвоении переменной значения true или false. Например, левая ветвь, выходящая из корня, соответствует значению первой переменной true. Если в логическом выражении N переменных, то дерево решений представляет собой двоичное дерево высотой N + 1. Это дерево имеет 2N листьев, каждый из которых соответствует разной комбинации значений переменных. В задаче о формировании портфеля можно было использовать метод ветвей и границ для того, чтобы избежать поиска в большей части дерева. В задаче о выполнимости выражение либо истинно, либо ложно. При этом нельзя получить частичное решение, которое можно использовать для отсечения путей в дереве. Нельзя также использовать эвристики для поиска приблизительного решения для задачи о выполнимости. Любое значение переменных, полученное при помощи эвристики, будет делать выражение истинным или ложным. В математической логике не существует такого понятия, как приближенное решение. Из-за неприменимости эвристик и меньшей эффективности метода ветвей и границ, задача о выполнимости обычно является очень сложной и решается только в случае небольшого размера задачи. Задача о разбиении Если задано множество элементов со значениями X1, X2, … , XN, то существует ли способ разбить его на два подмножества, так чтобы сумма значений всех элементов в каждом из подмножеств была одинаковой? Например, если элементы имеют значения 3, 4, 5 и 6, то их можно разбить на два подмножества {3, 6} и {4, 5}, сумма значений элементов в каждом из которых равна 9. Чтобы смоделировать эту задачу при помощи дерева, предположим, что ветвям соответствует помещение элемента в одно из двух подмножеств. Левая ветвь, выходящая из корневого узла, соответствует помещению первого элемента в первое подмножество, а правая ветвь — во второе подмножество. Если всего существует N элементов, то дерево решение будет представлять собой двоичное дерево высотой N + 1. Оно будет содержать 2N листьев и 2N+1 узлов. Каждый лист соответствует одному из вариантов размещения элементов в двух подмножествах. При решении этой задачи можно применить метод ветвей и границ. При рассмотрении частичных решений задачи можно отслеживать, насколько различаются суммарные значения элементов в двух подмножествах. Если в какой- то момент суммарное значение элементов для одного из подмножеств настолько меньше, чем для другого, что добавление всех оставшихся элементов не позволяет изменить это соотношение, то нет смысла продолжать движение вниз по этой ветви. Так же, как и в случае с задачей о выполнимости, для задачи о разбиении (partition problem) нельзя получить приближенное решение. В результате всегда должно получиться два подмножества, суммарное значение элементов в которых будет или не будет одинаковым. Это означает, что для решения этой задачи неприменимы эвристики, которые использовались для решения задачи о формировании портфеля. Задачу о разбиении можно обобщить следующим образом: если имеется множество элементов со значениями X1, X2, … , XN, как разбить его на два подмножества, чтобы разница суммы значений элементов в двух подмножествах была минимальной? Получить точное решение этой задачи труднее, чем для исходной задачи о разбиении. Если бы существовал простой способ решения задачи в общем случае, то его можно было бы использовать для решения исходной задачи. В этом случае можно было бы просто найти два подмножества, удовлетворяющих условиям, а затем проверить, совпадают ли суммы значений элементов в них. Для решения общего случая задачи можно использовать метод ветвей и границ, примерно так же, как он использовался для решения частного случая задачи, чтобы избежать поиска по всему дереву. Можно также использовать при этом эвристический подход. Например, можно проверять элементы в порядке убывания их значения, помещая очередной элемент в подмножество с меньшей суммой значений элементов. Также можно было бы легко использовать случайный поиск, метод последовательных приближений, или метод отжига для поиска приближенного решения этого общего случая задачи. Задача поиска Гамильтонова пути Если задана сеть, то Гамильтоновым путем (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!) узлов. Так же, как и в обобщенной задаче о разбиении, для отсечения ветвей дерева и ускорения поиска решения задач |
|
