WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Пошук шляхів у графі - Реферат

Пошук шляхів у графі - Реферат


Реферат на тему:
Пошук шляхів у графі
Користуючись методами, викладеними в попередньому розділі, можна визначити зв'язність (тобто наявність або відсутність шляху) між будь-якими вершинами vi і vj заданого графа G =(V,E ). Однак часто буває необхідним не просто встановити існування шляху між заданими вершинами, але й знайти послідовність вершин і ребер (шлях), що веде з vi у vj.
Крім того, для різних практичних застосувань теорії графів важливою є проблема систематичного обходу (перебору) всіх вершин і/або ребер графа.
Двома класичними методами розв'язання цих проблем є: метод або алгоритм пошуку (обходу графа) вшир та метод або алгоритм пошуку (обходу графа) вглиб.
Сформулюємо постановку проблеми пошуку та обидва методи її розв'язання.
Нехай задано граф G =(V,E ), VO V множину початкових вершин і VK V множину кінцевих (заключних, цільових) вершин графа G. Необхідно знайти шлях з деякої вершини v VO в одну з вершин w VK , тобто знайти послідовність ребер (vi,vi +1) E, і =1,2,...,t 1 таку, що v1= v і vt= w.
Зокрема, множина початкових вершин VO і/або множина кінцевих вершин VK можуть містити тільки по одній вершині. Такі вершини природно називати початковою і кінцевою вершинами графа G.
Для опису алгоритмів нам знадобляться три списки ребер ВІДКР, ЗАКР і РОЗВ. Крім того, для вершини v V через S (v) будемо позначати множину всіх вершин w V таких, що в графі G існує ребро (v,w) E. Такі вершини w часто називають синами вершини v, а множину S (v) множиною синів вершини v.
Для зручності додамо до множини вершин V графа G "порожню" вершину p, а до множини ребер - "порожні" ребра виду (р,v), де v VO. При визначенні шляху з VO у VK "порожні" ребра не враховуються.
Оскільки в запропонованій нижче формі обидва алгоритми пошуку відрізняються тільки в одній позиції, викладемо їх одночасно і відзначимо те місце, яким вони різняться між собою.
Алгоритм пошуку вшир / вглиб.
1. Всі "порожні" ребра розмістити у списку ВІДКР (у довільному порядку).
2. Якщо ВІДКР = , то РОЗВ = (тобто сформульована задача не має розв'язку) і алгоритм завершує свою роботу.
3. Закрити перше ребро (v,w) з ВІДКР, тобто перенести ребро (v,w) зі списку ВІДКР у список ЗАКР.
4. Якщо вершина w закритого ребра є кінцевою вершиною (w VK), то шуканий список РОЗВ (тобто шуканий шлях з VO у VK) міститься серед ребер списку ЗАКР і може бути виділений з нього послідовно, починаючи з останнього закритого ребра шляху. Зауважимо, що при побудові результуючого шляху для кожного з ребер (v,w) списку ЗАКР необхідно вибирати ребро-попередника (u,v) так, що воно є першим ребром з кінцем v у списку ЗАКР. Алгоритм завершує свою роботу.
У противному разі (w VK) перейти до пункту 5.
5. Визначити S (w) множину синів вершини w останнього закритого ребра, а також множину ребер R (w)={(w,z) | z S (w) }.
Розмістити у списку ВІДКР усі ребра з множини R (w) (ВІДКР ЗАКР) після / перед усіх ребер, що вже містяться в цьому списку.
6. Перейти до пункту 2.
Відмінність між обома алгоритмами пошуку знаходиться в позиції 5 і полягає в тому, що в алгоритмі пошуку вшир необхідно розміщувати відповідні ребра після, а в алгоритмі пошукувглиб перед усіма ребрами, що знаходяться в списку ВІДКР.
Для наведених алгоритмів вживають скорочені назви АПШ і АПГ (відповідні англійські назви BFS (breadth first search) i DFS (depth first search)).
Таким чином, для АПШ список ВІДКР є чергою, тобто такою сукупністю елементів, в якій нові елементи розміщуються в кінці сукупності, а елемент, що "обслуговується" (закривається), вибирається з голови (початку) цієї сукупності. У той час для АПГ список ВІДКР є так званим стеком, тобто сукупністю, в якій елементи, що додаються до сукупності, і елементи, що відбираються для "обслуговування", розміщуються тільки на початку сукупності - у верхівці стеку (за принципом: "останній прийшов - перший обслуговується").
Приклад 3.8. Розглянемо дію алгоритму пошуку вшир для графа, зображеного на рис.3.6 (див. таблицю 3.1). Вважаємо, що VO= {3} i VK= {11}.
Рис.3.6
Кожний рядок таблиці описує результат виконання одного циклічного кроку (позиції 2 6) алгоритму. Оскільки список ЗАКР тільки поповнюється і на кожному кроці поповнюється тільки одним ребром, то в таблиці записуємо лише це ребро (не повторюючи всі елементи, які ввійшли до складу ЗАКР на попередніх кроках). Нагадаємо також, що ребра (v,w) і (w,v) збігаються.
Таблиця 3.1.
Алгоритм пошуку вшир (АПШ)
Крок ВІДКР ЗАКР w R (w)
0 (p,3)
1 (3,2),(3,4) (p,3) 3 (3,2),(3,4)
2 (3,4),(2,1),(2,4),(2,5),(2,6) (3,2) 2 (2,1),(2,4),(2,5),(2,6)
3 (2,1),(2,4),(2,5),(2,6),(4,5),(4,8) (3,4) 4 (4,5),(4,8)
4 (2,4),(2,5),(2,6),(4,5),(4,8) (2,1) 1
5 (2,5),(2,6),(4,5),(4,8) (2,4) 4
6 (2,6),(4,5),(4,8),(5,8) (2,5) 5 (5,8)
7 (4,5),(4,8),(5,8),(6,7) (2,6) 6 (6,7)
8 (4,8),(5,8),(6,7) (4,5) 5
9 (5,8),(6,7),(8,7),(8,9) (4,8) 8 (8,7),(8,9)
10 (6,7),(8,7),(8,9) (5,8) 8
11 (8,7),(8,9) (6,7) 7 (7,12),(7,11),(7,9),(7,10)
12 (8,9),(7,12),(7,11),(7,9),(7,10) (8,7) 7
13 (7,12),(7,11),(7,9),(7,10) (8,9) 9
14 (7,11),(7,9),(7,10),(12,10),(12,11) (7,12) 12 (12,10),(12,11)
15 (7,9),(7,10),(12,10),(12,11) (7,11) 11
Алгоритм завершує свою роботу на п'ятнадцятому кроці. Аналізуючи список ребер ЗАКР від його кінця до початку, будуємо список РОЗВ, тобто знаходимо шуканий шлях від вершини 3 у вершину 11: 3,(3,2),2,(2,6),6,(6,7),7,(7,11),11. Довжина цього шляху 4.
Радимо побудувати аналогічну таблицю для алгоритму пошуку вглиб шляху з вершини 3 у вершину 11 і порівняти дію та результати обох алгоритмів.
Список літератури
1. Харари Т. Теория графов.- М.,1973.
2. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И.- М., 1990.
3. Зыков А.А. Основы теории графов.- М., 1987.
4. Оре О. Теория графов.- М., 1980.
5. Свами М., Тхуласираман К. Графы, сети, алгоритмы.- М., 1984.
6. Уилсон Р. Введение в теорию графов.- М., 1977
7. Кристофидес Н. Теория графов. Алгоритмический подход.- М.,1978
8. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы.-М.,1980
Loading...

 
 

Цікаве