Movatterモバイル変換

[0]ホーム
URL:

最短路問題

最短路問題とその変形

準備

importnetworkxasnxfromnetworkximportDiGraphimportmatplotlib.pyplotaspltfromnumpyimportarrayimportnumpyasnpfromheapqimportheappush,heappopfromitertoolsimportcountimportrequestsimportpprintfromheapdictimportheapdictfromcspyimportBiDirectional

最短路問題

ここで考える最短路問題は多くの応用をもつ基本的なネットワーク最適化問題である．

（1対1の）最短路問題（shortest path problem）

$n$個の点から構成される点集合 $V$，$m$ 本の枝から構成される枝集合 $E$，$V$ および $E$ からなるグラフ $G=(V,E)$，枝上に定義される非負の費用関数$c: E \rightarrow \mathbf{R}_+$，始点 $s \in V$ および終点 $t \in V$ が与えられたとき，始点 $s$ から終点 $t$ までのパスで，パスに含まれる枝の費用の合計が最小のものを求めよ．

最短路問題の目的である「パスに含まれる枝の費用の合計が最小のもの」を最短路（shortest path）とよぶ．

枝 $e$ がパスに含まれるとき $1$ になる変数を使うと，最短路問題は以下のように定式化できる．

$$\begin{array}{c l} minimize & \sum_{e \in E} c_{e} x_{e} \\s.t. & \sum_{w: wv \in E} x_{wv} - \sum_{w: vw \in E} x_{vw} = \left\{ \begin{array}{c l} -1 & v=s \\ 0 & \forall v \in V \setminus \{s,t\} \\ 1 & v=t \end{array} \right. \\ & x_e \in \{ 0,1 \} \ \ \ \forall e \in E \end{array}$$

$0$-$1$変数 $x$ を $0$ 以上に緩和した線形最適化を解くことによって，整数解が得られることが知られている．

実用的なアルゴリズムとして，Dijkstra法（Dijkstra's method）がある。Dijkstra法は，最短路問題に対する最も有名なアルゴリズムであり，ほとんどのテキストでは最初にとりあげられるアルゴリズムである．

networkXには様々な最短路アルゴリズムのための関数が準備されているが，単一始点から他のすべての点に対する最短路を求めるものとしては，dijkstra_predecessor_and_distanceが使いやすい．この関数の引数と返値は，以下の通りである．

引数：

  • source: 始点を表すラベル
  • cutoff: この値を超える費用をもつパスは探索しない（カットオフする）
  • weight: 枝(u,v)の費用がG.edges[u,v][weight]に格納されていると仮定する

返値： 以下の2つの辞書のタプル

  • pred: 点のラベルをキーとし，先行点のリストを値とした辞書
  • distance: 点のラベルをキーとし，その点までの最短路の費用を値とした辞書

networkXを使うと，有向・無向の両方のグラフに対する最短路問題を簡単に解くことができる．例として，小さな問題例（有向グラフを仮定）で求解してみよう．

D=nx.DiGraph()D.add_weighted_edges_from([("s",1,10),("s",2,5),(2,1,3),(1,"t",4),(2,3,2),(3,"t",6)])pred,distance=nx.dijkstra_predecessor_and_distance(D,source="s")print(pred)print(distance)
{'s': [], 1: [2], 2: ['s'], 3: [2], 't': [1]}{'s': 0, 2: 5, 3: 7, 1: 8, 't': 12}
edge_labels={}pos=nx.kamada_kawai_layout(D)for(i,j)inD.edges():edge_labels[i,j]=f"{D[i][j]['weight']}"nx.draw_networkx_edge_labels(D,pos=pos,edge_labels=edge_labels)nx.draw(D,node_size=300,pos=pos,node_color="y",edge_color="g",width=3,with_labels=True)plt.show()

始点と終点が決まっている場合には， A*探索を使うと（多少は）高速になると言われているが，問題例によっては遅くなる場合もある．

ランダムな格子グラフで試してみる． $m \times n$ の格子グラフの各枝に， $[lb,ub]$ の一様整数乱数の費用を設定する．端にある点 $(0,0)$ から $(m-1,n-1)$ までの最短路を，色々なアルゴリズムで求めてみよう．

m,n=1000,1000lb,ub=1,300G=nx.grid_2d_graph(m,n)for(i,j)inG.edges():G[i][j]["weight"]=random.randint(lb,ub)
%%timepred,distance=nx.dijkstra_predecessor_and_distance(G,source=(0,0))
CPU times: user 7.6 s, sys: 78 ms, total: 7.67 sWall time: 7.67 s

標準的なdijkstra_predecessor_and_distanceを使うと， $1000 \times 1000$ の問題例が8秒程度で解ける． 点$(m-1,n-1)$ までの最小費用は辞書distanceに格納されている．また，最短路自身は，パスの前の点を保持する辞書predに格納されているので，以下のように復元できる．$1000 \times 1000$ は大きすぎるので， $10 \times 10$ で計算してみる．

m,n=10,10lb,ub=1,300G=nx.grid_2d_graph(m,n)for(i,j)inG.edges():G[i][j]["weight"]=random.randint(lb,ub)pred,distance=nx.dijkstra_predecessor_and_distance(G,source=(0,0))print("minimum cost=",distance[m-1,n-1])i=(m-1,n-1)path=[]whilei!=(0,0):path.append(i)i=pred[i][0]path.reverse()print("optimal path =",path)
minimum cost= 1440optimal path = [(1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 6), (8, 6), (9, 6), (9, 7), (9, 8), (9, 9)]

始点と終点が決まっている場合には，$A^{*}$探索が使える．この場合には，あまり高速化しない．

%%timepath=nx.astar_path(G,(0,0),(m-1,n-1))
CPU times: user 440 µs, sys: 1 µs, total: 441 µsWall time: 443 µs

始点と終点の両方から探索するという関数もあったので試してみる． 高速化どころか，5倍以上の計算時間がかかるので，これは使うべきではない．

%%timelength,path=nx.bidirectional_dijkstra(G,(0,0),(m-1,n-1))
CPU times: user 294 µs, sys: 2 µs, total: 296 µsWall time: 300 µs

1対全の最短路問題

Dijkstra法は，1つの始点から他のすべての点に対する最短路を一度に求めることができる． これは，1対全の最短路問題と呼ばれる．

$n$個の点から構成される点集合 $V$，$m$ 本の枝から構成される枝集合 $E$，$V$ および $E$ からなる有向グラフ $G=(V,E)$，枝上に定義される非負の費用関数$c: E \rightarrow \mathbf{R}_+$，始点 $s \in V$ が与えられたとき，始点 $s$ から他のすべての点までの最小費用のパスを求めよ．

dijkstra_predecessor_and_distanceを用いて得られるパスの前の点を保持する辞書predは，すべての最短路の情報を保持している．直前の点 $pred[v]$ から $v$ に有向枝を張ることによって，始点 $s$ を根にした有向木が得られる．この有向木を最短路木（shortest path tree）とよぶ．

$10 \times 10$ の格子グラフの最短路木（左下の点が始点）を描画してみる．

D=nx.DiGraph()foriinpred:iflen(pred[i])>=1:D.add_edge(pred[i][0],i)pos={(i,j):(i,j)for(i,j)inG.nodes()}plt.figure()nx.draw(D,pos=pos,width=2,edge_color="b",node_size=10)plt.show()

枝の費用が負のものがある場合

Dijkstra法は効率的な解法であるが，枝の費用が負の場合には使えない．しかも，負の閉路があると（そこをくるくる回ると永遠に儲かるので）アルゴリズムが破綻する． そのような場合にはBellman-Ford法を使う．この解法は，動的最適化の一種であり，以下のBellman等式（Bellman's equation）に基づく．

$$\begin{array}{lll} y_w = & \min_{v: vw \in E} \{ y_v +c_{vw} \} & \forall v \in V \setminus \{s\} \\ y_s = & 0 & \end{array}$$

使用する関数はbellman_ford_predecessor_and_distanceである．どこかに負の閉路（そこを巡回すると費用はマイナス無限大に発散する）があると，NetworkXUnbounded例外を発生して終了する．引数としてheuristicが追加されており，それをTrueに設定すると，負の閉路がある場合に高速に計算できる．goldberg_radzik関数も同様の手法であるが，より高速である．

$100 \times 100$ の有向格子グラフを生成し，枝の費用を $[-100,100]$ の一様整数乱数として解いてみる．（有向グラフにしたのは，無向グラフだと負の費用をもつ枝が存在するだけで，負の閉路になるためである．）

m,n=10,10lb,ub=-100,100G=nx.grid_2d_graph(m,n)D=G.to_directed()for(i,j)inD.edges():D[i][j]["weight"]=random.randint(lb,ub)
%%timepred,distance={},{}try:pred,distance=nx.bellman_ford_predecessor_and_distance(D,source=(0,0),heuristic=False)exceptnx.NetworkXUnboundedase:print(e)
Negative cost cycle detected.CPU times: user 1.15 ms, sys: 66 µs, total: 1.21 msWall time: 1.16 ms
%%timetry:pred,distance=nx.goldberg_radzik(D,source=(0,0))exceptnx.NetworkXUnboundedase:print(e)
Negative cost cycle detected.CPU times: user 297 µs, sys: 51 µs, total: 348 µsWall time: 298 µs

全対全の最短路

すべての点間の最短路を出すための専用アルゴリズムもある．

  • Johnsonのアルゴリズム: グラフ $G=(V,E)$ に対して， $𝑂(|V|^2 \log |V| + |V| \cdot |E|)$ 時間

  • Floyd-Warshallアルゴリズム： $O(|V|^3)$ 時間

これらの方法は，両者とも非常に遅いので，実務には使うべきではない．１対全の最短路をすべての点に対して求める方が，まだ速い．以下で述べる前処理を用いた方法も有効である．

m,n=50,50lb,ub=1,100G=nx.grid_2d_graph(m,n)for(i,j)inG.edges():G[i][j]["weight"]=random.randint(lb,ub)
%%timetry:paths=nx.johnson(G)exceptnx.NetworkXUnboundedase:print(e)
CPU times: user 41.8 s, sys: 671 ms, total: 42.5 sWall time: 43.2 s
%%timenx.floyd_warshall_numpy(G)
CPU times: user 54.9 s, sys: 18.9 s, total: 1min 13sWall time: 1min 14s
array([[0.000e+00, 3.800e+01, 6.200e+01, ..., 2.316e+03, 2.285e+03,        2.284e+03],       [3.800e+01, 0.000e+00, 2.400e+01, ..., 2.336e+03, 2.305e+03,        2.304e+03],       [6.200e+01, 2.400e+01, 0.000e+00, ..., 2.343e+03, 2.312e+03,        2.311e+03],       ...,       [2.316e+03, 2.336e+03, 2.343e+03, ..., 0.000e+00, 3.100e+01,        3.200e+01],       [2.285e+03, 2.305e+03, 2.312e+03, ..., 3.100e+01, 0.000e+00,        1.000e+00],       [2.284e+03, 2.304e+03, 2.311e+03, ..., 3.200e+01, 1.000e+00,        0.000e+00]])

道路ネットワークの最短路と前処理による高速化

実際の道路ネットワークでの最短路の計算に，通常のDijkstra法を使うことは推奨できない． 遠い2点間の最短路の計算には，結構な時間がかかるからだ．

実際には適当な前処理（これには時間がかかる）をしておき，実際の始点と終点が与えられたときには，前処理の情報を用いて超高速に最短路を計算するというテクニックが使われる．

オープンソースの地図であるOpenStreetMapに，Highway Hierarchyという前処理法を適用したプログラムとしてOSRMhttp://project-osrm.org/ がある．

Highway Hierarchyにおける前処理を簡単に解説する．

まず高速ネットワークの階層の概念を導入する．ここで言う高速とは，有料道路のことではなく，遠くの地点に行くときに用いられる疎なネットワークのことである．

始点 $s$ から他の全点に対する最短路をDijkstra法によって求める際，優先キューから出される順番をDijkstraランクと定義する．点 $v$ のDijkstraランクを $r_s(v)$ と記す．始点 $s$ のDijkstraランク $r_s(s)$ は $0$ であり， $s$ に最も近い点 $v$ のDijkstraランク $r_s(v)$ は $1$ である．

$H$ 番目の（言い換えれば $H=r_s(v)$ を満たす） 点 $v$ への距離以下の点集合を $s$ の $H$ 近傍とよび， $N_H(s)$ と記す．パラメータ $H$ を与えたとき，第1階層の高速ネットワーク $G_1=(V_1,E_1)$ は， オリジナルのグラフ $G=(V,E)$ から以下のように作成する．ある始点 $s$ からある終点 $t$ への最短路に含まれる枝 $(v,w)$ において，$w \not\in N_H(s)$ かつ $v \not\in N_H(t)$ を満たすものをすべて合わせた集合を $E_1$ とする．$E_1$ は遠くの地点間に行くときに使用する枝の集合であり，高速遠路と考えれば良い．

次に，$E_1$ から構成されるグラフ $G_1=(V_1,E_1)$ において，点の次数が $2$ 以上のもの（インターチェンジと考えれば良い）を抽出し，さらに次数 $2$ の点を除いて，その点に隣接する2つの点の間に枝をはる操作を繰り返すことによってを縮約高速ネットワーク $G'_1$ を生成する．上の操作を第2，第3階層と順に繰り返すことによって，多階層の高速ネットワークを得る．

このネットワークを使って，始点 $s$ から終点 $t$ までの最短路を計算する際には，始点 $s$ と終点 $t$ からの両方向探索を行う．また，通常のDijkstra法で上の階層に移動できるときには， 必ず上の階層を優先して探索することによって，高速に最短路を求めることができる．

この手法を使うと，日本全国の地図で（メモリが十分にあれば）数時間で前処理ができ，地点間の最短路が高速に計算できるようになる．

例として，東京海洋大学から東京駅までの移動距離と移動時間を求めてみる．

requestsでOSRMのサーバーにクエリを渡すと，結果が返される． responseをJSON化すると， 3675メートル，324秒（車で）かかることが分かる．

response=requests.get("http://router.project-osrm.org/route/v1/driving/139.792429,35.667864;139.768525,35.681010")pprint.pprint(response.json())
{'code': 'Ok', 'routes': [{'distance': 3708.6,             'duration': 344.1,             'geometry': 'ujuxEaeftY{DxEe@k@}@lAiNeRkC_CgGhQaM`RsC`R{Rxa@wIdZlSlKyKt]cAk@e@x@',             'legs': [{'distance': 3708.6,                       'duration': 344.1,                       'steps': [],                       'summary': '',                       'weight': 344.1}],             'weight': 344.1,             'weight_name': 'routability'}], 'waypoints': [{'distance': 12.447899,                'hint': 'g6oLgZiqC4G2AAAAFAAAAAAAAADRAAAAJbyYQjyT_UAAAAAA8ratQrYAAAAUAAAAAAAAANEAAAAjVwAAyQ9VCEs_IAItEFUImD8gAgAAjwgjun_8',                'location': [139.792329, 35.667787],                'name': ''},               {'distance': 32.443406,                'hint': '1tNch____38AAAAAFwAAACUAAAAGAAAAAAAAAIUgGUHOOXJBTx0mQAAAAAAXAAAAJQAAAAYAAAAjVwAAF7RUCIByIALNslQI8nIgAgIAzwEjun_8',                'location': [139.768855, 35.680896],                'name': 'タクシー・一般車降車場(一般車用)'}]}

単なる最短路ではなく，与えた複数の座標間の全対全の最短路長と移動時間のテーブルも（高速に）計算できる．

response=requests.get("http://router.project-osrm.org/table/v1/driving/13.388860,52.517037;13.397634,52.529407;13.428555,52.523219"+"?annotations=distance,duration")pprint.pprint(response.json())
{'code': 'Ok', 'destinations': [{'distance': 4.231666,                   'hint': '8wIKgOftmIUXAAAABQAAAAAAAAAgAAAAfXRPQdLNK0AAAAAAsPePQQsAAAADAAAAAAAAABAAAABI7QAA_kvMAKlYIQM8TMwArVghAwAA7wpmVo2F',                   'location': [13.388798, 52.517033],                   'name': 'Friedrichstraße'},                  {'distance': 2.795167,                   'hint': 'v-rcgZkeiIcGAAAACgAAAAAAAAB3AAAA5JSNQJ0fwkAAAAAAGjmEQgYAAAAKAAAAAAAAAHcAAABI7QAAfm7MABiJIQOCbswA_4ghAwAAXwVmVo2F',                   'location': [13.39763, 52.529432],                   'name': 'Torstraße'},                  {'distance': 2.226595,                   'hint': 'ZjAYgP___38fAAAAUQAAACYAAAAeAAAAsowKQkpQX0Lf6yZCvsQGQh8AAABRAAAAJgAAAB4AAABI7QAASufMAOdwIQNL58wA03AhAwMAvxBmVo2F',                   'location': [13.428554, 52.523239],                   'name': 'Platz der Vereinten Nationen'}], 'distances': [[0, 1886.7, 3802.9], [1903, 0, 2845.9], [3279.9, 2292.9, 0]], 'durations': [[0, 255.4, 386.1], [262.3, 0, 365.5], [354.4, 301.3, 0]], 'sources': [{'distance': 4.231666,              'hint': '8wIKgOftmIUXAAAABQAAAAAAAAAgAAAAfXRPQdLNK0AAAAAAsPePQQsAAAADAAAAAAAAABAAAABI7QAA_kvMAKlYIQM8TMwArVghAwAA7wpmVo2F',              'location': [13.388798, 52.517033],              'name': 'Friedrichstraße'},             {'distance': 2.795167,              'hint': 'v-rcgZkeiIcGAAAACgAAAAAAAAB3AAAA5JSNQJ0fwkAAAAAAGjmEQgYAAAAKAAAAAAAAAHcAAABI7QAAfm7MABiJIQOCbswA_4ghAwAAXwVmVo2F',              'location': [13.39763, 52.529432],              'name': 'Torstraße'},             {'distance': 2.226595,              'hint': 'ZjAYgP___38fAAAAUQAAACYAAAAeAAAAsowKQkpQX0Lf6yZCvsQGQh8AAABRAAAAJgAAAB4AAABI7QAASufMAOdwIQNL58wA03AhAwMAvxBmVo2F',              'location': [13.428554, 52.523239],              'name': 'Platz der Vereinten Nationen'}]}

ベンチマーク問題例の読み込みとDial法

最短路問題のベンチマーク問題例（道路ネットワーク）が，以下のサイトで入手できる．

http://users.diag.uniroma1.it/challenge9/download.shtml

以下の関数を用いてデータを読み込んで，道路ネットワークに強いDial法を実装して解いてみる．

defReadDimacs(filename):"""Read the data from DIMACS shortest path format    that can be downloaded from DIMACS site"""f=open(filename+".co","r")f2=open(filename+".gr","r")# read data from fileline=f.readline()x_cord=[]y_cord=[]G=nx.Graph()G.position={}whileline.find("v 1")==-1:line=f.readline()(dum,i,x,y)=line.split()x_cord.append(float(x))y_cord.append(float(y))while1:line=f.readline()ifline.find("v")==0:(dum,i,x,y)=line.split()x_cord.append(float(x))y_cord.append(float(y))else:break# edge infoedge_info=[]line=f2.readline()foriinrange(6):line=f2.readline()while1:line=f2.readline()ifline.find("a")==0:(dum,i,j,length)=line.split()edge_info.append((int(i)-1,int(j)-1,int(length)))else:breakminx=float(min(x_cord))maxx=float(max(x_cord))xwidth=maxx-minx+1miny=float(min(y_cord))maxy=float(max(y_cord))ywidth=maxy-miny+1# add nodes after scaling coordinatesn=len(x_cord)foriinrange(n):G.add_node(i)x=(x_cord[i]-minx)/xwidthy=(y_cord[i]-miny)/ywidthG.position[i]=(x,y)print("number of nodes=",n)# add edgesm=len(edge_info)C=0for(i,j,length)inedge_info:G.add_edge(i,j,weight=length)ifC<length:C=lengthC+=1print("number of edges=",m)f.close()f2.close()returnG,n,m,C
defDialSub(n,G,settled,reached,dist,prev,C,source,sink):"""Dial method subroutine"""circular=[[-1]foriinrange(C)]# -1 represents the list is emptycircular[0].append(source)reached[source]=1prev[source]=-1current=0while1:first=currentwhile1:v=circular[current][-1]# v is the node with minimum potentialifv>=0:break# the current list is empty, so we increment itcurrent+=1current=current%Cifcurrent==first:# the circular list is empty, so we quitv=-1breakifv==-1:# the circular list is empty, so we quitbreakcircular[current].pop()settled[v]=1ifv==sink:breakforwinG.neighbors(v):# scan operationifsettled[w]==0:temp=dist[v]+G[v][w]["weight"]ifreached[w]==0:# w is not in the circular listreached[w]=1dist[w]=tempprev[w]=vcircular[temp%C].append(w)else:# w is in the circular listiftemp<dist[w]:circular[dist[w]%C].remove(w)circular[temp%C].append(w)dist[w]=tempprev[w]=v
filename="USA-road-d.NY"G,n,m,C=ReadDimacs(filename)print("number of nodes in the largest connected componet=",n,"max length+1=",C)source=0sink=50000# if sink =-1 then find all shortest paths from source to other nodessettled=np.zeros(n,np.int0)# =1 if node is settled (or has an eternal label or is scanned)reached=np.zeros(n,np.int0)# =1 if node is heap or list (or has a finite potential)dist=np.zeros(n,np.int0)prev=np.zeros(n,np.int0)settled=[0foriinrange(n)]reached=[0foriinrange(n)]dist=[0foriinrange(n)]prev=[0foriinrange(n)]
number of nodes= 264346number of edges= 733846number of nodes in the largest connected componet= 264346 max length+1= 36947
%%timeDialSub(n,G,settled,reached,dist,prev,C,source,sink)
CPU times: user 736 ms, sys: 4.54 ms, total: 740 msWall time: 739 ms
%%timelength=nx.dijkstra_path_length(G,source,sink)dist[50000],length
CPU times: user 550 ms, sys: 9.18 ms, total: 559 msWall time: 558 ms
(801036, 801036)

networkXのパス長だけを算出する関数 dijkstra_path_lengthを用いた方が多少速い．以下で，結果を描画する．

path=[sink]w=sinkwhile1:v=prev[w]path.append(v)ifv==source:breakw=vpath.reverse()print("Path Length=",dist[sink])print("Optimal Path",path)G.clear()nx.draw(G,G.position,node_size=1000/n,with_labels=None,width=1,node_color="b",edge_color="g",)nx.add_path(G,path)nx.draw(G,G.position,node_size=1000/n,with_labels=None,width=3,node_color="b",edge_color="r",)
Path Length= 801036Optimal Path [0, 1362, 1357, 1356, 1355, 1275, 1272, 1276, 1268, 1266, 1267, 1283, 1282, 1281, 1254, 1252, 1259, 1258, 1248, 1245, 962, 963, 961, 1001, 951, 999, 997, 993, 994, 995, 986, 987, 978, 979, 968, 976, 988, 989, 990, 2464, 2465, 2383, 2381, 2384, 2378, 2379, 2444, 2443, 2404, 2405, 2397, 2394, 2396, 2141, 2142, 2143, 2138, 2130, 2129, 2128, 2086, 2080, 2072, 2074, 2163, 2162, 2161, 2158, 2157, 2159, 70, 60, 59, 1850, 1846, 1845, 1823, 1796, 1786, 1774, 1760, 5525, 5513, 5509, 5506, 5483, 5486, 5485, 5628, 5611, 5610, 4146, 5615, 5595, 5591, 5580, 5578, 5577, 5537, 5536, 5535, 260610, 260609, 260603, 260604, 260606, 260600, 257181, 257184, 257178, 257225, 257223, 257212, 257210, 257211, 257190, 257188, 257189, 256720, 256721, 256722, 256719, 256739, 256730, 256729, 256731, 256726, 256698, 256697, 256699, 256701, 256923, 256918, 256912, 256914, 256806, 256807, 256811, 256781, 256783, 256776, 256773, 256483, 256484, 256537, 259077, 256546, 256545, 256513, 256523, 256521, 256514, 256504, 256502, 256500, 256371, 256374, 256381, 256382, 256378, 256326, 256321, 256324, 256306, 256309, 256302, 256303, 256297, 257350, 255930, 255927, 255928, 255924, 255911, 255913, 255912, 255915, 255864, 255917, 255867, 255869, 255868, 255872, 255871, 255846, 255751, 255752, 255747, 255739, 255740, 255741, 255764, 255763, 255766, 254745, 254280, 254277, 261437, 254279, 254278, 254268, 254267, 254519, 254515, 254359, 254358, 254362, 254336, 254390, 253215, 253210, 253208, 253201, 253203, 253202, 253222, 253223, 253180, 253181, 253184, 253175, 253732, 253729, 253634, 253635, 253652, 253641, 253640, 253638, 253612, 253611, 253615, 253614, 253599, 253597, 253506, 253504, 253544, 253541, 253539, 253538, 253530, 253527, 253528, 253516, 253523, 253519, 253518, 253520, 253380, 253379, 253378, 134102, 134100, 134099, 134103, 134087, 134085, 134083, 134081, 134078, 134076, 134067, 133907, 139605, 133910, 133904, 133902, 133253, 133252, 133886, 133891, 133856, 134003, 134002, 134000, 133987, 133986, 133984, 133981, 133966, 133967, 133970, 133975, 133971, 133968, 133964, 133962, 133959, 133940, 133941, 133936, 133947, 133945, 133944, 133605, 133597, 133588, 133602, 133587, 133585, 133552, 133545, 133544, 133525, 133527, 133033, 133032, 132799, 133523, 133521, 133518, 133522, 134614, 134613, 134608, 134610, 134609, 134616, 134615, 134562, 134561, 134558, 134556, 134548, 134552, 134553, 134551, 134550, 134488, 134489, 134502, 134501, 134500, 134495, 134494, 134404, 134400, 134383, 134380, 134388, 134385, 134384, 134341, 134340, 134316, 134319, 134318, 134304, 134252, 134251, 134250, 134242, 134243, 134239, 134216, 134214, 134215, 189571, 189592, 189561, 189560, 189562, 189554, 189553, 187904, 187903, 189519, 189521, 189525, 189524, 187232, 187233, 187234, 187251, 187256, 187257, 187246, 187222, 187224, 187215, 187193, 187192, 187194, 190807, 190789, 187636, 187204, 187205, 34160, 25151, 24027, 25148, 25146, 25089, 25069, 25063, 25061, 24900, 24896, 24894, 23790, 23767, 23764, 23729, 23728, 23724, 23722, 23720, 23707, 23708, 23706, 23702, 23643, 23640, 23638, 23633, 23631, 23621, 23620, 23615, 23613, 23581, 23579, 23556, 23553, 23547, 23545, 23544, 23515, 23514, 23513, 23511, 23512, 28490, 28489, 28485, 28460, 28372, 28370, 28368, 28367, 28365, 28364, 28357, 28350, 28349, 28341, 28339, 23219, 23195, 23193, 7438, 23191, 23189, 23176, 23147, 23122, 23121, 23119, 23115, 23106, 23105, 23103, 23102, 21418, 21409, 21406, 21405, 21394, 21393, 21376, 21374, 21371, 21339, 21337, 21322, 21321, 21320, 21319, 21303, 21302, 21299, 21037, 21022, 20741, 20737, 20722, 20720, 20714, 20674, 20671, 20659, 20657, 20655, 20654, 20508, 20496, 20487, 20480, 20475, 20398, 20474, 13070, 20426, 20356, 20424, 20421, 20420, 20416, 20346, 20412, 18883, 18882, 18879, 18876, 18784, 18774, 18772, 18771, 18770, 18751, 18749, 18747, 18584, 18573, 18572, 18569, 18547, 18545, 18540, 18538, 18534, 18532, 18531, 18310, 18308, 18307, 18306, 18295, 18263, 18261, 18258, 18253, 18244, 18242, 18239, 18236, 18235, 33966, 33963, 33959, 33932, 33929, 33927, 33922, 33921, 113452, 113450, 113216, 113210, 113215, 113202, 113201, 113128, 113129, 112951, 112923, 112906, 112905, 112907, 112895, 112675, 112674, 111784, 111785, 112651, 112582, 112583, 112584, 111677, 111674, 111457, 111456, 111450, 111449, 111438, 111437, 111443, 111445, 111453, 103404, 103403, 103405, 105582, 110814, 110757, 110758, 110759, 110744, 110751, 110760, 110731, 110224, 110222, 110221, 110039, 110040, 110613, 110614, 110449, 110462, 110460, 110459, 110458, 110457, 110456, 110600, 110601, 110599, 110598, 110424, 110425, 110426, 110409, 110410, 110408, 110407, 110401, 110398, 110363, 109664, 109665, 109666, 110367, 109616, 109620, 109619, 109715, 109716, 110302, 109066, 109062, 109063, 109054, 109045, 109003, 109002, 109001, 109000, 108996, 108994, 108978, 108977, 108934, 108935, 108969, 108906, 108907, 50097, 50096, 50095, 50233, 50232, 50231, 50074, 50072, 50073, 50070, 50066, 50065, 50042, 50036, 50038, 50037, 50028, 50025, 50002, 50000]

最短路ヒープの比較

networkXでは，decrease-keyを用いない通常のヒープのデータ構造を利用している．以下では，decrease-keyが実装されているheapdictモジュールを利用したものと比較する．

  • networkXの実装（heapのみ）

  • heapdictを用いた実装

以下のheapdictパッケージを用いる．

https://github.com/DanielStutzbach/heapdict

%%timesource=0target=50000#if sink =-1 then find all shortest paths from source to other nodesweight='weight'get_weight=lambdau,v,data:data.get(weight,1)G_succ=G.succifG.is_directed()elseG.adjpred={source:[]}paths={source:[source]}push=heappushpop=heappopdist={}# dictionary of final distancesseen={source:0}c=count()fringe=[]# use heapq with (distance,label) tuplespush(fringe,(0,next(c),source))whilefringe:(d,_,v)=pop(fringe)ifvindist:continue# already searched this node.dist[v]=difv==target:breakforu,einG_succ[v].items():cost=get_weight(v,u,e)ifcostisNone:continuevu_dist=dist[v]+get_weight(v,u,e)ifuindist:ifvu_dist<dist[u]:raiseValueError('Contradictory paths found:','negative weights?')elifunotinseenorvu_dist<seen[u]:seen[u]=vu_distpush(fringe,(vu_dist,next(c),u))ifpathsisnotNone:paths[u]=paths[v]+[u]ifpredisnotNone:pred[u]=[v]elifvu_dist==seen[u]:ifpredisnotNone:pred[u].append(v)dist[50000]
CPU times: user 4.43 ms, sys: 371 µs, total: 4.8 msWall time: 4.79 ms
678
%%timesource=0target=50000#if sink =-1 then find all shortest paths from source to other nodesweight='weight'get_weight=lambdau,v,data:data.get(weight,1)G_succ=G.succifG.is_directed()elseG.adjpred={source:[]}paths={source:[source]}dist={}# dictionary of final distanceshd=heapdict()seen={source:0}c=count()hd[source]=0distwhilehd:(v,d)=hd.popitem()# decrease-keyの場合には以下が不要#if v in dist:#    continue  # already searched this node.dist[v]=difv==target:breakforu,einG_succ[v].items():cost=get_weight(v,u,e)ifcostisNone:continuevu_dist=dist[v]+get_weight(v,u,e)ifuindist:ifvu_dist<dist[u]:raiseValueError('Contradictory paths found:','negative weights?')elifunotinseenorvu_dist<seen[u]:seen[u]=vu_dist#push(fringe, (vu_dist, next(c), u))hd[u]=vu_distifpathsisnotNone:paths[u]=paths[v]+[u]ifpredisnotNone:pred[u]=[v]elifvu_dist==seen[u]:ifpredisnotNone:pred[u].append(v)dist[50000]
CPU times: user 5.61 ms, sys: 389 µs, total: 6 msWall time: 6.03 ms
678

時刻依存の移動時間をもつ最短路問題

道路ネットワークに対する最短路（最短時間路）を求めたい場合には，道路の混雑などで移動時間が時刻によって変化する場合がある．ここでは，そのような拡張が簡単に解けることを示す．

地点 $i,j$ 間の移動時間が時刻 $t$ によって $c_{ij}(t)$ という関数で与えられている場合を考える．

任意の2つの時刻 $t \leq t'$ に対して，$t+c_{ij}(t) \leq t' + c_{ij}(t')$ が成立するとき，移動時間は先入れ・先出し（First In First Out: FIFO）であるとよばれる．

点の上で「待つ」ことを許す場合には，FIFOになるように移動時間を変形できる．待ちを許さない場合には，$NP$-困難になる．

FIFOの場合には，通常のDijkstra法において，枝の移動時間を計算する部分を，到着時刻関数に変更するだけで動作する．

区間，速度，距離から到着時刻関数を生成する関数 arrival_func

到着時刻関数は，区分的な線形関数になる．以下に，時速が変化する区間のリスト interval，速度のリスト velocityと距離 distanceを与えると，新しい区間のリスト，$y$-切片のリスト，傾きのリストのタプルを返す関数を準備しておく．

arrival_func[source]

arrival_func(interval,velocity,distance)

interval=[0,4,8,10]# time intervalv=[10,20,30,20]# velocitydistance=10interval,b,a=arrival_func(interval,v,distance)print(interval,b,a)
[0, 3.5, 4, 7.833333333333334, 8, 10] [1.0, 4.5, 4.5, 8.333333333333334, 8.333333333333334, 10.5] [1, 0, 1, 0, 1, 1]

到着時刻関数 arrival

上の区分的線形関数の情報 interval, b, a を用いると，時刻tに出発したときの到着時刻を返す関数は，以下のように記述できる．

arrival[source]

arrival(t,interval,b,a)

fortinrange(interval[-1]+5):print(t,arrival(t,interval,b,a))
0 1.01 2.02 3.03 4.04 4.55 5.56 6.57 7.58 8.3333333333333349 9.33333333333333410 11.511 12.512 13.513 14.514 15.5

区分的線形な到着時刻関数をプロットする関数 plot_arrival

到着時刻関数をプロットする関数を以下の示す．

plot_arrival[source]

plot_arrival(interval,b,a)

plot_arrival(interval,b,a)
G=nx.Graph()G.add_weighted_edges_from([("s",1,50),("s",2,30),(2,1,20),(1,"t",80),(2,3,50),(3,"t",60)])interval=[0,2,4,7]# time intervalvelocity=[16,20,35,20]# velocityfor(i,j)inG.edges():G[i][j]["piecewise"]=arrival_func(interval,velocity,distance=G[i][j]["weight"])
for(i,j)inG.edges:interval,b,a=G[i][j]["piecewise"]plot_arrival(interval,b,a)

上で準備した例題に対して，FIFOを仮定した時刻依存最短路問題を解く．

source="s"target="t"G_succ=G.succifG.is_directed()elseG.adjpred={source:[]}paths={source:[source]}push=heappushpop=heappopdist={}# dictionary of final distancesseen={source:0}c=count()fringe=[]# use heapq with (distance,label) tuplespush(fringe,(0,next(c),source))whilefringe:(d,_,v)=pop(fringe)ifvindist:continue# already searched this node.dist[v]=difv==target:breakforu,einG_succ[v].items():interval,b,a=G[v][u]["piecewise"]vu_dist=arrival(dist[v],interval,b,a)ifuindist:ifvu_dist<dist[u]:raiseValueError("Contradictory paths found:","negative weights?")elifunotinseenorvu_dist<seen[u]:seen[u]=vu_distpush(fringe,(vu_dist,next(c),u))ifpathsisnotNone:paths[u]=paths[v]+[u]ifpredisnotNone:pred[u]=[v]elifvu_dist==seen[u]:ifpredisnotNone:pred[u].append(v)print(pred)print(dist)
{'s': [], 1: [2], 2: ['s'], 3: [2], 't': [3]}{'s': 0, 2: 1.875, 1: 3.0, 3: 4.5, 't': 6.214285714285714}

資源制約付き最短路問題

ここでは，運搬車スジューリング問題や乗務員スケジューリング問題を列生成法を用いて解く際の子問題としてあらわれる資源制約付き最短路問題について考える．列生成法では，主問題で線形最適化問題を解き，子問題では主問題の最適双対変数の情報を点の価値とみなした制約付きのパスを求める必要がある．資源制約付き最短路問題は，付加制約を一般化した資源としてモデル化し，価値を負の費用として最短路を求める．

資源制約付き最短路問題(resource constrained shortest path problem)とは，以下の仮定をもつ問題である．

  • 始点から終点までのパスを求める． これは人や運搬車の経路を抽象化したものである．実際には，初等パス（同じ枝を2度以上通過しないパス）である必要があるが， この条件を外した（すなわち，同じ枝を2度以上通過することを許した）パスを考える場合もある．

  • 資源の集合 $R$ が与えられており， 終点における資源量 $r$ の下限 $RLB_r$ と上限 $RUB_r$ が与えられている． これは，時刻，重量，容量などに関する諸制約を抽象化したものである．

  • 枝 $(i,j)$ をパスが通過した際には，資源 $r$ が $t_{ij}^r$ だけ増加するものとする． 荷物の積み降ろしなどで重量や容量が減少する場合や，タスクを処理することによる利益を扱う場合には，対応する $t_{ij}^r$ を負の値に設定すれば良い．

基本モデルにおいては，点 $i$ から点 $j$ に移動したとき，資源 $r$ の量は定数 $t_{ij}^{r}$ だけ大きくなると仮定する．すなわち，点 $i$ における資源 $r$ の量を $T_i^r$ としたとき， 点 $i$ から点 $j$ のへの移動の際には， 以下の関係が成り立つ．$$T_j^r =T_i^r + t_{ij}^r $$

しかし実際には，点 $i$ における幾つかの資源の量に依存して点 $j$ における資源量が決められる場合がある．ここでは，点 $i$ における資源量を表すベクトル $T_i$ を入力したときに点 $j$ における資源 $r$ の量を返す関数資源拡張関数 (resource extension function） $f_{ij}^r: \mathbf{R}^{|R|} \rightarrow \mathbf{R}$ を導入することによってモデルの一般化を行う．

資源拡張関数は，以下の2つの条件を満たす必要がある．

  • 最初の資源は単調増加（たとえば使用した枝の本数）
  • 逆写像が計算可能

以下のcspyパッケージを用いる．

https://github.com/torressa/cspy

使用法は以下の通り．

  • 入力グラフは networkX の有向グラフ DiGraph のインスタンスとする．

  • 入力グラフは， 資源数を表す n_res属性（グラフの生成時に指定する）をもたなければならない．

  • 入力グラフは，単一の始点 'Source' と終点 'Sink'をもたなければならない．

  • 枝上の属性に $t_{ij}^r$ を表すNumPyの配列型 res_cost と枝の費用を表す特別な資源を表す weightの属性をもたなければならない．

  • 最適化は様々なクラスで行われるが，クラスを生成する際に，終点における資源の上限を表すリスト max_res と下限を表すリスト min_res を設定する．

使用できる最適化手法のクラスは，以下の通り．

  • BiDirectional: 双方向型の厳密解法

  • Tabu: タブーサーチ

  • GreedyElim: 貪欲削減法

  • GRASP: 貪欲ランダム化適応型探索法 (greedy randomized adaptive search procedure)

  • PSOLGENT: 蟻コロニー法の亜種 (Particle Swarm Optimization with combined Local and Global Expanding Neighbourhood Topology: PSOLGENT)

使用法は，クラスを生成（elementaryをTrueにすると初等パスを探索）し， runメソッドで求解する．パスはpath属性，総費用はtotal_cost属性，使用した資源量はcomsumed_resources属性で得ることができる．

max_res,min_res=[4,20],[1,0]G=DiGraph(directed=True,n_res=2)G.add_edge("Source","A",res_cost=[1,2],weight=0)G.add_edge("A","B",res_cost=[1,0.3],weight=0)G.add_edge("A","C",res_cost=[1,0.1],weight=0)G.add_edge("B","C",res_cost=[1,3],weight=-10)G.add_edge("B","Sink",res_cost=[1,2],weight=10)G.add_edge("C","Sink",res_cost=[1,10],weight=0)for(i,j)inG.edges():G[i][j]["res_cost"]=np.array(G[i][j]["res_cost"])bidirec=BiDirectional(G,max_res,min_res,elementary=True)bidirec.run()print("Path=",bidirec.path)print("Cost=",bidirec.total_cost)print("Resource=",bidirec.consumed_resources)
Path= ['Source', 'A', 'B', 'C', 'Sink']Cost= -10Resource= [ 4.  15.3]
nx.draw(G,with_labels=True,node_color="y")

強化学習

以下では，強化学習の例として，格子世界のロボットに対するモンテカルロ方策評価法の実装を示す．

https://github.com/MJeremy2017/reinforcement-learning-implementation/blob/master/GridWorld/gridWorld.py

importnumpyasnpBOARD_ROWS=3BOARD_COLS=4WIN_STATE=(0,3)LOSE_STATE=(1,3)START=(2,0)DETERMINISTIC=TrueMOVE_PROB=[0.8,0.9,1.0]# 確率的移動のときの確率の閾値 (UPのときUP=0.8,LEFU=0.1,RIGHT=0.1)classState:"""    状態を定義するクラス    """def__init__(self,state=START):self.board=np.zeros([BOARD_ROWS,BOARD_COLS])self.board[1,1]=-1# 壁self.state=state# 現在の位置self.isEnd=False# 終了か否かself.determine=DETERMINISTIC# 確定的ならTruedefgiveReward(self):ifself.state==WIN_STATE:return1elifself.state==LOSE_STATE:return-1else:return0defisEndFunc(self):if(self.state==WIN_STATE)or(self.state==LOSE_STATE):self.isEnd=TruedefnxtPosition(self,action):"""        action: up, down, left, right        次の位置を返す        return next position        """ifself.determine:ifaction=="up":nxtState=(self.state[0]-1,self.state[1])elifaction=="down":nxtState=(self.state[0]+1,self.state[1])elifaction=="left":nxtState=(self.state[0],self.state[1]-1)else:nxtState=(self.state[0],self.state[1]+1)# 壁や外側ではないif(nxtState[0]>=0)and(nxtState[0]<=(BOARD_ROWS-1)):if(nxtState[1]>=0)and(nxtState[1]<=(BOARD_COLS-1)):ifnxtState!=(1,1):# 壁returnnxtState# 違法な移動なのでそのままreturnself.stateelse:# 確率的推移rnd=np.random.random()# [0,1) unoform randomifaction=="up":ifrnd<MOVE_PROB[0]:nxtState=(self.state[0]-1,self.state[1])# upelifrnd<MOVE_PROB[1]:nxtState=(self.state[0],self.state[1]-1)# leftelse:nxtState=(self.state[0],self.state[1]+1)# rightelifaction=="down":ifrnd<MOVE_PROB[0]:nxtState=(self.state[0]+1,self.state[1])elifrnd<MOVE_PROB[1]:nxtState=(self.state[0],self.state[1]+1)# rightelse:nxtState=(self.state[0],self.state[1]-1)# leftelifaction=="left":ifrnd<MOVE_PROB[0]:nxtState=(self.state[0],self.state[1]-1)elifrnd<MOVE_PROB[1]:nxtState=(self.state[0]-1,self.state[1])# upelse:nxtState=(self.state[0]+1,self.state[1])else:# rightifrnd<MOVE_PROB[0]:nxtState=(self.state[0],self.state[1]+1)elifrnd<MOVE_PROB[1]:nxtState=(self.state[0]+1,self.state[1])# downelse:nxtState=(self.state[0]-1,self.state[1])# up# 壁や外側ではないif(nxtState[0]>=0)and(nxtState[0]<=(BOARD_ROWS-1)):if(nxtState[1]>=0)and(nxtState[1]<=(BOARD_COLS-1)):ifnxtState!=(1,1):# 壁returnnxtState# 違法な移動なのでそのままreturnself.statedefshowBoard(self):"""        盤面を返す        """self.board[self.state]=1foriinrange(0,BOARD_ROWS):print("-----------------")out="| "forjinrange(0,BOARD_COLS):ifself.board[i,j]==1:token="*"ifself.board[i,j]==-1:token="z"ifself.board[i,j]==0:token="0"out+=token+" | "print(out)print("-----------------")# Agent of playerclassAgent:def__init__(self):self.states=[]self.actions=["up","down","left","right"]self.State=State()self.lr=0.2#self.exp_rate=0.3# ランダムに選択する確率# initial state rewardself.state_values={}foriinrange(BOARD_ROWS):forjinrange(BOARD_COLS):self.state_values[(i,j)]=0.0# set initial value to 0defchooseAction(self):# choose action with most expected valuemx_nxt_reward=0action=""ifnp.random.uniform(0,1)<=self.exp_rate:action=np.random.choice(self.actions)else:# 貪欲法forainself.actions:# 移動が確定的のときnxt_reward=self.state_values[self.State.nxtPosition(a)]ifnxt_reward>=mx_nxt_reward:action=amx_nxt_reward=nxt_rewardreturnactiondeftakeAction(self,action):position=self.State.nxtPosition(action)returnState(state=position)defreset(self):self.states=[]self.State=State()defplay(self,rounds=10,LOG=False):i=0whilei<rounds:# to the end of game back propagate rewardifLOG:self.State.showBoard()ifself.State.isEnd:# back propagatereward=self.State.giveReward()# explicitly assign end state to reward valuesself.state_values[self.State.state]=reward# this is optionalifLOG:print("Game End Reward",reward)forsinreversed(self.states):reward=self.state_values[s]+self.lr*(reward-self.state_values[s])self.state_values[s]=round(reward,3)self.reset()i+=1ifLOG:self.showValues()else:action=self.chooseAction()# append traceself.states.append(self.State.nxtPosition(action))ifLOG:print("current position{} action{}".format(self.State.state,action))# by taking the action, it reaches the next stateself.State=self.takeAction(action)# mark is endself.State.isEndFunc()ifLOG:print("nxt state",self.State.state)print("---------------------")defshowValues(self):foriinrange(0,BOARD_ROWS):print("----------------------------------")out="| "forjinrange(0,BOARD_COLS):out+=str(self.state_values[(i,j)]).ljust(6)+" | "print(out)print("----------------------------------")
ag=Agent()ag.play(5,LOG=True)ag.showValues()
-----------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action rightnxt state (2, 1)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| 0 | * | 0 | 0 | -----------------current position (2, 1) action rightnxt state (2, 2)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | * | 0 | -----------------current position (2, 2) action upnxt state (1, 2)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | * | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (1, 2) action rightnxt state (1, 3)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | * | -----------------| 0 | 0 | 0 | 0 | -----------------Game End Reward -1----------------------------------| 0.0    | 0.0    | 0.0    | 0.0    | ----------------------------------| 0.0    | 0.0    | -0.2   | -1.0   | ----------------------------------| 0.0    | -0.008 | -0.04  | 0.0    | ---------------------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action leftnxt state (2, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action leftnxt state (2, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action leftnxt state (2, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action leftnxt state (2, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action leftnxt state (2, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action leftnxt state (2, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action leftnxt state (2, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action leftnxt state (2, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action leftnxt state (2, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action downnxt state (2, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action leftnxt state (2, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action leftnxt state (2, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action leftnxt state (2, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action leftnxt state (2, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action upnxt state (1, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| * | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (1, 0) action rightnxt state (1, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| * | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (1, 0) action upnxt state (0, 0)--------------------------------------| * | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (0, 0) action rightnxt state (0, 1)--------------------------------------| 0 | * | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (0, 1) action rightnxt state (0, 2)--------------------------------------| 0 | 0 | * | 0 | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (0, 2) action rightnxt state (0, 3)--------------------------------------| 0 | 0 | 0 | * | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------Game End Reward 1----------------------------------| 0.008  | 0.04   | 0.2    | 1.0    | ----------------------------------| 0.002  | 0.0    | -0.2   | -1.0   | ----------------------------------| 0.0    | -0.008 | -0.04  | 0.0    | ---------------------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action upnxt state (1, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| * | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (1, 0) action upnxt state (0, 0)--------------------------------------| * | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (0, 0) action rightnxt state (0, 1)--------------------------------------| 0 | * | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (0, 1) action rightnxt state (0, 2)--------------------------------------| 0 | 0 | * | 0 | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (0, 2) action rightnxt state (0, 3)--------------------------------------| 0 | 0 | 0 | * | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------Game End Reward 1----------------------------------| 0.027  | 0.104  | 0.36   | 1.0    | ----------------------------------| 0.007  | 0.0    | -0.2   | -1.0   | ----------------------------------| 0.0    | -0.008 | -0.04  | 0.0    | ---------------------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action upnxt state (1, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| * | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (1, 0) action upnxt state (0, 0)--------------------------------------| * | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (0, 0) action rightnxt state (0, 1)--------------------------------------| 0 | * | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (0, 1) action rightnxt state (0, 2)--------------------------------------| 0 | 0 | * | 0 | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (0, 2) action rightnxt state (0, 3)--------------------------------------| 0 | 0 | 0 | * | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------Game End Reward 1----------------------------------| 0.058  | 0.181  | 0.488  | 1.0    | ----------------------------------| 0.017  | 0.0    | -0.2   | -1.0   | ----------------------------------| 0.0    | -0.008 | -0.04  | 0.0    | ---------------------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action downnxt state (2, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| * | 0 | 0 | 0 | -----------------current position (2, 0) action upnxt state (1, 0)--------------------------------------| 0 | 0 | 0 | 0 | -----------------| * | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (1, 0) action upnxt state (0, 0)--------------------------------------| * | 0 | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (0, 0) action rightnxt state (0, 1)--------------------------------------| 0 | * | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (0, 1) action rightnxt state (0, 2)--------------------------------------| 0 | 0 | * | 0 | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (0, 2) action leftnxt state (0, 1)--------------------------------------| 0 | * | 0 | 0 | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (0, 1) action rightnxt state (0, 2)--------------------------------------| 0 | 0 | * | 0 | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------current position (0, 2) action rightnxt state (0, 3)--------------------------------------| 0 | 0 | 0 | * | -----------------| 0 | z | 0 | 0 | -----------------| 0 | 0 | 0 | 0 | -----------------Game End Reward 1----------------------------------| 0.109  | 0.315  | 0.525  | 1.0    | ----------------------------------| 0.035  | 0.0    | -0.2   | -1.0   | ----------------------------------| 0.007  | -0.008 | -0.04  | 0.0    | --------------------------------------------------------------------| 0.109  | 0.315  | 0.525  | 1.0    | ----------------------------------| 0.035  | 0.0    | -0.2   | -1.0   | ----------------------------------| 0.007  | -0.008 | -0.04  | 0.0    | ----------------------------------
[8]ページ先頭
©2009-2025 Movatter.jp