7

予備数論に関するいくつかの講義ノートを読んでいるときに、次のように要約される水差し問題（ 2つの水差しを使用）の解決策に出くわしました。

GCD(a,b) は a と b の可能な限り最小の線形結合であるという 2 つの数値の GCD の特性を使用して、Q が an*GCD(a, b) Q=sA + tB であるため、ここで:

n = a positive integer
A = capacity of jug A
B=  capacity of jug B

そして、その解決方法を議論する

ソリューションの別のモデルは、人工知能でよく使われる状態空間探索問題としてさまざまな状態をモデル化することです。

私の質問は次のとおりです。ソリューションをモデル化する他の既知の方法とその方法は何ですか? グーグルはあまり吐きませんでした。

4

5 に答える 5

7

厳密に 2 ジャグの問題

Q = A * x + B * y

Q = 必要なガロン。

注: Q は Gcd(A,B) の倍数でなければなりません。それ以外の場合は解がありません。Gcd(A,B) == 1 の場合、任意の Q の解があります。

1)方法 1 : 拡張 Euclid のアルゴリズムは、どのグラフ アルゴリズムよりも高速に解決します。

2)方法 2: これが単純なアプローチです。(注、これは 2 つのソリューションをスローする可能性があります。短い方を選択する必要があります)

repeatedly問題の問題は、あるバケット A から別のバケット B に (順序は関係ありません) 必要な量でいっぱいになるまで Fillすることで簡単に解決できます。

    A = 3, B = 4 and Q = 2

A→Bを繰り返し埋める

    A B
   ######
    0 0
    4 0
    1 3
    1 0
    0 1
    4 1
    2 3 <-Solution

逆に、B->A を埋めるとどうなるか観察してみましょう。

A  B
#####
0  0
0  3
3  0
3  3
4  2 <- Solution

この場合、B->A を満たすと、A->B よりも速く目標状態が得られます。

Generic N Jugs ここに興味深い論文があります

于 2010-09-25T11:21:12.670 に答える
4

驚くべき面白いアプローチ（3つの水差しの場合）は、常に素晴らしいWebサイトCut-the-Knot：Barycentric座標：A Curious Applicationで説明されているように、重心座標（本当に！）を使用することです。

于 2009-03-16T18:00:06.827 に答える
1

このタイプの問題は、多くの場合、動的計画法の手法に適しています。私は、この特定の問題がオペレーションズ リサーチ コースの例として使用されているのをよく見てきました。ステップバイステップの説明がここにあります。

于 2009-03-15T17:03:56.000 に答える
0

検索空間法は、私が提案したものです。BFS を使用して一般的な水差しの問題を解決するプログラムを作成しました。ご希望があればお送りできます。

于 2009-04-11T05:36:27.600 に答える