NP困難の問題のアルゴリズムを考えるその2 - kbigwheelのプログラミング・ソフトウェア技術系ブログ

kbigwheel.hateblo.jp

の末尾に書いた通り、ortoolsを使おうとしている。そのためには定式化が必要で、今見ている問題がどのタイプの問題かを判断する必要がある。

ここら辺で重大なことに気づいた。巡回サラリーマン問題などは点と点の間に距離があり、それが問題だった。しかし、今回の塗装の問題は塗る色の間に距離などない。白と黄色の距離と、白とくろの距離は同じである(なぜならエアブラシのカップの中に入れる色が何であれ、手間は変わらないからである)。

この問題、もしかしてNP困難ではないのでは？

問題を整理する

$C_1$ ~ $C_N$ のN個の色を塗るとする。また、 $C_a → C_b$ のような塗装順の制約がP個ある。このとき、最小となるような塗装順を見つけたい。

これは、書き換えると次のような問題になる。

$C_1$ ~ $C_N$ のN個の記号がある。 $C_1$ ~ $C_N$ をそれぞれ1つ以上含んだ最短の記号列を求めよ。ただし、 $C_a$ より後に必ず $C_b$ を含む必要がある、といった制約LがP個ある。

こう考えるとNP困難ではない気がする。

多角的にこの問題を考えよう。まず、[text: L_1] ~ [text: L_P]のどれにも含まれていない記号 $C_x$ は考慮からすべて外せる。というのは、制約に含まれる記号を制約を満たすように順序付けしたあとは、制約に含まれていない記号はその列の任意の間に好きな順序でおけるからである。先頭にあまり全てをおいても良いし、末尾でも良い。ランダムでも数字順にソートでもいが、そのどれでも塗装回数に影響しない。

となると問題は以下のように書き換えられる。

$C_1$ ~ $C_N$ のN個の記号がある。 $C_1$ ~ $C_N$ をそれぞれ1つ以上含んだ最短の記号列を求めよ。ただし、 $C_a$ より後に必ず $C_b$ を含む必要がある、といった制約LがP個ある。また、 $C_1$ ~ $C_N$ は制約 $L_1$ ~ $L_P$ の中に必ず1度以上出てくる。