Пролог: поиск списка, не удовлетворяющего цели

Если у меня есть список ребер для такой задачи, как «Покажите мне маршруты из города, который считается опасным, в тот, который считается безопасным», так что...

dangerous(oakland).
safe(portland).

move(rome,plane,portland).
move(portland,plane,rome).
move(halifax,train,gatwick).
move(gatwick,car,rome).
move(portland,plane,newyork).
move(oakland,plane,rome).
move(oakland,plane,gatwick).
move(halifax,train,gatwick).
move(gatwick,plane,rome).
move(oakland,train,newyork).

Я могу получить список путей, ведущих к безопасному городу, используя следующий поиск в глубину (найденный на SO)...

dfs_start(Start, Goal, Path) :- phrase(dfs(Start, [], Goal), Path).

dfs(Node, _, Goal)   --> [Node], { call(Goal, Node) }.
dfs(Node0, Es, Goal) --> [Node0],
        { move(Node0,_,Node1), \+ member(Node1, Es) },
        dfs(Node1, [Node0|Es], Goal).

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

dfs_start(oakland,safe,Path).

...Я получил

Path = [oakland, rome, portland] ;
Path = [oakland, gatwick, rome, portland] ;
Path = [oakland, gatwick, rome, portland] ;

... но то, что я хочу сделать, это вызвать что-то вроде...

dfs_start(oakland,unsafe,Path).

...и получить...

Path = [oakland, newyork] ;

Любой совет будет принят с благодарностью!


depth-first-search prolog goal-tracking
person matt_dev    schedule 09.06.2012    source источник
comment
почему только один oakland->newyork? Что не так с oakland->rome? Чем rome отличается от newyork?   -  person Will Ness    schedule 10.06.2012
comment
Рим может в конечном итоге привести к Портленду, который является безопасным городом.   -  person matt_dev    schedule 10.06.2012

Ответы (1)


arrow_upward
2
arrow_downward

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

% unsafe(X) :- findall(Y,safe(Y),SafeList), member(X,SafeList), !, fail.
unsafe(X) :- \+ safe(X).

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

unsafe_path([Start|Path]) :-
    dangerous(Start),
    phrase(dfs(Start), Path).

dfs(Node) --> [Node1],
   {  move(Node, _, Node1),
      \+ lead_to_safe(Node1)
    } -> dfs(Node1) ; {true}.

lead_to_safe(Node) :- safe(Node).
lead_to_safe(Node) :-
    move(Node, _, Node1),
    lead_to_safe(Node1).

тест:

?- unsafe_path(P).
P = [oakland, newyork].

если мы добавим вымышленный город, путь удлинится:

?- assertz(move(newyork,train,turin)).

?- unsafe_path(P).
P = [oakland, newyork, turin].

если мы сделаем турин воротами в безопасный город:

?- assertz(move(turin,train,portland)).

?- unsafe_path(P).
P = [oakland].
person CapelliC    schedule 10.06.2012
comment
Хмммм. Я согласен с вами, что мое описание проблемы неоднозначно. Я ломаю голову, пытаясь понять это. Что мне нужно, так это любой список путей, где хвостовой город никогда не сможет быть соединен с безопасным городом. это делает его более ясным? - person matt_dev; 10.06.2012