【数学】小木津山トレイルランニング問題

はじめにお断りしますが、これはトレイルランナーのマナーを問うような類の話ではありません。
12/1の山行記録にて、小木津山自然公園 (茨城県日立市) 内に張り巡らされているトレイルのマップを作成しようとしている旨を述べました。駐車場を始点兼終点としてこの全てを通るような最短経路を自分用の練習コースにするつもりです。
さて、この最短経路を求める問題は「中国人郵便配達問題」というらしい。Wikipediaから引用すると、「グラフ理論において、グラフ中のすべての辺を1度ずつ通るような閉路が存在するグラフをオイラーグラフといい、その閉路をオイラー路という。よってこの問題を解くには、与えられたグラフにおいて、グラフ中の一部の辺を2本に増やすことで、オイラーグラフが得られるようにすることを考えればよい。そのような辺の組み合わせは一般に複数通りあるため、その中で増やした辺に割り当てられた距離が最小になるような辺の組み合わせを求めることになる。」とのこと。うん、なんとなく判る。
但し、このままだと単純に折り返してしまうポイントが出てきそうで、それだとトレランコースとしては好ましくありません。そこで、折り返しを禁則とする制約条件を課した「中国人郵便配達問題」を「小木津山トレイルランニング問題」と勝手に呼ばせていただくことにします。本日、二日連続の二日酔いのため運動する気力が湧かないので、この問題のアルゴリズムを考えてみようかしら。でも、なんだか難しそう…。理系ヤマレコユーザーの参入をお待ちしております。

コメント

mnakano

RE: 【数学】小木津山トレイルランニング問題
kilkennyさん、こんにちは。

すでに御承知のこととは思いますが、ネットで見てみると、東京メトロ問題が出てきました。東海大学の先生がやっているようで、馬鹿らしいが面白いです。
http://www.dm.u-tokai.ac.jp/~hama/tokyometro.pdf

↓はゲームになっていて面白い。
http://gascon.cocolog-nifty.com/blog/2007/01/32_2a8e.html

とりあえず、小木津山トレイルの模式図と区間距離を記した図面がほしいところ。区間内の垂直移動距離もほしいですね

kilkenny

RE: 【数学】小木津山トレイルランニング問題
mnakanoさん、こんにちは。

東海大学の先生の[1]は未だ熟読してません。後者は初見です。

>小木津山トレイルの模式図
[1]の図1と同じのを御要求ですね。しばしお待ちを(今日は疲れたので御容赦)

なんだか理系魂を擽ってしまったようですね

kohi-

私は文系なのでさっぱり・・・
kilkennyさん、こんにちは。

なかなかややこしい話になってますね
この「小木津山TR問題」が解決できたら私も参考にさせて頂きたいと思います。

でも間違えずにぐるっと走れるかどうかも、また大変そうですが

kilkenny

RE: 【数学】小木津山トレイルランニング問題
kohi-さん、こんにちは。
文系の参入も大歓迎ですよ

解決したら、地図を日記にアップするか、実際に走ってみてGPS軌跡を山行記録へ挙げますので気長にお待ちください