最小全域木問題について（プリム法）
class MinimumSpanningTree(object): def __init__(self, v): self.v = v self.e = 0 self.mincost = [float("inf") for i in range(v)] self.cost = [[float("inf") for i in range(v)] for i in range(v)] self.used = [0 for i in range(v)] def append(self, _from, _to, _cost): self.cost[_from][_to] = _cost self.e += 1 def prim(self): res = 0 self.mincost = [float("inf") for i in range(v)] self.used = [0 for i in range(v)] self.mincost[0] = 0 while 1: v = -1 for u in range(self.v): if not self.used[u] and (v == -1 or self.mincost[u] < self.mincost[v]): v = u if v == -1: break self.used[v] = 1 res += self.mincost[v] for u in range(self.v): self.mincost[u] = min(self.mincost[u], self.cost[v][u]) return res def append_test(self): self.append(0, 2, 1) self.append(1, 2, 2) self.append(1, 4, 10) self.append(2, 0, 1) self.append(2, 1, 2) self.append(2, 3, 3) self.append(2, 5, 7) self.append(3, 2, 3) self.append(3, 5, 1) self.append(3, 6, 5) self.append(4, 1, 10) self.append(4, 5, 5) self.append(5, 2, 7) self.append(5, 3, 1) self.append(5, 4, 4) self.append(5, 6, 8) self.append(6, 3, 5) self.append(6, 5, 8)
pip install で詰まった時の話
python2.6 の pip install で詰まった時の話。 HTTP Error 403: SSL is required
http://pypi.python.org/simple/ で pip install しようとしている場合、
以下で指定すると、うまくいく。
$ pip install xxxx -i https://pypi.python.org/simple/ $ pip install git+https://github.com/<user>/<project>
プロセス監視する時の /service 配下の設定とか
daemontoolsをインストールして、ごちょごちょ設定行う。
スティッキービットを立てるとか言うらしい。
$ chmod +t test_job
大きく分けると...らしい。
- svscan サービスディレクトリの監視
- supervise プロセスの監視および制御
- multilog ロギング
sudo -iを使用した場合
sudo -iで移ったユーザの環境変数まで読んでくれるらしい
パスワード: [root@localhost ~]# sudo -u vagrant -i /home/vagrant/list.sh /var/tmp
単一始点最短距離問題をPythonで解答
負の閉路が存在しない場合、更新はいずれ止まるため、この更新方法で対応できるらしい。
## ベルマンフォード法 class BellmanFord(object): def __init__(self, v): self.e = 0 self.d = [float("inf") for i in range(v)] self.edge = [] def append(self, _from, _to, _cost): self.edge.append({ 'from': _from, 'to': _to, 'cost': _cost }) self.e = len(self.edge) def shortest_path(self, s): self.d[s] = 0 while 1: update = True for i in range(self.e): e = self.edge[i] if self.d[e['from']] != float("inf") and self.d[e['to']] > self.d[e['from']] + e['cost']: self.d[e['to']] = self.d[e['from']] + e['cost'] update = True if update: break ## ダイクストラ法 class Dijkstra(object): def __init__(self, v): self.v = v self.e = 0 self.d = [float("inf") for i in range(v)] self.used = [0 for i in range(v)] self.cost = [[float("inf") for i in range(v)] for i in range(v)] def append(self, _from, _to, _cost): self.cost[_from][_to] = _cost self.e += 1 def shortest_path(self, s): self.d[s] = 0 while 1: v = -1 for u in range(self.v): if not self.used[u] and (v == -1 or (self.d[u] < self.d[v])): v = u if (v == -1): break self.used[v] = 1 for u in range(self.v): self.d[u] = min(self.d[u], self.d[v] + self.cost[v][u])
b = BellmanFord(7) b.append(0, 1, 2) b.append(1, 0, 2) b.append(0, 2, 5) b.append(2, 0, 5) b.append(1, 2, 4) b.append(2, 1, 4) b.append(1, 3, 6) b.append(3, 1, 6) b.append(2, 3, 2) b.append(3, 2, 2) b.append(1, 4, 10) b.append(4, 1, 10) b.append(3, 5, 1) b.append(5, 3, 1) b.append(4, 5, 3) b.append(5, 4, 3) b.append(4, 6, 5) b.append(6, 4, 5) b.append(5, 6, 9) b.append(6, 5, 9) b.shortest_path(0) In [40]: b.d Out[40]: [0, 2, 5, 7, 11, 8, 16] In [41]: b.d[6] Out[41]: 16
