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

Поиск решений на основе таблицы

Несмотря на то что табл. 10.2 позволяет определить стоимость минимальной триангуляции, из нее непосредственно нельзя определить саму минимальную триангуляция, так как для этого надо знать значение к, которое обеспечивает минимум в формуле (10.5). Если мы знаем значение к, тогда решение состоит из хорд (Vi, и (fH*, 1»; s-i) (за исключением случая, когда одна из них не является хордой, так как к = 1 или к = S - 2) плюс хорды, указываемые решениями S.j+i и S+t.s-t. При вычислении элементов таблицы полезно включить в нее значения к, при которых получаем минимум в формуле (10.5).

Пример 10.3. В табл. 10.2 значение элемента Со, (который представляет решение задачи триангуляции многоугольника из рис. 10.5) получено как минимум формулы (10.5) при к = 5. Другими словами, задача So7 разбивается на подзадачи Sos и S52 первая из них представляет собой задачу с шестью вершинами Vo, Vy, ... ,05, а вторая является тривиальной "задачей" стоимости О. Таким образом, мы имеем хорду (оо. fs) стоимостью 22.09 и должны решить подзадачу Soe.

Минимальная стоимость для Сое получается из (10.5) при к = 2, в результате чего задача Soe разбивается на подзадачи S03 и S24. Первая из них представляет собой треугольник с вершинами Vo, Vi и i>2, в товремя как вторая представляет собой четырехугольник, определяемый вершинами Vj, 1*3, Щ и v. S03 решать не требуется, нужно решить только подзадачу S24. Кроме того, надо включить в стоимость минимальной триангуляции стоимости хорд (t>o, У2)и (1)2, vs), равные соответственно 17.89 и 19.80. Для С24 минимальное значение в (10.5) получается при к = \, давая подзадачи С22 и Сзз, причем обе они имеют размер, не больший трех, и, следовательно, их стоимость равна 0. Вводим хорду (t>3, v) стоимостью 15.65 в минимальную триангуляцию. □



Рис. 10.8. Шаблон просмотра таблицы при вычислении одного элемента

Рис. 10.9. Триангуляция с минимальной стоимостью

10.3. „Жадные" алгоритмы

Рассмотрим небольшую "детскую" задачу. Допустим, что у нас есть монеты достоинством 25, 10, 5 копеек и 1 копейка и нужно вернуть сдачу 63 копейки. Почти не раздумывая, мы преобразуем эту величину в две монеты по 25 копеек, одну монету в 10 копеек и три монеты по одной копейке. Нам не только удалось быстро определить перечень монет нуясного достоинства, но и, по сути, мы составили самый короткий список монет требуемого достоинства.



Алгоритм, которым читатель в этом случае наверняка воспользовался, заключался в выборе монеты самого большого достоинства (25 копеек), но не больще 63 копеек, добавлению ее в список сдачи и вычитанию ее стоимости из 63 (получается 38 копеек). Затем снова выбираем монету самого больщого достоинства, но не больще остатка (38 копеек): этой монетой опять оказывается монета в 25 копеек. Эту монету мы опять добавляем в список сдачи, вычитаем ее стоимость из остатка и т.д.

Этот метод внесения изменений называется "жадным" алгоритмом. На каждой отдельной стадии "жадный" алгоритм выбирает тот вариант, который является локально оптимальным в том или ином смысле. Обратите внимание, что алгоритм для определения сдачи обеспечивает в целом оптимальное рещение лищь вследствие особых свойств монет. Если бы у нас были монеты достоинством 1 копейка, 5 и 11 копеек и нужно было бы дать сдачу 15 копеек, то "жадный" алгоритм выбрал бы сначала монету достоинством 11 копеек, а затем четыре монеты по одной копейке, т.е. всего пять монет. Однако в данном случае можно было бы обойтись тремя монетами по 5 копеек.

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

Следует подчеркнуть, что не каждый "жадный" алгоритм позволяет получить оптимальный результат в целом. Как нередко бывает в жизни, "жадная стратегия" подчас обеспечивает лищь сиюминутную выгоду, в то время как в целом результат может оказаться неблагоприятным. Посмотрим, например, что произойдет, если в алгоритмах Дейкстры и Крускала допустить наличие ребер с отрицательными весами. Оказывается, что на алгоритм Крускала построения остовного дерева это никак не повлияет: с его помощью по-прежнему можно будет получить дерево минимальной стоимости. Но алгоритм Дейкстры в некоторых случаях уже не позволяет получить кратчайщие пути.

Пример 10.4. На рис. 10.10 показан граф с ребром отрицательной стоимости между верщинами бис. Если источником является верщина s, то алгоритм Дейкстры сначала правильно определяет, что минимальный путь до а имеет протяженность 1. Теперь,

рассматривая ребра от s (или а) до Ъ или с, алгоритм рассчитывает, что кратчайший путь от S до Ь, а именно s а Ь, имеет длину 3. Но далее получаем, что с имеет кратчайший путь от s длиной 1.

Однако "жадный" выбор Ь вместо с является неоправданным. Оказывается, что путь S -> а -> с -> Ь имеет длину лишь 2, поэтому вычисленное нами минимальное расстояние для Ъ является неправильным. □


Рис. 10.10. Граф с ребром отрицательного geca

„Жадные" алгоритмы как эвристики

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

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



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

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

На рис. 10.11,а показан граф с шестью вершинами (их часто называют "городами"), который может служить основой для задачи коммивояжера. Заданы координаты каждой вершины, а весом каждого ребра считается его длина. Обратите внимание: мы предполагаем (и такое предположение характерно для задачи коммивояжера), что сушествуют все ребра графа, т.е. граф является полным. В более общих случаях, когда вес ребер не основывается на евклидовом расстоянии, у ребра может оказаться бесконечный вес, чего в действительности, конечно, не бывает.

На рис. 10.11, б, в, г, д показаны четыре маршрута по шести "городам". Читатель может самостоятельно прикинуть, какой из этих маршрутов является оптимальным (может быть, такого маршрута вообще нет). Протяженности этих четырех маршрутов равняются 50.00, 49.73, 48.39 и49.78 соответственно; маршрут на рис. 10.11,гявля-ется кратчайшим из всех возможных маршрутов.

С. (1,7)

Ь» (4.3) а .(0,0)

(15,7) (15,4)

f- (18,0)

а. Шесть "городов"





Рис. 10.11. Пример задачи коммивояжера

Задача коммивояжера имеет ряд практических применений. Как следует из самого названия задачи, ее можно использовать для составления маршрута человека, который должен посетить ряд пунктов и, в конце концов, вернуться в исходный пункт. Например, задача коммивояжера использовалась для составления маршрутов лиц, занимающихся выемкой монет из таксофонов. В этом случае вершинами являются места установки таксофонов и "базовый пункт". Стоимостью каждого ребра (отрезка маршрута) является время в пути между двумя точками (вершинами) на маршруте.





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.0019