1

グラフで反復的な深化 dfs 検索を実装する次の Prolog プログラムを変更する必要があります。

s(a, b).
s(b, c).
s(c, d).
s(a, d).

goal(d).

/* Solution is the inverse list of the visited node 
           from the start node Node and a goal node
           if it is TRUE that:

   path/3 predicate is TRUE (Solution is the inverse list 
           from the start node Node and a GoalNode)
           and it is TRUE that GoalNode is a goal 
*/
depth_first_iterative_deepening(Node, Solution) :- 
    path(Node, GoalNode, Solution),
    goal(GoalNode).

/* Path/3 predicate generate, for the given initial node, 
           all the possibles acyclic paths of increasing
           length
*/

/* BASE CASE: The shorter path from a node X to itself is Path=[X] */
path(Node, Node, [Node]).

/* GENERAL CASE: If I have to go from a start node X 
           to an end node Y and X != Y
   [LastNode|Path] is the path from FirstNode and LastNode 
           if it is TRUE that:

   1) Path is the path from FirstNode and OneButLast node
   2) Exist an edge from OneButLast and LastNode
   3) I have yet never visited LastNode
*/
path(FirstNode, LastNode, [LastNode|Path]) :- 
    path(FirstNode, OneButLast, Path),
    s(OneButLast, LastNode),
    not(member(LastNode, Path)).

path/3述語は、指定された初期ノードに対して、長さが増加するすべての可能な非循環パスを生成するため、述語を使用してdepth_first_iterative_deepening/2、開始ノードから終了ノードまでの長さで並べ替えられたすべてのソリューションを生成します (最短のものから最長のものまで)。

わかりましたので、ソリューションの長さに制限を課すような方法でこのプログラムを変更する必要があります

depth_first_iterative_deepening2/3次のような述語が必要です。

depth_first_iterative_deepening2(Node, Max, Solution)

ここMaxで、 は訪問したノードの最大数であるため、Solution許容されます。

長さが小さいか等しい場合、開始ノードからゴール ノードまでSolutionのソリューション パスも同様です。NodeSolutionMax

前の述語でこの変更を試みましたが、いくつかの問題があり、うまく機能しません。

depth_first_iterative_deepening2(Node, Max, Solution) :- 
    path2(Node, GoalNode, Solution),
    goal(GoalNode),
    length(Solution, Length),
    write(Length),
    (Length =< Max).

Solution(述語を使用して) ゴール ノードにもたらす a を計算するときにどのようにわかるかpath2/3、この解の長さを Length 変数に入れ、この解の長さが の値以下でなければならないことを課します。変数Max

問題は、見つかった解が問題ない (長さが<=値Maxである) 場合はうまく機能しますが、問題が見つかった場合 (長さ>が値のMax場合) はエラーになることです。

[debug]  ?- depth_first_iterative_deepening2(a,1,Solution).
24
ERROR: Out of local stack
   Exception: (1,597,352) path2(a, _G4793274, _G4792038) ?

トレースを見ると、問題は、(Length =< Max)失敗したときにpath2/3述語を再度呼び出して別の解決策を見つけることです (path2/3 常に最初の呼び出しへの最短パスを見つけるため、同じ解決策が見つかるため、同じ解決策が見つかることです)不合格）

(Length =< Max)チェックが失敗した場合は、depth_first_iterative_deepening2/3失敗する必要があることを望みます

これを行うためにカットを使用できますか？もしそうなら、どのように？

4

2 に答える 2

4

あなたが試すことができます

( (Length =< Max) ; (Length > Max), !, fail).

それ以外の

(Length =< Max).
于 2013-05-13T14:30:08.730 に答える
0

それは私が以前に提案したのと同じ「トリック」です。

訪問を呼び出す前にテストを配置します。

depth_first_iterative_deepening2(Node, Max, Solution) :-
   length(Solution, Length),
   Length =< Max,
   path2(Node, GoalNode, Solution),
   goal(GoalNode).
于 2013-05-13T12:18:11.083 に答える