「世界初、来店不要のフルオーダーメイド靴」のプレスリリースを行いました。

18-6. 第1回ビネクラ杯 ―ドラゴンへの道―

やること

前回は「ルートが見つからなかったら次を調べる」でスコア233が出ました。今回はさらなる工夫を追加して、スコア311以上(ドラゴンレベル)を目指しましょう

実行環境

WinPython3.6をおすすめしています。

WinPython - Browse /WinPython_3.6/3.6.7.0 at SourceForge.net
Portable Scientific Python 2/3 32/64bit Distribution for Windows

用意するもの

18-4のコードを実装し、18-5の修正を加えておいてください。これをさらに書き換えます。

考え方

発電機と装置には、遠いペアと近いペアがあります。例えば、次のようなシステムはマンハッタン距離が8あるので、これらをつなぐと途中の7点は使えなくなってしまいます。

できるだけたくさんのシステムを繋ぎたいので、7点も死んでしまうのはもったい気がします。一方、次のようなシステムは距離が近いので、つないでもほとんど”死に座標”が生じません。

ですから、マンハッタン距離が短いシステムから順につなぐのが効率的なのです。

遠いシステムはいろいろなつなぎ方ができますから、先に短いケーブルをつないでしまって、長いケーブルにはそれらを避けてもらおうということでもあります。

コードを修正する

前回のコードの「メイン処理」のfor文に入る前に処理を加えます。4000システムのマンハッタン距離を計算して(=manhattan_dist)、それが短い順のインデックス配列を取得します(=manhattan_short_index)。

for文ではこのインデックス順に探索を行います。その後は変更ありません。

#============================
# メイン処理(マンハッタン距離が短い順につなぐ、経路が見つからなかったら飛ばして次を探索する)
#============================

#通った場所(Falseで初期化)
barrier = np.zeros((20, 20, 20), dtype=bool)

#記録用の配列
score = 0
routes = []

#4000システム(発電機と装置の)のマンハッタン距離を求める
manhattan_dist = np.sum(np.abs(equipments - generators), axis=1)
print('manhattan_dist:\n{}'.format(manhattan_dist))

#マンハッタン距離の短い順に添え字を取得
manhattan_short_index = manhattan_dist.argsort()
print('manhattan_short_index:\n{}'.format(manhattan_short_index))

#一応、マンハッタン距離順に並び替えて表示してみる
print('manhattan_short:\n{}'.format(manhattan_dist[manhattan_short_index]))

for i in manhattan_short_index:
    print(i)
    
    #これからつなぐスタートやゴールが、すでに障害物となっていたら終わり
    if barrier[generators[i, 0], generators[i, 1], generators[i, 2]] == True:
        continue
    if barrier[equipments[i, 0], equipments[i, 1], equipments[i, 2]] == True:
        continue

    #ルートを見つける
    route = find_route(barrier, generators[i], equipments[i])
    
    #ルートが見つからなかったら終わり
    if route is None:
        continue
    else: #ルートが見つかったら、スコアを記録する
        score += 1
        routes.append(route)

    #通った場所を障害物とする
    for [x, y, z] in route:
        barrier[x, y, z] = True

#
print('score:\n{}'.format(score))
#print('routes:\n{}'.format(routes))
manhattan_dist:
[22  3 12 ... 25 20 15]
manhattan_short_index:
[ 585 1268 2398 ... 2456 2199 3985]
manhattan_short:
[ 1  1  1 ... 46 47 48]
585
1268
2398
(中略)
2456
2199
3985
score:
470

マンハッタン距離は、先頭から順に [22, 3, 12, … , 25, 20, 15] とバラつきがあることがわかりました。これが短い順になるような添字配列は [585, 1268, 2398, … , 2456, 2199, 3985] となりました。一応、添字の順にマンハッタン距離を表示してみると、距離1(発電機と装置が隣り合っている)が数個あり、一方で、距離48のシステムがあることも分かります。

結果、なんとスコア470が出ました。いや、え、いや(動揺)

ルートを可視化する

前回のshow_routes関数を用いて可視化します。

show_routes(routes)

キタ━━━(゚∀゚)━━━!!(2回目)

※前回よりも赤く見えますが、スコアが高いから赤いわけではありません。引数として渡されたroutesの順に、青から赤に色を変えながら表示しています。序盤に確定した短いルートが青で、終盤に確定した長いルートが赤で表示されるため、相対的に赤の量が多くなるためです。

まとめ

ちょっとした発想でスコアが233→470にまで向上しました。いろいろなアイデアを試しているとき、そこには夏休みの小学生がいます。あの頃のワクワク、高揚感。いくつになっても大きな子どもでありたい。

タイトルとURLをコピーしました