Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Сравнение стратегий поиска


Поиск в глубину

Этот вид поиска противоположен поиску в ширину. Поиск в глубину (рис.9) просматривает одно направление до тех пор, пока его вершины не исчерпаются или пока не будет достигнута цель. Проблема заключается в том, что при этом поиске при неизвестной глубине может возникнуть потребность в некотором останавливающем правиле.

 

Рисунок 9 – Дерево поиска в глубину

Сравним поиск в глубину и в ширину на примере.

Рассмотрим в качестве примера задачу построения слова из некоторого множества букв. Задавшись набором операций установки букв, можно сформировать пространство состояний. .

Предположим, что множество доступных букв включает P = {К, Т, О}. На каждом уровне графа мы будем добавлять по одной определенной букве. Каждая ветвь, исходящая из узла, соответствует установке буквы в определенную позицию в последовательности, а эта последовательность должна образовать осмысленное слово. Если это про­изошло, то головоломка считается собранной. Целью работы будет построить все распознаваемые человеком последовательности и найти слово КОТ.

Примем за начальную точку – O . Дерево пространства состояний (неизменно) рис.10:

 

Рисунок 10 – Дерево пространства состояний

Метод формирования, анаграмм последовательным перечислением является приме­ром применения алгоритма, получившего наименование generate-and-test (порождение и проверка).

1. Генерировать новое состояние, модифицируя существующее; например, изменитьоследовательность букв, добавив новую в существующую последовательность.

2. Проверить, не является ли образовавшееся состояние конечным (решением); на­пример, проверить, не является ли образовавшаяся последовательность осмыслен­ным словом. Если это так, то завершить, иначе перейти к шагу (1).

Алгоритм имеет два основных варианта: поиск в глубину и поиск в ширину. Отличаются варианты порядком формирования состояний на шаге (1).

Алгоритм поиска в ширину - сначала формируются все "соседи" узла N , а потом уже строятся его потомки. Таким образом, в алгоритме поиска в ширину просматриваются последовательно состояния, представлен­ные узлами одного и того же уровня на графе. Дерево решений при использовании поиска в ширину:

 

 

Рисунок 11 – Дерево решений при использовании поиска в ширину

 

Алгоритм поиска в глубину. Для любого данного узла N алгоритм поиска в глубину строит потомок этого узла, т.е. формирует состояние, которое образуется в результате применения операторов к уз­лу N, а потом переходит к формированию узла, ближайшего к N, на том же уровне графа ("соседу" N ), т.е. формирует состояние, которое образуется в результате применения оператора к узлу-родителю N.



Дерево решений при использовании поиска в глубину:

Рисунок 12 – Дерево решений при использовании поиска в глубину

 

Алгоритм поиска в ширину отыскивает решение, путь к которому кратчайший, если оно существует (это кратчайший путь между исходным состоянием и решением). Алгоритмы, обладающие такими свойствами, называются разрешимыми.

Поиск в глубину может быстрее найти решение, особенно если используются эвристики для выбора очередной ветки, но алгоритм может никогда не закончиться, если пространство состояний неограниченно. Оба алгоритма завершат работу (найдут конечное состояние) после формирования узла «кот». Но алгоритму поиска в ширину придется для этого "посетить" пять узлов (сформировать и проанализировать пять состояний), а алгоритму поиска в глуби­ну - четыре.

Нетрудно заметить, что число узлов растет экспоненциально по мере увеличения числа уровней на графе. Это явление часто называют комбинаторным взрывом, и оно представляет очень серьезную проблему при программировании таких задач, например при "грубом" переборе всех возможных вариантов позиций в игре в шахматы. Поскольку человеческий мозг слабее компьютера при решении задач, связанных с перебором вариантов, естественно предположить, что серьезный шахматист решает эту задачу каким-то другим способом. Скорее всего, он использует свой опыт, воображение и аналитические способности, во-первых, для формирования общей стратегии игры, а во-вторых, для выбора наилучшего очередного хода. Вот такой-то способ решения мы и на­зываем "интеллектуальным".

 

<== предыдущая лекция | следующая лекция ==>
Поиск в ширину | Эвристический поиск

Дата добавления: 2014-01-03; Просмотров: 293; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2020) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.002 сек.