середу, 2 листопада 2011 р.

Теорія графів. Пошук у ширину

У п'ятницю 4 листопада о 15.00 відбудеться чергове заняття обласної очно-дистанційної Школи олімпійського резерву з програмування.
Тема заняття "Теорія графів. Пошук у ширину".

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

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

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

Пошук в ширину – один із базових алгоритмів, що є основою багатьох інших. Наприклад, алгоритм Дейкстри пошуку найкоротших шляхів з одної вершини й алгоритм Прима пошуку мінімального остовного дерева можуть розглядатися як узагальнення пошуку в ширину.

Нехай дано граф G = (V, E) і фіксована початкова вершина v. При обході графа в ширину на першому кроці відвідуються всі вершини, сусідні з початковою. При другому проході відвідуються всі вершини "на відстані двох ребер" від початкової. При кожному новому проході опрацьовуються вершини, відстань від яких (кількість ребер) до початкової на одиницю більша від попередньої. У графі можуть бути цикли, тому не виключено, що одну й ту саму вершину можна досягти з початковою двома різними шляхами. Ця вершина опрацьовується один раз, коли буде досягнутою найкоротшим до неї шляхом, і відвідувати її другий раз немає сенсу. Тому, щоб попередити повторне відвідування, доцільно або вести список відвіданих вершин, або завести для кожної прапорець, який би вказував, чи опрацьована вже ця вершина.

Немає коментарів:

Дописати коментар