TIM Labs

fujiによるエントリー一覧

一般的な巡回セールスマン問題は、一人のセールスマンが多数の街を巡回することになっているが、これでは過重労働になり、過労死するかも知れない。

ということで、セールスマンを増員してみよう。

2人のセールスマンは、いずれもセンター(基地、本社、本部、、、、何と呼んでも良いのだが)から出発して、全ての街をいずれかのセールスマンが立ち寄り、二人とも出発点のセンターに戻ってくるとする。

2人の負荷はできるだけ差が少ないことが望ましい。それで、各人の経路長の差を少なくしたい。かつ、各人の経路長も短くしたい。

それで、平均経路長+経路長の差 をできるだけ小さく(短く)することにしてみた。

すると、こんな結果が得られた。

100-2-2-2202-s.png    100-2-2-2120-s.png

左は赤と青の巡路が分かれているが、右は巡路が交叉している。

点の位置は同じになっているのだが、どちらが 平均経路長+経路長の差 が小さくなっている、つまり望ましいプランであろうか?

通常の巡回セールスマン問題は、スタート地点まで戻る、つまり一周する最短のループを求めるのであるが、それとはちょっと違う次図の場合について考えてみよう。

100-Line-3750.png  100-Line-3745.png

全ての点を結んでいるが、元の点には戻っていない。こういう場合の最短経路が欲しい場合もあろう。

開始点、終了点を任意としているので、実行の度に異なる。

求まるのは準最適解(それなりに良い解)であり、理論上の最適解ではないので、実行毎に異なってしまう。

さて、どうプログラムを変更すれば良いだろうか?

標準的な巡回セールスマン問題は、経路長が最短のものを見つけるのであるが、これを変えてみた。

最適化の対象になる関数を適応度関数(fitness function)とか、コスト関数、評価関数とか呼ぶわけだが、このfitness関数を距離ではない次のようなものに変えてみた。

AngleExp.JPG

各頂点で曲がることになるのだが、そのときの回転角度の2乗和を最小にすることにした。

プログラムで変更したのはたったそれだけ。

すると、こんなことになった。500-Angle.pngこれは前のより点数が増えて500点であり、もっとぐるぐる回っているように見える。

つまり、fitness関数は、なにか適当なのをでっちあげて、その関数の値を最適なもの(通常は最小か最大)を指定すると、後は延々と計算して、結果を表示してくれる。

ということで、巡回セールスマン問題だからといって、最短距離に凝り固まる必要はなく、ちょっと頭を柔軟にすると、色々なことを調べるのに使えるのだ。

巡回セールスマン問題は、実はもっともっと汎用性に富んでいるのだが、その話はまた次で。

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

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つの問題、何が違うだろうか?

このアーカイブについて

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

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

月別 アーカイブ