Искусство программирования на Си (984073), страница 49
Текст из файла (страница 49)
вершине ц в С (обратное ревсрсированпе направления Теперь очевилно. что для графа требуются ограни- ребра, перемещенного в С,). Однако и и ч должны быть чсння. Граф не лолжен быть связанным. Однако этот ч о в в сильно связанными. граф должен содержать только один связанный подграф. Это означает, что глубинный остовный лес в графе Если граф содержит больше олного связанного подгра- С, определяет все сильно связанные компоненты в гра- фа, то он нс может иметь путей или контуров Эйлера, фе С. так как некоторые ребра никогла не будут пройлеиы. чг га Уг Любой граф, который удоазетаоряет указанным усОпределение путей и контуров Эйлера ловиям, должен иметь путь Эйлера или контур ЭйлеПуть Эйлера проходит по ка:клону ребру а графе толь- Р' ""'" ')"ф " '"""" '"" (о" к"м ко олин ра..
Контур Эйлера прохолит каждое ребро в Опрслслсние п)ти или контУРа Эйлера люжно про2 и 5 ч в графе тоже од «раз, а также на инастся и закан ива- вести с использованием методики, похожей на глУбин- ется в одной и той же вершние (рис (б 2() Многи же ый поиск. Следуюший алгоРитм используегса лла РИСУНОК 16.1З. Ребра графа, по которым проходит п>ть знакомы с концепцией следующей простой головолом- поиска контУРа ЭйлеРа, Но его можно немного изме- О~! -л 4-+ 3-ь О, удаляются. кн — нарисовать какое-то очертание без отрыва ручки нить, чтобы он позволЯл также нахолить пУть Эйлера в от бумаги.
любом графе, который удовлетворяет привеленным Затем глубинный поиск продолзкастся с первой вер- выше условиям. шины, которая имела выхоляшес из нее ребро. В нашем Если серьезно, то поиск путеи и контуроа Эйлера Органик»ни» данник рарнкта с графини г ~ Часть и Глава 16 Это проблему можно представить в виде графа. Го- а таблицу результатов использовать для создания ново- ла.
Разъелинсние пары ребер так, чтобы цикл разделялся прослкотренных вершин. Другими словами, это значит, рода будут вершинами, а дороги от олного города к го полного графа. Рис. 16.26 демонсгрируст исходный на .1аа пути (более чем из олной вершины) и другое что шккл ч, — лч,— эчк — л ч, эх,— л ч, в контексте оридругому — ребрами. Затраты на прохожленис ребра мо- граф и созланный на его основе полный граф. сос инснис этих ребер — вот верный механизм измене- гинального графа является самым коротким путем от ч» тут представлять собой дсньпк, расстояние, время или ния найденного более короткого цикла.
Для любой та- до ч,, за которым следует самый короткий путь от ч, до определенную комбинацию этих параметров. кои пары ребер существ)ет только одна комбинация, ч„за которым, в свою очередь, слелует самый корот- 4 Задачу ТбР можно решить, если найти циклы Га- которая позволяет создать цикл, отличающийся от пре- кий путь от ч, до ч, и т.д. В эзом примере все получснмильтона 1Напп!гоп)ап сус1са) в графе, который представ- 3 а 4 з г 4 дыдущего.
Если один нли несколько из вновь созданных ные пути имеют длину в одно ребро, однако это нс обяляет некую реальную сеть. Цикл Гамильтона — это з циклов имеют более низкие общие затраты, чем прелы- зательно будет справедливо для всех графов. з цикл, который проходит только один раз через квкдую чг 5 1 г 5 3 дущий, то он становится исходным, и этот пропесс Для большинства целей эта технология позволяет вершину, а затем возвращается к первоначальной вер- повторястся со следуюшеи парои ребер этого цикла до получить приемлемо точные результаты за небольшос шине.
Оптимальным решением Тбр будет цикл Гамиль- в 4 1 Б 1 тех пор, пока больше нельзя будет делать перестановок время. Приложения такого алгоритма применяются нс тона наименьшей длины в графе. ребер. только для путешествующих коммивояжеров и опреле- ко Решение задачи ТБР, представленнои в виде графа, о По окончании мы лолжны получить цикл, который лсния оптимальных маршрутов доставки грузов. оказывается довольно банальным.
Метод грубой силы должен иметь большие, но близкие к реальному оптипредназначен для определения всех возможных циклов муму общие затраты, или иметь точный оптилгум зат- АДГОРИТ$ЯЫ ПОИСКа КратЧаКШЕГ0 ПутИ Гамильтона и сравнения их длин. Решением будет пика РИСУНОК 16.26. Исходный граф и со»данныи на его основе рат.
На рис. 16.28 показаны циклы, полученные при с наименьшими общими затратами. Этот подход гараннолный граф. первом проходе. Номер в квадратике возле каждого цик- Одним из принципов использования теории графов явтирует, что найлено действительно оптимальное реше- ла — это общая их длина. Только один новый цикл ляется поиск наилучшего из нескольких маршрутов. ние, но имеется один существенный недостаток. Начальный цикл можно найти с использованием зак имеет общую длину, которая меньше, чем оригиналь- Такой маршрут определяется путем подсчета пути с называемого алгоритма "ближайшего соседа". Начиная ! расюта с графова $д~ Часть и Глава 16 являются проблемы, связанныс с самым коротким вре- те вершины, которые у;ке поссщсны, — имеют черный Таблица 16.6. Алгоритм Дийкстры — стадия 2.
Выбирается вершина ч,, и обновляется значение затмснем, расстоянием или ценой, которые необхолимы цвез, а непосешенные вершины остаются светлыми. р ат на ч Марш„,ч от ч к ч имеет меньшие затраты (5) 11 1 3 для перемещения из одного места на другое. Опредслс- Цифры возле каждой вершины представляют маршрут чем определенный ранее маршрут (б). Общие затраты ние самого короткого маршрута можно применить ко к этой вершине с наименьшими затратами на данный на ч, обновляются, и ч,устанавливается как предыдувсему, что представляется в виде графа. момент. После посещения вершины общие затраты от 1 ла О нет начала не изменяются. Здесь ч, — начальная вершина.
2 НЕ1 1 ч, г Алгоритм Дийкстры: единственный з в источник после выполнения шага !. Общие затраты на путь для 4 нет 2 стартовой вершины ч, устанавливаются равными О, а 1 5 2 В алгоритме Дийкстры (Овймга) рассчитываются общие р 5 НЕТ Нвт для остальных вершин — равными бесконечности. о з з затраты на кратчайший маршрут от любой единствснб нет НЕТ 2 1'з !в ной вершины в графе ко всем остальным вершинам. Таблица 16.6. Алгоритм Дийкстры — стадия 1. 7 нег нет з Алгоритм выполняется как определенная последователь- ч„ Посещенные Общие Предыдгщ не 2 1 ность действий.
Нз ка1кдой итерации опрелеляются вершины затраты вершины Среди непосещенных вершин выбирается вершина с 2 наименьшие общие затраты на одну вершину. минимальными общими затратами (ч,). Она помсчает- 1 нет О нет ся как посещенная, и корректируются общие затраты на Алгоритм Аийкотры: итерации 2 нет ч и ч РИСУНОК 16.32. г(ггоритмдийхстры — диаграмма стадии 4 Для каждой вершины в графе сохраняются два значе- 3 НЕ1 ния. Общие затраты на путь от стартовой вершины к 4 каждой всершине используются для отслеживания зат- Организация бинниг $ Масть и Таблица 16.10. Алгоритм Дийкстры — стадия 6. Таблица 16.12.
Алгоритм Дийкстры — стадия 8. Листинг 16.3. Алгоритм Дийкстры и функция (п!Тйевц!тв 1пт 1пзьяеви11в(вссисе Оз)авета Вои ' ° Веви1ев, Тпс Иипкоив) ч„ Посещенные Общие Предыдтщие т„ Посещенные Общие Предыд) тине вершины загнраты вершины аернтины затраты вершины 1пс 1; 1 да 0 нет 1 Дд О нет ветисе ОРЗКвьта Вои * рег) 2 Лд 1 ч, 2 Лд 1 ч, ртт аа11ос(а(аеот(ввгиск О!)Каста Вои) ' Ииваоив); г чг 11 (1ркг) тееитп Саара ООТОРИКИ; 4 Лд 2 ч, 4 да 2 ч, 5 да 4 чг 5 да 4 чг сос ! 1 011<иивяовв 1++) 6 дд 3 ч, 6 па 3 ч, ( рсс(11 тосатсовс=саара иотсоиикстко; 7 нет 6 ча 7 да 6 ч б рес(11.реев(оив=-1; рес(1).Ч1взьеб=таЬКК1 Выбирается чь но, так как обе смсзкныс вершины Теперь табл.
16.12 содержит кратчайший маршрут от уже были поссшены, онн просто помечаются как посс- ~~артовой вершины ч, ко всем другим вершинам а грашсннзас без влияния на друтнс вершины фс. КРатчайший маршрут можно проследить от любой акево1ев=рстт вершины с использованием информации о прслыдушсй теситп о; Таблица 16.11. Алгоритм Дийкстры — стадия 7.
вершине, содсржашсйся в таблице. Например, кратчан! 1пе Оз)авета 51вр1е(вегасе Стара а С, (пк Воиссе, т„ Посещенные Общие Предыдущие шнй маршрут от ч, к ч, по таблице — зто ч,, чта ч,, т, т встисс о1)касса такте таите) вершины затразззы вершины обшнми затратами, равными 5 ( Рабан а с графами Глава 16 $ ПР«аоомцо«доооы» Робота г гро</иоо $ $ Часть ц Глава \6 ТаЫе->охв! ния, перемещения и исследования кажлою элемента в Все сказанное выше не касается ребер с отрица~ельТаЫе->вояков=воиксе< очереди задаст/ю больше, чем при поиске в очереди.
ными затратами В таком <рафе должен быть путь обТаЫе->йеви1св=йвви1св< Структура данных, используемых как приоритетная ратно к >же посешенной вершине, который имеет затгисикп 0; очсрс.«ч имеет большое значение во время выполнения раты, меньшие, чем ранее найленные. Однако решение ) залзчн.
При простой реализации связанного списка по- ссгь: алгоритм Беллмана-Форда (Вс[[п<ап-рог<)). лучаются нсприемлсмыс результаты, в ка<клом поиске выпи.<настоя У итераций, требующих времени выпол- АЛГОРИТМ БЕЛЛМВНа-ФОРДа' Листинг (6.4. Алгоритм Днйкстры для разреженных графов. пения порядка О(у<). Хотя это то же самое, что и про- цЕНтраЛИЗОВаННЫЕ рЕбра С кпе п15йвега 5рагкв(вегисе сгарь ' 5, 1пе воигсв, вегасе О1)авета таые ' таыв) стаЯ описаннаЯ Ранее Рсазизацил, она булет выполнЯть- г<ГрИцвуВЛБ)(ЫМИ ЗВГрвтВМИ ( ся ло <ьшс, поскольку подлержка связанного списка 1пс и< /* и — зто видике текущей вервввв «/ занимает больше времени. Алгоритм Беллмана-Форда очень похож нз алгоритм (пе 1; Использование двои <ной динамической памяти мо- Дийкстры. Основное их различие состоит атом, что алвсгисс удивив ц! же<:<изволить значительно снизить время, необходимое горитм Дийкстры предполагает, что вы никоглз нс бувсгисе цу)каста йои * йвви1св< оегиск йддввсап 5; /» содерквт ввформаиви о тракте '/ для р.ыреженных графов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
