お知らせ

ただいま、シンタックスハイライターの設定を見直しております。
プログラムが見にくくなっているページがありますが、ご容赦ください。

ナノピコ教室の東海道五十三次をPythonで解いてみた(4)

プログラミング

東海道本線

前回の続きです。今回は最安運賃を計算する部分と結果出力の説明です。

ナノピコ教室の東海道五十三次をPythonで解いてみた(1)
ナノピコ教室の東海道五十三次をPythonで解いてみた(2)
ナノピコ教室の東海道五十三次をPythonで解いてみた(3)

find関数

def find():
    for station in stations:
        route ,lowest = find_route(station)
        normal = calc(math.ceil( round(float(station[2]) - start_distance) ))
        new_station = [ station[0] ,float(station[2]) ,lowest ,normal ,route ]
        best_route.append(new_station)

前回の20行目で、stations.pop(0)により、stationsには出発駅の大船駅以外の駅が残っています。

37行目のループにより、次の藤沢駅から順に岡崎駅までの駅について38〜41行目のことを処理します。

38行目は、駅のデータをfind_route関数に渡して、その駅までの最安になる乗り継ぎと最安運賃を戻り値として受け取り、routeとlowestで受け取っています。カンマを付けて書くと複数の戻り値の授受ができるということはPythonの便利な点の1つだと思います。実際にはタプルというデータ型により行われているようです。

39行目は、大船駅から乗り通した場合の運賃を計算してnomalに代入しています。

40行目は、計算結果をリストにまとめています。データの形式は前回のbest_routeの要素として示したものです。

41行目は、40行目でnew_stationでまとめた結果をbest_routeの要素に追加しています。このbest_routeは何回も同じ計算をしないで済むように使っています。

find_route関数

def find_route(station):
    lowest = sys.maxsize
    for best in best_route:
        distance = math.ceil(round( float(station[2]) - best[1] ))
        price = best[2] + calc(distance)
        if price < lowest:
            lowest = price
            route = copy.deepcopy(best[4])
    route.append(station[0])
    return route ,lowest

ようやくですが、アルゴリズムの核心部分です。

44行目は、仮の最安運賃をものすごく大きい数にしています。64ビット環境では2**63-1で約922京です。2回目でハイパーインフレについて触れましたが、単にパズル的な問題を解くためのプログラムなので、今回は仮の最小値として使うことにします。

45行目から50行目は、最安運賃を求めている部分になります。ここでは考え方を示します。

例えば小田原駅までの最安値を求めることを考えます。

  • 大船駅→藤沢駅 + 藤沢駅→小田原駅
  • 大船駅→辻堂駅 + 辻堂駅→小田原駅
    ・・・(途中省略)・・・・・
  • 大船駅→鴨宮駅 + 鴨宮駅→小田原駅
  • 大船駅 (乗り継がない) →小田原駅

のいずれかの乗り継ぎがあります。この中から最安運賃になるものを見つければよいことになります。

2回以上乗り継ぐ場合がないという疑問があると思います。例えば鴨宮駅に行くまでに乗り継いだ方が安いとしましょう。その場合には、大船駅→鴨宮駅の運賃として乗り継いだ最安運賃を使えば、鴨宮駅より手前で乗り継いでいるので、乗り継ぎ回数が2回以上になります。乗り継ぐかどうかを毎回計算すると計算時間が無駄に多くなるので、鴨宮駅までの最安となる乗り継ぎをメモしておきます。

ここで、乗り継ぎなしの場合が他の場合と異なっています。そこで

  • 大船駅→大船駅 + 大船駅→小田原駅

ということにすれば、乗り継ぐ場合と同じ計算で扱うことができます。乗り継ぐか乗り継がないか場合分けするとプログラムが複雑になってしまいます。前回の初期化で大船駅から大船駅まで運賃0円というダミーデータを用意したのは、ここでプログラムを簡略化するためです。

このように問題を分割してメモ化する方法を動的計画法といいます。

50行目でdeepcopyしているのは、浅いコピーでは51行目でappendしたときにコピー元のbest[4]にもappendされてしまうのを避けるためです。

calc関数

def calc(distance):
    for fare in fare_list:
        if distance <= float(fare[0]):
            return int(fare[1])
    return sys.maxsize

fare.csvから読み込んだデータと距離distanceを1つ1つ付け合わせて運賃を返しています。念のために読み込んだデータの範囲外のときにはsys.maxsize(約922京)を返しています。

print_result関数

def print_result():
    for station in best_route:
        print(station)

best_routeから1駅ずつリストを出力しているだけです。もう少し作り込んだ方がよいですね。

以上でプログラムの説明は終わりです。アルゴリズムの核心部分を考えると、今回だけでよかったかもしれません。

次回は計算結果をお示しします。もう1回お付き合いください。

この記事を書いた人
春日井 優

高校で情報科という教科を担当しています。以前は数学科も担当していました。(今でも数学科の教員免許状は有効です。)プログラムを覚えたのは、「ゲームセンターあらし」という漫画のキャラクターがBASICを解説する「こんにちはマイコン」を読んだことがきっかけでした。

Posted by kasugai