No.2ベストアンサー
- 回答日時:
情報学あるいはビッグデータの問題中の
複雑ネットワークの問題です。キーワードに「」を付けましたので、
自分で調べてみて下さい。
各ノードは、n次元の特徴(たとえば漢字の画数(線分数)、
端点数、穴数、交点数、部首数のような)を持っていて、
それらの特徴がどのくらい近いかで、線が引いてあります。
(フェイスブックなら、共通の趣味・応援するサッカーチームなど
を持つ友達です)
多くのパスが出ているノードを「ハブ」と言います。
希望のノードに行くのに、平均6ホップで行けると言われています。
これを「スモールワールド性」と言います。
(友達の友達をたどっていくと、6人で世界中とつながります)
今、「クエリー(処理要求)」の部首数が分かったら、
(仮にハブが部首に依存してできているとします)
そのハブから探索を始めて、その漢字がなにかを突き止めます。
これを「類似探索」問題といいます。
(普通、漢和辞典は部首で引きますよね)
このように、たとえば自動読み取りソフトを作る時、
漢字のパターンマッチングを
いかに高速化するかというときの、基本になる問題がこれです。
(別の見方をすれば、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
平均を下げるには、平均を上回るホップ数を下げればよいが、
最も効果があるのは、4ホップを1ホップにすることなので、
A-E,A-Gのどちらかに線を入れればよいです。
しかし、多くの現実問題では、探索時間の問題を解決できません。
時として、離れ孤島のAをCに結び付けることを考えます。
こうすると、多くのノードが三角形に含まれるようになります。
この三角形を「クラスタ」と言います。
クラスタ性と言われる性質は、類似探索問題では重要です。
(フェイスブックなら、共通の知人がいるという性質です)
なお、どうやって平均を下げるかですが、具体的には、
変数(観測する特徴)を増やします。
フェイスブックなら、好きな歌手とか、いわゆるタグを
増やすと類似性が出てくることが多いです。
この回答へのお礼
お礼日時:2013/08/14 13:49
ご丁寧にご回答頂いてありがとうございました。
本当にわかりやすいです。
やはり情報学でしたか。キーワードをきちんと調べて
勉強したいと思います。
No.3
- 回答日時:
#2です。
訂正です。平均を下げる問題を間違えました。
たとえば、B-E,C-E間に線を引くことによって
Aがらみ、Bがらみがまとめ下がることを見落としていました。
どっちが効果があるかは、やってみて下さい。
一般的解法としては、各ノードの空間座標から
距離の式(ユークリッド距離ではない)を立てておいて、
新たな定義(この場合は軸)を与えながらコスト計算することになりますが、
問題が大きくなると計算時間爆発が起きます。
この回答へのお礼
お礼日時:2013/08/14 13:52
計算したところBE、CEよりやはりAEかAGの方が最も平均値を減らせるのです。
ここは一般的なやり方ではなく、直感でなりそうなつなぎ方を幾つか計算して
比較した方が早いですかな。
No.1
- 回答日時:
これは問題がおかしい.
そもそもノード間の線分が何を意味するか書いてないし, 「全ノードの最小移動コストの平均値」というのもどう解釈していいのかがわからない. 「『全ノードの最小移動コスト』の平均値」という意味なら「全ノードの最小移動コスト」を定義しなきゃならないし, 「全ノードの『最小移動コストの平均値』」なら「最小移動コストの平均値」とは何ぞやってことになる.
さらにいえば, 「最小移動コスト」が数字で与えられていない以上「最小移動コストの平均値を最も減少させる」といわれてもどうにもならない.
と指摘はするけど, 「この手の問題をやったことがなくてどうやってやればいいかも分かりません」がおかしいってことは理解できてる?
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
- ・ゆるやかでぃべーと タイムマシンを破壊すべきか。
- ・歩いた自慢大会
- ・許せない心理テスト
- ・字面がカッコいい英単語
- ・これ何て呼びますか Part2
- ・人生で一番思い出に残ってる靴
- ・ゆるやかでぃべーと すべての高校生はアルバイトをするべきだ。
- ・初めて自分の家と他人の家が違う、と意識した時
- ・単二電池
- ・チョコミントアイス
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
数学の問題がわからず困ってお...
-
至急!!二次関数について aは...
-
3で割ると2余り、7で割ると4余...
-
2次関数の応用
-
3次元での点群に対する最小二...
-
おしどり遊び(テイトの飛び石...
-
高校数学1の問題集に、2次関数...
-
ノードに関する問題
-
y=x^xの最小値
-
(a+c)(a-c)=(d+b)(d-b)でa,b,c,...
-
C#使っております。 numericupd...
-
f(x,y)の最小値
-
cを教えてください というか問...
-
三角関数の問題なのですが257の...
-
持続係数
-
二次関数の決定。
-
最小二乗多項式
-
最小値を求める問題なんですけど…
-
なぜ自然数を平方した数の約数...
-
最小値が-2でグラフは2点(0、0)...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
全員と同じグループを経験でき...
-
3次元での点群に対する最小二...
-
問題文は解答欄に載せます。 四...
-
2次関数の応用
-
三角関数の問題なのですが257の...
-
中学受験用の小5算数の問題です
-
高校数学1の問題集に、2次関数...
-
3で割ると2余り、7で割ると4余...
-
おしどり遊び(テイトの飛び石...
-
至急!!二次関数について aは...
-
2進数のバイアス表現について
-
x.>0ときγ(x)が最小値となるxの...
-
Xの二次関数 y=x ²ーmx+m(mは...
-
正の約数の個数が20個である最...
-
数学2です x>0のとき、x + 16/(...
-
n!が10の40乗で割り切れるとき...
-
最小値のルートについて。
-
y=x^xの最小値
-
ある数字を割り切れる最小の数...
-
min{a,b,c}って何?
おすすめ情報