1

私は推論エンジンを開発しています。これは、基本的に、特定の瞬間の世界の表現である特定の数の「事実」を持っていることを意味します。事実 (通常は開始状態と目標状態の 2 つだけです) とともに、多くのルールがあります (特定の問題については文字通り数百になる場合もあります)。推論エンジンの目的は、開始状態と一連のルールを指定して、許容可能な目標状態の 1 つへの最短パスを見つけることです。これは、DFS、BFS、A* などのいくつかのアルゴリズムで実行できます。プログラムの基本構造は次のとおりです。

事実名
  attribute1 = "値";
  attribute2 = [1、2、3];
  属性3 = 4;
  属性4 = 7;
  ...
エンドファクト

ルールルールワン
  equalsto(属性、「値」) または
  より大きい(属性, 5)
  >
  削除 (属性);
endRule

ルールルール2
  isprimeinteger(属性)
  >
  add(属性, 1)
endRule

ルールでは、LHS (> の前の部分)は、「値」に等しいファクト内のすべての属性に一致します。factnameこの場合は 1 つだけですが、複数ある場合もあります。つまり、変数を解決する必要があり (多くの場合、同じ事実に対して複数回)、ルールの LHS には複数の条件が設定されているか、適切な優先度の解析が行われている可能性があります。

問題は、この種の変数を効率的に解決する方法はありますか? 私が今行っていることは、実際のすべての属性を反復処理することであり、基本的に、バランスの取れていない非常に大きな n-ary ツリーを生成しています。これは、特に上記の条件を考えると非常に遅いです。

この種のパターンマッチングの論文へのポインタが欲しい

4

3 に答える 3

2

投稿のどこにも統一という言葉を使用していないことに気づきました。これが、実装しようとしているアルゴリズムが一般的に呼ばれているものです。ウィキペディアの記事をチェックしてください。下部にいくつかの参照があります..スペースとサイクルが重要だった70年代のものを含みます。

于 2009-06-11T17:59:55.547 に答える
0

eduffy にはそれがあります。これは統合と呼ばれます。Prolog は、一般的に、ユーザーがしようとしていることを正確に実行するように設計されたプログラミング言語であり、統合を使用して汚れた作業を実行します。

しかし、Prolog で Peano 公理を使用して算術を実装しようとした人なら誰でも、それが常に可能な限り最速の方法でそこに到達するとは限らないことを知っています。ほぼ同じことを行う「制約プログラミング」言語がありますが、ソルバーが最適なソリューションをできるだけ早く見つけるのに役立つヒューリスティックを提供することに重点が置かれています。それらの 1 つがコメットです。

于 2009-06-12T15:45:19.590 に答える
0

ここで大きな驚きはありません。単純なハッシュテーブルが O(1) になる O(N) アルゴリズムを使用しています。ハッシュテーブルには、属性値ごとに対応する属性が格納されます。

于 2009-06-11T08:48:50.700 に答える