TIM Labs

fujiによるエントリー一覧

巡回セールス問題というと、与えられた点の全てを通る巡回路で一番距離が短いものということであり、下図のようなものを思い浮かべるであろう。

100-Normal.png

今回は、こういう普通のまっとうな巡回セールス問題ではなく、次図のような巡回セールス問題を考えてみよう。

100-Angle2.png

この結果も、巡回セールスマン問題を解くプログラムで巡回路を最適化したものである。
正確に言うと、ほんのちょっとだけプログラムを変更した。

与えられた全ての町(点)を一度だけ通過しているので、巡回しているが、どうみても、距離が最短ではない。最短距離なら、巡回路が重なる場合には、さらに短い巡回路を簡単に作れる。

何だが、ぐるぐる回る巡回路になっているようだが、何を最適化したのだろうか?

殆どの巡回セールスマン問題を取り扱っている本では、巡回セールスマン問題を深く説明することがあっても、巡回セールスマン問題を多様に拡張する、あるいは抽象化することで、非常に多様な問題を解く基本的なアルゴリズムとして使えることの説明がほとんど皆無であり、とても残念である。

...ということで、ぐるぐる回る巡回路について、何を最適化しようとしたか、考えてみよう。

説明は、次回に行う。

(つづく)

DSCN3396-600.JPG

恵存(けいぞん、けいそん)村上雅人 と書かれてあり、恵存とは本などにサインするときに使われる言葉で、「お手元に保存していただければ幸い」(デジタル大辞泉)という謙譲語である。

実は、村上雅人著作本にサインをいただいたのだのだが、村上雅人って誰だか知っている人は少ない気がする。

今回は、この人の本について書く。

ところで、最近やたらと数学、そしてちょっと物理学が流行っている気がする。

10月初めには MATH POWER 2018 という、数学の狂った祭典が六本木の地下で夜を徹して行われ、それに付き合ったのだが、満員御礼の人気なのである。

数学、物理学というと、理工系大学ではだいたい必須の科目であり、そのための書籍も多数でている。

以前、そういう分野の本としてマセマを紹介した。

プログラミングに数学はどのくらい必要か

プログラミングに物理はどのくらい必要か

マセマは、まるで受験参考書のような書き方で説明や演習が載っていていて、これで勉強すれば単位は取れるという謳い文句の参考書である。

でも、大人になってから読むには、どうも受験や定期試験を思い出させるのでよろしくない。

今回は、280合体ナンプレの問題としての正当性について書く。

ギネス世界記録™として認めてもらうには、当然問題の正当性が保証されないといけない。

その中でも面倒なのが、解の一意性(ユニーク性)である。

「ルールを満たす解が存在し、その数は1つだけである」

これは、ギネス世界記録™だけでなく、普通にナンプレ本、ナンプレ雑誌などに載る問題でも当然保証しなければいけない事で、問題を作ったプログラムの中に、そういう検証も含まれている。

しかし、パズルを作ったプログラムで、ユニーク性を確認しても、それは保証にはならないだろう。

公式記録となるためには、第三者がユニーク性を確認しなければいけない。

方法としては、まあ色々あり、検討された。

ナンプレの権威者の保証

そもそも、ナンプレの権威者って存在するのか?

権威者なら間違わないのか? 所詮人間であり、280合体ナンプレをノーミスで解くのは神でも無い限り無理だろう。

ということで却下。

第三者のプログラムで検証

人間が無理なら、プログラムで解くことになる。

第三者のプログラムで280合体を解けるプログラムが存在するかどうかよく分からない。

誰かに頼んでプログラムを作ってもらうのは可能かもしれないが、こういうのをホイホイ作るようなプログラマとは何らかの関係があったりして第三者として認められない。

他にも問題がある。

標準の9x9のナンプレ問題を解くプログラムでよく使われる、ルールと手筋を実装して調べるのでは、問題を自動生成するプログラムに使われている方法と本質的な差がなく、正当性の検証には無理がある。

280合体が完成するかどうかなかなか事前に予想ができなかった。

ギネス記録を達成したかどうか、詳しいことは、ニコニコ生放送のMATH POWER 2018を見てもらえばわかるのだが、全部で32時間30分もあるので大変かもしれない。

ということで、ここで手短に説明する。

こういう巨大な合体ナンプレは、問題の難易度よりも、どれだけのレベルの人が、どのくらい解き続けるかの影響が圧倒的に多いので、とても難しい。

しかし、結果は、ちゃんと完成して、ニコニコの動画はこんな感じになった。

nicoguiness8888.png

32:15:57

32時間より前に完成したのだが、1マスだけ残していて、ギネス記録達成の式典の直前に、最後の1マスを書き込んで完成しときのニコニコの画面が上である。

今年のMATH POWERでは、昨年247合体がフィナーレまでに終わらなくて、少々延長して何とか終わらせたので、ちゃんと時間内に終わらせるようにしようというのがあった。
そして、今回は、ギネス世界記録™を狙うというのもあった。
今までの合体ナンプレ(マルチ数独)の記録は、2015年の中国で樹立されたもので、去年の時点で既に世界記録だったのだが、今年はちゃんとギネス世界記録™を狙おうという魂胆があったのだ。
時間内に終わる、200合体を超えれば良い、という条件だけで問題を作るのは、問題作成者および参加者のモチベーションが上がらない。
それで、次のようにした。

まず、貼りだす壁の大きさの報告を受け、さまざまな条件を考慮し、280合体にした。

280Q-1000.png

PDF版Excel版も用意した。良いプリンタがあれば印刷できると思う。

Unix(Linux,...)では、lsは最もよく使用するコマンドではないだろうか。
ls は、ファイルとか、フォルダ(ディレクトリ)についての情報が分かる。

最近は、周辺機器をUSBで繋ぐのが一般的だ。
そして、何でも繋いでいるので、何がつながっているのか調べるのに困るくらいだ。
そうなると、lsコマンドと同じように、USBについてlsできないかと思うのが自然だろう。

実は、存在する。

lsusb(8)                                          Linux USB Utilities                                          lsusb(8)

NAME
       lsusb - list USB devices

SYNOPSIS
       lsusb [ options ]

DESCRIPTION
       lsusb is a utility for displaying information about USB buses in the system and the devices connected to them.

OPTIONS
       -v, --verbose
              Tells  lsusb  to be verbose and display detailed information about the devices shown.  This includes con‐
              figuration descriptors for the device's current speed.  Class descriptors will be shown, when  available,
              for USB device classes including hub, audio, HID, communications, and chipcard.

       -s [[bus]:][devnum]
              Show only devices in specified bus and/or devnum.  Both ID's are given in decimal and may be omitted.

以下省略
ということで、さっそく使ってみよう。
fuji$ lsusb
Bus 002 Device 001: ID 1d6b:0003 Linux Foundation 3.0 root hub
Bus 001 Device 003: ID 03f0:134a Hewlett-Packard Optical Mouse
Bus 001 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub
fuji$ lsusb -t
/:  Bus 02.Port 1: Dev 1, Class=root_hub, Driver=xhci_hcd/8p, 5000M
/:  Bus 01.Port 1: Dev 1, Class=root_hub, Driver=xhci_hcd/16p, 480M
    |__ Port 7: Dev 3, If 0, Class=Human Interface Device, Driver=usbhid, 1.5M
fuji$ 
マウスは見えるが、キーボードが見えない。
実は、キーボードは、USBではなく、PS2でHHK(Happy Hacking Keyboard)をつないでいるからである。
ナンプレブームが今も続いていて、今年もMATH POWER 2018 に巨大合体ナンプレ世界一(?)を提供することになった。
去年は国政選挙に邪魔されて、六本木のニコファーレが使えず、会場が青山になったが、今年はニコファーレの予定である。
巨大合体ナンプレは現在鋭意制作中であり、世界一になるかどうかはまだ分からない。
さて今回は、合体ナンプレの話ではなく、サイズが9x9の単体のナンプレ問題の話をしよう。
NPSame1.png NPSame2.png
さて、この2つの問題、何が違うだろうか?
数学の祭典 MATH POWER が今年も開催される。
時期は、10月最初にある連休の最初の2日間に行われる。
今年の場合、10月6日昼から7日夜まで、31時間連続で夜を徹して数学を愛でるイベントだ。
場所は、六本木のニコファーレだ。

既に MATH POWER 2018 のサイトが公開されていて、参加申し込みも受け付けている。


MathPower2018SiteHeadImage.png

サイトは、まだまだ情報不足だが、どんなことが行われるかは、去年のサイト MATH POWER 2017 を見ると良いだろう。
去年は、イベントの最初から最後まで、多人数でやっと解ける程度の合体ナンプレを作って欲しいというので、247合体ナンプレを作った。
フィナーレまでには終わらなかったが、若干の延長で解き終えると思われたので、イベントをちょっと延長し、完成したのであった。
その問題がこれだ。

MP247Q.png
MATH POWER 2017 のサイトを見れば、ExcelとPDFで問題があるので、興味のある場合は解いてみよう。

さて、今年のMATH POWERでは、もうちょっとグレードアップした問題を提供することになっていて、現在鋭意製作中である。

去年は「世界最大級」というふうに級をつけていたが、今年はそんなに遠慮せずに、「世界最大」とすることにした。
そのために、去年よりもさらに大きくなってしまった。

去年のデザインは、美しいけれども単純な繰り返しなので、解き筋もモノトーンになってしまう。もっと色々な手筋が現れるように、もうちょっとデザインを頑張ってみた。
その他にも、色々なことにチャレンジしている。

しかし、そんなことをすると、どうやっても問題ができなくなることがある。

それに、いきなり巨大なものを作るのは危険だ。何時間、いや何日も連続でコンピュータを走らせても、何の結果も得られないことが多くなる。
そのため、小さい問題、といっても148合体とかなのだが、その程度の小ぶりな問題(?)で試作をしてみる。
この程度のサイズですんなり出来ない場合には、今年の問題サイズでは絶対に無理なのだ。

コンピュータ、ネットワークなど何でも同じなのだが、小さい場合にうまくいっても、そのまま拡大したら破綻することが多い。
サイズが2倍になったら、計算時間は10倍、100倍どころか永久に終わらなくなる。

ということで、色々な小さな問題を作っては問題生成の調子をみて、スケールアウトできそうだったら本番サイズで試すというのを繰り返している。
使っているアルゴリズムは、進化計算の一種である。
デタラメに問題をつくっては解き、どのくらい酷いかを判定し、ちょっと問題をいじっては酷さを判定している。
どんどんひどくない方向にヒントの数字をいじるのを繰り返しているだけである。
要するに、仕組みは簡単至極である。

問題の難易度はポイントで示される。
これを元に解くのにかかる時間が予想できる。
しかし、それだけでは十分ではない。
極端に易しい場所や、極端に難しい場所がないか、コンピュータに計算させている。
その結果を見て、ざっと判定し、良さそうな問題ができたら、実際に解いてみて、解き心地を調べる。

こういうのを繰り返して、イベントで解いてもらう問題を1問選定するのだ。
とても時間のかかる作業だ。

去年うまくいったので、さらにレベルアップして、来場者が驚くような、印象的なイベントにしようとしているのだ。
どんなサプライズがあるかは、イベントに参加して体感してみよう。

コピーの基礎的なことから書くので、話が無駄に長くなるのを最初に断っておく。 最後に、a[...] のような記述について書くので、そこだけ読みたい場合は最後から読もう。
まず、Pythonでの浅いコピーを示す。
>>> a = [[1,2,3],[4,5,6]]
>>> b = a
>>> a[0][0],a[1][1] = 100,200
>>> a
[[100, 2, 3], [4, 200, 6]]
>>> b
[[100, 2, 3], [4, 200, 6]]
aの要素だけを変更しようとしても、 b = a の代入により浅いコピーが行われているので、bの対応する要素も変わってしまう。

これを避けるためには、b=aの代わりに、copyのdeepcopy()を使う。
>>> import copy
>>> a = [[1,2,3],[4,5,6]]
>>> b = copy.deepcopy(a)
>>> a[0][0],a[1][1] = 100,200
>>> a
[[100, 2, 3], [4, 200, 6]]
>>> b
[[1, 2, 3], [4, 5, 6]]
さて、Pythonで色々計算しようとすると、Pythonではやってられなくて、NumPyを使うのが普通だ。 そもそも、Pythonには配列がなく、Deep Learningで必須の行列計算に困る。
では、numpyの配列で同じことをやってみよう。
>>> a = np.array([[1,2,3],[4,5,6]])
>>> b = np.array([[2,4,6],[3,6,9]])
>>> b = a
>>> a[0][0],a[1][1] = 100,200
>>> a
array([[100,   2,   3],
       [  4, 200,   6]])
>>> b
array([[100,   2,   3],
       [  4, 200,   6]])
単に代入ではコピーにならないようだ。
次に、numpyで用意されているcopy()を使ってみよう。


深いコピーができたようだが、念の為、サイズが歪なarrayでやってみよう。
>>> a = np.array([[1,2,3],[4,5]])
>>> b = np.array([[2,4,6],[3,6]])
>>> b = np.copy(a)
>>> a[0][0],a[1][1] = 100,200
>>> a
array([list([100, 2, 3]), list([4, 200])], dtype=object)
>>> b
array([list([100, 2, 3]), list([4, 200])], dtype=object)
歪んだarrayでやったら、元のaがリストの配列になってしまい、失敗したようだ。
numpyには、copy()はあるようだが、deepcopy()が存在しない。 それで、ここはやむなく、copy.deepcopy()でやるとどうなるか試してみよう。
>>> a = np.array([[1,2,3],[4,5,6]])
>>> b = np.array([[2,4,6],[3,6,9]])
>>> b = copy.deepcopy(a)
>>> a[0][0],a[1][1] = 100,200
>>> a
array([[100,   2,   3],
       [  4, 200,   6]])
>>> b
array([[1, 2, 3],
       [4, 5, 6]])
>>> a = np.array([[1,2,3],[4,5]])
>>> b = np.array([[2,4,6],[3,6]])
>>> b = copy.deepcopy(a)
>>> a[0][0],a[1][1] = 100,200
>>> a
array([list([100, 2, 3]), list([4, 200])], dtype=object)
>>> b
array([list([1, 2, 3]), list([4, 5])], dtype=object)
これで深いコピーができたわけだが、元の配列aは2次元配列ではなくて、リストの配列になっているので深いコピーができなかったようだ。
さて、配列の深いコピーをするのに、copy.deepcopy()を使えば問題ない。 しかし、普通のnumpyの配列なら、numpyのcopy()で深いコピーができる。


ごちゃごちゃ書いてきたが、最後に ...(3点)の使い方について書いておく。
>>> a = np.array([[1,2,3],[4,5,6]])
>>> a
array([[1, 2, 3],
       [4, 5, 6]])
>>> a[...]
array([[1, 2, 3],
       [4, 5, 6]])
配列aを表示するのに、単にaと書けば済むのだが、a[...]と書くこともできる。
ならば、a[...]に代入するとどうなるだろうか?
>>> a = np.array([[1,2,3],[4,5,6]])
>>> b = np.array([[2,4,6],[3,6,9]])
>>> b[...]=a
>>> a[0][0],a[1][1] = 100,200
>>> a
array([[100,   2,   3],
       [  4, 200,   6]])
>>> b
array([[1, 2, 3],
       [4, 5, 6]])
同じサイズの配列の場合、これで配列の深いコピーができている。 copy.deepcopy()やnumpy.copy()を使わなくてもできるのだが、事前に同じサイズの配列が存在していないといけない。

最後に、...が何者か示しておく。
>>> ...
Ellipsis
>>> type(...)

...はオブジェクトなので、引数として渡すなどもできる。
日本でも、大学の講義がビデオで公開されるようになったとはいうものの、通常行われている講義がそのまま公開されるのではなく、かなり短い特別な講義だけが公開される感じで、とても世界と比較てきるようなオープン性は見られない。

まあ、そんなことを言っても仕方がない、ここは日本だ。
それよりも、世界の大学でどんな講義が公開されているのか、探して勉強したほうが良い。

MITOPENCOURSEWAREでは、MITの実際の講義がそのままビデオでじゃんじゃん公開されている。
現在、2400コースあり、3億人が見たそうだ。
この数字は、MITだけでの数字である。

実際の正規のコース授業がそのまま公開されているようで、形態もいろいろあるようだが、VIDEOが一番気楽でよい。
VIDEOだけではなく、資料、問題、なども用意されていて、とても親切である。

日本の大学だと、あれこれ登録しないと見せてくれないケチな根性のところが多いが、ここは何の登録をしなくても、見せてくれる。
ちゃんと授業を受けて、試験も受けて、サーティフィケイトを貰いたいとかの場合は、登録などが必要みたいだ。

さて、最近、MITでパズルの授業を行っているというのを伝え聞いた。
それで、さっそく調べて見つけたのが、Programming for the Puzzled というコースだ。

レベルは学部生向けで、パズルでアルゴリズムを考えることで、プログラミング能力の基礎を鍛えようという意図らしい。
実際、この授業だけではなく、パズルやゲームを授業に使っている例は簡単に見つかる。

先生は、Srini Devadas教授で、インド人である。
あのIITマドラス校出身で、バークレーで学位を取得し、MITのFull Professorになっている。
ということで、ちょっと英語にインド訛りがあるが、そんなに気にしなくて良い感じだ。
そもそも、MITとかでコンピュータ関係を勉強しようとしたら、インド英語は必須科目だろう。
この講義には、トランスクリプション(発言内容を全部文字にしたもの)が用意されているので、聞き取りにくければ、テキストとして読むこともできる。

講義は全部で11本のビデオになっている。
毎回、色々なパズルを取り上げて、アルゴリズムについて細かく解説し、Pythonのプログラムを示しながら講義は進む。
Pythonのプログラムや、課題の解答プログラムも用意されていて、懇切丁寧だ。

講義の中に、SUDOKUがあるというので、この講義を知ったわけである。
SUDOKUの回は、再帰呼出しが話の中心であった。
最後の方で、再帰呼出しをしないで解くやりかた(普通にルールや手筋に基づく方法)の説明が簡単にされていた。
SUDOKUの問題を作ることには触れていなかった。
まあ、そこまでやると、さすがにMITでも、学部生向けの入門コースとしては無理があるのだろう。

第3回は、Puzzle 3: You Can Read Minds というタイトルで、トランプ手品が題材であった。
手品を1つ身につけたい場合には、ちょっと聴講するとよいだろう。

その他にも、アルゴリズムを考えないといけない、アルゴリズムによって大差がでてしまう例などが取り上げられている。

といっても、どれも基本的なものばかりだ。
パズルに関する高度な内容ではないので、プログラマなら出来て当然と思われるものばかりである。

このアーカイブについて

このページには、fujiが最近書いたブログ記事が含まれています。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。

月別 アーカイブ