ノードに関する問題

質問

以下のようなノードがあり、各ノード間の移動コストを考える。
なおノード A,Bの最小移動コストを X(A,B)と表す。
(1)全ノードの最小移動コストの平均値はいくらか。
(2)最小移動コストの平均値を最も減少させるために新たに 1 本の経路を引いた。
どのノード間に新たな経路を引けばよいか。

という問題です。

数学の問題を解く中でこの問題が出てきました。この手の問題をやったことがなくて
どうやってやればいいかも分かりません。
これは情報学ですか。

この問題の解き方をご存知の方、ご指導よろしくお願いします。

回答No.2

kamiyasiro · ベストアンサー

情報学あるいはビッグデータの問題中の
複雑ネットワークの問題です。キーワードに「」を付けましたので、
自分で調べてみて下さい。

各ノードは、n次元の特徴（たとえば漢字の画数（線分数）、
端点数、穴数、交点数、部首数のような）を持っていて、
それらの特徴がどのくらい近いかで、線が引いてあります。
（フェイスブックなら、共通の趣味・応援するサッカーチームなど
を持つ友達です）

多くのパスが出ているノードを「ハブ」と言います。
希望のノードに行くのに、平均６ホップで行けると言われています。
これを「スモールワールド性」と言います。
（友達の友達をたどっていくと、６人で世界中とつながります）

今、「クエリー（処理要求）」の部首数が分かったら、
（仮にハブが部首に依存してできているとします）
そのハブから探索を始めて、その漢字がなにかを突き止めます。

これを「類似探索」問題といいます。
（普通、漢和辞典は部首で引きますよね）
このように、たとえば自動読み取りソフトを作る時、
漢字のパターンマッチングを
いかに高速化するかというときの、基本になる問題がこれです。

（別の見方をすれば、ORの問題（最短経路問題）でもあります。
「中国郵便配達人問題」で探してみてください）

いま、X(y1,y2)において、y1，y2は可換であるので、
いま、7C2＝21　間の移動が考えられます。
面倒ですが、これを全て調べます。

X(A,B)=1
X(A,C)=2
X(A,D)=3
X(A,E)=4
X(A,F)=3
X(A,G)=4
X(B,C)=1
X(B,D)=2
X(B,E)=3
X(B,F)=2
X(B,G)=3
X(C,D)=1
X(C,E)=2
X(C,F)=1
X(C,G)=2
X(D,E)=1
X(D,F)=2
X(D,G)=1
X(E,F)=1
X(E,G)=1
X(F,G)=1

合計は41ですから、平均は41／21＝1.952

平均を下げるには、平均を上回るホップ数を下げればよいが、
最も効果があるのは、４ホップを１ホップにすることなので、
A－E，A－Gのどちらかに線を入れればよいです。

しかし、多くの現実問題では、探索時間の問題を解決できません。
時として、離れ孤島のAをCに結び付けることを考えます。
こうすると、多くのノードが三角形に含まれるようになります。
この三角形を「クラスタ」と言います。
クラスタ性と言われる性質は、類似探索問題では重要です。
（フェイスブックなら、共通の知人がいるという性質です）

なお、どうやって平均を下げるかですが、具体的には、
変数（観測する特徴）を増やします。
フェイスブックなら、好きな歌手とか、いわゆるタグを
増やすと類似性が出てくることが多いです。

お礼

ご丁寧にご回答頂いてありがとうございました。

本当にわかりやすいです。

やはり情報学でしたか。キーワードをきちんと調べて
勉強したいと思います。

回答No.3

kamiyasiro

#2です。訂正です。

平均を下げる問題を間違えました。
たとえば、B－E，C－E間に線を引くことによって
Aがらみ、Bがらみがまとめ下がることを見落としていました。

どっちが効果があるかは、やってみて下さい。

一般的解法としては、各ノードの空間座標から
距離の式（ユークリッド距離ではない）を立てておいて、
新たな定義（この場合は軸）を与えながらコスト計算することになりますが、
問題が大きくなると計算時間爆発が起きます。

お礼

計算したところBE、CEよりやはりAEかAGの方が最も平均値を減らせるのです。

ここは一般的なやり方ではなく、直感でなりそうなつなぎ方を幾つか計算して
比較した方が早いですかな。

回答No.1

Tacosan

これは問題がおかしい.

そもそもノード間の線分が何を意味するか書いてないし, 「全ノードの最小移動コストの平均値」というのもどう解釈していいのかがわからない. 「『全ノードの最小移動コスト』の平均値」という意味なら「全ノードの最小移動コスト」を定義しなきゃならないし, 「全ノードの『最小移動コストの平均値』」なら「最小移動コストの平均値」とは何ぞやってことになる.

さらにいえば, 「最小移動コスト」が数字で与えられていない以上「最小移動コストの平均値を最も減少させる」といわれてもどうにもならない.

と指摘はするけど, 「この手の問題をやったことがなくてどうやってやればいいかも分かりません」がおかしいってことは理解できてる?

お礼

ご回答ありがとうございました。