Зміст
Введення
1. Робота алгоритму пошуку в ширину
1.1 Неформальне опис
1.2 Формальний опис
2. Схема алгоритму пошуку в ширину
3. Приклади реалізації
Висновок
Список літератури
Введення
Алгоритм - набір інструкцій lt;http://ru.wikipedia/wiki/%D0%9E%D0%BF%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80_%28%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%29gt;, описують порядок дій виконавця для досягнення результату рішення задачі lt;http://ru.wikipedia/wiki/%D0%A0%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87gt; за кінцеве число дій. У старій трактуванні замість слова порядок використовувалося слово послідовність raquo ;, але в міру розвитку паралельності в роботі комп'ютерів слово послідовність стали замінювати більш загальним словом порядок raquo ;. Це пов'язано з тим, що робота якихось інструкцій алгоритму може бути залежна від інших інструкцій або результатів їх роботи. Таким чином, деякі інструкції повинні виконуватися строго після завершення роботи інструкцій, від яких вони залежать. Незалежні інструкції або інструкції, що стали незалежними через завершення роботи інструкцій, від яких вони залежать, можуть виконуватися в довільному порядку, паралельно або одночасно, якщо це дозволяють використовувані процесор і операційна система.
Раніше часто писали алгорифм raquo ;, зараз таке написання використовується рідко, але, тим не менш, має місце (наприклад, Нормальний алгорифм lt;http://ru.wikipedia/wiki/%D0%9D%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%84%D0%BCgt; Маркова lt;http://ru.wikipedia/wiki/%D0%9C%D0%B0%D1%80%D0%BA%D0%BE%D0%B2,_%D0%90%D0%BD%D0%B4%D1%80%D0%B5%D0%B9_%D0%90%D0%BD%D0%B4%D1%80%D0%B5%D0%B5%D0%B2%D0%B8%D1%87_%28%D0%BC%D0%BB%D0%B0%D0%B4%D1%88%D0%B8%D0%B9%29gt;).
Часто в якості виконавця виступає деякий механізм (комп'ютер, токарний верстат, швейна машина), але поняття алгоритму необов'язково відноситься до комп'ютерних програм lt;http://ru.wikipedia/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80%D0%BD%D0%B0%D1%8F_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0gt;, так, наприклад, чітко описаний рецепт приготування страви також є алгоритмом, в такому випадку виконавцем є людина.
Поняття алгоритму відноситься до первинних, основним, базисним поняттям математики. Обчислювальні процеси алгоритмічного характеру (арифметичні дії над цілими числами, знаходження найбільшого загального дільника двох чисел і т.д.) відомі людству з глибокої давнини. Однак в явному вигляді поняття алгоритму сформувалося лише на початку XX століття.
Пошук в ширину - метод обходу графа і пошуку шляху в графі. Пошук в ширину є одним з неінформованих алгоритмів пошуку.
Малюнок 1 - Пошук в ширину
1. Робота алгоритму пошуку в ширину
Пошук в ширину
Пошук завширшки або BFS (breadth-first search, пошук спочатку в ширину ??raquo;) - це метод обходу графа, за яким після стартової вершини спочатку відзначаються всі вершини суміжні з нею, тобто всі досяжні за один крок, а потім все досяжні за два (суміжні з попередніми і не суміжні зі стартовою), а потім за три кроки і т.д. Це нагадує розповсюдження хвилі, з цього пошук в ширину називає методом хвилі.
Приклад пошуку в ширину
Пошук в ширину (обхід за рівнями) - один з алгоритмів обходу графа. Метод лежить в основі деяких інших алгоритмів близької тематики. Пошук в ширину увазі поуровневого дослідження графа: спочатку відвідується корінь - довільно обраний вузол, потім - всі нащадки даного вузла, після цього відвідуються нащадки нащадків і т.д. Вершини проглядаються в порядку зростання їх відстані від кореня.
Пошук в ширину працює шляхом послідовного перегляду окремих рівнів графа, починаючи з вузла-джерела.
Розглянемо всі ребра, що виходять з вузла. Якщо черговий вузол є цільовим вузлом, то пошук завершується; в іншому випадку вузол додається в чергу. Після того, як будуть перевірені всі ребра, що виходять з вузла, з черги витягується наступний вузол, і процес повторюється.
Нехай заданий граф G=(V, E) і корінь s, з якого починається обхід. Після відвідин вузла s, наступними за ним будуть відвідані суміжні з s вузли (безліч суміжних з s вузлів позначимо як q; очевидно, що q? V, тобто q - деяке підмножина V). Далі, ця процедура повторитися для вершин суміжних з вершинами з безлічі q, за винятком вершини s, тому вона вже переглянуло. Так, продовжуючи обходити рівень за рівнем, алгоритм обійде всі доступ...
