2014年5月30日金曜日

数独とシフト勤務表の等価性

下は、サンプルフォルダに入っている数独プロジェクトです。(実際に難問が入っていて解く様子が見られます。)この問題は、フィンランドの数学者が3ヶ月かかって作った世界一難しい問題といわれているその世界では、有名な問題です。数独の名人でも、数日かかるとされているこの問題をスケジュールナースは、1秒もかからずに解く事ができます。
勤務表を解くアルゴリズムでも説明していますが、勤務表の込み入った拘束条件を満たす解の解法というのは、方程式を解くようなものではなく、基本的には探索によるものです。その意味で数独のパズルとナーススケジューリングというのは、同じ種類の問題なのです。ただ、皆さんの抱えているナーススケジューリング問題というのは、実はこの数独を解く難しさからすると2桁から3桁程度難しいです。

ここで難しいという定義は、制約を式に置き換えたときの規模を言います。下記は、スケジュールナースのソルバが示す内部の状況です。

                                    変数 式の数
数独             738    3249
池上2ShiftData    25542  114302
池上3ShiftData1.1 67512  325062


必ずしも、解く時間と上記の規模は比例関係に有る訳ではないのですが、ある程度の相関関係が
知られており、問題の規模でいうと、2桁程度違うことが分かります。皆さんが普段やられている規模は、池上ShiftData2-3位の規模です。ですから、数独より2桁難しいパズルを毎月解いているというのは、あながち間違っていません。

数独は、全部ブランクのときの値です。それは、世界一難しい問題ではないだろう?という疑問があるかもしれませんが、全部ブランクが、一番難しいのです。というのは、論理的には、解けなくて仮定を置かないと解けなくなるからです。数独専用のソルバでやってみると、この事が実感できる筈です。(やった事はありません。)

スケジュールナースでは、このくらいの小さい規模ではマルチスレッドをオフにしているのですが、ブランク数独を0.2sec/個(Core i5 3GHz)位で解き続けられます。はたして、スケジュールナースに勝てる専用ソルバはあるでしょうか?

難しいナーススケジューリング問題に対して、まだ、紙と鉛筆、あるいはExcelで立ち向かおうとする人には、名人の数日と一秒の探索能力の差を思い起こして欲しいな、と思います。



0 件のコメント:

コメントを投稿

注: コメントを投稿できるのは、このブログのメンバーだけです。