Rubyでの連立方程式の複数解出力に関して

Question

###前提・実現したいこと
Rubyでネットワーク計測シミュレーションのプログラムを作っています．
ある情報が得られたときに考えられるパケットロスの全パターンを出力したいのですが，
うまくいかず困っております．

###発生している問題
得られる情報は以下のようなハッシュです．
{[2, 4, 8, 9]=>1, [2, 4, 5]=>1, [2, 6, 7]=>3, [2, 6, 10, 12, 13]=>3}
keyとなる配列はリンクの識別子を示し，valueはロスしたパケットの数です．
一番右の例で言えば，リンク2,4,8,9を通過し，1つのパケットがロスしたことを表します．
つまり，このハッシュ内，全ての条件を満たす，パケットロスの組み合わせを全て取得したいということになります．
例えば，配列の添字をリンクに対応させて，全パターンの配列を出力する等．

###試したこと
おそらく連立方程式を解くことになると思うのですが，
Array#productとselectを組み合わせて，
全パターンを出力しようとしましたが，
変数の数が動的に変化するため，
断念いたしました．

#追記
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分木のトポロジに対して，あるフローに沿ってパケットを全リンクにマルチキャストで通過させます．その後，各末端のポートに到着したパケット数から各リンクでのパケットロスのパターンを全て出力したいということです．

Comments

[can110]

「全ての条件」とはどのような条件なのか？例（ハッシュ）の場合の結果例（組み合わせ）を明示すると回答えられやすいかと思います。

[ikedas]

途中でパケットロスしているのに、そのパケットがどのリンクを通過するはずだったかは全てわかる、ということなんでしょうか。

Answer 1

面白そうなので書いてみた
いいアイディアが思いつけばよかったですが、ほぼ総当たりになりました

@routes = {[2, 3]=>2, [2, 4]=>2}

@every_nodes = [] # すべてのnodeを保持する変数
@tmp_losts = {} # nodeごとのlost数を一時的に保存する変数

@routes.each do |route, _|
  @every_nodes += route
end
@every_nodes.uniq!

@max_lost = @routes.map(&:last).max # 最大lost数を保持
@global_index = 1 # 結果の添字用の変数

def coverall_pattern(nodes)
  return false unless check_over_lost # lost数を超えているものがあるかチェック
  if nodes.size == 0 && check_lost # tmp_losts内のすべてのnodeに数字位が割り当てられている && lost数が一致する
    ret = { @global_index => @every_nodes.map { |node| @tmp_losts[node] } }
    @global_index += 1
    return ret
  end
  return false if nodes.size == 0 # tmp_losts内のすべてのnodeに数字位が割り当てられている && lost数が一致しない

  (0..@max_lost).map do |i| # nodeごとにmax_lost以下の値で顕彰する
    clear_after_tmp_losts(nodes[1..-1])
    @tmp_losts[nodes.first] = i 
    coverall_pattern(nodes[1..-1])
  end.select(&:itself).flatten # falseの削除
end

# @tmp_lostsには入っている、渡されたnodesに割れ当てられている値を0にする
def clear_after_tmp_losts(nodes)
  nodes.each { |node| @tmp_losts[node] = 0 } 
end

# @tmp_lostsにセットしている値がroutesにあるlostの値を超えていないかチェック
def check_over_lost
  @routes.each do |nodes, lost|
    return false if nodes_sum(nodes) > lost
  end
  true
end

# routeごとのlostの合計値を取得
def nodes_sum(nodes)
  sum = 0
  nodes.each { |node| sum += @tmp_losts[node] || 0 }
  sum
end

coverall_pattern(@every_nodes)
# =>[{1=>[0, 2, 2]}, {2=>[1, 1, 1]}, {3=>[2, 0, 0]}]

なお、質問に書いてあるパターンしか試してないです。

Comments

[YukiFujimura]

だーいぶ返信が遅くなりましたが．．（笑）
このプログラムを実行するとエラーを吐かれませんか？
check_lostの定義やitselfでエラーを吐かれるのですが．

Answer 2

アイディアだけなのですが。

次のことを仮定します。

• パケットロスは各リンクで独立に起こる。
• パケットがある端点からある端点へ送られるとき、通過する各リンク上での配送方向は一意に定まる。

各リンクに成功スコアs[i]、失敗スコアf[i]を持たせます。iはリンクの番号です。

各パケットの通過リンク全てについて、疎通時は成功スコア、パケットロスなら失敗スコアを加算します (加算量は重みづけした方がいいでしょう。たとえば、通過し得るリンクが5つならそれらのリンク毎に0.2など)。

充分な数のパケットについてスコア加算を行なった後には、各リンクの推定故障確率を次の式で計算できます。

d[i] = f[i] / (s[i] + f[i])

もちろん、これは真の確率を与えるとは限りません。が、他とくらべて有意に高い値を示すリンクはパケットロスが多く発生している可能性があると考えられます (健全なリンクでもパケットロスはある程度起きるので、低い値を示すリンクは無視してもよいかも知れません)。

---

より真の値に近い確率を求めたければ、なんらかのモデルをもとに各リンクのスコアから全経路の成功/失敗率を計算し、実測データとずれのある経路に対する「学習」によってスコアを修正することも考えられます。しかし、適切なモデルを構築することは難しいのではないかと思います。

また、どういう方法にせよ、ネットワークのトポロジによってはパケットロスの起きたリンクを絞り込めない場合もあると考えられます。

以上、お望みの回答ではないと思いますが。

Answer 3

ちょっと自信はないのですが、この問題、多項式時間で解けない（つまりNP）なのではないかと思います。総当りで解くしかないのではないでしょうか。

解けるかた求む。

Answer 4

すみません。回答ではありませんが、問題を以下のようにまとめてみました。
参考になれば幸いです。

以下「経路」は例示「[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)

Comments

[MasashiKimura]

そうなんです。こうなるんです。そうすると、ナップサック問題より難しい問題ということになります。

[MasashiKimura]

この問題で、LLが予めわかっている場合が、ナップサック問題なのです。。。

[can110]

あとはアルゴリズムの得意な方におまかせしたいと思いますw

[can110]

このシミュレーションの目的って結局リンク毎のロス（確率）分布を知りたいってことですよね？
であれば馬鹿正直に数え上げるのではなく、統計力学やエントロピーの手法で解くのが筋のような気がします。