2013-08-11

ダイクストラの最短経路アルゴリズム

Coursera Python

courseraで課題になってたのでいろいろ参考にしながらpythonで実装した。

参考ページ
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Pseudocode
http://taichino.com/programming/1333

./dijkstra.py graph_file start end のようにオプションを渡す。
graphデータのファイルは、各行に、vertexと、隣接したvertex,lengthを記述したもの。

#!/usr/bin/env python

import sys
from altgraph import Graph

def read_graph(f):
    g = Graph.Graph()
    for l in file(f):
        l = l.rstrip().split()
        # read vertex
        v = int(l[0])
        l.pop(0)

        # read neighbor & length
        for i in l:
            i = i.split(',')
            g.add_edge(v, int(i[0]), int(i[1]))

    return g

def dijkstra(graph, start):
    dist = {}
    for v in graph.nodes:
        dist[v] = sys.maxint

    prev = {}
    for v in graph.nodes:
        prev[v] = None

    dist[start] = 0
    Q = graph.nodes.copy()

    while len(Q):
        # find vertex with smallest distance.
        min_dist = sys.maxint
        u = Q.keys()[0] # first vertex
        for v in Q:
            if dist[v] < min_dist:
                u = v
                min_dist = dist[v]

        del(Q[u])
        if dist[u] == sys.maxint:
            break

        # find neighbors
        neighbors = {}
        for e in graph.edges.values():
            if e[0] == u:
                neighbors[e[1]] = e[2]

        for v in neighbors:
            alt = dist[u] + neighbors[v]
            if alt < dist[v]:
                dist[v], prev[v] = alt, u
    return dist, prev

if __name__=='__main__':
    if len(sys.argv) > 2:
        graph_file = sys.argv[1]
        start = int(sys.argv[2])
        end = int(sys.argv[3])

        g = read_graph(graph_file)
        dis = dijkstra(g, start)
        print dis[0][end]

1->3への最短経路

$ ./dijkstra.py graph.txt 1 3
3

2013-07-03

HackerRank - Changing Bits

HackerRankのChanging Bitsを解いた。

AとB用にsize Nの配列を作り、setされるたびに指定indexのbitを更新する。
getのときにLSB側から愚直にA+Bを計算するとTime limit exceededになるのでA+Bの計算量を減らす工夫が必要。
ここでpythonからC++に変更。

getするindexのbitを決めるのはA[index]+B[index]だけでなく、下位bitからの繰り上がりもあるので、index部分からLSBに向かって繰り上がりがないかAとBを走査していく。A[i]とB[i]がともに１なら繰り上がりありで終了、ともに0ならなしで終了。
これでTLEは結構減るが、いくつかのテストデータはもう10%くらい処理時間を削る必要がある。

あるindex値xからLSB側に走査していき、y番目で繰り上がりあり・なしが確定して終了したとすると、
次に[x,y]内のindexがgetされた場合は、走査を省略して繰り上がりあり・なしを判断すれば計算量を減らせるので、
走査した結果をキャッシュしておくような仕組みを入れた。ただ、このキャッシュ内にsetされると、無効化したり範囲を狭くしないとまずいのでややこしい…
これでローカルだと4倍以上速くなったが、submitしたら結構ギリギリのAcceptだった。

出題者の想定するアルゴリズムになってない気がするが、効率的な解き方があるんだろうか？？
問題名でググるとStack Overflowとか海外のブログが引っかかるけど、斬新な解き方みたいな情報は見つからなかったし、途中であきらめてる人が多いっぽい。