Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Особливості реалізації пошуку в глибину в графах
Інформація про навчальний заклад
ВУЗ:
Львівський національний університет ім.Івана Франка
Інститут:
Не вказано
Факультет:
ФЕіП
Кафедра:
Не вказано
Інформація про роботу
Рік:
2016
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
СП
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України Львівський національний університет імені Івана Франка
Звіт про виконання лабораторної роботи №4:
«Особливості реалізації пошуку в глибину в графах»
Львів 2016
Завдання до роботи № 4.
Тема роботи: Особливості реалізації пошуку в глибину у графах.
Вихідні дані:
Задано:
– звичайний розгалужений граф (не менше 4-5и гілок) порядку 15-20 розміром 20-30;
– початкова і цільова вершини графа;
– напрям обходу.
Завдання:
– візуально представити заданий граф;
– створити програму виконання пошуку на одній з мов програмування;
– знайти найкоротший шлях до вказаної вершини, використовуючи алгоритм пошуку в глибину;
– відмітити переваги і недоліки цього виду пошуку.
Вимоги:
У програмі передбачити:
– можливість змінювати розмірність і порядок графа;
– можливість змінювати напрям обходу графа;
– зреалізувати візуалізацію процесу пошуку і його результатів.
Теоретичні відомості
Відповідно до використання евристичної інформації алгоритми діляться на два класи – сліпі та евристичні (спрямовані).
У сліпих алгоритмах пошуку місцезнаходження в просторі цільової вершини ніяк не впливає на порядок, в якому розкриваються (перебираються) вершини.
Сліпий метод має два види пошуку –пошук углиб і пошук вшир.
При пошуку вширину на фіксованому рівні досліджуються всі альтернативи і лише після цього здійснюється перехід на наступний рівень. Метод може виявитися гіршим за метод пошуку вглибину, якщо в графі всі шляхи, що ведуть до цільової вершини, розташовані приблизно на одній і тій же глибині.
При пошуку углибинукожна альтернатива досліджується до кінця, без урахування решти шляхів. Метод поганий для "високих" дерев, оскільки легко можна прослизнути мимо потрібної гілки і витратити багато зусиль на дослідження "порожніх" альтернатив.
Метод перебору в глибину.
При переборі в глибину насамперед слід розкривати ті вершини, які були побудовані останніми. Першою вершиною, що розкривається, є коренева. Процес завжди буде йти по крайній лівій (або правій – згідно з заданим напрямком обходу) гілці вершин. Щоб якось обмежити перебір, вводиться поняття глибини вершини в дереві перебору. Глибина кореня дерева дорівнює нулю, а глибина будь-якої наступної вершини дорівнює одиниці плюс глиби на вершини, що безпосередньо їй передує. Найбільшу глибину завжди буде мати та вершина, яка повинна бути в цей момент розкрита. Якщо шлях, який утворюється при пошуку, виявляється марним, тобто при заданій глибині розкриття цільової вершини не досягнуто, необхідно повернутися в попередню розкриту вершину і спробувати ще раз застосувати до неї операцію розкривання. І так до тих пір, поки не буде отримана цільова вершина.
Повернення здійснюється за допомогою покажчиків. Як тільки в про-цесі породження вершин досягається задана гранична глибина, розкривається вершина найбільшої глибини, що не перевищує цієї межі.
Порядок обходу вершин графа проілюстровано на рис. 2.
/
Рис. 2. Порядок обходу вершин графа при пошуку у глибину.
Алгоритм перебору в глибину полягає в наступному.
1. Розкривається початкова вершина, відповідна початкового стану.
2. Розкривається перша вершина, що отримується в результаті розкриття початкової. Ставиться покажчик вершини.
3. Якщо ця вершина розкривається, то наступною буде розкриватися знову породжена вершина. Якщо ж вершина не розкривається, то процес повертається в попередню вершину.
4. Після отримання цільової вершини процес розкриття закінчується і за вказівниками будується шлях, що веде до кореня. Відповідні дугам (їх послідовний перелік) оператори утворюють рішення задачі.
5. Якщо для заданої глибини розкриття цільова вершина не знаходиться, то весь процес повторюється знову, а в якості нової вершини розглядається сама ліва з отриманих на попередньому етапі.
Для виконання роботи було написано програму в середовищі Visual Studio 2015 мовою C#.
Дана програмна реалізація алгоритму демонструє процес знаходження шляху в графі за допомогою алгоритму пошуку в глибину з порядком обходу: зліва направо та справа наліво. На рис. 1 бачимо загальний вигляд початкового вікна програми.
/
Рис. 1. Початкове вікно програми.
Для початку роботи необхідно вибрати граф, натиснувши відповідну кнопку, вибрати порядок обходу: «Від молодшого біта до старшого», або «Від старшого біта до молодшого», також ввести номер початкової та цільової вершин. Натиснути кнопку «Пошук» для запуску пошуку по графі. Зеленим позначено ребра біля не розкритих вершин графа. Фіолетовим ребра біля розкритих вершин. Червоним позначається шлях, знайдений в процесі пошуку на графі.
Нижче приведено порівняння кількості ітерацій для визначення впливу евристики на швидкість та ефективність пошуку у графах (рис. 2.-19.), адже евристичні алгоритми використовують апріорну, евристичну інформацію про загальний вид графа-простору про те, де в просторі станів розташована мета; тому для розкриття зазвичай вибирається перспективніша саме з цієї точки зору вершина.
На рисунках 2 і 3 зображено пошук в глибину з різними способами обходу від початкової 0 до цільової вершини 12.
/
Рис. 2. Пошук в глибину, за способом обходу від молодшого біта до старшого (0-12)
/
Рис. 3. Пошук в глибину, за способом обходу від старшого біта до молодшого (0-12)
/
Рис. 4. . Пошук в глибину, за способом обходу Від молодшого біта до старшого для графа 1 (0-23)
/
Рис. 5. Пошук в глибину, за способом обходу Від старшого біта до молодшого для графа 1 (0-23)
/
Рис. 6. Пошук в глибину, за способом обходу Від молодшого біта до старшого для графа 1 (0-27)
/
Рис. 7. Пошук в глибину, за способом обходу Від старшого біта до молодшого для графа 1 (0-27)
/
Рис. 8. Пошук в глибину, за способом обходу Від молодшого біта до старшого для графа 1 (23-32)
/
Рис. 9. Пошук в глибину, за способом обходу Від старшого біта до молодшого для графа 1 (23-32)
/
Рис. 10. Пошук в глибину, за способом обходу Від молодшого біта до старшого для графа 1 (32-23)
/
Рис. 11. Пошук в глибину за способом обходу Від старшого біта до молодшого для графа 1 (32-23)
/
Рис. 12. Пошук в глибину, за способом обходу Від молодшого біта до старшого для графа 5 (6-84)
/
Рис. 13. Пошук в глибину, за способом обходу Від старшого біта до молодшого для графа 5 (6-84)
/
Рис. 14. Пошук в глибину, за способом обходу Від молодшого біта до старшого для графа 5 (84-6)
/
Рис. 15. Пошук в глибину, за способом обходу Від старшого біта до молодшого для графа 5 (84-6)
/
Рис. 16. Пошук в глибину, за способом обходу Від молодшого біта до старшого для графа 5 (45-6)
/
Рис. 17. Пошук в глибину, за способом обходу Від старшого біта до молодшого для графа 5 (45-6)
На рисунках 18 і 19 зображено пошук в ширину з різними способами обходу від початкової 7 до цільової вершини 84 , у обох випадках довжина шляху однакова – 5, однак кількість кроків різна: 77 та 14 кроків відповідно. В даному випадку використання порядку обходу Від старшого біта до молодшого дозволяє знайти цільову вершину за значно меншу кількість ітерацій.
/
Рис. 18. Пошук в глибину, за способом обходу Від молодшого біта до старшого для графа 7 (7-84)
/
Рис. 19. Пошук в глибину, за способом обходу Від старшого біта до молодшого для графа 7 (7-84)
Висновки: реалізовано програму, що демонструє алгоритм пошуку в глибину на графі, досліджено роботу алгоритму за різних способів обходу, а також у різних комбінаціях стартової і цільової вершин. Здійснено порівняння кількості кроку залежно від способу обходу, та визначено, яку роль відіграє евристична інформація у швидкості обходу графа. У звіті приведено дослідження трьох різних графів. Пошук в глибину є ефективним, коли ми знаємо, що цільова вершина розміщена на краю дерева, тоді давши порядок обходу, який закінчується в цьому краю, ми можемо перебрати декілька крайніх віток до листків і знайти цільову вершину. Отже швидкість обходу залежить від порядку розгляду сусідів, структури графу, а також розміщення стартової і фінішної вершин графа.
02.04.2017 12:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора