真面目なノート

こまめにその日の進捗などをメモしておく。

完璧主義者は完遂する

20160623

今日したこと

グラフ問題

Single Source Shortest Path | Aizu Online Judge

動的計画法以外も流石にせなばなるまいと思い、今日はグラフ問題にチャレンジした。
単純にダイクストラ法を用いて全てのノードについて最短経路長を求める問題である。
しばらく動的計画法の問題を多く解いていたので、なんとなくダイクストラ法は動的計画法じみていると思って調べてみたら、おもしろい記事があった。

kuuso1.hatenablog.com

ダイクストラ法自体の説明は、この記事を見ておけば良い。
あとは、ちょっと詰まった点について記録しておく。

import heapq
 
l = input().split()
V = int(l[0])
E = int(l[1])
r = int(l[2])
 
graph = [[0 if i==j else -1  for j in range(V)] for i in range(V)] # [[source, target, cost]]
for i in range(E):
    l = input().split()
    graph[int(l[0])][int(l[1])] = int(l[2])
 
heap = [(0,r)]
dist = [float("inf") for _ in range(V)]
visited = [False for _ in range(V)]
while heap:
    pop = heapq.heappop(heap)
    if dist[pop[1]] < pop[0]:
        continue
    dist[pop[1]] = pop[0]
    edges = [(w,i) for (i,w) in enumerate(graph[pop[1]]) if i != pop[1] and w >= 0 and not visited[i]]
    for (weight, target) in edges:
        heapq.heappush(heap, (pop[0]+weight, target))
 
for d in dist:
    if d == float("inf"):
        print("INF")
    else:
        print(d)

最初に書いたプログラムはこのようなものだ。アルゴリズム自体は正しいため、返される結果は正しい。
しかし、これは Memory Limit Exceeded で弾かれてしまう。
弾かれるテストケースは、ノードの数が非常に多い場合であった。
このプログラムにおいては、全体のグラフの情報を、二次元の配列として格納している。xがターゲットノード、yがソースノードとなる。例えば、テストケース 1 については、次のような配列が作られる。

[[0, 1, 4, -1],
[-1, 0, 2, 5]
[-1, -1, 0, 1]
[-1, -1, -1, -1]]

xからyへの辺が存在しない時は -1 を辺の重みにしている。また、自己ループの重みを 0 としているわけだが、これが非常にマズい。問題点は以下のとおり。

  • 問題の条件にある通り、ノード間の重みは 0 になりうる。
  • ノードの数が非常に多く、エッジが少ないような場合、不必要なメモリ -1 のために多く確保してしまう。

そんなこんなで、最終的にはこうなった。

import heapq
 
l = input().split()
V = int(l[0])
E = int(l[1])
r = int(l[2])
 
graph = [[] for _ in range(V)]
for i in range(E):
    l = input().split()
    graph[int(l[0])].append((int(l[2]),int(l[1])))
 
heap = [(0,r)]
dist = [float("inf") for _ in range(V)]
while heap:
    pop = heapq.heappop(heap)
    if dist[pop[1]] < pop[0]:
        continue
    dist[pop[1]] = pop[0]
    for (w,i) in graph[pop[1]]:
        if i!= pop[1] and w >= 0 and dist[i] == float("inf"):
            heapq.heappush(heap, (pop[0]+w, i))
 
for d in dist:
    if d == float("inf"):
        print("INF")
    else:
        print(d)

グラフ問題自体の勉強になったのは勿論のこと、メモリの使い方について意識を向けねばな、と反省させられた(´ . .̫ . `)

プログラミング言語の講義

A Proposal for Making Eiffel Type-safe の論文を読み始めた。
これのために、しばらくはEiffelの基本的なシステムをちょっと調べないと行けないかな、と思う。