Структуры данных и алгоритмы (1021739), страница 75
Текст из файла (страница 75)
Триангуляция с минимальной стоимостью10.3. „Жадные" алгоритмыРассмотрим небольшую "детскую" задачу. Допустим, что у нас есть монеты достоинством 25, 10, 5 копеек и 1 копейка и нужно вернуть сдачу 63 копейки. Почти нераздумывая, мы преобразуем эту величину в две монеты по 25 копеек, одну монету в10 копеек и три монеты по одной копейке. Нам не только удалось быстро определитьперечень монет нужного достоинства, но и, по сути, мы составили самый короткийсписок монет требуемого достоинства.288ГЛАВА 10.
МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВАлгоритм, которым читатель в этом случае наверняка воспользовался, заключался в выборе монеты самого большого достоинства (25 копеек), но не больше 63 копеек, добавлению ее в список сдачи и вычитанию ее стоимости из 63 (получается 38копеек). Затем снова выбираем монету самого большого достоинства, но не большеостатка (38 копеек): этой монетой опять оказывается монета в 25 копеек. Эту монетумы опять добавляем в список сдачи, вычитаем ее стоимость из остатка и т.д.Этот метод внесения изменений называется "жадным" алгоритмом.
На каждой отдельной стадии "жадный" алгоритм выбирает тот вариант, который является локальнооптимальным в том или ином смысле. Обратите внимание, что алгоритм для определения сдачи обеспечивает в целом оптимальное решение лишь вследствие особыхсвойств монет. Если бы у нас были монеты достоинством 1 копейка, 5 и 11 копеек инужно было бы дать сдачу 15 копеек, то "жадный" алгоритм выбрал бы сначала монетудостоинством 11 копеек, а затем четыре монеты по одной копейке, т.е. всего пять монет. Однако в данном случае можно было бы обойтись тремя монетами по 5 копеек.Мы уже встречались в этой книге с несколькими "жадными" алгоритмами, например алгоритмом построения кратчайшего пути Дейкстры и алгоритмом построения остовного дерева минимальной стоимостью Крускала.
Алгоритм кратчайшегопути Дейкстры является "жадным" в том смысле, что он всегда выбирает вершину,ближайшую к источнику, среди тех, кратчайший путь которых еще неизвестен. Алгоритм Крускала также "жадный"; он выбирает из остающихся ребер, которые несоздают цикл, ребро с минимальной стоимостью.Следует подчеркнуть, что не каждый "жадный" алгоритм позволяет получить оптимальный результат в целом. Как нередко бывает в жизни, "жадная стратегия"подчас обеспечивает лишь сиюминутную выгоду, в то время как в целом результатможет оказаться неблагоприятным. Посмотрим, например, что произойдет, если валгоритмах Дейкстры и Крускала допустить наличиеребер с отрицательными весами.
Оказывается, что наалгоритм Крускала построения остовного дерева этоникак не повлияет: с его помощью по-прежнемуможно будет получить дерево минимальной стоимости. Но алгоритм Дейкстры в некоторых случаях ужене позволяет получить кратчайшие пути.Пример 10.4. На рис. 10.10 показан граф с ребромотрицательной стоимости между вершинами б и с .Если источником является вершина s, то алгоритм ?ис- 10.10. Граф с ребромДейкстры сначала правильно определяет, что мини- отрицательного весамальный путь до а имеет протяженность 1.
Теперь,рассматривая ребра от s (или а) до Ъ или с, алгоритм рассчитывает, что кратчайшийпуть от s до Ъ, а именно s —> а —> Ь, имеет длину 3. Но далее получаем, что с имееткратчайший путь от s длиной 1.Однако "жадный" выбор Ь вместо с является неоправданным. Оказывается, чтопуть s —> а —> с —» Ъ имеет длину лишь 2, поэтому вычисленное нами минимальноерасстояние для Ъ является неправильным.1 П„Жадные" алгоритмы как эвристикиСуществуют задачи, для которых ни один из известных "жадных" алгоритмов непозволяет получить оптимального решения; тем не менее имеются "жадные" алгоритмы, которые с большой вероятностью позволяют получать "хорошие" решения.Нередко вполне удовлетворительным можно считать "почти оптимальное" решение,1Вообще говоря, когда допускается наличие ребер с отрицательными весами (стоимостью),к понятию "кратчайший путь" нужно относиться очень осторожно.
Если, например, допускается наличие циклов с отрицательной стоимостью, то ничто не мешает многократно проходитьтакой цикл, получая при этом сколь угодно большие отрицательные расстояния. Поэтому былобы вполне естественным ограничиться лишь ациклическими путями.10.3. "ЖАДНЫЕ" АЛГОРИТМЫ289характеризующееся стоимостью, которая лишь на несколько процентов превышаетоптимальную. В таких случаях "жадный" алгоритм зачастую оказывается самым быстрым способом получить "хорошее" решение. Вообще говоря, если рассматриваемаязадача такова, что единственным способом получить оптимальное решение являетсяиспользование метода полного поиска, тогда "жадный" алгоритм или другой эвристический метод получения хорошего (хотя и необязательно оптимального) решенияможет оказаться единственным реальным средством достижения результата.Пример 10.5.
Рассмотрим одну знаменитую задачу, для получения оптимальногорешения которой из всех известных нам алгоритмов подходят лишь алгоритмы полногоперебора, время выполнения которых зависит экспоненциально от объема входныхданных. Эта задача, которая называется задачей коммивояжера, сводится к поиску внеориентированном графе с весовыми значениями ребер такого маршрута (простогоцикла, включающего все вершины), у которого сумма весов составляющих его ребербудет минимальной. Такой маршрут часто называют гамильтоновым циклом.На рис. 10.11,а показан граф с шестью вершинами (их часто называют"городами"), который может служить основой для задачи коммивояжера. Заданы координаты каждой вершины, а весом каждого ребра считается его длина.
Обратитевнимание: мы предполагаем (и такое предположение характерно для задачи коммивояжера), что существуют все ребра графа, т.е. граф является полным. В более общих случаях, когда вес ребер не основывается на евклидовом расстоянии, у ребраможет оказаться бесконечный вес, чего в действительности, конечно, не бывает.На рис. 10.11, б, в, г, д показаны четыре маршрута по шести "городам". Читательможет самостоятельно прикинуть, какой из этих маршрутов является оптимальным(может быть, такого маршрута вообще нет). Протяженности этих четырех маршрутовравняются 50.00, 49.73, 48.39 и 49.78 соответственно; маршрут на рис. 10.11,г является кратчайшим из всех возможных маршрутов.с.
(1.7)Ь.(4,3)а» (0,0)cU(15,7)е. (15,4)f • (18,0)а. Шесть "городов"Рис. 10.11. Пример задачи коммивояжераЗадача коммивояжера имеет ряд практических применений. Как следует из самого названия задачи, ее можно использовать для составления маршрута человека, который должен посетить ряд пунктов и, в конце концов, вернуться в исходный пункт.Например, задача коммивояжера использовалась для составления маршрутов лиц,занимающихся выемкой монет из таксофонов. В этом случае вершинами являютсяместа установки таксофонов и "базовый пункт".
Стоимостью каждого ребра (отрезкамаршрута) является время в пути между двумя точками (вершинами) на маршруте.290ГЛАВА 10. МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВЕще одним применением задачи коммивояжера является задача обхода доски шахматным конем: надо найти последовательность ходов, которые позволят коню обойти всеполя шахматной доски, попадая на каждое поле лишь один раз, и вернуться, в концеконцов, на исходное поле.
В этом случае роль вершин графа выполняют поля шахматнойдоски. Предполагается также, что ребра между двумя полями, которые являются"составными частями" хода коня, имеют нулевой вес; все остальные ребра имеют вес,равный бесконечности. Оптимальный маршрут имеет нулевой вес и должен быть маршрутом коня. Читатель, возможно, удивится, узнав, что поиск маршрутов коня с помощью хороших эвристических алгоритмов для задачи коммивояжера вообще не составляетпроблемы, в то время как поиск "вручную" является весьма непростой задачей."Жадный" алгоритм для задачи коммивояжера, речь о котором пойдет ниже, является вариантом алгоритма Крускала.
Здесь, как и в основном алгоритме Крускала, сначаларассматриваются самые короткие ребра. В алгоритме Крускала очередное ребро принимается в том случае, если оно не образует цикл с уже принятыми ребрами; в противномслучае ребро отвергается. В случае задачи коммивояжера "критерием принятия" ребраявляется то, что рассматриваемое ребро (в сочетании с уже принятыми ребрами)1• не приводит к появлению вершины со степенью три и более ;• не образует цикл (за исключением случая, когда количество выбранных реберравняется количеству вершин в рассматриваемой задаче).Совокупности ребер, выбранных в соответствии с этими критериями, образуютсовокупность несоединенных путей; такое положение сохраняется до выполнения последнего шага, когда единственный оставшийся путь замыкается, образуя маршрут.На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
