質問: can100さん,ご質問ありがとうございます. ・「全ての条件」とはどのような条件なのか?例(ハッシュ)の場合の結果例(組み合わせ)を明示すると回答えられやすいかと思います。 →上述の例では分かりにくいかもしれないので,簡単な例を挙げると, {[2, 3]=>2, [2, 4]=>2} の場合は, {1=>[nil, nil, 2, 0, 0], 2=>[nil, nil, 1, 1, 1], 3=>[nil, nil, 0, 2, 2]} のようなハッシュを返すということになります. keyはただの識別子でvalueの配列の添字がリンクに対応しています. つまり,{[2, 3]=>2, [2, 4]=>2} の場合は, リンク2でパケットロス2個,リンク3,4ではパケットロス0個. or リンク2,3,4でパケットロス1個ずつ. or リンク2でパケットロス0個,リンク3,4ではパケットロス2個. の3パターンが出力されます. ikedasさん,ご質問ありがとうございます. ・途中でパケットロスしているのに、そのパケットがどのリンクを通過するはずだったかは全てわかる、ということなんでしょうか。 →2分木のトポロジに対して,あるフローに沿ってパケットを全リンクにマルチキャストで通過させます.その後,各末端のポートに到着したパケット数から各リンクでのパケットロスのパターンを全て出力したいということです.
回答: すみません。回答ではありませんが、問題を以下のようにまとめてみました。 参考になれば幸いです。 以下「経路」は例示「[2, 3]=>2」の「[2, 3]」とします。 ``` E(m,n) = (Exist) 経路nがリンクmを含むか 0or1 LL(m) = (LinkLoss) リンクmのパケットロス数 0以上の整数 TL(n) = (TotalLoss) 経路nの合計ロス数 ただし m = 1...M = 対象のリンク総数 n = 1...N = 与えられた経路(ハッシュ)の要素数 ``` とすると ``` E(1,1)*LL(1) + E(2,1)*LL(2) + ... + E(M,1)*LL(M) = TL(1) E(1,2)*LL(1) + E(2,2)*LL(2) + ... + E(M,2)*LL(M) = TL(2) : E(1,N)*LL(1) + E(2,2)*LL(2) + ... + E(M,N)*LL(M) = TL(N) ``` というM元連立一次方程式を満たすLL(m)の解(組み合わせ)をすべて求める。 という問題に表せるかと思います。 >変数の数が動的に変化するため という部分を`E(m,n)`で表現してみました。 LMax = TL(1)~TL(N)の最大値 とすると 0 <= LL <= LMax は明らか?なので M,N,LMaxが小さければ、適切な枝刈+全探索でも解けそうな気がします。 2017/01/23追記 : 提示された例をpythonで単純に解いてみました。 ``` import itertools TL = (2,2) # TotalLoss 方程式の右辺値 E = ((1,1,0), (1,0,1)) # Exist 未使用のリンク(列)は除外してます。 M = len(E[0]) # LLの個数 N = len(TL) # 方程式の個数 LMax = max(TL) # LLの取りうる最大値 for LLs in itertools.product(range(LMax+1), repeat=M): # LLのすべての組み合わせ match = True for n in range(N): # 方程式毎にチェック left = 0 # 左辺値を算出 for m in range(M): left += E[n][m] * LLs[m] if left != TL[n]: # 式が成立しない match = False break if match: print( LLs) return 0 ``` 出力結果 ``` (0, 2, 2) (1, 1, 1) (2, 0, 0) ```