ナノピコ教室の東海道五十三次をPythonで解いてみた（４）
前回の続きです。今回は最安運賃を計算する部分と結果出力の説明です。
https://joho-ka.mints.ne.jp/stopover01find関数
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の便利な点の１つだと思います。実際にはタプルというデータ型により行われているようです。
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京です。２回目でハイパーインフレについて触れましたが、単にパズル的な問題を解くためのプログラムなので、今回は仮の最小値として使うことにします。
45行目から50行目は、最安運賃を求めている部分になります。ここでは考え方を示します。
例えば小田原駅までの最安値を求めることを考えます。
- 大船駅→藤沢駅 ＋ 藤沢駅→小田原駅
- 大船駅→辻堂駅 ＋ 辻堂駅→小田原駅
・・・（途中省略）・・・・・ - 大船駅→鴨宮駅 ＋ 鴨宮駅→小田原駅
- 大船駅 （乗り継がない） →小田原駅
のいずれかの乗り継ぎがあります。この中から最安運賃になるものを見つければよいことになります。
２回以上乗り継ぐ場合がないという疑問があると思います。例えば鴨宮駅に行くまでに乗り継いだ方が安いとしましょう。その場合には、大船駅→鴨宮駅の運賃として乗り継いだ最安運賃を使えば、鴨宮駅より手前で乗り継いでいるので、乗り継ぎ回数が２回以上になります。乗り継ぐかどうかを毎回計算すると計算時間が無駄に多くなるので、鴨宮駅までの最安となる乗り継ぎをメモしておきます。
ここで、乗り継ぎなしの場合が他の場合と異なっています。そこで
- 大船駅→大船駅 ＋ 大船駅→小田原駅
ということにすれば、乗り継ぐ場合と同じ計算で扱うことができます。乗り継ぐか乗り継がないか場合分けするとプログラムが複雑になってしまいます。前回の初期化で大船駅から大船駅まで運賃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を１つ１つ付け合わせて運賃を返しています。念のために読み込んだデータの範囲外のときにはsys.maxsize（約922京）を返しています。
print_result関数
def print_result():
for station in best_route:
print(station)
best_routeから１駅ずつリストを出力しているだけです。もう少し作り込んだ方がよいですね。
以上でプログラムの説明は終わりです。アルゴリズムの核心部分を考えると、今回だけでよかったかもしれません。
次回は計算結果をお示しします。もう１回お付き合いください。