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