7

NP完全であることが証明されていることは知っていますが、それで問題ありません。私は現在、通常のバイナリ平方/乗算アルゴリズムを使用する乗算の​​数に初期上限を設定する分岐限定法で解決しており、正しい答えが得られますが、実行には満足していません時間 (200 前後の数値の場合、数秒かかる場合があります)。これは NP 完全な問題であるため、目を見張るものは何も期待していません。しかし、多くの場合、実際の時間をある程度制御するためのトリックがあります。

実際にこれを行うためのより速い方法はありますか? もしそうなら、それらは何ですか?

4

3 に答える 3

6

これは、Knuth Vol 2 Seminumerical Algorithms のセクション 4.6.3 "Evaluation of Powers" のように見えます。これは、さまざまなアプローチを提供するためにかなり詳細になり、分岐限定よりもはるかに高速に見えますが、すべてが絶対的に最適なソリューションを提供するわけではありません。

クヌースは、定理 F の後の議論で、l(191) = 11 を証明するためにバックトラック探索を使用すると述べているので、これに対する近道の答えが見つかるかどうかは疑問です。彼は、バックトラック検索の説明をセクション 7.2.2 に委ねています。セクション 7.2.2 はまだ公開されていないと思いますが、http://www-cs-faculty.stanford.edu/~uno/programs.htmlにこれに関する作業の痕跡があります。

于 2011-09-07T17:44:50.050 に答える
1

メタヒューリスティックアルゴリズムは、はるかに優れたスケーリングを実現します。それらには、タブ検索、遺伝的アルゴリズム、シミュレーテッド アニーリング、...が含まれます。

無料の 本や無料のソフトウェアがいくつかあります。

于 2011-09-07T10:39:59.643 に答える