Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 5.1.1. АЛГОРИТМЫ А И А*Решение произвольной задачи рассматривается как поиск пути на графе от некоторой фиксированной вершины, называемой начальным состоянием, к одной из вершин, принадлежащих некоторому заранее выбранному подмножеству, называемому множеством конечных состояний. Этот граф, характеризующий пространство состояний, лишь потенциально известен в том смысле, что помимо начального и конечных состояний имеется множество операторов, позволяющих порождать новые состояния из заданного. Применение произвольного оператора к некоторому выделенному состоянию («родительскому” состоянию) представляется в виде дуги, направленной от этого родительского состояния к вершине — потомку, называемой «дочерним” состоянием. Каждой дуге приписывается некоторая стоимость, характеризуемая положительным числом. Цель поиска заключается в построении пути между начальным состоянием и одним из конечных состояний, имеющего минимальную стоимость, причем стоимость пути рассчитывается как сумма стоимостей составляющих его дуг. Методология поиска состоит в последовательном спуске по дереву от начального состояния до тех пор, пока не будет достигнуто некоторое конечное состояние Граф, соответствующий заданному этапу поиска, называется графом поиска Когда не удается достичь конечного состояния в графе поиска, возникает задача выбора некоторого состояния, на которое будут действовать операторы с целью порождения новых состояний ("раскрытие” состояния). Этот выбор направляется оценочной функцией, которая каждому способному к раскрытию состоянию
Функция В алгоритме производится проверка на принадлежность некоторого состояния к множеству конечных состояний, причем она делается не при возникновении этого состояния на графе поиска, а лишь тогда, когда указанное состояние берется для раскрытия Если граф поиска конечный, а эвристический член В более общем случае если не обеспечивается существование такой нижней оценки
|
1 |
Оглавление
|