質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.35%

  • Ruby

    8182questions

    Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

  • ネットワーク

    561questions

    ネットワークとは、複数のコンピューター間を接続する技術です。インターネットが最も主流なネットワークの形態で、TCP/IP・HTTP・DNSなどの様々なプロトコルや、ルータやサーバーなどの様々な機器の上に成り立っています。

  • ハッシュ

    41questions

    ハッシュは、高速にデータ検索を行うアルゴリズムのことです。

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

受付中

回答 4

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 857

YukiFujimura

score 2

前提・実現したいこと

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • can110

    2017/01/20 15:59

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

    キャンセル

  • ikedas

    2017/01/20 22:36

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

    キャンセル

回答 4

0

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/01/20 18:52

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

    キャンセル

  • 2017/01/20 18:59

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

    キャンセル

  • 2017/01/20 18:59

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

    キャンセル

  • 2017/01/23 18:55

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

    キャンセル

0

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

解けるかた求む。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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

次のことを仮定します。

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

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

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

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

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

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


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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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

@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]}]

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/06/14 20:33

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

    キャンセル

同じタグがついた質問を見る

  • Ruby

    8182questions

    Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

  • ネットワーク

    561questions

    ネットワークとは、複数のコンピューター間を接続する技術です。インターネットが最も主流なネットワークの形態で、TCP/IP・HTTP・DNSなどの様々なプロトコルや、ルータやサーバーなどの様々な機器の上に成り立っています。

  • ハッシュ

    41questions

    ハッシュは、高速にデータ検索を行うアルゴリズムのことです。