Как я могу изменить алгоритм возврата, чтобы он мог работать на графиках "и / или"? - PullRequest
Новая
       22

Как я могу изменить алгоритм возврата, чтобы он мог работать на графиках "и / или"?

0 голосов
/ 09 октября 2009

В Искусственном интеллекте мы изучили алгоритм возврата. Вот псевдокод, который предлагает наша книга: 

function backtrack;
begin
    SL:= [Start]; NSL := [Start]; DE := [] CS := Start;
    while NSL != [] do
        begin
            if CS = goal (or meets goal description)
                then return SL;
            if CS has no children (excluding nodes already on DE, SL, and NSL)
                then begin
                    while SL is not empty and CS = the first element of SL do
                        begin
                            add CS to DE
                            remove first element froM SL;
                            remove first element from NSL;
                            CS := first element of NSL;
                        end
                    add CS to SL;
             end
             else begin
                 place children of CS (except nodes already on DE, SL or NSL) on NSL;
                 CS := first element of NSL;
                 add CS to SL;
             end
      end
      return FAIL;
end
  • SL : список состояний, перечисляет состояния в текущем пути пробовал.
  • NSL : новый список состояний, содержащий узлы, ожидающие оценки.
  • DE : тупики, списки состояний, чьи потомки не смогли содержать Целевой узел.
  • CS : текущее состояние

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

Однако теперь перед нами стоит задача изменить его, чтобы он мог работать на графиках "и / или".

(пример и / или график) альтернативный текст http://starbase.trincoll.edu/~ram/cpsc352/notes/gifs/whereisfred.gif

В учебнике было следующее предложение о возврате и / или графиках:

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

Несмотря на то, что я понимаю, что такое «и / или» графики, у меня возникают проблемы с изменением вышеупомянутого алгоритма обратного отслеживания, чтобы он работал с «и / или» графиками. Как говорится в книге, если они являются узлами «ИЛИ», все должно продолжаться как обычно, но с чем я сталкиваюсь, это узлы «и». Нужно ли делать что-то вроде: 

if CS has children and is "AND" node   then  
     resolve all children of CS  
         if children are all true, add children to NSL  
         else backtrack?

Это настолько близко, насколько я могу себе представить, мысленно, но все равно это не так. Может ли кто-нибудь помочь мне конкретизировать это немного дальше?

1 Ответ

1 голос
/ 10 октября 2009

В отрывке книги, который вы перечислили, есть решение, которое вы ищете.

Во-первых, псевдокод, который вы перечислили, довольно сложен, если вы не знаете, что означают переменные. Первым я понял CS, который довольно стандартен для текущего состояния. Тогда я предполагаю, что DE - тупики, SL - текущее состояние до текущего узла, а NSL - все непроверенные ветви. После этого я просто использовал свое собственное понимание алгоритма возврата, которое я обычно реализую рекурсивно. В будущем, пожалуйста, постарайтесь использовать более описательные переменные при публикации общих вопросов.

В основном, когда вы добираетесь до узла ИЛИ, вы можете продолжить поиск с неизмененным алгоритмом обратного отслеживания, потому что, как только вы нажмете на один истинный узел, он вернется к исходному результату. Однако, когда вы достигнете узла AND, вы должны проверить всех потомков в этом месте и убедиться, что все они верны или их легче понять, как только один из потомков окажется ложным, вы можете вернуться назад.

В узлах ИЛИ вы предполагаете, что все ложны, пока не подтвердится хотя бы один раз. В узлах AND вы предполагаете, что все верно, пока не подтвердится хотя бы один раз.

Добавленная вами модификация должна быть помещена в предложение else исходного алгоритма. Вы знаете, что у него есть дочерние элементы, поэтому все, что вам нужно сделать, это заставить его проверить всех потомков, а не останавливаться на одном хорошем экземпляре для узлов AND. Упомянутая вами модификация - правильная идея, но она не соответствует тому, как написан оригинальный псевдокод. Алгоритм, который вы перечислили, не позволяет вызову «разрешить все дочерние элементы CS», потому что это будет рекурсивный вызов, и ваш алгоритм хочет прямой цикл. На той же ноте, если все дочерние элементы верны, добавление их в NSL также потребует рекурсии, потому что вы не знаете, насколько глубоко дерево находится за пределами текущего состояния и непосредственных дочерних элементов.

Я рекомендую переписать его как рекурсивное решение. Если это не вариант, ответ не выскакивает у меня.

Вот хорошее видео для просмотра , если у вас есть час.

...