0 просмотров

Искусственный
Интеллект

Все методы поиска в предыдущем разделе являются неинформативными в том смысле, что они не учитывают цель. Они не используют никакой информации о том, куда они пытаются попасть, если только не наткнутся на цель. Одной из форм эвристической информации о том, какие узлы кажутся наиболее перспективными, является эвристическая функция. ч (п), который принимает узел н и возвращает неотрицательное действительное число, которое является оценкой стоимости пути от узла н к целевому узлу. Функция ч (п) является недооценивать если ч (п) меньше или равно фактической стоимости пути с наименьшей стоимостью от узла н к цели.

Эвристическая функция – это способ информирования поиска о направлении к цели. Он предоставляет информированный способ угадать, какой сосед узла приведет к цели.

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

Стандартный способ получения эвристической функции состоит в том, чтобы решить более простую задачу и использовать фактические затраты в упрощенной задаче в качестве эвристической функции исходной задачи.

Пример 3.12: Для графика на рис. 3.2 в качестве эвристической функции можно использовать прямолинейное расстояние в мире между узлом и позицией цели. Следующие примеры предполагают следующую эвристическую функцию:

ч(почта)=26ч (тс)=23ч(о103)=21
ч(о109)=24ч(о111)=27ч(о119)=11
ч(о123)=4ч(о125)=6ч(р123)=
ч(б1)=13ч(б2)=15ч(б3)=17
ч(б4)=18ч(с1)=6ч(с2)=10
ч(с3)=12ч (хранилище)=12

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

Пример 3.13: Рассмотрим робота-доставщика из примера 3.2, где пространство состояний включает посылки, которые нужно доставить. Предположим, что функция стоимости — это общее расстояние, пройденное роботом для доставки всех посылок. Одной из возможных эвристических функций является максимальное расстояние от посылки до пункта назначения. Если бы робот мог нести только одну посылку, возможной эвристической функцией была бы сумма расстояний, на которые должны быть перенесены посылки. Если робот может нести несколько посылок одновременно, это не может быть занижением фактической стоимости.

час Функция может быть расширена для применения к (непустым) путям. Эвристическое значение пути — это эвристическое значение узла в конце пути. То есть:

ч(〈nо. нк〉)=h(nк)

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

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

Рисунок 3.8: График, который не подходит для поиска по принципу «лучшее-первое».

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

  • 3.6.1 А * Поиск
  • 3.6.2 Краткое изложение стратегий поиска

Искусственный интеллект, Пул и Макворт (LCI, UBC, Ванкувер, Канада)
Copyright © 2010, Дэвид Пул и Алан Макворт.
Эта работа находится под лицензией Creative Commons Attribution-Noncommercial-No Derivative Works 2.5 Canada License.

голоса
Рейтинг статьи
Статья в тему:  Как искусственный интеллект разделяет людей
Ссылка на основную публикацию
0
Оставьте комментарий! Напишите, что думаете по поводу статьи.x
Adblock
detector