Узагальнений пошук на графах

Алгоритми DFS і BFS - фундаментальні та важливі методи, що лежать в основі численних алгоритмів обробки графів. Знаючи їх основні властивості, ми можемо перейти на більш високий рівень абстракції, на якому видно, що обидва методи є окремі випадки узагальненої стратегії переміщення по графу - тієї, яка була запропонована в реалізацію пошуку в ширину (програма 18.9).

Основний принцип простий: ми знову звертаємося до опису пошуку в ширину з розділу 18.6, тільки замість поняття чергу (queue) використовуємо узагальнений термін накопичувач (fringe) - безліч ребер-кандидатів для наступного включення в дерево пошуку. Ми відразу ж приходимо до загальної стратегії пошуку зв'язкового компонента графа. Почавши з петлі вихідної вершини в накопичувачі і порожнього дерева, виконуємо наступну операцію, поки накопичувач не стане порожнім:

Перенесіть якесь ребро з накопичувача в дерево. Якщо вершина, в яку воно веде, ще не відвідувалася, відвідайте цю вершину і помістіть в накопичувач все ребра, які ведуть з цієї вершини в ще не відвідані вершини.

Ця стратегія описує сімейство алгоритмів пошуку, які забезпечують відвідування всіх вершин і ребер зв'язного графа незалежно від того, який тип узагальненої черзі використовується для зберігання ребер в накопичувачі.

Якщо для реалізації накопичувача використовувати чергу, вийде пошук в ширину, описаний в розділі 18.6. Якщо для реалізації накопичувача використовувати стек, вийде пошук в глибину. Це явище докладно представлено на Мал. 18.25 , Який корисно порівняти з малюнками 18.6 і 18.21.

Доведення еквівалентності рекурсивного DFS і DFS на базі стека є цікава вправа з видалення рекурсії, в процесі якого стек, що лежить в основі рекурсивної програми, фактично перетворюється в стек, який реалізує накопичувач (див. Вправу 18.63). Порядок перегляду в DFS, показаний на Мал. 18.25 , Відрізняється від порядку перегляду на Мал. 18.6 тільки тим, що через дисципліну LIFO ребра, інцидентні кожній вершині, перевіряються в порядку, зворотному порядку в матриці суміжності (або в списках суміжності). Однак головне не змінюється: якщо змінити структуру даних в програмі 18.8 з черги на стек (що легко зробити, оскільки інтерфейси АТД цих двох структур даних відрізняються тільки іменами функцій), то програма буде виконувати пошук не в ширину, а в глибину.

Як було сказано в розділі 18.7, цей узагальнений метод може виявитися не таким ефективним, як хотілося б, оскільки накопичувач виявляється захаращений ребрами, що вказують на вершини, які вже були перенесені в дерево, коли дане ребро знаходилося в накопичувачі. У разі черг FIFO цього вдається уникнути завдяки позначці кінцевих вершин в момент занесення їх в чергу. Ми ігноруємо ребра, які ведуть в вершини, що знаходяться в накопичувачі, оскільки знаємо, що вони не будуть використані: старе ребро (і відвідана вершина) вилучають із черги раніше, ніж нове (див. Програму 18.9). У реалізації зі стеком все навпаки: коли в накопичувач потрібно помістити ребро з тієї ж кінцевої вершиною, що і вже зберігається ребро, ми знаємо, що не буде використано старе ребро, оскільки нове ребро (і відвідана вершина) вилучають із стека раніше старого. Щоб охопити ці два крайніх випадку і забезпечити можливість реалізації накопичувача, яка може скористатися будь-який інший стратегією, яка блокує наявність в накопичувачі ребер, які вказують на ту ж вершину, ми скорегуємо нашу узагальнену схему наступним чином:

Виберіть з накопичувача ребро і перенесіть його в дерево. Відвідайте вершину, в яку воно веде, і помістіть в накопичувач все ребра, які ведуть з цієї вершини в ще не відвідані вершини, керуючись стратегією заміни в накопичувачі, яка гарантує, що ніякі два ребра в накопичувачі не вказують на одну і ту ж вершину ( р Мал. 18.26 ).

Мал.18.25.

Алгоритм пошуку в глибину з використанням стека

Разом з Мал. 18.21 даний малюнок демонструє, що пошуки в ширину і в глибину відрізняються один від одного тільки робочої структурою даних. Для пошуку в ширину використовується чергу, а для пошуку в глибину - стек. Виконання починається з перегляду всіх вершин, суміжних з вихідної вершиною (угорі ліворуч). Потім ми переміщаємо ребро 0-7 з стека в дерево і заштовхуємо в стек інцідентние вершині 7 ребра 7-1, 7-4 і 7-6, які ведуть в ще не включені в дерево вершини (друга діаграма зверху зліва). Дисципліна LIFO передбачає, що при приміщенні ребра в стек інші ребра, що ведуть у ту ж вершину, вважаються неактуальними і ігноруються, коли піднімаються в верхівку стека. Ці ребра заштриховані на малюнку сірим кольором. Після цього ми переносимо ребро 7-6 з стека в дерево і заносимо інцідентние йому ребра в стек (третя діаграма зверху зліва). Потім ми витягаємо з стека ребро 4-6 і заносимо інцідентние йому ребра, два з яких приводять нас до нових вершин (внизу зліва). На завершення пошуку, Чорноморське стека залишилися ребра, ігноруючи "сірі" ребра, коли вони піднімаються в верхівку стека (праворуч).

Стратегія блокування однакових кінцевих вершин в накопичувачі дозволяє відмовитися від перевірки, чи була відвідана кінцева вершина витягнутого з черги ребра. У разі пошуку в ширину використовується реалізація черги з правилом ігнорування нових елементів, а для пошуку в глибину потрібен стек з правилом ігнорування старих елементів. Однак будь-яка узагальнена чергу в поєднанні з будь-яким правилом блокування також дасть ефективний метод перегляду всіх вершин і ребер графа за лінійний час з використанням обсягу додаткової пам'яті, пропорційного V. Схематична ілюстрація цих відмінностей приведена на Мал. 18.27 . Так що в нашому розпорядженні є ціле сімейство стратегій пошуку на графі, яка утримує та BFS, і DFS, і члени якого відрізняються один від одного тільки реалізацією узагальненої черзі. Як ми побачимо нижче, в це сімейство входять і багато інших класичні алгоритми обробки графів.

У програмі 18.10 представлена ​​реалізація цих ідей для графів, представлених списками суміжності. Вона поміщає ребра накопичувача до узагальненої чергу і використовує звичайні вектори, індексовані іменами вершин, для ідентифікації вершин в накопичувачі, щоб можна було скористатися явною операцією АТД оновити, коли зустрічається інше ребро, що веде в вершину, яка вже занесена в накопичувач. Конкретна реалізація АТД може вибирати, ігнорувати чи їй нове ребро або замінити їм старе ребро.

Мал.18.26.

Термінологія пошуку на графі

Для виконання пошуку на графі ми використовуємо дерево пошуку (чорні лінії) і накопичувач (сірі лінії), що містять ребра, які є кандидатами на наступне включення в дерево. Будь-яка вершина або занесена в дерево (чорні), або знаходиться в накопичувачі (сірі), або ще не переглянута (білі). Вершини дерева з'єднані дерев'яними ребрами, а кожна вершина з накопичувача з'єднана ребром з деякою вершиною дерева.

Мал.18.27.

Стратегії пошуку на графі

Тут показані різні можливості при виборі наступного кроку пошуку, показаного на Мал. 18.26 . Ми переносимо вершину з накопичувача в дерево (з центру колеса, вгорі праворуч), перевіряємо всі її ребра і поміщаємо ребра, провідні в неперевірені вершини, в накопичувач. При цьому використовується правило заміщення, яке визначає обробку ребер, що вказують на вершини, які вже присутні в накопичувачі і вказують на ту ж саму вершину: чи потрібно пропустити таке ребро або замінити їм ребро з накопичувача. У пошуку в глибину ми завжди замінюємо старі ребра, а в пошуку в ширину - завжди ігноруємо нові ребра; в інших стратегіях ми замінюємо одні ребра і пропускаємо інші.

Програма 18.10. Узагальнений пошук на графі

Даний клас пошуку на графі узагальнює алгоритми BFS і DFS і підтримує інші алгоритми обробки графів (див. "Найкоротші шляхи" , В якому обговорюються ці алгоритми і альтернативні реалізації). У ньому використовується узагальнена чергу ребер, яка називається накопичувачем (fringe). Спочатку в накопичувач заноситься петля вихідної вершини; потім, поки накопичувач не пустили, ми переносимо з нього ребро e в дерево (з початком в вершині ev) і переглядаємо список суміжності вершини ew, поміщаючи в накопичувач непереглянутих вершини і викликаючи функцію update при появі нових ребер, що вказують на вершини, які вже занесені в накопичувач.

Цей код використовує вектори ord і st, щоб ніякі два ребра в накопичувачі не вказували на одну і ті ж вершину. Вершина v є кінцевою вершиною ребра, поміщеного в накопичувач, тоді і тільки тоді, коли вона позначена (значення ord [v] не дорівнює -1), але ще не знаходиться в дереві (st [v] дорівнює -1).

#include "GQ.cc" template <class Graph> class PFS: public SEARCH <Graph> {vector <int> st; void searchC (Edge e) {GQ <Edge> Q (GV ()); Q.put (e); ord [ew] = cnt ++; while (! Q.empty ()) {e = Q.get (); st [ew] = ev; typename Graph :: adjIterator A (G, ew); for (int t = A.beg ();! A.end (); t = A.nxt ()) if (ord [t] == ​​-1) {Q.put (Edge (ew, t)); ord [t] = cnt ++; } Else if (st [t] == ​​-1) Q.update (Edge (ew, t)); }} Public: PFS (Graph & G): SEARCH <Graph> (G), st (GV (), -1) {search (); } Int ST (int v) const {return st [v]; }};

Лемма 18.12. Узагальнений пошук на графі відвідує все вершини і ребра графа за час, пропорційне V2, для подання матрицею суміжності і за час, пропорційне V + E для подання списками суміжності плюс, в гіршому випадку, час на V операцій вставки, V операцій видалення і E операцій поновлення в узагальненій черзі розміру V.

Доведення. Доказ леми 18.11 не залежить від реалізації черги і тому можна застосувати і тут. Зазначені додаткові витрати часу на операції з узагальненої чергою йдуть безпосередньо з програмної реалізації.

Існує безліч інших заслуговують уваги ефективних моделей АТД накопичувача. Наприклад, як у випадку нашої першої реалізації BFS, можна дотримуватися нашої першої загальної схеми: просто помістити все ребра в накопичувач, а при вилученні з накопичувача ігнорувати ті з них, які ведуть в вершини, вже включені в дерево. Недолік такого підходу, як і в разі BFS, полягає в тому, що максимальний розмір черги має дорівнювати E, а не V. Або можна виконувати оновлення неявно в реалізації АТД, просто вказавши, що ніякі два ребра з однієї і тієї ж кінцевої вершиною не можуть перебувати в черзі одночасно. Однак найпростіший спосіб зробити це в реалізації АТД по суті еквівалентний використанню вектора, індексованого іменами вершин (див. Вправи 4.51 і 4.54), тому така перевірка більше вписується в клієнтські програми, які виконують пошук на графі.

Поєднання програми 18.10 з абстракцією узагальненої черзі дає універсальний і гнучкий механізм пошуку на графі. Для ілюстрації цього твердження ми коротко розглянемо дві цікавих і корисних альтернативи пошуків в глибину і ширину.

Перша альтернативна стратегія заснована на використанні рандомизированной черзі (randomized queue, см. "Абстрактні типи даних" ). З рандомізованих черг елементи витягуються у випадковому порядку: будь-який елемент такої структури даних може бути обраний з однаковою ймовірністю. Програма 18.11 являє собою реалізацію, яка забезпечує таку поведінку. Якщо використовувати цей код для реалізації АТД узагальненої черзі, то вийде алгоритм випадкового пошуку на графі, де будь-яка вершина, яка перебуває в накопичувачі, з однаковою ймовірністю може стати кандидатом на включення в дерево. Вибір ребра (провідного в цю вершину) для додавання в дерево залежить від реалізації операції оновити. Реалізація в програмі 18.11 не виконує ніяких оновлень, і кожна вершина з накопичувача додається в дерево разом з ребром, яке послужило причиною її занесення в накопичувач. Але можна, навпаки, виконувати всі оновлення (тоді в дерево буде додаватися найостанніше зустрінуте ребро з усіх, які ведуть в кожну вершину, вміщену в накопичувач), або використовувати випадковий вибір.

Програма 18.11. Реалізація рандомизированной черзі

Під час вилучення елемента з цієї структури даних з однаковою ймовірністю вибирається будь-який з знаходяться в ній елементів. Цей код можна використовувати для реалізації АТД узагальненої черзі для виконання "випадкового" пошуку на графі (див. Текст).

template <class Item> class GQ {private: vector <Item> s; int N; public: GQ (int maxN): s (maxN + 1), N (0) {} int empty () const {return N == 0; } Void put (Item item) {s [N ++] = item; } Void update (Item x) {} Item get () {int i = int (N * rand () / (1.0 + RAND MAX)); Item t = s [i]; s [i] = s [N-1]; s [N-1] = t; return s [- N]; }};
Мал. 18.28. Розміри накопичувача при роботі пошуку в глибину, рандомізованого пошуку і пошуку в ширину

Ці графіки розмірів накопичувача під час пошуків, представлених на Мал. 18.13 , Мал. 18.24 і Мал. 18.29 , Показують, який величезний вплив надає на пошук на графі вибір структури даних для накопичувача. При використанні стека в DFS (вгорі) накопичувач заповнюється на самому початку пошуку, оскільки на кожному кроці ми знаходимо нові вузли, а потім витягуємо з накопичувача весь його вміст. При використанні рандомизированной черзі (в центрі) максимальний розмір черги набагато менше. При використанні черзі FIFO в BFS (внизу) максимальний розмір черги ще менше, а нові вузли виявляються в процесі пошуку.

Інша стратегія відіграє винятково важливу роль у вивченні алгоритмів обробки графів, оскільки лежить в основі цілого ряду класичних алгоритмів, які будуть розглянуті в лекціях 20-22 - це використання для накопичувача АТД черзі з пріоритетами (priority queue, см. "Черги з пріоритетами і пірамідальна сортування" . Кожному ребру в накопичувачі присвоюється певне значення пріоритету, яке потім може змінюватися, і вибираємо для чергового включення в дерево ребро з найвищим пріоритетом. Докладний аналіз цього алгоритму буде проведено в главі 20 "Мінімальні остовне дерева" . Операції по роботі з чергою з пріоритетами вимагають великих витрат, ніж аналогічні операції для стеків і черг, оскільки для них необхідні неявні операції порівняння елементів черги, але зате вони можуть підтримувати значно ширший клас алгоритмів пошуку на графах. Як ми побачимо нижче, деякі з найбільш важливих завдань обробки графів можна вирішити, просто вибравши необхідний спосіб призначення пріоритетів в реалізації узагальненого пошуку на графі на базі черги з пріоритетами.

Всі узагальнені алгоритми пошуку на графах переглядають кожне ребро всього один раз і в гіршому випадку вимагають додаткового обсягу пам'яті, пропорційного V; однак вони все-таки різняться деякими показниками продуктивності. Наприклад, на Мал. 18.28 показано, як змінюється розмір накопичувача в процесі виконання пошуку в глибину, в ширину і рандомізованого пошуку; на Мал. 18.29 показано дерево, обчислене за допомогою рандомізованого пошуку для прикладу, представленого на Мал. 18.13 і Мал. 18.24 . Для рандомізованого пошуку не характерні ні довгі шляхи, як в DFS, ні вузли з великими ступенями, як в BFS. Форми цих дерев і графіків розмірів накопичувача залежать від структури конкретного графа, на якому проводиться пошук, але вони все-таки характеризують різні алгоритми.

Пошук на графах можна узагальнити і далі, якщо працювати з лісом (а не тільки з деревом). Ми вже впритул пішли до цього рівня абстракції, проте відкладемо розгляд ряду таких алгоритмів до "Мінімальні остовне дерева" .

Мал.18.29.

Граф рандомізованого пошуку

Тут показаний процес рандомізованого пошуку на графі (зліва) в тому ж стилі, що і на малюнках 18.13 і 18.24. Форма дерева пошуку знаходиться десь між пошуком в глибину і пошуком в ширину. Динамічні характеристики цих трьох алгоритмів, які відрізняються тільки структурою даних, необхідної для виконання роботи, разюче відрізняються.

вправи

18.61. Проаналізуйте переваги і недоліки реалізації узагальненого пошуку на графі на базі наступного правила: "Перенесіть ребро з накопичувача в дерево. Якщо вершина, в яку воно веде, чи не відвідувалася, відвідайте цю вершину і занесіть в накопичувач все інцідентние їй ребра".

18.62. Розробіть реалізацію АТД графа, представленого списками суміжності, яка містить ребра (а не тільки їх кінцеві вершини) в списках. Потім реалізуйте пошук на графі, заснований на стратегії з вправи 18.61, який відвідує кожне ребро, але руйнує граф, скориставшись тим, що ребра всіх вершин можна переміщати в накопичувач за допомогою зміни лише однієї посилання.

18.63. Доведіть, що рекурсивний пошук у глибину (програма 18.3) еквівалентний узагальненому пошуку на графі з використанням стека (програма 18.10) в тому сенсі, що обидві програми відвідують всі вершини будь-якого графа в одному і тому ж порядку тоді і тільки тоді, коли ці програми переглядають списки суміжності в різних напрямках.

18.64. Наведіть три різних порядку обходу при рандомізованому пошуку на графі

3-71-47-80-55-23-82-90-64-92-66-4.

18.65. Чи може рандомізований пошук відвідати вершини графа 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.

в порядку зростання їх індексів? Обгрунтуйте свою відповідь.

18.66. Скористайтеся бібліотекою STL для побудови реалізації узагальненої черзі ребер графа, яка блокує занесення ребер з однаковими вершинами за правилом ігнорування нових елементів.

18.67. Розробіть алгоритм рандомізованого пошуку на графі, який з однаковою ймовірністю вибирає з накопичувача будь ребро. Вказівка. Див. Програму 18.8.

18.68. Опишіть стратегію обходу лабіринту, яка відповідає використанню звичайного стека магазинного типу для узагальненого пошуку на графі (див. Розділ 18.1).

18.69. Додайте в узагальнений пошук на графі (див. Програму 18.10) можливість виводу значень висоти дерева та відсотка оброблених ребер для кожної переглядається вершини.

18.70. Емпірично визначте середні значення величин, описаних у вправі 18.69, для узагальненого пошуку на графі з використанням випадкової черзі в графах різних розмірів і побудованих на основі різних моделей (див. Вправи 17.64-17.76).

18.71. Реалізуйте похідний клас, який будує динамічні графічні анімації узагальненого пошуку на графах, в яких з кожною вершиною пов'язані координати (x, у) (див. Вправи 17.55-17.59). Протестуйте отриману програму на випадкових евклідових графах з сусідніми зв'язками, використовуючи стільки крапок, скільки зможете обробити за прийнятний проміжок часу. Ваша програма повинна будувати зображення на зразок діаграм на Мал. 18.13 , Мал. 18.24 и Мал. 18.29 , Хоча для позначення вершин і ребер, які знаходяться в дереві, або в накопичувачі, або ще не переглянуті, замість відтінків сірого можна використовувати різні кольори.