Aritalab:Lecture/Algorithm/Sudoku

From Metabolomics.JP
< Aritalab:Lecture | Algorithm(Difference between revisions)
Jump to: navigation, search
m (Exact Cover by 3-Sets)
m (Hitting Set)
Line 31: Line 31:
 
; 問題: Sの部分集合S', |S'| &le; K で、Cのどの部分集合とも少なくとも一つ重なる要素を持つものがあるか?
 
; 問題: Sの部分集合S', |S'| &le; K で、Cのどの部分集合とも少なくとも一つ重なる要素を持つものがあるか?
  
この条件をきつくして、ちょうど一回だけ重なる要素を持つ、としたものが Exact Hitting Set です。
+
この条件をきつくして、ちょうど一回だけ重なる要素を持つ、としたものが Exact Hitting Set と呼ばれる問題です。
Exact Hitting Set 問題は、実は、Exact Cover 問題に同じです。
+
Exact Cover における集合 X の各要素について、それを含む部分集合 C のラベルを集めた集合を作って S とします。
+
  
 
; 例
 
; 例
Line 44: Line 42:
 
* 6 = {<span style="color:red">D</span>, E};
 
* 6 = {<span style="color:red">D</span>, E};
  
 +
上の場合は {A, D} という部分集合が、Exact Hitting Set になっています。この問題、実は、Exact Cover 問題に同じです。
 +
Exact Cover における集合 X の各要素について、それを含む部分集合 C のラベルを集めた集合を作って S とおけばよいからです。
  
 
+
{| class="wikitable" style="width:200px"
{|
+
|valign="top"|上の Exact Cover と見比べてください。
+
Exact Cover の要素集合 X が制約の集合に対応し、Exact Cover の制約 A~E が集合 S になっています。
+
ここで {A, D} がHitting Setです。上記のExact Cover問題と全く同じ条件を読み替えている点を理解してみましょう。
+
| <br/>'''どの列も行{A,D}<br/>(Exact Cover)で覆われる &rarr;'''
+
|
+
{| class="wikitable"
+
|+ どの列も Hitting Set {A,D} を含む<br/>&darr;
+
 
|-
 
|-
 
!  ||  1 || 2 || 3 || 4 || 5 || 6
 
!  ||  1 || 2 || 3 || 4 || 5 || 6
 
|-
 
|-
 
! <span style="color:red">A</span>
 
! <span style="color:red">A</span>
| * || * ||  || * ||  ||   
+
| || ||  || ||  ||   
 
|-
 
|-
 
! B
 
! B
| * ||  || * || * ||  ||
+
| ||  || || ||  ||
 
|-
 
|-
 
! C
 
! C
| * ||  || * ||  || * ||
+
| ||  || ||  || ||
 
|-
 
|-
 
! <span style="color:red">D</span>
 
! <span style="color:red">D</span>
|  ||  || * ||  || * || *
+
|  ||  || ||  || ||
 
|-
 
|-
 
! E
 
! E
|  || * || * ||  ||  || *
+
|  || || ||  ||  ||
|}
+
 
|}
 
|}
  

Revision as of 13:01, 22 August 2017

Wiki Top Up one level レポートの書き方 Arita Laboratory

Contents

KnuthのアルゴリズムX

Donald KnuthはTeXの開発者、"The Art of Programming"の著者で、様々なアルゴリズムも開発した著名な計算機科学者です。 Algorithm Xは、KnuthがExact CoverというNP完全問題を力ずくで解くための全解探索ソルバーのことで、Dancing Linksと題された論文(PDF at arXiv.org)で面白く紹介されています。 ここではExact Cover, Hitting Setという問題の説明と、それを用いた数独の解法について解説します。

Exact Cover

以下の組み合わせ問題を Exact Cover と呼びます。

設定
集合Xと、Xの部分集合からなる集合C
問題
Cの部分集合 C'⊆Cで、Xの要素が全てぴったり1回だけ現れるものがあるか?

この問題は3DMと呼ばれる問題を部分問題として含むため、NP完全であることが示されています。

集合 X = {1, 2, 3, 4, 5, 6};

  • A = {1, 2, 4};
  • B = {1, 3, 4};
  • C = {1, 3, 5};
  • D = {3, 5, 6};
  • E = {2, 3, 6};

このうち、AとDをあわせると、集合Xとちょうど一致するので {A, D} が Exact Cover になっています。  この例では、 {A, D} 以外の Exact Cover はありません。

Hitting Set

以下の組み合わせ問題を Hitting Set と呼びます。

設定
集合Sの部分集合の集合Cと、正の整数 K ≤ |S|
問題
Sの部分集合S', |S'| ≤ K で、Cのどの部分集合とも少なくとも一つ重なる要素を持つものがあるか?

この条件をきつくして、ちょうど一回だけ重なる要素を持つ、としたものが Exact Hitting Set と呼ばれる問題です。

集合 S = {A, B, C, D, E};

  • 1 = {A, B, C};
  • 2 = {A, E};
  • 3 = {B, C, D, E};
  • 4 = {A, B};
  • 5 = {C, D};
  • 6 = {D, E};

上の場合は {A, D} という部分集合が、Exact Hitting Set になっています。この問題、実は、Exact Cover 問題に同じです。 Exact Cover における集合 X の各要素について、それを含む部分集合 C のラベルを集めた集合を作って S とおけばよいからです。

1 2 3 4 5 6
A
B
C
D
E

Sudoku

ここで、数独が Exact Cover 問題に等しいことを示しましょう。 一般的な数独は9x9の升目に1から9の数が入るので、9x9x9=729個の選択肢を持ちます。つまり、集合 S の要素が729個です。 これらの要素は行をR, 列をC, 番号を#で表記すれば、(1,1,1)から(9,9,9)まで

R1C1#1, R1C1#2, …, R9C9#9

の形に書けます。

数独の制約は

各マスi, jに注目すると、1から9までの数字のどれか一つしか入らない
RiCj = { RiCj#1, RiCj#2, RiCj#3, ..., RiCj#9 }. (1 ≤ i, j ≤ 9)
各行iと数字nに注目すると、数字nは列1から列9までのどこかに入る
Ri#n = { RiC1#n, RiC2#n, RiC3#n, ..., RiC9#n }. (1 ≤ i, n ≤ 9)
各列jと数字nに注目すると、数字nは行1から行9までのどこかに入る
Cj#n = { R1Cj#n, R2Cj#n, R3Cj#n, ..., R9Cj#n }. (1 ≤ j, n ≤ 9)
9個ある3x3ボックスと数字nに注目すると、数字nは各ボックスのどこかに入る(例として左上のボックス)
B1#n = { R1C1#n, R1C2#n, R1C3#n, R2C1#n,R2C2#n, R2C3#n, R3C1#n,R3C2#n, R3C3#n }. (ボックスは9個; 1 ≤ n ≤ 9)

という4つに分けられます。制約の数は、上記の4制約それぞれについて9x9パターンあるので4 * 81 = 324通りです。 つまり Exact Hitting Set 問題の例で 1~6 とあった制約が324個に増え、それぞれの制約にはちょうと9通りの選択肢があるのです。 この問題設定は上記のHitting Setと同じですね。

数独の制約には規則性があります。 例えばマス(1,1)に1を入れる選択肢 R1C1#1 は、上記の制約のうち{ R1C1, R1#1, C1#1, B1#1} という4通りの制約に現れます。同様にすべての選択肢は、正確に4回ずつ規則性を持って出現します。ただし、数独の問題で実際に数字が埋まっている部分は、選択肢の数が9個ではなく1個になります。

数独は、Hitting Setとして解釈しなくても全解探索ですぐに解ける(Javaプログラム)のですが、理論的にはNP完全問題と同じ構造を持つということです。

Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox