path - プロローグを使用してパスを見つける

Question

ある点から別の点への道があるかどうかを調べたい。

例えば、2 -> 4 -> 7 1 -> 3 -> 2 -> 9 5 -> 1 -> 6 -> 8

これらがパスです。述語パス (開始、終了) を記述したいのですが、アークは一連のアーク (From、To) ファクトで表されます。

たとえば、path(1, 7) が指定された場合、これは true を返す必要があります。path(6, 1) が指定された場合、これは false を返す必要があります。弧が向いているからです。

score 1 · Accepted Answer

XとYの間に円弧がある場合、Path = arc（X、Y）です。つまり、arc（X、Y）の場合はpath（X、Y））です。または、Prologではこれは次のとおりです。

path（X、Y、[arc（X、Y）]）：-arc（X、Y）。
それ以外の場合、Xと他のノードZの間にアークがあり、ZからYへのパスがある場合は、XからYへのパスもあります。つまり、arc（X、Z）とpath（Z、Y）の場合、path（X、Y）です。Prologではこれは次のとおりです。

path（X、Y、[arc（X、Z）| P]）：-arc（X、Z）、path（Z、Y、P）。

このサイトから取得。

これを1つの述語にバンドルして、アークのリストを取得し、パスを再帰的に検索することもできます。

score 0 · Accepted Answer

問題を基本的な問題に分割することに答えてみてください。

path(From, To) :-
  arc(From, Intermediate),
  path(Intermediate, To).

しかし、パスがどこで停止するかわかりますか？そして、サイクルがある場合、何が起こりますか？

path(X, X)見逃しているのは、それが常に真実であると述べている些細なケースです。上記のルールに追加：

path(To, To).

If Then Elseを使用して単一のルールを作成すると、より明確になる可能性があります。

path(From, To) :-
  (   From \= To
  ->  arc(From, Intermediate),
      path(Intermediate, To)
  ;   true
  ).

2 に答える 2