Студопедия

КАТЕГОРИИ:



Мы поможем в написании ваших работ!

Архитектура-(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)

Мы поможем в написании ваших работ!

Эвристический поиск


 

Методы слепого поиска требуют чрезмерных затрат времени и (или) памяти. Стремление сократить время поиска привело к созданию эвристических методов поиска, т.е. методов, использую­щих некоторую информацию о предметной области для рассмотрения не всего пространства поиска, а таких путей в нем, которые с наи­большей вероятностью приводят к цели. Один из них состоит в использовании эвристической информации для определения на каждом шаге дальнейшего направления перебора. Для этого необходимо ввести меру "перспективности" вершины в виде некоторой оценочной функции:

,

где - соответствует расстоянию на графе от узла до начального состояния;

- оценка расстояния от до узла, представляющего конечное состояние(целевое).

В некоторых случаях удается ввести такую оценочную функцию, что она, сокращая перебор, не теряет свойства полноты. Чаще же используемые эвристики, существенно сокращая перебор, влекут за собой потерю свойства полноты. Как правило, оценочные функции пытаются количественно оценить рас­стояние от текущей вершины до конечной. Из двух вершин при оди­наковой глубине перспективней та, от которой меньше расстояние до цели. Для многих приложений, в частности для экспертных систем, применение количественных оценок не позволяет эффективно направлять процесс поиска.

На рис.12 показано гипотетическое пространство с эвристическими оценками некото­рых из его состояний. Состояния, по которым велся эвристи­ческий поиск, отмечены полужирным шрифтом, отметим, что поиск не ведется по всему пространству. Другими словами, цель алгоритма поиска состоит в том, чтобы прийти к целевому состоянию кратчайшим путем. Чем более обоснованной является эври­стика тем меньше состояний нужно проверить при поиске цели.

Путь, по которому находится целевое состояние, по­казан на рисунке жирными стрелками. Предположим, что Р — целевое состояние. Поскольку Р — цель, состояния на пути к Р имеют низкие эвристические зна­чения. Эвристика подвержена ошибкам: состояние О имеет более низкое эвристическое значение, чем целевое, и поэтому было исследовано ранее. Данный алгоритм восстанавливается после ошибки и находит целевое состояние.

 

Рисунок 12 - Эвристический поиск в гипотетическом пространстве состояний и алгоритм

 

<== предыдущая лекция | следующая лекция ==>
Сравнение стратегий поиска | Индуктивное обучение

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


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



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


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

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