Problem 82
下の5×5の行列の左の列の要素のどこかから出発して右の列のマスのどこかに到着して、進む方向は上下右の経路で和が最小のものは、下に赤と太字で示される。その和は994である。
与えられた80×80の行列で左の列から右の列への経路の最小和を求めよ。
131 673 234 103 18
201 96 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 37 331
http://projecteuler.net/index.php?section=problems&id=82
左から順にそのマスまでの経路の最小和を計算していきます。例えば上の(2, 2)の96と書かれたマスなら、左の列のマスまでの最小和が分かっているとして、そこへ至る経路は、
131 -> 673 -> 96
201 -> 96
630 -> 803 -> 96
537 -> 699 -> 803 -> 96
805 -> 732 -> 699 -> 803 -> 96
の5つがあります。このうちの最小和を取ればよいです（Code1）。
上の方法は行列の辺の長さをNとして各マスまで経路の最小和を求めるのにO(N2)の計算量が要ります。すなわち全体でO(N4)の計算量が要ることになります。
経路の和を都度計算するのではなく、徐々に計算していきます。5行目の最小経路を計算するのに、まず4行目の計算をします。732+699=1431。これに537を足したのが537からの経路の和です。次に1431+803=2234に630を足したのが次の経路の和です。こうするとO(N3)になります（Code2）。
列ごとに考えるのはやめましょう。現在最前線のマス、すなわち右に最小和が計算されていないマスのうち、和が最小のマスを考えます。この右のマスはこのマスから直接来る経路が最も和が小さいです。その上下のマスも同じです。ただし、まだそのマスの最小和が計算されていないことが前提です（Code3）。この考え方で、Problem 83も解けます。このコード自体はスピードを追求していません。
# Code1 def next(b, c): def min_path(k): def sum_path(l): if l <= k: return sum(c[l:k+1]) + b[l] else: return sum(c[k:l+1]) + b[l] return reduce(min, map(sum_path, range(N))) return map(min_path, range(N)) file = open("matrix.txt") a = map(lambda s: map(int, s.split(',')), file.readlines()) file.close() N = len(a) print min(reduce(next, ([ e[c] for e in a ] for c in range(N))))
# Code2 def next(b, c): def min_path(k): min_s = b[k] + c[k] sum_column = c[k] for l in range(k - 1, -1, -1): sum_column += c[l] min_s = min(min_s, sum_column + b[l]) sum_column = c[k] for l in range(k + 1, len(c)): sum_column += c[l] min_s = min(min_s, sum_column + b[l]) return min_s return map(min_path, range(N)) file = open("matrix.txt") a = map(lambda s: map(int, s.split(',')), file.readlines()) file.close() N = len(a) print min(reduce(next, ([ e[c] for e in a ] for c in range(N))))
# Code3 def gen_neighbor(pt0): x, y = pt0 if x < N - 1: yield x + 1, y if y > 0: yield x, y - 1 if y < N - 1: yield x, y + 1 def gen_not_arrived_neighbor(pt0): for pt in filter(lambda pt: pt not in exist, gen_neighbor(pt0)): yield pt def insert(queue, s): pt, n = s for k in xrange(len(queue) - 1, -1, -1): if n > queue[k][1]: queue.insert(k + 1, s) return queue.insert(0, s) def gen_min_path(s): pt0, sum_path = s for pt in gen_not_arrived_neighbor(pt0): s = sum_path + a[pt[1]][pt[0]] insert(queue, (pt, s)) exist.add(pt) yield pt, s def solve(): while True: for pt, min_path in gen_min_path(queue.pop(0)): if pt[0] == N - 1: return min_path file = open("matrix.txt") a = map(lambda s: map(int, s.split(',')), file.readlines()) file.close() N = len(a) exist = set([ (0, y) for y in range(N) ]) queue = [ ((0, y), a[y][0]) for y in range(N) ] queue.sort(key = lambda t: t[1]) print solve()
