2

「危険と見なされる都市から安全と見なされる都市へのルートを表示してください」などの問題のエッジのリストがある場合は...

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).

しかし、私が解決しようとしている問題は、安全な都市(この場合は1つのオークランド->ニューヨークのみ)につながらない危険な都市からのすべてのパスを見つけることです。上記の関数をで呼び出すと、 ..

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] ;

アドバイスをいただければ幸いです。

4

1 に答える 1

2

問題の説明があいまいです。おそらくそれが疑問の原因です。私が理解しているように、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].
于 2012-06-10T06:05:18.373 に答える