---
# System prepended metadata

title: 透過Qlearning在網路拓樸上尋徑
tags: [上課筆記]

---

---
tags: Q_Learning
---

# 透過Qlearning在網路拓樸上尋徑

強化式學習 

## dijkstra.py

### output

```
path= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023]
time difference: 202375
```

### init

adjacency
![0](https://i.imgur.com/MjUYeg4.png)
基本上就是讓每個點都可以被兩個以上的點到達和被到達 的一個圖
![1](https://i.imgur.com/vUd4XFl.png)

```python
from collections import defaultdict
import datetime
# 用於graph本體
adjacency=defaultdict(lambda:defaultdict(lambda:None))

src=512
dst=1023
n=1023
# 建立一個 graph
for i in range(1,int(n/2)+1):
  if 2*i<=(n-1):
    for j in [2*i, 2*i+1]:
      #print(i,j)
      adjacency[i][j]=1  # 1是指成本還是只是 True 代表可達?
      adjacency[j][i]=1  # 構成無向邊
```

### main

```python
start=datetime.datetime.now()
get_path(src,dst)
end=datetime.datetime.now()
diff=end-start
print("time difference:", diff.microseconds)
```

### get_path(src, dst)

```python
def get_path(src,dst):
  global adjacency, n
  distance = {}
  previous = {}
 
  for dpid in range(1,n+1): # 1 ~ 1023
    distance[dpid] = float('Inf') # 初始化 distance 1~1023 = Inf
    previous[dpid] = None # 初始化 previous 1~1023 = None
 
  distance[src]=0

  # distance = {1:inf, 2:inf, ..., 512:0, ... 1023:inf} 
  # previous = {1:None, 2:None, ... 1023:None} 

  Q=set(range(1,n+1))
  # Q = {1,2,...n}
  #print "Q=", Q
 
  while len(Q)>0:
    u = minimum_distance(distance, Q) # 0 or min
    #print "u=", u
    Q.remove(u)
    #print "After removing ", u, " Q=", Q
    for p in range(1,n+1): # 1 ~ 1023
     if adjacency[u][p]!=None: # u 節點 到其他節點 的距離(不可達為None)
        #print u, "--------",  p
        # 第一次進入這邊是u:512, p:256 ,adjacency[512][256]=1 代表u節點第一個可達的點 (p節點)
        w = 1 # 成本?
        # distance = {1:inf, 2:inf, ..., 512:0, ... 1023:inf} 
        if distance[u] + w < distance[p]: # 可到達u節點的最小距離 +1 < 可到達p節點的最小距離 ?(判斷是否有更短距離的節點可達p節點)
          distance[p] = distance[u] + w # 記錄可達p節點的最短距離 + 1?
          previous[p] = u # 記錄距離p節點最短的節點
 
  #print "distance=", distance, " previous=", previous
  r=[]
  p=dst
  r.append(p)
  q=previous[p] # 最短路徑可達終點的前一個節點
 
  while q is not None:
    if q == src:
      r.append(q)
      break
    p=q
    r.append(p)
    q=previous[p] # 最短路徑可達p點的前一個節點
 
  r.reverse()
  if src==dst:
    path=[src] # 當終點等於起點時,避免選擇到環路而不是本身
  else:
    path=r
  
  print("path=", path)
```

path= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127,
 255, 511, 1023]
time difference: 201360

### minimum_distance(distance, Q)

```python
def minimum_distance(distance, Q):
  min = float('Inf')
  node = 0
  for v in Q:
    if distance[v] < min: # if distance存在
      # distance[v] 預設為 inf
      min = distance[v]
      node = v #記錄 成立時 (distance中)的位置
  return node # distance中最後一個有賦値的 位置 
```

---

## dijkstra_random.py

### output

```txt
path= [1, 2, 4, 10]
time difference: 0 0
```

### init

```python
from collections import defaultdict
import datetime
import random

adjacency=defaultdict(lambda:defaultdict(lambda:None))

random.seed(1)
src=1
dst=10
n=10 # 節點數
for i in range(1,n): # 1~9
  flag=0
  for j in range(i+1, n+1): # 1~10 -> 9~10
    if random.uniform(0,1)<0.01: # 0~1間的隨機數 < 0.01 -> 1%
      #print(i,j)
      adjacency[i][j]=1
      adjacency[j][i]=1  
      flag=1
  if flag==0: # 99% 沒有設定無向邊時
    choice=random.choice(range(i+1, n+1)) # 在 i+1 ~ n 間隨機選一個數
    #print(i,choice)
    adjacency[i][choice]=1 # 設定無向邊
    adjacency[choice][i]=1  

  # 1% 99% 設定無向邊 看起來都是隨機設? 那為甚麼不要100% 都走flag==0時 的隨機?
```

### main

```python
start=datetime.datetime.now()
get_path(src,dst)
end=datetime.datetime.now()
diff=end-start
print("time difference:", diff.seconds, diff.microseconds)
```

### get_path(src, dst)

```python
def get_path(src,dst):
  global adjacency, n
  distance = {}
  previous = {}
 
  for dpid in range(1,n+1): # 1 ~ 1023
    distance[dpid] = float('Inf') # 初始化 distance 1~1023 = Inf
    previous[dpid] = None # 初始化 previous 1~1023 = None
 
  distance[src]=0

  # distance = {1:inf, 2:inf, ..., 512:0, ... 1023:inf} 
  # previous = {1:None, 2:None, ... 1023:None} 

  Q=set(range(1,n+1))
  # Q = {1,2,...n}
  #print "Q=", Q
 
  while len(Q)>0:
    u = minimum_distance(distance, Q) # 0 or min
    #print "u=", u
    Q.remove(u)
    #print "After removing ", u, " Q=", Q
    for p in range(1,n+1): # 1 ~ 1023
     if adjacency[u][p]!=None: # u 節點 到其他節點 的距離(不可達為None)
        #print u, "--------",  p
        # 第一次進入這邊是u:512, p:256 ,adjacency[512][256]=1 代表u節點第一個可達的點 (p節點)
        w = 1 # 成本?
        # distance = {1:inf, 2:inf, ..., 512:0, ... 1023:inf} 
        if distance[u] + w < distance[p]: # 可到達u節點的最小距離 +1 < 可到達p節點的最小距離 ?(判斷是否有更短距離的節點可達p節點)
          distance[p] = distance[u] + w # 記錄可達p節點的最短距離 + 1?
          previous[p] = u # 記錄距離p節點最短的節點
 
  #print "distance=", distance, " previous=", previous
  r=[]
  p=dst
  r.append(p)
  q=previous[p] # 最短路徑可達終點的前一個節點
 
  while q is not None:
    if q == src:
      r.append(q)
      break
    p=q
    r.append(p)
    q=previous[p] # 最短路徑可達p點的前一個節點
 
  r.reverse()
  if src==dst:
    path=[src] # 當終點等於起點時,避免選擇到環路而不是本身
  else:
    path=r
  
  print("path=", path)
```

path= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127,
 255, 511, 1023]
time difference: 201360

### minimum_distance(distance, Q)

```python
def minimum_distance(distance, Q):
  min = float('Inf')
  node = 0
  for v in Q:
    if distance[v] < min: # if distance存在
      # distance[v] 預設為 inf
      min = distance[v]
      node = v #記錄 成立時 (distance中)的位置
  return node # distance中最後一個有賦値的 位置 
```

---

## qlearning_tree.py

### output

```txt
A_Z_dict==A_Z_dict={1: [2, 3], 2: [1, 4, 5], ..., 1023: [511]}
R={1: {2: 1, 3: 1}, 2: {1: 1, 4: 1, 5: 1}, ..., 1023: {511: 1}}
Q: {1: {2: 100, 3: 100}, 2: {1: 100, 4: 100, 5: 100}, 1023: {511: 100}}
in get_result(), start= 512  end= [1023]
================================================== e= 30
Q= {1: {2: 110.987043, 3: 109.0}, 2: {1: 109.999998, 4: 111.789482, 5: 110.751853}, ..., , 1023: {511: 100}}
node_use= [512, 256] next_level= [256]
node_use= [512, 256, 128] next_level= [128]
node_use= [512, 256, 128, 64] next_level= [64]
node_use= [512, 256, 128, 64, 32] next_level= [32]
node_use= [512, 256, 128, 64, 32, 16] next_level= [16]
node_use= [512, 256, 128, 64, 32, 16, 8] next_level= [8]
node_use= [512, 256, 128, 64, 32, 16, 8, 4] next_level= [4]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2] next_level= [2]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1] next_level= [1]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3] next_level= [3]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7] next_level= [7]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15] next_level= [15]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31] next_level= [31]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63] next_level= [63]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127] next_level= [127]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127, 255] next_level= [255]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127, 255, 511] next_level= [511]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023] next_level= [1023]
nodes: [512, 256, 128, 2, 4, 1, 3, 7, 8, 511, 15, 16, 1023, 31, 32, 63, 64, 127, 255]
================================================== e= 35
Q= {1: {2: 110.996113, 3: 109.0}, 2: {1: 110.0, 4: 111.936844, 5: 110.751853}, ..., 1023: {511: 100}}
node_use= [512, 256] next_level= [256]
node_use= [512, 256, 128] next_level= [128]
node_use= [512, 256, 128, 64] next_level= [64]
node_use= [512, 256, 128, 64, 32] next_level= [32]
node_use= [512, 256, 128, 64, 32, 16] next_level= [16]
node_use= [512, 256, 128, 64, 32, 16, 8] next_level= [8]
node_use= [512, 256, 128, 64, 32, 16, 8, 4] next_level= [4]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2] next_level= [2]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1] next_level= [1]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3] next_level= [3]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7] next_level= [7]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15] next_level= [15]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31] next_level= [31]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63] next_level= [63]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127] next_level= [127]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127, 255] next_level= [255]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127, 255, 511] next_level= [511]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023] next_level= [1023]
nodes: [512, 256, 128, 2, 4, 1, 3, 7, 8, 511, 15, 16, 1023, 31, 32, 63, 64, 127, 255]
================================================== e= 40
Q= {1: {2: 110.996113, 3: 109.0}, 2: {1: 110.0, 4: 111.936844, 5: 110.751853}, ..., 1023: {511: 100}}
node_use= [512, 256] next_level= [256]
node_use= [512, 256, 128] next_level= [128]
node_use= [512, 256, 128, 64] next_level= [64]
node_use= [512, 256, 128, 64, 32] next_level= [32]
node_use= [512, 256, 128, 64, 32, 16] next_level= [16]
node_use= [512, 256, 128, 64, 32, 16, 8] next_level= [8]
node_use= [512, 256, 128, 64, 32, 16, 8, 4] next_level= [4]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2] next_level= [2]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1] next_level= [1]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3] next_level= [3]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7] next_level= [7]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15] next_level= [15]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31] next_level= [31]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63] next_level= [63]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127] next_level= [127]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127, 255] next_level= [255]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127, 255, 511] next_level= [511]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023] next_level= [1023]
nodes: [512, 256, 128, 2, 4, 1, 3, 7, 8, 511, 15, 16, 1023, 31, 32, 63, 64, 127, 255]
in get_result(),
Q= {1: {2: 110.996113, 3: 109.0}, 2: {1: 110.0, 4: 111.936844, 5: 110.751853}, ..., 1023: {511: 100}}
node_use= [512, 256] next_level= [256]
node_use= [512, 256, 128] next_level= [128]
node_use= [512, 256, 128, 64] next_level= [64]
node_use= [512, 256, 128, 64, 32] next_level= [32]
node_use= [512, 256, 128, 64, 32, 16] next_level= [16]
node_use= [512, 256, 128, 64, 32, 16, 8] next_level= [8]
node_use= [512, 256, 128, 64, 32, 16, 8, 4] next_level= [4]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2] next_level= [2]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1] next_level= [1]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3] next_level= [3]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7] next_level= [7]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15] next_level= [15]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31] next_level= [31]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63] next_level= [63]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127] next_level= [127]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127, 255] next_level= [255]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127, 255, 511] next_level= [511]
node_use= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023] next_level= [1023]
nodes= [512, 256, 128, 2, 4, 1, 3, 7, 8, 511, 15, 16, 1023, 31, 32, 63, 64, 127, 255]
graph= {512: [256], 256: [128], 128: [64], 2: [1], 4: [2], 1: [3], 3: [7], 7: [15], 8: [4], 511: [1023], 15: [31], 16: [8], 1023: [511], 31: [63], 32: [16], 63: [127], 64: [32], 127: [255], 255: [511]}
routes= [[512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023]]
result= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023]
path= [512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023]
time difference: 268082
```

### init

```python
from collections import defaultdict
import datetime
import copy
import random
from collections import Counter

adjacency=defaultdict(lambda:defaultdict(lambda:None))

src=512
dst=1023
n=1023
for i in range(1,int(n/2)+1):
  if 2*i<=(n-1):
    for j in [2*i, 2*i+1]:
      #print(i,j)
      adjacency[i][j]=1
      adjacency[j][i]=1 
```

### main

```python
start=datetime.datetime.now()
get_path2(src,dst)
end=datetime.datetime.now()
diff=end-start
print("time difference:", diff.microseconds)
```

### get_path2(src,dst)

```python
def get_path2(src,dst):
  A_Z_dict={}
  for p in range(1,n+1):
    A_Z_dict[p] = [] # 初始化
    for q in range(1,n+1):
      if adjacency[p][q]!=None:
        A_Z_dict[p].append(q) # 將adjacency設定好的有向邊 複製給 A_Z_dict
        
  print(f"A_Z_dict=={A_Z_dict=}")
  R={}      
  net = copy.deepcopy(A_Z_dict) # 建立一份完全獨立的變數
  for i in net.keys(): #{key:value} -> {節點:[所有可達節點]}
    sub_key=net[i] # [所有可達節點]
    sub_dic={}
    for j in sub_key:
      sub_dic[j]=adjacency[i][j] # 節點1:{可達節點1:1, 可達節點2:1, ...,可達節點n:1}
    R[i] = sub_dic # R is for Reward
  print(f"R={R}")
    
  Q = copy.deepcopy(R) # 建立一份完全獨立的變數
  for i in Q.keys():
    for j in Q[i].keys():
      Q[i][j] = 100 # 把R可達節點的值全部從1變成100 -> 節點1:{可達節點1:100, 可達節點2:100, ...,可達節點n:100}
      
  print("Q:",Q) 
  alpha = 0.7 # learning rate # 決定這次結果的誤差有多少會被學習
  epsilon = 0.1 #greedy policy # 10% 按照Q表選擇最佳路徑， 90% 隨機選則 # 隨著learn的次數提高
  n_episodes = 1000
  result = get_result(R,Q,alpha,epsilon,n_episodes,src,[dst])
  print(f"result= {result[0]}")
  
  if src==dst:
    path=[src]
  else:
    path=result[0]

  print(f"path= {path}")
```

### get_result(R,Q,alpha,epsilon,n_episodes,src,[dst])

```python
def get_result(R,Q,alpha,epsilon,n_episodes,start,end):
    print("in get_result(), start=", start, " end=", end)
    Q = Q_routing(R,Q,alpha,epsilon,n_episodes,start,end)
    print("in get_result(), Q=", Q)
    nodes = get_best_nodes(Q,start,end)
    print("nodes=", nodes)
    graph = get_best_net(Q,nodes)
    print("graph=", graph)
    route_len = len(get_route(Q,start,end))
    routes = get_all_best_routes(graph,start,end,route_len+1)
    print("routes=", routes)
    result = count_routes(routes)
    return routes
```

### Q_routing(R,Q,alpha,epsilon,n_episodes,start,end)

```python
def Q_routing(T,Q,alpha,epsilon,n_episodes,start,end):
    nodes_number = [0,0]
    for e in range(n_episodes):
        #print("="*50, "e=", e)
        #if e in range(0,n_episodes,1000):
        #    print("loop:",e)
        current_state = start
        #current_route = [start]
        goal = False
        while not goal:
            valid_moves = list(Q[current_state].keys()) #Q[current_state] = 節點1:{可達節點1:100, 可達節點2:100, ...,可達節點n:100}, keys = [可達節點n...可達節點n]
            
            if len(valid_moves) <= 1: # 設計上 每個節點都有至少一條路可以走
                next_state = valid_moves[0]
            else:
                best_action = random.choice(get_key_of_min_value(Q[current_state])) # 隨機選一個 Q值最小的的可達節點

                if random.random() < epsilon: # if epsilon = 0.1 -> 10%
                    valid_moves.pop(valid_moves.index(best_action))
                    next_state = random.choice(valid_moves) #除了最短路徑以外的路
                
                else: # if epsilon = 0.1 -> 90%
                    next_state = best_action
            
            Q = update_Q(T,Q,current_state, next_state, alpha)
            #print("Q=",Q)
            #print("current_state=", current_state, "next_state=", next_state)
        
            if next_state in end:
                goal = True

            current_state = next_state
            #current_route.append(next_state)
        #print "current:",current_route   
        #print get_route(Q,start,end)
        # check stop standard

        # 離開while後
        # e : 0~999 (for e in range(n_episodes):)
        if e in range(30,1000,5): # 30、35、...998
            print("="*50, "e=", e) 
            for i in Q.keys():
                for j in Q[i].keys():
                    Q[i][j]  = round(Q[i][j],6) # 只取小數點後6位
            print("Q=", Q)
            nodes = get_best_nodes(Q,start,end) # 取得start 到 end 的所有路徑上的節點 + 可能可以到end的節點(透過遍歷所有路徑 直到找到終點 所以還沒到終點的路徑也會被記錄?)
            print("nodes:",nodes)
            nodes_number.append(len(nodes)) # 紀錄 目前的最佳路徑 步數
            #print("nodes_number:",nodes_number)
            if len(set(nodes_number[-3:])) == 1: # set去除重複元素 當set(nodes_number[-3::]) = set([0]) 時 break -> 當 紀錄的最佳路徑步數 連續3次都一樣 則停止尋找
                break
    return Q
```

### get_key_of_min_value(Q[current_state])

```python
def get_key_of_min_value(dic):
    min_val = min(dic.values())
    return [k for k, v in dic.items() if v == min_val] # 取得value為min_val的key
```

### update_Q(T,Q,current_state, next_state, alpha)

```python
def update_Q(T,Q,current_state, next_state, alpha):
    current_t = T[current_state][next_state] # 最初 全為1
    current_q = Q[current_state][next_state] # 最初 全為100
    new_q = current_q + alpha * (current_t + min(Q[next_state].values()) - current_q)
    # current_t 永遠=1, 代表每走一步 距離+1 (reward (最終的score越小越好))

    #new_q = current_q + alpha * (current_t + max(Q[next_state].values()) - current_q)
    Q[current_state][next_state] = new_q
    return Q
```

### get_best_nodes(Q,start,end)

```python
def get_best_nodes(Q,start,end):
    next_level = [start]
    node_use = [start]
    while list(set(next_level) & set(end)) == []: # set(next_level) & set(end) 取交集 -> 判斷是否到達終點
        temp_level = []
        for i in next_level: # 不是尋找路徑 是遍歷從起點出發的所有路徑
            temp_level += get_single_dict(Q[i]) # 取得節點Q[i] 所有可達節點中Q值最小的
        next_level = list(set(temp_level))
        node_use += next_level
        print("node_use=", node_use, "next_level=", next_level)
    return list(set(node_use))
```

### get_single_dict(Q[i]) # 初始Q[i] = 可達節點1:100, 可達節點2:100, ..., 可達節點n:100

```python
def get_single_dict(dic):
    single_link = {}
    min_value = min(dic.values()) # 取得 所有可達節點中 值最小的 值
    for key in dic.keys(): # dic.keys = 所有可達節點
        if dic[key] == min_value:
            single_link[key] = dic[key] # single_link[值最小的節點] = 值
    return single_link.keys() # 回傳"一個"最小Q值的節點(可能不唯一 但只回傳節點名稱最小的) # 值 可代表 距離
```

### get_best_net(Q,nodes)

```python
def get_best_net(Q,nodes): # nodes= [512, 256, 128, 2, 4, 1, 3, 7, 8, 511, 15, 16, 1023, 31, 32, 63, 64, 127, 255]
    best_net = {}
    for i in nodes:
        best_net[i] = list(set( get_single_dict(Q[i]) ) & set(nodes))
    return best_net
```

### get_route(Q,start,end)

```python
def get_route(Q,start,end):
    """ input is  Q-table is like:{1: {2: 0.5, 3: 3.8},
                                   2: {1: 5.9, 5: 10}} """
    single_route = [start]
    while single_route[-1] not in end:
        next_step = min(Q[single_route[-1]],key=Q[single_route[-1]].get)
        # min(,key=...) key設定比較的方式 -> Q[single_route[-1]].get 代表 取得Q[single_route[-1]]字典中 值(Q值)最小的 "值" 最後next_step會得到最小"值"的鍵 -> 最小Q值節點
        single_route.append(next_step)
        if len(single_route) > 2 and single_route[-1] in single_route[:-1]:
#                                    single_route[-1] in single_route[:-1] 代表出現重複元素(single_route[-1])
            break
    return single_route
```

### get_all_best_routes(graph,start,end,route_len+1)

```python
# graph = {512: [256], 256: [128], 128: [64], 2: [1], 4: [2], 1: [3], 3: [7], 7: [15], 8: [4], 511: [1023], 15: [31], 16: [8], 1023: [511], 31: [63], 32: [16], 63: [127], 64: [32], 127: [255], 255: [511]}
# start= 512  end= [1023]
# route_len+1 = 19 + 1    # len([512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023]) = 19

def get_all_best_routes(graph,start,end,max_depth):
    past_path = []
    # maintain a queue of paths
    queue = []
    # push the first path into the queue
    queue.append([start]) # 二維陣列
    while queue:
        # get the first path from the queue
        path = queue.pop(0) # 一維陣列
        # get the last node from the path
        node = path[-1]
        # path found
       # print "*"
        # enumerate all adjacent nodes, construct a new path and push it into the queue
        for adjacent in graph.get(node, []): # graph.get(node,[]) 回傳 graph中node對應的值 若node沒有對應的值回傳[] # ex: graph.get(512,[]) = [256]
            new_path = list(path) # ex: [512] (一維)
            ## end the current loop if we already reach the point
            if adjacent in end:
                new_path.append(adjacent)
                past_path.append(new_path)
                continue

            if adjacent in new_path: # 避免重複
                continue

            new_path.append(adjacent)
            if len(new_path) >= max_depth and new_path[-1] not in end:
                break # 跳出for loop
           # print new_path
            queue.append(new_path)
            past_path.append(new_path)

    best_paths = []
    for l in past_path:
        if l[-1] in end:
            best_paths.append(l)
    return best_paths
```

### 實驗數據
```
在 10 個 節點
di: *100 (執行100次後 取10次平均)
996+1003+1595+996+1004+996+1008+2169+1007+1981 = *12,755* 

12.755 # 最終結果 單位(microsecond)

ql: *100
21098+21049+22564+22375+23049+22133+22691+22325+22642+21590 = *221,516* 

221.516 # 最終結果 單位(microsecond)

------------------------------------------------------------------------
在 50 個 節點
di:*100
19962+20103+20015+19177+18990+20936+18978+18510+19052+20259 = *195,982* 

195.982 # 最終結果 單位(microsecond)

ql:*100
87753+91628+84637+86088+86100+89192+88802+93270+88635+93979 = *890,084* 

890.084 # 最終結果 單位(microsecond)

------------------------------------------------------------------------
在 100 個節點
di:*100
74740+85027+74699+77784+75551+70264+73045+68555+76592+75287 = *751,544* 

751.544 # 最終結果 單位(microsecond)

ql:*100
181232+192641+181541+184840+207016+198307+187308+190106+197272+189659 = *1,909,922* 

1909.922 # 最終結果 單位(microsecond)

------------------------------------------------------------------------
在 500 個節點

di:*1
48413+47036+48090+46205+48617+46103+46063+49696+49538+46514 = *476,275* 

476.275 # 最終結果 單位(microsecond)

ql:*1
47931+47070+43957+49026+45667+45019+44293+48721+47991+45318 = *464,993* 

46499.3 # 最終結果 單位(microsecond)

------------------------------------------------------------------------
在 1000 個節點
di:*1
185386+200810+205391+191985+189766+204043+185073+212553+194596+196716 = *1,966,319* 

196631.9 # 最終結果 單位(microsecond)

ql:*1
175255+180451+183513+174370+178361+182982+192534+188779+186701+185487 = *1,828,433* 

182843.3 # 最終結果 單位(microsecond)

------------------------------------------------------------------------
在 5000 個節點
di:
(409858+431286+560219+550301+600138+584622+530526+690033+607939+530798) / 10 = *549572.0* # 最終結果 單位(microsecond)

ql:
(349916+464350+409767+310032+335007+329855+335007+383069+454963+383605) / 10 = *375557.1* # 最終結果 單位(microsecond)
```