2

ガーディアン(英国の新聞)の今日の版では、クリス・マスランカによる43ページの「ピルジックパズル」セクションで、次のパズルが与えられました。

東方の三博士は...クリスマスの買い物をするためにハロッズに行きました。キャスパーはゴールドを購入し、メルヒオールはフランキンセンスを購入し、バルタザールはデイリーミルラのコピーを購入しました。レジ係は、これらのそれぞれのコストのユーロ数を利用し、3つの数値を加算することを意図していましたが、代わりにそれらを乗算しました。...驚異的なのは、結果がまったく同じであるということでした:€65.52。3つの合計は何でしたか[彼は3つの数字を意味していると思います]?

私の解釈は次のとおりです。a+b+ c = abc = 65.52(正確に)となるようなa、b、cを見つけます。ここ a b cは小数点以下2以下小数です。したがって、 ab、およびcも65.52(約)未満である必要があります。

したがって、私のアプローチは次のとおりです。a、b、およびcのすべての候補セットを見つけますここa + b + c = 6552であり、 ab、およびcは{1 ... 6550}からの整数です(概念的には、すべてのオペランドを乗算しました便宜上100ずつ)。次に、すべての候補セットについて、すべてのオペランドを100で除算し、それらを乗算することによって(任意精度の演算を使用して)、他の条件を満たすのは簡単です。

これは、私が見ているように、サブセット和問題のインスタンスです。そこで、ダーティ(指数時間)アルゴリズムを実装しました。これにより、a = 0.52、b = 2、c=63という1つの明確な解決策が見つかりました。

サブセット和問題にはもっと良いアルゴリズムがありますが、これは平均的なGuardianリーダーには少し手が届かないものになっていると思いませんか?

40ページに答えがリストされています:

これは試行錯誤で簡単です。デイリーミルラの52pを推測します。しかし、0.52を掛けると、およそ半分になるので、1つの合計が約2になる必要があります。したがって、2 X 63X0.52を試してください。Etvoilà。この答えはユニークですか?

まあ、私たちは答えがユニークであることを知っています(2、63、0.52の他の順列を無視して)。

私が知りたいのは、どうすればこれを「簡単」にできるのかということです。パズルを部分和問題のインスタンスとして特徴づけるのは正しいですか?ソリューションを簡素化するために利用できるパズルのいくつかの特徴を見落としていませんか?誰かが同様の「試行錯誤」のアプローチを採用することができましたか?もしそうなら、彼らは私をそれを通して連れて行くことができますか?クリス・マスランカは、NP完全問題に単純に臆することはありませんか?

4

1 に答える 1

3

いいえ、それはサブセット和問題のインスタンスではありません。理由は次のとおりです。

  1. サブセットのサイズは3に制限されているためO(n^3)、単純な全数検索(指数関数ではない)を使用した最悪の場合のソリューションになります。
  2. ここには、数値の積である追加のデータがあります。
  3. 実際にはセットが与えられていません。すべての整数のセットは、サブセット和のサブ問題であり、はるかに簡単です。

ここで理解しておくべき重要なことは、問題がNP困難な問題によって解決できる場合、それがNP困難であるという意味ではなく、逆に、問題が発生し、解決できる場合です。それに関するいくつかのNP困難な問題(多項式的に)、そしてあなたの問題はNP困難です。これは、多項式縮小1と呼ばれます。


の値を(すべての候補を反復することによって)「推測」するだけなので、アプローチは簡単です。これから、-(2つの変数、既知の場合は2つの方程式a)の可能な解を導き出すことができます。各反復-それはそうです)、したがって、解は線形でさえあります-サブ指数だけではありません。bca

二分探索のバリエーションを使用してサブリニア最適化を取得するように最適化することもできますが、現時点ではその最適化について考えることはできません。


(1)注:これは直感的な説明であり、正式な定義ではありません。

于 2012-12-22T19:42:19.367 に答える