2

私はアルゴリズムについて勉強していて、最近興味深い課題を見つけました。

行/列が得られます。私たちの使命は、一度だけ表示され、行と列の合計が指定された行/列に等しい整数 1~N でテーブルを埋めることです。

チャレンジの簡単な例:

    [ ]  [ ]  [ ]   13
    [ ]  [ ]  [ ]    8
    [ ]  [ ]  [ ]   24
     14   14   17

answer:

    [2]  [6]  [5]   13
    [3]  [1]  [4]    8
    [9]  [7]  [8]   24
     14   14   17

ありがとう

4

4 に答える 4

3

ああ、これらの小さな最適化の問題が発生するのが大好きです。彼らは、私が最初の年に、数独の問題を解決するものを作り、それでとても楽しかったことをいつも思い出させてくれます! それ以来、私が解いた数独の数がわかるかもしれません:)。

さて、あなたの問題はILP (Integer Linear Program)です。その記事を読む前であっても、 ILP は難しいことに注意してください。解空間をNまたはZに制限することは非常に制限的であり、多くの場合、そのような解は存在しません!

あなたの問題の場合、当面のタスクは本質的にこれを解決することです。

Minimise 0 (arbitrary objective function)

を条件として、

x1 + x2 + x3 = 13
x4 + x5 + x6 = 8
x7 + x8 + x9 = 24

x1 + x4 + x7 = 14
x2 + x5 + x8 = 14
x3 + x6 + x9 = 17

と、 

x_i in N, x_i distinct.

行列形式では、これらの方程式は次のようになります。

    |1   1   1   0   0   0   0   0   0|
    |0   0   0   1   1   1   0   0   0|
A = |0   0   0   0   0   0   1   1   1|
    |1   0   0   1   0   0   1   0   0|
    |0   1   0   0   1   0   0   1   0|
    |0   0   1   0   0   1   0   0   1|

と、

    |13|
    | 8|
B = |24|
    |14|
    |14|
    |17|

制約が に減少するようにA*x = B。したがって、解決したい問題は、次のように同等に記述できます。

Minimise 0

を条件として、

A * x = B

と、

x in N^7, x_i distinct.

これはあなたには難しいように見えますか？そうでない場合は、これについて考えてみてください。実際の線は巨大で、その線上には時々小さな点があります。それは整数です。それらのいくつかが必要です。どちらかはわかりません。つまり、干し草の山から針を探すのは完璧な例えです。

さて、絶望しないでください、私たちはこれらの ILP 針を見つけるのが驚くほど得意です! この問題が発生する分野の自明ではない難しさを理解してもらいたいだけです。

動作するコードを提供したいのですが、言語/ツールキットの選択がわかりません。これが単なる趣味のアプローチである場合、Excel のソルバーでさえうまく機能します。そうでない場合は、Willem Van Onsem が既に持っている以上にうまく言い表すことができなかったと思います。実装に関する彼の回答を紹介したいと思います。

于 2016-01-12T11:10:58.050 に答える
-1

ここでは、バックトラッキングアルゴリズムが非常にうまく機能すると思います。

バックトラッキングは依然として「ブルートフォース」ですが、平均的なケースでは非常に高速です。たとえば、バックトラッキングを使用して数独を解くには、通常 1000 ～ 10000 回の反復しかかかりません (O の複雑度が O(9^n) であることを考えると、これは非常に高速です。ここで、n は空のスペースであるため、平均的な数独には約 9^60 の可能性があり、これは平均的なコンピューターで完了するには数年かかります)。

このタスクには多くのルール (数値の一意性と行/列での合計) があり、バックトラッキングには非常に適しています。より多くのルール = 各ステップの後により多くのチェックを行い、解決策をもたらさないブランチを破棄します。

これが役立ちます: https://en.wikipedia.org/wiki/Sudoku_solving_algorithms

于 2016-01-12T09:55:32.247 に答える