hirax.net::Keywords::「NP困難」のブログ



2015-06-21[n年前へ]

NP困難?な「点を結んでいくと絵が浮かび上がる」新ルールのコネクティング・ドット 

 点を結んでいくと(たとえば数字の順番にしたがって点を純に繋いでいくと)、次第に一枚の絵が浮かび上がってくる…コネクティング・ドットが好きだ。なぜかというと、意味なくばらまかれた点を、ひとつひとつ、今いる点から次の点へとただ辿っているうちに、いつの間にか何かしらのものが描かれていく、というのが人生そのものみたいで面白いからだ。

 そんなコネクティング・ドットで、たとえば明暗の階調(グラデーション)豊かな絵を細かな場所ごとに表現しようとすると、ひとつの問題に行き当たる。それは、濃い部分は密集した線で描かれることとなり、当然のように、そうした部分には(線を繋ぐための)点が密集する。…すると、密度バラバラにばらまかれた点群は、それだけで「何が描かれているか」わかってしまう(下左図)。そして、それどころか、その点群を線で結ぶと、絵はわかりにくく・汚くなってしまうのだ(下右図)。

 そこで、 Bob Bosch and Tom Wexler たちが考え・行った研究が When the Mona Lisa Is NP-Hard(モナリザがNP困難になる時)に紹介されている。彼らは、新たなコネクティング・ドットの「ルール」、「規則正しく配置された点群を、一筆書きしつつ通過しながら、目的の絵に一番似るような全景を描き出すルートで通っていく」というものを考えてみたのだ。たとえば、左下のような規則正しい「格子点」の上を、目的を思い浮かべながら描いていくと、右のような一枚の絵が浮かび上がってくる。

 本当は、意味なくランダムに見える点群を、ただ目の前の次の点へと辿った結果として、一枚の絵が浮かび上がってくる方が(人生に似ていて)好きだ。…けれど、人によっては、自分の目標を心に描きつつ、無味乾燥とした格子点の上に、自分の足で何かを描いていこうとする人もいるかもしれない。そんな人の好みを考えると、こんなコネクティング・ドットも面白いかもしれない、と思う*。


* しかも、記事タイトルにもなっているように、そんな「描きたい画像に一番近い(格子点の)辿り方を見つける」ということはNP困難な問題で、そんな人生を計算通りにするのはおそらく不可能だろう、と考えてみたりするのも面白いと思う。



■Powered by yagm.net