問題タブ [knuth]

ここで、数独のアルゴリズム Xは O(N^3) 時間の複雑さを持ち、N はボード サイズであるというステートメントを見つけました。

数独の場合、計算するバイナリ行列には N^3 行があるため、これはおそらく論理的です。しかし、それは数独問題を多項式時間で解決可能にし、数独はNP問題であることが知られています。つまり、（私が理解しているように）

• 常に多項式時間で解くことはできない

• 多項式時間で解を検証可能

では、数独のアルゴリズム X の時間計算量はどのくらいで、多項式時間で数独を解くことは可能でしょうか?

ありがとうございました！

RでKnuthのアルゴリズムXのようなものを実装しようとしています.

問題: 実数値のエントリがコストを表す anxk 行列 A、n>=k があります。一般に、n と k はどちらもかなり小さくなります (n<10、k<5)。単一の行を 2 回使用できないという制約に従って、行列の総コストを最小化する列への行のマッピングを見つけたいと考えています。

これは、合理的なアプローチが次のように思われるという点で、アルゴリズム X に似ていると思います。

1. A の列を選択し、その中で最小値を見つけます。
2. その行とその列を削除します。これで、Asub が残ります。
3. ステップ 1 に進み、ncol(Asub)=1 になるまで Asub と新しい列を選択して繰り返します。

しかし、セルレベルのコストの結果のツリーを格納する再帰的なデータ構造を R で作成する方法がわかりません。ここに私がこれまでに持っているものがあります.1つのブランチしか下らないため、最適な解決策が見つかりません.

R関数で再帰を処理する方法について、何か基本的なことが欠けていると確信しています。このアルゴリズムが実際に最適でない場合、この問題を解決する他の方法を聞いてうれしいです.