Композитная эвристика для 8-головоломок

Question

При чтении искусственного интеллекта современный подход Я натолкнулся на концепцию выведения эвристики из стоимости решения подзадачи данной проблемы.

Например, следующие головоломки показывают подпункт 8-головоломки, где цель состоит в том, чтобы поместить плитки 1, 2, 3, 4 в их правильные положения.

Start State = [ * 2 4 ] Goal State = [ 1 2 ]      
       [ * * ]     [ 3 4 * ] 
       [ * 3 1 ]     [ * * * ] 

Затем автор расширить эту концепцию, сказав, что эти эвристики, полученные из подзадач могут быть объединены, принимая максимальное значение.

h(n)= max{ h1(n), . . , hm(n) } 

Кроме того, при использовании этого подхода производительность значительно улучшена по сравнению с простой эвристики как Manhattan distance.

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

h1234(n) = [ 1 2 ]  h5678(n) = [ * * ]      
      [ 3 4 * ]    [ * * 5 ] 
      [ * * * ]    [ 6 7 8 ] 

Будет составной эвристический как:

h1...8(n)= max{ h1234(n), h5678(n) } 

1. действительно работает в поиске решения для полного- проблема с загадкой?

Мне кажется, что с помощью эвристики как h1 ... 8 (п) мы в конечном итоге чередуя эвристики h1234 (п) и h5678 (п), который, в свою очередь, может привести к одной эвристике, испортившей работу другого и никогда не достигающему решения.

2. Или эвристика поможет друг другу в достижении полного решения?

Честно говоря, я делать не вижу, как это может работать ...

Answer 1

Сначала я дам вам краткий обзор идеи за эвристического и почему решения подзадачи, называемые также расслабленной проблемы, помогает найти решение. Затем я рассмотрю следующие общие соображения по проблеме 8-головоломок и, таким образом, отвечу на ваш конкретный вопрос. Для получения более подробной информации вы можете начать, как вы это делали, внимательно прочитать главу 3 из Artificial Intelligence: a Modern Approach Стюартом и Расселом; если вы хотите углубить тему о лучших стратегиях поиска и эвристике, вы можете начать с одной из основных работ Dechter and Pearl, 1984, ACM и посмотреть на цитированные статьи и те, кто ее цитирует.

Обзор эвристики и осознанного поиск

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

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

проблема 8-головоломки

В конкретном случае 8-головоломки, эвристический исходя из подзадачи по-прежнему интуитивно допустимый для исходной задачи. В частности, оптимальное решение в исходной задаче также является решением ослабленной задачи и дополнительно удовлетворяет всем ослабленным ограничениям. Таким образом, стоимость решения соответствует не более оригинальным оптимальным решением. Во-вторых, ослабленная проблема имеет меньше ограничений. Таким образом, алгоритм поиска может найти менее дорогостоящие решения и предоставить ниже, что является приемлемым, расслабленным решением.

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