2

現在、2 点間の最短経路を計算するプロローグ プログラムを実装しています。フレームワークは Java プロジェクトに既に存在します。要件として、パスはプロローグで実装する必要があります。したがって、私は gnu.prolog ( http://www.gnu.org/software/gnuprologjava/ )を使用します。

Javaの外で私が呼び出すsearchPath(1,5,Path)ものは返されますPath=[5,4,3,2,1]

ここに私のプロローグコードがあります:

:- dynamic(path/3).

findPath( [Goal | Rest], Goal, Temp, Temp, [Goal | Rest]).

findPath( [A | Rest], Goal, Cost, Temp, Path) :-
    path(A,B,C),
    \+member(B, [A | Rest]),
    NewCosts is (Temp + C),
    findPath([B, A | Rest], Goal, Cost, NewCosts, Path).

searchPath(Start,Goal,Path_to_goal) :-
    findPath([Start], Goal, Cost1, 0, Path),
    findPath([Start], Goal, Cost2, 0, Path2),
    Cost1=<Cost2,
    Path_to_goal = Path.

それには2つの問題があります：

  1. searchPathメソッドは最短パスを返す必要があります。ただし、そうではありません。これにより、ゴーストがある時点で方向を切り替えることを「決定」し、ゴーストが左から右に揺れます。

  2. 私のプロローグ コードは、結果を返すのに最大6 秒かかります。時間がかかりすぎると言う必要はありません。ただし、prolog が19msしか必要としない場合もあります。これがどの状況に依存しているかを理解できませんでした。たとえば、99 個の要素を含むパス リストの計算には 19 ミリ秒かかりますが、38 個の要素のみを含むリストには 6 秒が費やされました。

改善策を提案できますか？

事前にご協力いただきありがとうございます。

4

1 に答える 1

2

ダイクストラのアルゴリズムを使用できます。この質問に答えて実装しました。私のコードは属性付き変数を使用しています。GnuProlog で動作するはずです (今テストします)。とにかく、そこには、動作する純粋な Prolog 実装へのリンクがあります。

よく編集してください。問題があるため、コードを修正できると思います。

Path2searchPath/3 ではシングルトンです: その場合、明らかに常に最初のパスで終了します。2 番目の findPath/3 は常に(データベースが変更されていない場合) 最初のものとまったく同じコストとパスを見つけるため、次のようにCost1=<Cost2,なります。常に真実。あなたは試すことができます

searchPath(Start,Goal,Path_to_goal) :-
    findall(Cost-Path, findPath([Start], Goal, Cost, 0, Path), Paths),
    sort(Paths, [_-Path_to_goal|_]).

あなたの割り当てには十分に速いです。それ以外の場合は、インクリメンタル検索を実装する必要があります。Prolog はバックトラッキングで代替パスを「返す」ため、簡単ではありません。最小値を選択するために何らかの副作用を使用する必要があります。

findall/3 をさらに編集すると、コードが非常に遅くなります。バックトラック不可能な割り当てを使用して、より効率的なコードを作成しました (SWI-Prolog nb_setarg/3 を使用しました。GProlog では setarg/3 を使用する必要があります)。

findPath(_Limit, [Goal | Rest], Goal, Temp, Temp, [Goal | Rest]) :- !.

findPath(Limit, [A | Rest], Goal, Cost, Temp, Path) :-
    path(A,B,C),
    \+member(B, Rest),
    NewCosts is (Temp + C),
    NewCosts < Limit,
    findPath(Limit, [B, A | Rest], Goal, Cost, NewCosts, Path).

% ?- searchPath(aberdeen, glasgow, Path, Length).
%
searchPath(Start, Goal, Path_to_goal, L) :-
    S = path_len([], 1000000),
    repeat,
    arg(2, S, Limit),
    (   findPath(Limit, [Start], Goal, Cost, 0, Path)
    ->  (   Cost < Limit
        ->  nb_setarg(1, S, Path),
        nb_setarg(2, S, Cost),
        fail
        )
    ;   true
    ),
    arg(1, S, Rev),
    reverse(Rev, Path_to_goal),
    arg(2, S, L).
于 2013-04-04T10:32:19.627 に答える