Эвристический поиск. Основные определения | MetodPro.ru

Реклама на сайте

Эвристический поиск. Основные определения


Программу ПсП можно получить как результат усовершенствования ПвШ. Один из путей использования эвристической i по задаче – это получение численных эвристических оценок. Для вершин ПС. Оценка вершины указывает на то, на сколько данная вершина перспективна с точки зрения достижения цели.

Идея состоит в том, чтобы всегда продолжать поиск, начиная с наиболее перспективной вершин, выбранной из всего Мн-ва Кандидатов. Аналогично ПаШ ПсП начинается со стартовой вершины и использует множество путей кандидатов. В то время как ПвШ всегда выбирает для продолжения самый короткий путь, т.е переходит в вершины наименьшей глубины. ПсП использует следующее усовершенствование: для каждого кандидата вычисляется оценка и для продолжения выбирается кандидат с наилучшей оценкой.

Будем предполагать, что для дуг ПС определена функция стоимости вида: c(n,n’)-стоимость перехода из вершины n к вершине приемнику n'. Пусть f – эвристическая оценочная функция, при помощи которой мы получаем для каждой вершины n оценку f(n) “трудности” этой вершины, тогда наиболее перспективной вершиной кандидатом следует считать вершину, для которой f принимает min значение.

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

Предположим что такой путь существует и что t –целевая вершина для которой этот путь минимален, тогда оценку f(n) можно представить в след.виде:

F(n)=g(n) + h(n),

Где g(n) – оценка стоимости оптимального пути из S в n, когда h(n) – оценка стоимости пути из n в t.

Когда в процессе поиска мы попадаем в вершину n мы оказываемся в следующей ситуации: путь из S в n уже найден и его стоимость может быть вычислена как сумма стоимостей составляющих его дуг. Этот путь не обязательно будет оптимальным (возможно существует более дешёвый, ещё не найденный путь из S в n), однако стоимость этого пути можно использовать в качестве оценки g(n) min-ой стоимости пути из s в n. Относительно 2го слагаемого h(n) трудно что-либо сказать, так как к этому моменту область пространства состояний, лежащая между n и t ещё “не изучена” программой поиска –> о значении h(n) можно строить только догадки на основании эвристических соображений , т.е на основе тех значений о конкр. Задаче , которым обладает алгоритм, т.к значение h зависит от предметной области универсального метода для его вычисления нет. Пока будем считать, что тем или иным образом функция h задана. После выполнения этих этапов ПсП может представить след. Образом. Процесс поиска состоит из нек. Числа конкурирующих между собой подпроцессов, каждый из которых занимается своей альтернативой, т.е просматривает своё поддерево, у поддеревьев есть свои поддеревья, их рассматривают подпроцессы процессов и т.д. В каждый данный момент среди всех конкурирующих процессов активен только один, который занимается наиболее перспективной в настоящий момент альтернативой (с наименьшим значением f).

Остальные процессы ждут того момента, когда f-оценки изменятся и в результате какая-нибудь альтернатива станет наиболее перспективной. В этом случае происходит переключение активности на эту альтернативу. Механизм активации (дезактивации) процессов функционирует так: процесс, работающий над текущей альтернативой высшего приоритета получает нек. “Бюджет” и остаётся в активном состоянии до тех пор, пока бюджет не будет исчерпан.  Находясь в активном состоянии процесс продолжает углублять свое поддерево, встретив целевую вершину он выдаёт соответствующее решение. Величина “Бюджета” предоставл. процессу на каждый конкретный запуск определяется эвристической оценкой конкурирующей альтернативы, ближайшей к данной.



Методические пособия

  • Системы автоматизированного проектирования
  • Социология молодёжи
  • Общая социология
  • Криптография
  • Проектирование трансляторов
  • Компьютерная графика
  • Моделирование систем
  • Информационная безопасность
  • Теория вычислительных процессов
  • Логические основы искусственного интелекта
  • Проектирование распределённых информационных систем