0

次のような事実でいっぱいのデータベースがあります。

overground(newcrossgate,brockley,2).
overground(brockley,honoroakpark,3).
overground(honoroakpark,foresthill,3).
overground(foresthill,sydenham,2).
overground(sydenham,pengewest,3).
overground(pengewest,anerley,2).
overground(anerley,norwoodjunction,3).
overground(norwoodjunction,westcroydon,8).
overground(sydenham,crystalpalace,5).
overground(highburyandislington,canonbury,2).
overground(canonbury,dalstonjunction,3).
overground(dalstonjunction,haggerston,1).
overground(haggerston,hoxton,2).
overground(hoxton,shoreditchhighstreet,3).

例: ニュークロスゲートからブロックリーまでの所要時間は 2 分です。

次に、クエリを入力すると istime(newcrossgate,honoroakpark,Z) になるようにルールを作成しました。プロローグは、これらの 2 つの駅間を移動するのにかかる時間を教えてくれるはずです。(私が作成したルールは、隣接する駅だけでなく、任意の 2 つの駅間の距離を計算するように設計されています)。

istime(X,Y,Z):- istime(X,Y,0,Z); istime(Y,X,0,Z).
istime(X,Y,T,Z):- overground(X,Y,Z), T1 is T + Z.
istime(X,Y,Z):- overground(X,A,T), istime(A,Y,T1), Z is T + T1.
istime(X,Y,Z):- overground(X,B,T), istime(B,X,T1), Z is T + T1.

newcrossgate から最初の 2 駅まで、たとえば newcrossgate から foresthill または sydenham までは完璧に機能するようです。しかし、26分かかるウェストクロイドンへのニュークロスゲートをテストした後、クリスタルパレスへのニュークロスゲートを試してみたところ、プロローグは15分かかるはずだと言いました...ウェストクロイドンの次の駅であるという事実にもかかわらず。ここで明らかに何かがおかしいのですが、ほとんどのステーションで機能しますが、時々時折エラーが発生します。何が問題なのか教えてもらえますか? :S

4

3 に答える 3

2

これは基本的に前の質問と同じ問題です。唯一の違いは、時間をかけて累積する必要があることです。

私が見ていることの1つは、あなたの「パブリック」述語istime/3がやりすぎていることです。アキュムレータをシードしてワーカー述語を呼び出すだけistime/4です。両方向のルート/時間を探しているので、パブリック述語はちょうど

istime( X , Y , Z ) :- istime( X , Y , 0 , Z ) .
istime( X , Y , Z ) :- istime( Y , X , 0 , Z ) .

上記は本質的にistime/3述語の最初の節です

istime(X,Y,Z):- istime(X,Y,0,Z); istime(Y,X,0,Z).

の残りの節istime/3、再帰的な節:

istime(X,Y,Z):- overground(X,A,T), istime(A,Y,T1), Z is T + T1.
istime(X,Y,Z):- overground(X,B,T), istime(B,X,T1), Z is T + T1.

適切にアキュムレータの一部でistime/4あり、アキュムレータが存在する必要があります。それがあなたの問題です。

もう一度試して、質問を編集して次の反復を表示します。それでもわからない場合は、別の方法をご紹介します。

いくつかのヒント

  1. あなたの "worker" 述語は、以前の "2 つのステーション間のルートを見つける" 演習とよく似ていますが、経過時間のアキュムレータという追加の引数があります。

  2. 特殊なケースが 2 つあります。「2 つのステーション間のルートを検索する」ソリューションで使用したアプローチを使用する場合、特殊なケースは次のとおりです。

    • A と B は隣接しています。
    • A と B は、少なくとも 1 つの中間ストップを介して接続されています。

先読みを使用すると説明される別のアプローチもあります。この場合、特殊なケースは次のとおりです。

  • A と B は同じです。この場合、あなたは到着しています。
  • A と B は接続されておらず、0 個以上の中間ストップで接続されています。

FWIW、最短の経過時間または最小限のホップ数のルートが最初に見つかったソリューションであると必ずしも期待する必要はありません。バックトラックはすべてのルートを生成しますが、ルートが見つかる順序は、ファクトがデータベースに格納される順序と関係があります。グラフの最小コスト検索は、まったく別のやかんです。

于 2012-01-13T23:41:29.587 に答える
1

で回答を循環しようとしました;か? 26分は、ニュークロスゲートとウェストクロイドンの間の最短時間ではありません...

編集：悪い！どうやら短い結果は、コードのバグによるものでした (4 番目の句に関する私のコメントを参照してください)。ただし、コードは正しいです。newcrossgate と Crystalpalace の間の最短ルートは 15 分です。newcrossgate から westcroydon、次に Crystalpalace に至るルートがあるという理由だけで、それが最短ルートである、またはプログラムが最初に生成するルートであるとは限りません。

更新: いくつかのルートへの回答を見つけるために問題が発生している場合は、3 番目の句を次のように変更することをお勧めします。

istime(X,Y,_,Z):- overground(X,A,T), istime(A,Y,T1), Z is T + T1.

理由は簡単です。最初の節で X を Y に置き換えています。ただし、3 番目の句は、スワップされた句によって呼び出されることはないため、その恩恵を受けません。3 番目の引数 (とにかく使用していない) を無視して、1 番目の句で 3 番目の引数を呼び出せるようにすると、問題が解決する可能性があります。

（また：ニコラス・キャリーの答えに同意します。3番目の引数をアキュムレータとして使用する方がよいでしょう。しかし、私が言ったように、今のところそれを無視してもうまくいくかもしれません）

于 2012-01-13T23:28:49.673 に答える
1

それを機能させるには、最後の節で述べた両方の旅の逆を行う必要があります。述語 istime(X,Y,Z) をそのままにして、逆の旅を含む別の句を作成します。このようにして、すべてのステーションで機能します。(試行錯誤)

于 2012-01-14T15:00:03.720 に答える