もう一度(これでだめな時は更新してください。) : 新しいNと場所で描き直します。
自動的編最短路重み付き最短路ハキミ需要に重み付きのハキミ道路に重み付きのハキミ需要と道路に重み付きのハキミ
クリック編最短路-ハキミ-
スクリーンセーバー

ハキミ問題(2000年9月9日公開、2010”N06ŒŽ03“ú22:18:37第5回の改訂)

上はJAVAで作られています。メモリを大量に使ったり、重くなるかもしれません。その時は、ごめんなさい。
実行後に画面をスクロールしたり、アプレット全体が画面に入ってないと、間違った画面になるかもしれないので、気をつけてください。画面の大きさを決めてから”もう一度”をクリックするか、更新(reload)してください。


●ハキミ問題
ここでいうハキミ問題とは、利用者全員の総移動距離が最小になるように施設を配置する問題です。
黄色い点と道路ネットワーク(赤)があるとします。黄色い点には施設の利用者が1人ずついるものとします。また、利用者は施設を利用する際、道路を使った最短の道で移動するものとします。この時、利用者全員の総移動距離が最小になるように施設を置く問題がハキミ問題(しばしばミニサム問題とも言います)です。
上では白い丸で囲まれた点が最適点となります。白い線はその最適点から各点への最短のネットワークをあらわします。
数学的に書くと、領域にn個の需要p(1),...,p(n)があるものとします。施設の場所をxとして、d(x,p(i))をxからp(i)までの道路ネットワークを利用した時の最短距離とします。この時、目的関数f
f=d(x,p(1))+...+d(x,p(n))
を最小にするようにxの位置を道路ネットワーク上に決める問題がハキミ問題です。ハキミ(Hakimi)はこの問題の答えが需要の位置p(1),...,p(n)のうちのどれかに少なくとも1つは存在することを示しました。このプログラムもその性質を利用して答えを求めています。答えを求めた後で、最短路問題を使って、各点への最短路を求めています。
●参考文献:日本建築学会編、井上書院、建築・都市計画のためのモデル分析の手法 ●Javaプログラムのダウンロード(haki.java 11KB)

ご意見、ご感想、お問い合わせ、お願い等がございましたら、お気軽に、
メール送信フォームからメールを送るか、
●掲示板に書き込むか、
どちらかお好きな方法で、ご連絡お願いいたします。


●大山崇のホームページの利用について
●大山崇のホームページ