東急沿線の公園を巡回するルート
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
元ネタは[[URBAN HACKS社>https://10q89s.jp/]]さんの広告で...
#contents
*お題 [#vbfc0000]
「東急沿線の素敵な公園を巡回する未来の乗り物の、最短周遊...
*概要 [#af6c29ea]
-無向グラフがあって頂点同士がいくつかのエッジで接続されて...
=それぞれのエッジには所要時間（コスト）があり、最短所要時...
-なおルートは問題文中に「周遊」「巡回」とあるように、スタ...
--経路はつまりハミルトン閉路である必要がある。
--ハミルトン閉路 (Hamiltonian Cycle) とは、グラフの各頂点...
-つまるところこの問題はセールスマン巡回問題なのである。
--自社から出発して全てのお客さんのところに訪問し、帰社す...
*解法1 [#mac010d4]
-概要に書いた通り、セールスマン巡回問題なので良い解法はな...
--全探索した上で一番コストの少ない経路を調べてみた。
--順回路なのでスタート地点にこだわる必要は無い。そこは便利
--全探索と言えど、頂点10個ぐらいなので、NP困難と言えど普...
-が、試してみたところ、順路は実質1つしか見つからなかった。
--厳密には1つの経路で、回る順序が2パターン
-というわけで、全探索するまでもなく、実はグラフとにらめっ...
*解法2 [#gc3d00b7]
-まず、このグラフを書き起こしたのが図1である
--各頂点のアルファベットはもとの問題と同じにしてある
図1&ref(graph00.png);
-このグラフのうち、「外側」と「内側」に分けた場合、いくつ...
--本当はグラフの外側と内側は厳密に話す必要があるのだけれ...
-具体的には図2の二重線にした部分は「内側」を通るエッジで...
図2&ref(graph01.png);
-さて、この内側のエッジを通った場合、困ったことがおきる。
-説明のため、図3のようなグラフを使う。
図3&ref(graph03.png);
-「内側」のエッジは必ず「外側」の頂点からつながるので、「...
外側の頂点→内側のエッジ→外側の頂点
-と移動する必要がある。
-しかし、内側のエッジを通る際に通過した外側の頂点にはもう...
内側のエッジを通るとグラフを二分割してしまう
-つまり、「内側のエッジ」は通ると問題が解決できなくなるた...
-それが図4である。
図4&ref(graph04.png);
-さて、今度は内側の頂点とも言うべき、頂点Dに着目してみよ...
-この頂点Dには4本のエッジが接続されており、頂点Dに入った...
-つまり頂点Dを通る方法は &mimetex("_4C_2"); で6通り存在...
-6通りのうち、2通りは前述の「内側のエッジ」と同じく、グラ...
-- A-D-E
-- E-D-H
-- H-D-C
-- C-D-A
--の４択となる。
--なお、グラフは無向グラフなので逆順に通るパターンは同一...
-今、頂点A、B、D、Eの4点で構成される部分グラフに着目しよ...
-図5に部分グラフを示す
図5&ref(graph05.png);
-この時、頂点AからEに抜けようとすると、頂点Bを通るか、頂...
-繰り返しになるが、問題文ではハミルトン閉路が制約なので、
A→D→E→B→A
-みたいにAにまた戻ってくる場合は解答に適さない
-つまりA→D→E（図中の点線の経路）を通ってしまうと、頂点Bに...
-よって、ここの部分グラフでは頂点A→B→E（あるいはその逆順...
-もう一度図4を見ると頂点Dを通れる経路として頂点C→D→A（あ...
-となると、ハミルトン閉路としてありうる経路は頂点Aを基準...
A→B→E→I→→H→G→F→C→D→A
-もしくはその逆順しかありえないことになる。
-というわけで、
--問題文は巡回セールスマン問題に見せかけて、
--実はハミルトン閉路問題で、
--グラフをよく眺めれば計算機を使わずに問題が解けることを...
-なお、実際の所要時間は各自広告とにらめっこして計算してみ...
[[:数学]]
終了行:
元ネタは[[URBAN HACKS社>https://10q89s.jp/]]さんの広告で...
#contents
*お題 [#vbfc0000]
「東急沿線の素敵な公園を巡回する未来の乗り物の、最短周遊...
*概要 [#af6c29ea]
-無向グラフがあって頂点同士がいくつかのエッジで接続されて...
=それぞれのエッジには所要時間（コスト）があり、最短所要時...
-なおルートは問題文中に「周遊」「巡回」とあるように、スタ...
--経路はつまりハミルトン閉路である必要がある。
--ハミルトン閉路 (Hamiltonian Cycle) とは、グラフの各頂点...
-つまるところこの問題はセールスマン巡回問題なのである。
--自社から出発して全てのお客さんのところに訪問し、帰社す...
*解法1 [#mac010d4]
-概要に書いた通り、セールスマン巡回問題なので良い解法はな...
--全探索した上で一番コストの少ない経路を調べてみた。
--順回路なのでスタート地点にこだわる必要は無い。そこは便利
--全探索と言えど、頂点10個ぐらいなので、NP困難と言えど普...
-が、試してみたところ、順路は実質1つしか見つからなかった。
--厳密には1つの経路で、回る順序が2パターン
-というわけで、全探索するまでもなく、実はグラフとにらめっ...
*解法2 [#gc3d00b7]
-まず、このグラフを書き起こしたのが図1である
--各頂点のアルファベットはもとの問題と同じにしてある
図1&ref(graph00.png);
-このグラフのうち、「外側」と「内側」に分けた場合、いくつ...
--本当はグラフの外側と内側は厳密に話す必要があるのだけれ...
-具体的には図2の二重線にした部分は「内側」を通るエッジで...
図2&ref(graph01.png);
-さて、この内側のエッジを通った場合、困ったことがおきる。
-説明のため、図3のようなグラフを使う。
図3&ref(graph03.png);
-「内側」のエッジは必ず「外側」の頂点からつながるので、「...
外側の頂点→内側のエッジ→外側の頂点
-と移動する必要がある。
-しかし、内側のエッジを通る際に通過した外側の頂点にはもう...
内側のエッジを通るとグラフを二分割してしまう
-つまり、「内側のエッジ」は通ると問題が解決できなくなるた...
-それが図4である。
図4&ref(graph04.png);
-さて、今度は内側の頂点とも言うべき、頂点Dに着目してみよ...
-この頂点Dには4本のエッジが接続されており、頂点Dに入った...
-つまり頂点Dを通る方法は &mimetex("_4C_2"); で6通り存在...
-6通りのうち、2通りは前述の「内側のエッジ」と同じく、グラ...
-- A-D-E
-- E-D-H
-- H-D-C
-- C-D-A
--の４択となる。
--なお、グラフは無向グラフなので逆順に通るパターンは同一...
-今、頂点A、B、D、Eの4点で構成される部分グラフに着目しよ...
-図5に部分グラフを示す
図5&ref(graph05.png);
-この時、頂点AからEに抜けようとすると、頂点Bを通るか、頂...
-繰り返しになるが、問題文ではハミルトン閉路が制約なので、
A→D→E→B→A
-みたいにAにまた戻ってくる場合は解答に適さない
-つまりA→D→E（図中の点線の経路）を通ってしまうと、頂点Bに...
-よって、ここの部分グラフでは頂点A→B→E（あるいはその逆順...
-もう一度図4を見ると頂点Dを通れる経路として頂点C→D→A（あ...
-となると、ハミルトン閉路としてありうる経路は頂点Aを基準...
A→B→E→I→→H→G→F→C→D→A
-もしくはその逆順しかありえないことになる。
-というわけで、
--問題文は巡回セールスマン問題に見せかけて、
--実はハミルトン閉路問題で、
--グラフをよく眺めれば計算機を使わずに問題が解けることを...
-なお、実際の所要時間は各自広告とにらめっこして計算してみ...
[[:数学]]
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
