Классический фермер, волк, козел, строительство системы производства капусты

Question

Я пытаюсь изучить систему продукта для решения проблемы искусственного интеллекта FWGC. Подробнее https://www.cs.unm.edu/~luger/ai-final2/CH4_Depth-.%20Breadth-,%20and%20Best-first%20Search.pdf

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

Как построен этот график? Может кто-нибудь объяснить?

Answer 1

Согласно документу, описывающему диаграмму:

"График" - это диаграмма перехода состояний, показывающая, в какие возможные состояния вы можете перейти из любого другого заданного состояния, начиная с state(w,w,w,w) в качестве исходного состояния. Как переход определяется путем рассмотрения логики описанной проблемы. Такой график может быть автоматически сгенерирован в Прологе, если у вас есть все правильные правила Пролога, настроенные для проблемы, или он может быть сгенерирован вручную, чтобы выяснить, как вы хотите написать правила. В документе не говорится точно, как они его сгенерировали, но они только говорят, что это частичное описание возможных переходов между состояниями и безотносительно к тому, является ли любое данное состояние "безопасным", что означает, что диаграмма содержит некоторые состояния, которые вы хотел бы, чтобы ваше решение Пролога исключило. Учитывая его место в документе и контекст, я считаю, что он создается вручную, чтобы помочь найти разумное представление данных и дизайн для программы Prolog.

Для примера, начальное состояние таково, что все 4 вещи (фермер, волк, коза, капуста) находятся на Западном берегу. Это состояние state(w,w,w,w) представляет местоположение F,W,G,C, соответственно. Возможные состояния, что один ход может привести вас оттуда, так как фермер может взять не более одного предмета за раз через реку:

West          East           State
----          ----           -----
G, C          F, W           state(e, e, w, w)
W, C          F, G           state(e, w, e, w)
W, G          F, C           state(e, w, w, e)
W, G, C       F              state(e, w, w, w)

Это выясняется, если подумать о правилах и возможных вариантах. В каждом из вышеуказанных новых штатов фермер либо переправлял один предмет через реку, либо перебирал себя ни с чем другим. Это 4 возможных хода. Стрелки на диаграмме показывают, в какие состояния вы можете перейти. Таким образом, диаграмма показывает, что переходы между состояниями рефлексивны (то есть, если вы переходите из состояния A в состояние B, вы также можете перейти от B к A).

В качестве другого примера, когда в state(e, e, w, w):

West            East           State
----            ----           -----
G, C            F, W           state(e, e, w, w)

Отсюда возможны только два хода: фермер забирает волка через реку (возвращается к state(w, w, w, w)или фермер самостоятельно возвращается через реку, что state(w, e, w, w) и это то, что показано на диаграмме перехода состояний.