研究帖17

そよ風さん「博士、今日は。」

ナイス博士「おお、そよ風さん、どうしたんだい？」

そよ風さん「博士、これを見て下さい！」

ナイス博士「おお！！、うまそうなニシンの干物だな！！」

そよ風さん「ええ、たくさんもらいました。博士もどうぞ。」

ナイス博士「やあ、有難う。うまく行って良かったな。」

そよ風さん「ええ、おかげさまで、部屋を決めたら、喧嘩も無くなって、みんなすごく 仲良くなりました。でも.......」

ナイス博士「でも？どうかしたのかい？」

そよ風さん「ええ、仲良くなったのはいいんですが、」

ナイス博士「なんだい？」

そよ風さん「みんな一緒に、和気藹々と行動するようになったんです。」

ナイス博士「うん。結構じゃないか。職場の和が保てないと、仕事もうまく行かないよ。」

そよ風さん「ええ、仕事自体はうまく行っているんですが、みんな帰る時も一緒なんです。」

ナイス博士「うん、良いじゃないか。チームワークが大切だよ。」

そよ風さん「でも、帰り道で、みんな一緒に遊ぶんです。」

ナイス博士「うん、別に良いだろう？息抜きも必要だよ。」

そよ風さん「で、翌日、みんな一緒に遅刻するんです。」

ナイス博士「うん、別に........ああ、それはまずいな。」

そよ風さん「そうなんですよ。女王様が8人、全員遅刻しちゃうから、早く来たお客さんも 怒って帰っちゃうんです。」

ナイス博士「そうか。どうも、困ったもんだな。」

そよ風さん「ええ、で、しょうがないからオーナーが、マイクロバスを買って、送り迎えする 事になったんです。」

ナイス博士「ええっ、幼稚園じゃないんだから、そこまでしなくても、 何とかならないかなあ。」

そよ風さん「そうですよねえ。でも、そうしないと、8人一緒にお店を止める、なんて言い出し たんです。」

ナイス博士「うーーん、わがままな人達だな。それじゃオーナーさんも大変だ。」

そよ風さん「いや、でも、巡回しながら美人に囲まれていくのを、楽しみにもしているようですよ。」

ナイス博士「そうかい？無事に巡回出来れば良いけど。」

そよ風さん「実はそれが、問題があるんです。」

ナイス博士「ほう、なんだい？」

そよ風さん「8人ともばらばらに離れて住んでいるんで、うまく回らないと営業に 間に合わないんです。で、」

ナイス博士「で？」

そよ風さん「で、パソコンで、一番早く巡回できるコースを見つけてくれと、 頼まれたわけです。いい方法はないですか？」

ナイス博士「うん、それなら『騎士の巡回問題(セールスマンの巡回問題)』が使えるぞ！」

そよ風さん「『騎士の巡回問題』ですか。じゃ、早速『何でも入門書』で探して見ます。」

ナイス博士「うん、それが良いな。」

そよ風さん「うーーん、」

ナイス博士「うーーーん、」

そよ風さん「難しいですね。専門用語ばかりで、読んでも良く分りません。」

ナイス博士「まったくだな。」

そよ風さん「何か簡単な、良いアイデアは、無いですか？」

ナイス博士「うーん、思いつかないな。こんな時、BB君が居てくれたらなあ。...」

そよ風さん「博士、いつもBB君ばかり頼らなくてもいいじゃないですか！少しは自分で 考えないと！」

ナイス博士「何を言ってるんだ！それは君じゃないか。」

そよ風さん「えっ、まあ、そうですね。うーーん、地道に考えるとですねえ。.....」

ナイス博士「何だい？」

そよ風さん「まず、全部のルートの組み合わせを出さないといけないですね。」

ナイス博士「そうだな。」

そよ風さん「博士は、前にエクセルVBAで、二進法を使って配列のすべての組み合わせを 書き出すコードを作ったじゃないですか。あれは使えませんか？」

ナイス博士「今回はだめだな。あの時は、順番が違っても要素が同じなら同じ組み合わせ と考えて良かったが、今度のは、同じ要素で順番だけが違う組み合わせを作らなくては いけないんだからな。」

そよ風さん「ああ、そうですね。目的地が8個所だと何通り有るんでしょうか。」

ナイス博士「8の階乗だよ。8×7×6×5×4×3×2×1=40320通りだよ。」

そよ風さん「そんなに有るんですか！すごいわ！」

ナイス博士「そうだな。要素が2つなら２通りだが、3つなら、6通りになるし、 どんどん増えるんだ。」

そよ風さん「ふうん、それなら.....たとえば、最初の2つの要素が1と2で、それだけで 組み合わせを作ると、{1,2}と、[2,1]の、2通り出来ますよね？」

ナイス博士「うん。それだけなら簡単だな。」

そよ風さん「で、3番目の要素が3だとして、2とおりの配列の最初と後と、間に数字を入れると 全部で6通りの配列が出来るわけですね？」

ナイス博士「その通りだよ！」

そよ風さん「その6つの配列は、全部違う配列のはずですね！！」

ナイス博士「ええっ、証明できるのかい！」

そよ風さん「出来ます！」

*************************************************************************

　　＊　{1,2}と、[2,1]は、別な配列だ。

　　＊　別の配列の同じ位置に、それまで使われていない同じ数字を入れれば、別の配列になる。

　　＊　{1,2}と、[1,2]は、同じ配列だ。

　　＊　同じ配列の別の位置に、それまで使われていない同じ数字を入れれば、別の配列になる。

　　＊　数字を挿入できる場所は、最初、最後と数字の間しかない。つまり、要素数+1箇所ある。

　　＊　だから、{1,2}と[2,1]に3を入れて出来る配列は、

　　　　{3,1,2},{1,3,2},{1,2,3},{3,2,1},{2,3,1},{2,1,3}だけで、全部違う配列だと言える。

*************************************************************************

そよ風さん「どうですか！博士！」

ナイス博士「すごい！完璧な論理だ！」

そよ風さん「はっはっはっ、いや、それほどでも無いですよ。」

ナイス博士「で、それからどうする？」

そよ風さん「とにかく、全部の組み合わせを出すアルゴリズムですが、」

*************************************************************************

　　＊　{1,2}と、[2,1]の配列を作る。

　　＊　それぞれの配列の所定の位置に、3を入れて、6つの配列にする。

　　＊　全部の数字を入れるまで、同じ要領で配列を増やして繰り替えす。

*************************************************************************

そよ風さん「こんな感じでしょうか。」

ナイス博士「でもこれだと、動的配列の動的配列が必要じゃないか？」

そよ風さん「ええ、ArrayListを使うつもりです。」

ナイス博士「そんな事しなくても、配列の数は最初にわかるんじゃないか？」

そよ風さん「どうするんですか？」

ナイス博士「まず、1つの配列の要素数は、女王様の家が8箇所だから8だね。」

そよ風さん「ええ、それがいくつ要るんですか。」

ナイス博士「要素数の階乗で出せるんだ。」

そよ風さん「ああ、そうでしたね。でも次の要素を入れる位置が色々だから、うまく入れる 場所を決めるのが難しいですよ。」

ナイス博士「そうだなあ、何か法則が無いかなあ。」

そよ風さん「そうですねえ。よく考えないと、分りませんね。」

さらに1時間が過ぎた.....................。

ナイス博士「うーーん。」

そよ風さん「うーーーん。」

ナイス博士「何か考えたかい？」

そよ風さん「ええ、少しだけ。」

ナイス博士「何を？」

そよ風さん「まず、仮に回る個所が4箇所だけだとして考えたんですが。」

ナイス博士「ああ、それがいいな。まず、単純な問題で考えるのがコツだ。」

そよ風さん「で、さっきの方法で、全部が別の配列で、しかも、有り得る全ての配列が 出来る筈ですよね。」

ナイス博士「その筈だな。」

そよ風さん「であれば、最初の数1は、全てのインデックスで同じ回数だけ出る筈ですね。」

ナイス博士「そうだ。」

そよ風さん「そうすると、要素数4の配列が24個で、1の位置はこんな感じですね？」

*************************************************************************

　　　{1,*,*,*}　{*,1,*,*}　{*,*,1,*}　{*,*,*,1}

　　　{1,*,*,*}　{*,1,*,*}　{*,*,1,*}　{*,*,*,1}

　　　{1,*,*,*}　{*,1,*,*}　{*,*,1,*}　{*,*,*,1}

　　　{1,*,*,*}　{*,1,*,*}　{*,*,1,*}　{*,*,*,1}

　　　{1,*,*,*}　{*,1,*,*}　{*,*,1,*}　{*,*,*,1}

　　　{1,*,*,*}　{*,1,*,*}　{*,*,1,*}　{*,*,*,1}

*************************************************************************

そよ風さん「同じ配列が6つずつ出来ましたね。」

ナイス博士「そうだな。これだけならループで、1を6つ入れるごとにインデックスを増やせば 出来るな！問題はその次だな。2はどうするんだ？」

そよ風さん「それぞれの空いている位置に、均等に2つずつ入れます。」

*************************************************************************

　　　{1,2,*,*}　{2,1,*,*}　{2,*,1,*}　{2,*,*,1}

　　　{1,2,*,*}　{2,1,*,*}　{2,*,1,*}　{2,*,*,1}

　　　{1,*,2,*}　{*,1,2,*}　{*,2,1,*}　{*,2,*,1}

　　　{1,*,2,*}　{*,1,2,*}　{*,2,1,*}　{*,2,*,1}

　　　{1,*,*,2}　{*,1,*,2}　{*,*,1,2}　{*,*,2,1}

　　　{1,*,*,2}　{*,1,*,2}　{*,*,1,2}　{*,*,2,1}

*************************************************************************

ナイス博士「いや、でも、均等といっても、2つずつの2は、どうやって計算する?」

そよ風さん「最初の6は、配列数24÷要素数4で出ますね。」

ナイス博士「うん。次は?」

そよ風さん「同じ配列の空いている要素に均等に入れるわけですから、同じ配列数6÷空いている 要素数3=2回ずつ入れて、同じ配列が2つずつ出来ますね。」

ナイス博士「すると次の3は、2÷2=1回ずつだな！」

*************************************************************************

　　　{1,2,3,*}　{2,1,3,*}　{2,3,1,*}　{2,3,*,1}

　　　{1,2,*,3}　{2,1,*,3}　{2,*,1,3}　{2,*,3,1}

　　　{1,3,2,*}　{3,1,2,*}　{3,2,1,*}　{3,2,*,1}

　　　{1,*,2,3}　{*,1,2,3}　{*,2,1,3}　{*,2,3,1}

　　　{1,3,*,2}　{3,1,*,2}　{3,*,1,2}　{3,*,2,1}

　　　{1,*,3,2}　{*,1,3,2}　{*,3,1,2}　{*,3,2,1}

*************************************************************************

そよ風さん「最後の4は、1÷1=1回ずつで、出来ましたっ！！」

*************************************************************************

　　　{1,2,3,4}　{2,1,3,4}　{2,3,1,4}　{2,3,4,1}

　　　{1,2,4,3}　{2,1,4,3}　{2,4,1,3}　{2,4,3,1}

　　　{1,3,2,4}　{3,1,2,4}　{3,2,1,4}　{3,2,4,1}

　　　{1,4,2,3}　{4,1,2,3}　{4,2,1,3}　{4,2,3,1}

　　　{1,3,4,2}　{3,1,4,2}　{3,4,1,2}　{3,4,2,1}

　　　{1,4,3,2}　{4,1,3,2}　{4,3,1,2}　{4,3,2,1}

*************************************************************************

ナイス博士「前に入れた数字をスキップさせないと、次の数字で消えちゃうな。」

そよ風さん「そうですね。何か、スキップ用の適当な数字で初期化するといいですね。 要約すると、」

*************************************************************************

　　 1.要素数が元の配列と同じ配列を、要素数の階乗の数だけ作る。

　　 2.適当な数字で全ての要素を初期化する。(たとえば-1)　　　　　　　

　　 3.ループで、まだ確定していない要素に1から順番に数字を入れていく。

　　　この時同じ配列数÷要素数の数だけ入れたら、インデックスを1つ進める。

　　　ただし、その要素が-1でなかったらスキップする。

*************************************************************************

ナイス博士「うん。とにかくコードを書こう。」

そよ風さん「はい！」

そして1時間が経過した。.....

ナイス博士「どうだい？うまくいったかい？。」

そよ風さん「博士、これを見て下さい！」

アプレット、巡回先の組み合わせ

ナイス博士「ああ、いいね！コードは？。」

そよ風さん「これです！」

コード　簡単なクラス図

ナイス博士「おお、良く出来たな！」

そよ風さん「ええ、でも、これからが大変ですね。」

続く

そよ風さん「博士、これからどうしますか？」

ナイス博士「そうだな。距離の入力だな。1-2なら何キロ、1-3なら何キロ、1-4なら何キロと、 全部入力するんだ。」

そよ風さん「はい。それから？」

ナイス博士「配列から数字を２つずつ出して、それをキーにして距離を出して 足していくんだ。」

そよ風さん「そうすると、配列が1,3,2,4だとすると、1-3,3-2,2-4の距離を 足すんですね？」

ナイス博士「そうだな。それを全部の配列でやるんだ。」

そよ風さん「距離は何に入力しますか？」

ナイス博士「HashMapが良いんじゃじゃないか？1-2や2-3をキーにして距離を 保存するんだ。」

そよ風さん「でも博士、たとえば配列が1、2と2、1では、別なキーになりますけど、 それで同じ距離が出ないとだめですよ！」

ナイス博士「そうだな。だから、2つの数字を昇順に並べて、キーを作るクラスも 作ろう。」

そよ風さん「なるほどね。あとは、それらを表示した上で、最短距離とその順番を別に 表示すれば良いですね！」

ナイス博士「うん。早速やってみよう！」

そよ風さん「はい！....................................博士、出来ました！」

追加したコード　簡単なクラス図

ナイス博士「うわっ！早いな！！どれどれ、最初は4つの目的地でやって見よう！」

そよ風さん「はい！...ほら、出来ました！！」

ナイス博士「早い！次は５つだ！」

そよ風さん「はい！.....出来ました！」

ナイス博士「よし！じゃ、6つで！」

そよ風さん「はい！..............出来ました！」

ナイス博士「すごい！次は7つだ！」

そよ風さん「はい！.......................................................... 出来ました！」

ナイス博士「よし！じゃあ、いよいよ8つでやって見よう！」

そよ風さん「はい！............................................................ ........................................................................................ ........................................................................................ ...................................................................................... ...................................................................................... ........................................................................................ ............................................................................................. ............................................................................................ ............................................................................................ ............................................................................................」

ナイス博士「どうしたの？」

そよ風さん「はい！すぐ出来ます！....................................................... ............................................................................................... .......................................................................................... .............................................................................................. .............................................................................................. ......................................................................................... ............................................................................................... ........................................................................................... .............................................................................................. ........................................................................................... ............................................................................................. ............................................................................................. ............................................................................................. ............................................................................................ .............................................................................................. ......................................................................................... ............................................................................................ .............................................................................................. ............................................................................................ ............................................................................................. ..............................................................................................」

ナイス博士「まだかな？」

そよ風さん「はい！ちょっとまって.................................................... .............................................................................................. .............................................................................................. ............................................................................................. ........................................................................................... ........................................................................................... ........................................................................................... ........................................................................................... ............................................................................................. .......................................................................................... .......................................................................................... ............................................................................................ ........................................................................................... ........................................................................................ ........................................................................................... ...................................................................................... .......................................................................................... ......................................................................................... ......................................................................................... ....................................................................................... .......................................................................................... ......................................................................................... ............................................................................................. .......................................................................................... .......................................................................................... ............................................................................................ ........................................................................................... ........................................................................................ ........................................................................................... ...................................................................................... .......................................................................................... ......................................................................................... ......................................................................................... ....................................................................................... .......................................................................................... ......................................................................................... ........................................................................................ ....................................................................................... .......................................................................................... ............................................................................................ ........................................................................................... .............................................................................................. ............................................................................................ .......................................................................................... .............................................................................................. ........................................................................................... .......................................................................................... ............................................................................................ ............................................................................................ ............................................................................................ ........................................................................................」

ナイス博士「うーーん、待ちくたびれたな。」

そよ風さん「ええ、もう2時間もたちましたよ。」

ナイス博士「やっぱり、40320通りもの配列を作って表示するとなると、ちょっと大変だなあ。」

そよ風さん「博士、そんなに配列を作って表示しても、だれも全部見ないですよ。」

ナイス博士「そうだな。じゃ、配列を全部表示するのは止めて、全部の合計距離と最短距離と最短ルートだけにしよう。」

そよ風さん「はい。..........................出来ました！」

アプレット

ナイス博士「これで何とか出来たな！」

そよ風さん「ええ、場所と距離の入力方法をもっとうまく考えれば、もっといろいろ実用的に 使えるソフトに出来るかも知れませんね！」

続く。

」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」

研究課題に戻る。

　見学者への注意事項に戻る。