Яка процедура ми можемо використовувати для освоєння лабіринту BFS або DFS - алгоритм, складність часу, глибина першого пошуку, широта першого пошуку, лабіринт

Я знаю, що ми можемо використовувати DFS для дослідження лабіринту. Але я думаю, що ми також можемо використовувати BFS для дослідження лабіринту. Я тут трохи заплутався, бо більшість прочитаних книг і статей використовували DFS для цієї проблеми. Я думаю, що це Кращий випадок часова складність DFS буде кращою порівняно з BFS. Але Середня і Найгірше Випадок часова складність буде однаковою як для BFS, так і для DFS, і тому ми віддаємо перевагу DFS над BFS. Я правий чи у мене є якесь неправильне уявлення

Відповіді:

У них схожий час роботи, але будь-яка може значно перевершити інших за будь-якою задачею просто через порядок відвідування комірок.

Що стосується використання місця, BFS буде в середньому використовувати більше пам'яті дерев, але для більш загальних графіків у певних випадках він може істотно використовувати менше пам'ять

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

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

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

Однак, якщо ви шукаєте найкоротший шлях для якоїсь даної комірки в загальній сітці, використовуйте BFS (або A *), оскільки це гарантує знаходження найкоротшого шляху, де DFS цього не робить (ви все ще можете використовувати будь-який у лабіринті, де є лише один шлях до будь-якої даної комірки).

Я дуже вражений тим, що досі ніхто не згадував про різницю в результатах, наданих DFS і BFS.

Основна різниця між цими двома алгоритмами полягає в тому, що BFS повертає найкоротший шлях і DFS повертає лише шлях.

Отже, якщо ви хочете отримати найкоротший шлях використання BFS, в іншому випадку враховуйте інші плюси і мінуси (пам’ять тощо)

І те, і інше має бути рівнозначним. DFS використовується більше, оскільки його трохи легше впровадити.