Langford(3)だから, 1,2,3を2個ずつ, 例えば323121のように並べる. 但し2個のnの間には他の数がn個なければならないという制限があるから, 先ほどのは駄目で, 231213がひとつの解である.
このくらいならちょっとやっただけで出来るが, 長くなる(nが増える)と大事だ.
TAOCPでの方法はこうだ. まずこういう表を作る.
1行目 1を1番と3番に置く. 間隔は1だ. 2行目 1を2番と4番に置く. ...
5行目 2を1番と4番に置く. ...
8行目 3を1番と5番に置く.
3を2番と6番に置くというのもありだが, 対称だから8行目だけにする.
表が出来たらd1の列に1のあるxjから1つ選ぶ. つまりx1, x2, x3, x4から1つ選ぶ. d2からもx5, x6, x7から1つ選ぶ. これをs6の列まで行う.
1つ選ぶ式をTAOCPではS1と表記するから, この関係は
の式になり, S1の展開式を当てはめると, SAT
が得られる. 2-4-, 1-3- が重複しているからそれを除き, リテラルの内部表現にすると
(define sat '((2 4 6 8) (3 5) (3 7) (3 9) (5 7) (5 9) (7 9) (10 12 14) (11 13) (11 15) (13 15) (16) (2 10 16) (3 11) (3 17) (11 17) (4 12) (5 13) (2 6 14) (3 15) (7 15) (4 8 10) (5 11) (9 11) (6 12 16) (7 13) (7 17) (13 17) (8 14) (9 15)))となる. 従って
(define ls '(9 15 8 14 13 17 7 17 7 13 6 12 16 9 11 5 11 4 8 10 7 15 3 15 2 6 14 5 13 4 12 11 17 3 17 3 11 2 10 16 16 13 15 11 15 11 13 10 12 14 7 9 5 9 5 7 3 9 3 7 3 5 2 4 6 8))前回と同様にsatの先頭だけとると, sが
(0 2 3 3 3 5 5 7 10 11 11 13 16 2 3 3 11 4 5 2 3 7 4 5 9 6 7 7 13 8 9)になり, zも作れ, wやlinkも得られる.
((0) () (19 13 1) (20 15 14 4 3 2) (22 17) (23 18 6 5) (25) (27 26 21 7) (29) (30 24) (8) (16 10 9) () (28 11) () () (12) ()) ws= (0 0 1 2 17 5 25 7 29 24 8 9 0 11 0 0 12 0) link= (0 13 3 4 14 6 18 21 0 10 16 28 0 19 15 20 0 22 23 0 0 26 0 0 30 0 27 0 0 0 0)節の長さがばらばらだから, STARTも作らなければならない.
(define a (map length sat)) a => (4 2 2 2 2 2 2 3 2 2 2 1 3 2 2 2 2 2 3 2 2 3 2 2 3 2 2 2 2 2) (define (ac ls) (if (null? ls) '(0) (let ((a (ac (cdr ls)))) (cons (+ (car ls) (car a)) a)))) (define start (ac a)) start => (66 62 60 58 56 54 52 50 47 45 43 41 40 37 35 33 31 29 27 24 22 20 17 15 13 10 8 6 4 2 0))これで準備が完了し, アルゴリズムBを実行すると01000011が得られ, x2,x7,x8を取るのが解と分かり, 泰山鳴動の一幕であった.
0 件のコメント:
コメントを投稿