Оптимистический и пессимистический взгляд на жизнь
Сверху вниз и снизу вверх. Часть I
Parsing - синтаксический анализ Сверху вниз и снизу вверх. Часть II
UPDATE 17-10-2010:
Testing first - сначала тестировать Сверху вниз и снизу вверх. Часть IV
END OF UPDATE
В рамках данной заметки я не буду давать точное определение BFS и DFS, ограничусь ли интуитивным описанием. Сначала я объясню, что такое BFS, затем, что такое DFS, а затем как это связано с основной мыслью серии заметок.
Ниже есть продолжение.
BFS - поиск в ширину
Рассмотрим карту дорог Германии.
Наша цель посетить все города без никаких дополнительных ограничений, т.е. можно быть в одном и том же городе дважды, нам не нужно искать самый короткий путь и т.п. С такими упрощениями карта дорог будет выглядеть так:
Один из способов это сделать, это BFS. Достаём бумагу и пишем на ней город, с которого мы хотим начать путешествие Frankfurt. Вычеркиваем его и едем туда.
Находясь в Frankfurt-е записываем на бумаге список городов, в который можно попасть оттуда. Едем в первый не вычеркнутый город в этом списке (Mannheim). Достаём нашу бумагу и в конец списка добавляем города, которые мы можем посетить, находясь в Mannheim. Далее вычеркиваем Mannheim и едем туда. Так продолжаем ездить пока не вычеркнем все города в нашем списке. Получится следующая картина:
Серый цвет показывает действие - добавление города в список. Чёрный цвет - посещение соответствующего города.
Таким образом легко видеть, что мы как бы проходит граф "по уровням" или "вширь".
DFS - поиск в глубину
Этот поиск похож на способ, каким мы пытаемся найти выходи из лабиринта. Просто пытаемся продвигаться "вглубь" ("вниз" по стрелкам), до тех пор пока не достигнет тупика. Попав в тупик мы возвращаемся к последнему разветвлению (метафорически это можно представить как будто мы используем нить Ариадны) и пробуем другой путь.
Как это связано с темой заметки "сверху вниз и снизу вверх"? Легко видеть, что BFS - это своеобразный способ решение задач "сверху вниз". На каждом этапе мы делаем краткий обзор системы, определяя (записываем в наш список, красим в серый цвет), но не детализируя любые подсистемы следующего уровня. Затем каждая подсистема (каждый "город" в нашем списке) усовершенствуется повторяя процесс.
Таким образом, DFS - это своеобразный способ решение задач "снизу вверх". Мы берём систему и начинаем её разбивает на всё меньшие и меньшие подсистемы, пока не доходим до атомов ("тупика"), которые мы можем имплиментировать (мы не обязаны их тут же имплиментировать, можем просто записать в отдельный список). Затем мы возвращаемся к последней развилке и продолжаем поиск пока не доходим опять до тупика (следующего атома). Здесь, есть два разных подхода. Можно, как я написал, составить отдельный список, в который будут записаны все "атомы", затем под-системы первого уровня (объедение атомов) и так выше и выше пока не будет получено описание всей системы. Своеобразный дизайн системы (лично я предпочитаю этот путь). Можно, также, каждый раз получив минимальную подсистему её тут же импиментировать. Этот подход уместен, когда "большая" система относительно простая ("маленькая") или когда нет на дизайн времени.
Надеюсь, этот пост был попроще предыдущих, а главное в нём нет загромождения деталей, надеюсь понятна мысль, которую я хотел донести. Если так, то остальные посты вы можете не читать. Впрочем, если вы не слышали об этих техниках, рекомендую прочитать, чтобы с ними ознакомится.
В следующих постах будет рассмотрены различные варианты применения этих подходов на примере:
4. Testing first - Сначала тестировать.
5. Note first - Сначала писать комментарии.
При написании поста была использована статья в википедии
http://en.wikipedia.org/wiki/Breadth-first_search
Текстовое содержимое доступно в соответствии с GNU Free Documentation License: http://www.gnu.org/copyleft/fdl.html. Источник: Википедиа http://en.wikipedia.org/wiki/Breadth-first_search. Авторы: http://en.wikipedia.org/w/index.php?title=Breadth-first_search&action=history
Продолжение следует.
No comments:
Post a Comment