それはカスタムエンドポイント

Question

に達するまで繰り返し処理がキーに指定された値を持つ辞書の上に、私は以下のような構造{key:[(next_key, value),...],....}と辞書を持っている：

d = {0: [(1, 10), (5, 9)], 1: [(0, 14), (3, 3), (4, 17)]} 

エンドポイントは以下のとおりです。

ここ

end_points = [2,3,4,5]

私がする必要がありますdの値をnext_keyで繰り返し、keyにあり、次のキーの隣にあり、次のキー値が終点にくるまで続きます。ですから、私がエンドポイントに到達すると、辞書にはend_pointsがキー要素として含まれ、それを繰り返したすべての値が乗算されます。つまりend_point 3の値は10*3 = 30となり、end_point 4の値は10 * 17 になりますが、0の要素がキー値1を指し、その要素点が0であるため問題が発生します。そのループを制動して値を考慮する必要がありますend_pointsに到達するための乗算。

基本的には、ループオーバーパスを含む場合と含まない場合があり、最終状態として扱うことができるend_pointsに到達するために値の乗算が必要です。

これまでのところ、私が試してみました：

d = {0: [(1, 10), (5, 9)], 1: [(0, 14), (3, 3), (4, 17)]} # dictionary 
end_points = [2,3,4,5] # end points 

end_points_cost = {} 
loop = lambda x : 1/(1-x) 

for key in d: 
    temp = 1 # multiplication constant 
    flag=True 
    for next_key, value in d[key]: 
     if next_key in end_points_cost: 
      temp = end_points[next_key] 
     if next_key not in end_points: 
      temp = temp * value 
     elif next_key in end_points: 
      temp = temp * value 
      end_points_cost[next_key] = temp 
     elif key in [i[0] for i in d[next_key]]: 
      temp = temp * loop(d[key][1] * value) 
      end_points_cost[next_key] = temp 

私の出力：

{3: 42, 4: 714, 5: 90} 

所望の出力：

{3: Fraction(-3,139), 4: Fraction(-17,139), 5: Fraction(-9,139)} 

---

更新：

方法の助けを借りて、

d = {0: {1: Fraction(7, 12), 3: Fraction(5, 12)}, 1: {0: Fraction(2, 5), 2: Fraction(3, 5)}, 2: {1: Fraction(1, 1)}} 

end_points = [3] 

私は私のキーに向けてパス[0, 3]を計算することができていますが、問題は、私は値1にキー0のループ値を計算することができていますし、その逆が、キー1は、キーと別のループを持っています2と私はサブループを含める方法の問題に直面している。

loop_list = [v for v,k in d.items() if source in k and v in d[source]] # considering 0 as source 

にこれを考慮する必要がある2キーのキー1である1のサブ結果を計算されない：

私が試みました。

Answer 1

（あなたは言いませんでしたが、あなたの例は0は、すべてのパスの出発点であることを示唆している。）

を使用すると、エンドポイントごとに単一の答えを期待している場合、あなたは何を使用するか、パスを決定する必要があります複数の選択肢があるとき。通常のケースはshortest path problemです。適切な定義が「最短」（おそらくステップ数または製品を最小限に抑える必要がある場合）を識別できる場合に適用されます。

最短経路が段階的に測定される場合（可能な製品が複数残っている可能性があります）、これはBFSで解決されます。適応するのは簡単なはずの実装があります。 Python標準ライブラリの最も単純なキューはcollections.dequeです。各ノードをエンキューするときは、そのポイントまでの製品（つまり1 for the initial node）を格納しておくことで、エンドポイントに達すると製品を知ることができます。すべてのエンドポイントが発生するまで作業を続けます。

製品を最小化する場合は、Dijkstra's algorithmが最初の距離を1（もう一度）に変更し、重みを追加するのではなく、乗算するようにします。 Python標準ライブラリは、heapqモジュールを介して必要な優先度キューを提供します。

Answer 2

あなたは有向グラフについて説明しています。 networkxあなたのすべてのグラフ理論のニーズにお応えします！

import networkx as nx 
from fractions import Fraction 
d = {0: [(1, 10), (5, 9)], 1: [(0, 14), (3, 3), (4, 17)]} 

G = nx.DiGraph() 

for n1,n2s in d.items(): 
    for n2,weight in n2s: 
    G.add_edge(n1, n2, weight=weight) 

start_point = 0 
for end_point in [2, 3, 4, 5]: 
    if end_point in G: 
    path = nx.shortest_path(G,start_point, end_point) 
    print("Path : %s " % path) 
    product = 1 
    for n1, n2 in zip(path, path[1:]): 
     product *= G.get_edge_data(n1,n2)['weight'] 
    print("Product : %d " % product) 
    print() 

これは、出力：

d = {0: {1: Fraction(7, 12), 3: Fraction(5, 12)}, 1: {0: Fraction(2, 5), 2: Fraction(3, 5)}, 2: {1: Fraction(1, 1)}} 

G = nx.DiGraph() 

for n1,n2s in d.items(): 
    for n2,weight in n2s.items(): 
    G.add_edge(n1, n2, weight=weight) 

start_point = 0 
for end_point in [2, 3, 4, 5]: 
    if end_point in G: 
    path = nx.shortest_path(G,start_point, end_point) 
    print("Path : %s " % path) 
    product = 1 
    for n1, n2 in zip(path, path[1:]): 
     product *= G.get_edge_data(n1,n2)['weight'] 
    print("Product : %r " % product) 
    print() 

それは出力：今

Path : [0, 1, 2] 
Product : Fraction(7, 20) 

Path : [0, 3] 
Product : Fraction(5, 12) 

あなたの第二の例については

Path : [0, 1, 3] 
Product : 30 

Path : [0, 1, 4] 
Product : 170 

Path : [0, 5] 
Product : 9 

、あなただけのグラフの初期化を変更する必要があります、あなたが使っているライブラリーであれ、陽性画分は常に陽性画分となる。

Answer 3

from fractions import Fraction 

loop_probability = lambda x : Fraction(1, 1-x) 

def find_all_paths(next_stage_probability, start, end, path=[]): 
    path = path + [start] 
    if start == end: 
     return [path] 
    if not next_stage_probability.__contains__(start): 
     return [] 
    paths = [] 
    for node in next_stage_probability[start]: 
     if node not in path: 
      newpaths = find_all_paths(next_stage_probability, node, end, path) 
      for newpath in newpaths: 
       paths.append(newpath) 
    return paths 

terminals = [2,3,4,5] 
next_stage_probability = {0: {1: Fraction(1, 2), 5: Fraction(1, 2)}, 1: {0: Fraction(4, 9), 3: Fraction(1, 3), 4: Fraction(2, 9)}} 
d = {0: [1, 5], 1: [0, 3, 4], 2: [], 3: [], 4: [], 5: []} 

paths_to_terminal = {} 
for terminal in terminals: 
    paths_to_terminal[terminal] = find_all_paths(next_stage_probability=next_stage_probability, start=0, end=terminal) 

# this is important stage where next_stage_probability is your tree and you need to calculate probability to reach to states in terminals which are values 0 rows in matrix 
terminal_probability = {} 
for terminal_state in paths_to_terminal: 
    if paths_to_terminal[terminal_state]: 
     probability_for_this_terminal = 0 
     considered_loop = [] 
     for path in paths_to_terminal[terminal_state]: 
      this_path_probability = 1 
      for x in range(len(path)-1): 
       source, destination = path[x], path[x+1] 
       current_to_next = next_stage_probability[source][destination] 
       loop_list = [v for v,k in next_stage_probability.items() if source in k and v in next_stage_probability[source]] 
       # loop_list = calculate_loop_states([source], next_stage_probability) 
       this_path_probability = this_path_probability * current_to_next 
       # print(path, (source, destination),loop_list, this_path_probability) 
       if loop_list: 
        for loop_state in loop_list: 
         # print((source, loop_state)) 
         if not considered_loop.__contains__((source, loop_state)) and not considered_loop.__contains__((loop_state, source)): 
          # print(Fraction(next_stage_probability[source][loop_state]), next_stage_probability[loop_state][source]) 
          # print(type(next_stage_probability[source][loop_state]), type(next_stage_probability[loop_state][source])) 
          loop_val = next_stage_probability[source][loop_state] * next_stage_probability[loop_state][source] 
          this_path_probability = this_path_probability * loop_probability(loop_val) 
          considered_loop.append((source, loop_state)) 
       # print(this_path_probability) 
      probability_for_this_terminal = probability_for_this_terminal + this_path_probability 
      terminal_probability[terminal_state] = probability_for_this_terminal 
    else: 
     terminal_probability[terminal_state] = Fraction(0) 
print(terminal_probability) 

私はそれがあなたを助けてくれることを願っています。