Жадный поиск в прологе с использованием эвристического значения - PullRequest
Новая
       13

Жадный поиск в прологе с использованием эвристического значения

0 голосов
/ 27 августа 2018

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

График: Graphical representation

Эвристическая таблица: The cost of visiting node

Они представлены в прологе следующим образом. 

s(a,b,2).
s(a,c,1).
s(b,e,4).
s(b,g,2).
s(c,d,1).
s(c,x,3).
s(x,g,1).

h(a,9)
h(b,3)
h(c,2)
h(d,8)
h(e,4)
h(g,0)
h(x,2)

Мой запрос, как мне выполнить жадный поиск, используя эвристические значения h (a, 9), чтобы найти следующий узел на каждой итерации.

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

ДФС: 

depthfirstsearch(GoalN,Path,[GoalN|Path]) :- goal(GoalN).

depthfirstsearch(Node,Path,Solution) :- s(Node,NextNode,_), \+member(NextNode,Path), 
depthfirstsearch(NextNode,[Node|Path],Solution)

Поскольку я выполняю поиск в SO и в Интернете (нахожу заметки о том, как работает жадный поиск), но ничего, что объясняет, как это на самом деле работает, используя код пролога. Объясняется, как это сделать в java, C++ и т. Д., Но я не использую эти языки.

Кто-нибудь может направить меня в правильном направлении? Я где-то читал, что findall можно использовать? Но как мне объединить эвристическое значение с узлом, например, узел "B" со стоимостью 2, от A до B. Могу ли я заменить стоимость 2 на эвристическое значение / стоимость 3. Пожалуйста, объясните подробнее подробно или направить меня на другой ресурс, который был бы полезен прямо сейчас?

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

Помните, что я новичок в прологе и пробую пути, но изо всех сил пытаюсь собрать все воедино.

Обновление: по этой ссылке я узнаю большую часть информации о поиске

1 Ответ

0 голосов
/ 10 сентября 2018

Я думаю, вам нужно знать, что такое эвристическое значение и как его можно использовать в вашем алгоритме поиска.

В моем ответе:

  • n - это узел, который мы хотим достичь

  • s - исходный узел

  • h() - эвристическая функция. h(n) является допустимым (?) значение, я предпочитаю думать о расчетной стоимости , чтобы достичь n из источника s. Мы называем эвристическое благо только в том случае, если оно небезопасно переоценить стоимость.

  • w(a,b) - фактическая стоимость перехода от a до b

  • g() - это функция, дающая фактическую стоимость для достижения узла n с s суммируя w(a,b), где оба a и b являются узлами в пути от n до s.

Теперь, чтобы ответить на ваш вопрос, AFAIK, вы можете использовать эту эвристику двумя способами:

  • Как вы сказали, вы можете лениво игнорировать w(a,b) значения и использовать h(b) значения для сортировки узлов-преемников (где b - любой преемник узел) - это называется лучший первый поиск алгоритм

  • Другим способом будет сортировка узлов-преемников по значению h(b) + g(b) (где b - любой узел-преемник) - это называется A * Алгоритм поиска .

Рекомендуемое чтение:

  • Стюарт Дж. Рассел и Питер Норвиг, «Искусственный интеллект - современный подход, третье издание»

  • Иван Бракто, rПрологическое программирование для искусственного интеллекта, Pearson Education, август 2011.

P.S. findall - это то, что нужно использовать в прологе для реализации этих двух поисков.

...