以下のような碁盤上の街並みがある。各マスの大きさは1キロ四方。どの道沿いからも病院までの距離が短くなるように3つの病院を配置するにはどうすれば良いか。
その時最も遠い人は病院まで何キロになるでしょうか？
例えば病院が１つだけなら以下のように配置して，
最大距離は8キロ。病院が4つならば以下のように配置して，
最大距離は4キロ。3つの場合4キロから8キロの間にあることがわかる。
3つの場合も答えは直感的に判ってしまったけど，本当にそれが正解かどうかどうやって証明するんだろう，と考えているうち，「よし，やはりこういう問題はコンピュータで解こう」と思ってプログラムしたら，第一回目はものの見事に以下の誤答を出力した。
これだと交差点間にある住宅を考慮していないのでダメ。下図の緑色の線上にある住宅から病院までの距離は5Km超になる。交差点上ではちょうど5Kmだけどね。
私は頭ではこの答えが全く浮かばなかったけど，案外この答えを出す人がいるんじゃないかな。
最初に作ったプログラムは以下の通り。最小値が見つかる毎に答えを出力した。
#include "puzutl.h"
YesNo used[81];
struct xy {
int x, y;
}xy[81];
inline int distance( int i, int j)
{
return abs(xy[i].x - xy[j].x) + abs(xy[i].y - xy[j].y);
}
inline int min3( int x, int y, int z)
{
return min(min(x,y),z);
}
int main( int argc, cstring argv[])
{
int cnt = 0;
ProcTime pt;pt.start();
for( int y=0; y< 9; y++) {
for( int x=0; x< 9; x++) {
xy[x + y*9].x = x;
xy[x + y*9].y = y;
}
}
int mindist = 8;
for( int a=0; a< 81; a++) {
used[a] = YES;
for( int b=0; b< 81; b++) {
if( used[b]) continue;
used[b] = YES;
for( int c=0; c< 81; c++) {
if( used[c]) continue;
used[c] = YES;
int maxdist = 0, dist;
for( int i=0; i< 81; i++) {
dist = min3( distance(i,a), distance(i,b), distance(i,c));
if( dist > maxdist) maxdist = dist;
}
if( maxdist && maxdist < mindist) {
ps( "%2d[%d,%d], [%d,%d], [%d,%d]\n", maxdist, xy[a].x, xy[a].y, xy[b].x, xy[b].y, xy[c].x, xy[c].y);
mindist = maxdist;
}
used[c] = NO;
}
used[b] = NO;
}
used[a] = NO;
}
pt.end();
ps( "%g秒\n", pt.sec());
return 0;
}
上記プログラムの出力結果は以下の通り。時間も掛かりすぎてしかも間違った答えを出力する。ちょっと酷いかな。
7[0,0], [2,0], [4,5] 6[0,0], [5,0], [4,6] 5[0,0], [8,0], [4,7] 14.921秒
改良版を作ったところ，思っても見なかった答えが出てきた。自分の直感と違うものが出てきたので大変。プログラムを疑って掛かったけど問題はないみたいだ。
重複を除くと6件出力された。この6件を頭だけで解答するのは難しいと思う。
改良したプログラムは上記プログラムの交差点間の距離を1でなく，1000(メートル)を設定し，全ての交差点間の中点から病院までの距離も計算するようにした。
プログラムは重複除去処理を入れたりしてちょっと汚くなってしまった。
病院は交差点にあり，最小距離は5Kmと計算したんだけど，もしかしてそれ以外の場所に配置して5Km未満の解があるのかなー?
解速度
即(PentiumⅢ500MHzで0.33秒)