0

漠然としたタイトルを許してください。この分野に関連する数学を行ってから数年が経ち、用語がかなり不足しています（この質問をしている理由の一部です）。私が達成しようとしていることをすでに扱っている明確に定義されたアルゴリズム/理論があると確信していますが、それを見つけるための言葉を完全に特定することはできません.

私がモデリングしている状況を説明しようとします：

アイテムのグループ [a,b,c,d,e,f] が与えられた場合、ある人が特定のアイテムの取引を申し出る場合があります。 「e」の場合。これらすべての取引をすくい上げて、提供されているオプションの概要を示すグラフを作成できます。私は特定の貿易経路を探すことに興味があります。余談ですが、私に余剰アイテムを与える貿易経路 - この種のものは金融部門にすでに存在しているに違いないと思います (繰り返しますが、名前/経験がありません数学）。

したがって、「a」があり、「f」が必要な場合、次のパスが利用可能でした。

a -> b, b -> f, c -> b, a-> 2(c), b -> a

私はで終わるだろう

a -> b -> f

a -> (2)c -> b -> f    
      |
      c             (An additional c)

循環できるところもあるかもしれないので、上記のb→aの関係を使えば、余ったc項目で連続的にcを抽出できました。

これを行うためのプログラムを作成できるとかなり確信していますが、このような問題の背後にある正しい用語と方法論を理解することが大好きです。誰かが特定のトピックについて読むべき正しい方向に私を向けることができれば、または私が達成しようとしていることの明白な名前があれば、私は非常に感謝しています.

漠然とした内容で重ねてお詫び申し上げます。

4

1 に答える 1

1

典型的な状態空間検索の問題のように聞こえます。BFSや反復深化のようなアルゴリズムは、最短の一連の取引を見つけることができ、さらにはすべての可能性を生み出すことができます。

これらのアルゴリズムを適用するには、グラフを再定義する必要があります。エッジのようなノードaを使用する代わりに、状態が各要素の有限数（この場合は整数の4タプルで十分です）と、可能なすべてを適用する後続関数Sで構成される状態空間を定義します。状態を指定して取引し、一連の後続状態を構築します。たとえば、疑似Python表記では、ba -> b{a, b, c, f}

S({a: 1, b: 2, c: 0, f: 0}) = [{a: 0, b: 3, c: 0, f: 0},   # trade a for b
                               {a: 1, b: 1, c: 0, f: 1},   # trade b for f
                               {a: 1, b: 2, c: 2, f: 0},   # trade a for 2c
                               {a: 2, b: 1, c: 0, f: 0}]   # trade b for a

状態空間検索はAIの古典的なパラダイムであるため、ほとんどのAI教科書がそれをカバーしています。特に、ラッセルとノーヴィグによるAIMAをお勧めします。このAIMAは、最初の数章で状態空間検索についてかなり詳細に説明しています。

于 2013-02-20T16:33:30.417 に答える