渋谷で働くSEのブログ

渋谷で働くSEのお粗末なブログです

グラフ理論、最適化問題

お久しぶりです(^^)/

実は、音楽の研究はあまりにも進まなかったもので、しばらくお休みにしてました。

そして、今は最適化問題にはまってます。

グラフ理論とか。

 

そんな中、最適化問題に関する面白い記事を見つけました。

原文はハングルですが、内容は以下のようなものです。

「ソウル市内の3箇所で同じ時間に結婚式が行われることになっています。どうしましょうか?」

その3箇所を地図上で見ると次のようになっています。

f:id:kyosuu1:20170219023621p:plain

この悩みを聞いた韓国の芸能人キム・スクさんは、次のように答えています。

ロッテワールドに、式の1時間前に言って、結婚するお友達に挨拶をし、一緒に写真を撮ってください。そして、彼らにバレないようにカンナムに移動します。カンナムでもまたお友達にちゃんと挨拶をし、結婚式に出席したことにしましょう。

そして次に、式が始まってから30分後にはホンデに着けるようにしましょう。この時間帯は、ちょうど式が終わって、写真を撮るためにバタバタする時間です。そこに紛れ込んで写真撮影ができたらミッションクリアです」

 

原文は

http://www.wikitree.co.kr/main/news_view.php?id=292256

ここにあります。

 

実は、これって、最適化問題の最も簡単な例です。

 

まず、前提として、日本と韓国の結婚式文化の違いだけ説明させてください。

日本では、結婚式に出席して、披露宴を行います。

しかし、韓国では、面白いことに、結婚式が行われている時間に結婚式場に付いている食堂で食事をすることができます。

(その食堂は、ご祝儀を出した人だけ利用できるようになっています)

なので、式はどうでもよくで、とにかくご祝儀出してご飯食べちゃう人もいたりします。

こんな文化ですから、式に出席しなくても、挨拶さえちゃんとすればバレないわけです。

 

そこで、結婚するお友達に挨拶できるポイントがどこにあるか。

ここでは、3箇所を見出しています。

1. 新郎新婦が待機している、挙式の1時間前

2. 結婚式が始まる直前

3. 集合写真を撮ろうとしている時間

 

この時間を合わせると、だいたい1時間半。

この制限時間と移動時間を考慮すると、

だいたい各結婚式場に滞在できる時間は約10分ずつです。

 

数学の言葉に直して見ると、次のような問題になります。

f:id:kyosuu1:20170219023316p:plain

実際、道はいっぱいあると思いますが、簡単のため1本ずつにしました。

往路と復路がそれぞれにあるので、ホンデ、カンナム、ロッテワールドを点とし、道のりを向きづけられたedgeとする有向グラフとして見なせます。

そして、各経路には、移動時間という重みが付いています。

各点にも、滞在時間という重みがついています。

 

制限時間の1時間半以内に、どうすれば3点全部回れるか。

という問題に帰着するわけです。

 

こんな問題を「巡回セールスマン問題」と言います。

特に、ここでは時間制約がついているので、特にこれを「時間制約の付いている巡回セールスマン問題」とも言うようです。

 

ここでは、点が3つのpath(グラフ理論でいうpathのこと)を考えているので、人の頭で十分計算できたんですが、

点がn個になると、人間の頭ではとても計算できなくなります。

 

そうなると、結局コンピュータの力を借りることになります。

「時間制約付き 巡回セールスマン問題」と検索したらたくさん出てきます。

滞在時間はさすがに10分よりも短いですし、各点の間の重みもさっきの結婚式問題よりはだいぶ小さくなってはいるんですけど、

結局考えてることは一緒です。

「一番時間かけない方法はどれだろう」

 

全部の組み合わせを試すなら、絶対爆発して行きます。

なので、爆発を防止するためにもいろんなアルゴリズムが研究されました。

 

最近はグラフ理論を勉強してますが、近いうちにこの最適化問題にも挑戦できるようになったらいいな、と思っています。