• Dev
  • 20th
  • Tips
  • English
  • Favorites
  • Others
temp

a deck for makers but poor

Buoy法

2016/10/11 by IKIX_temp

 仕事でアルゴリズムを考える機会があった.生徒のうち互いに兄弟であることを登録する機能を作っている.たとえば,AさんとBさんが兄弟であることをA⇔Bと表す.A⇔BとA⇔Cを登録したとき,自動でB⇔Cを登録できれば便利である.そのとき使うアルゴリズムを「ケビン=ベーコン クエリ」という.「6次の隔たり」で有名なケビン=ベーコンである.
 N人兄弟のクリークを家族Fとよぶ.FのメンバーそれぞれにN-1人の兄弟がいる.グラフで書くと,FのノードがそれぞれN-1本のエッジを重複なく持つとき,Fは完全グラフになる.家族Fの値が分かれば,兄弟の数はN-1人とすぐにわかる.これを利用してケビン=ベーコンクエリを考えてみたが,うまくいかなかった.グループG1に兄弟のメンバーN1,N2…を登録したとき,互いをグループIDで認識する仕組みに落ち着いた(この仕組みはDB更新が高頻度で必要なので採用しなかった).
 その代わり,buoy法なるものを考案した.buoyとはブイすなわち「浮き」である.Aさんで登録してある兄弟数をA=count(A)と書く.BさんはB=count(B)個登録されてある.浮きは兄弟数の最大値Y=max{A,B,C..}である.この浮きが「水位」によって増加するところがbuoyの由来である.アルゴリズムは,
for(from A){
   if(Y>A){A to B}
   elseif(Y=A){endif}
}

 3人兄弟の場合,次の図のようになる.
buoy3
 4人兄弟のときは以下である.
buoy4
 つまり,buoyの最大値はN-1に過ぎないため,兄弟数を求めるにはbuoy法は最適な方法でもない.現在兄弟数を,家族Fが完全グラフであれば全兄弟登録済,完全グラフでなければ未登録兄弟ありとして開発している最中である.

カテゴリー: Tips タグ: アルゴリズム
← 本
アプリ空間 →

Search

Tags

20th century Angular AP ASD Git Google HTML5 iOS IoT JS LW MCSA MS MVC NFT Office PCインストラクター PHP Processing Python SQL Town UNIQLO UX Web Windows WP YouTube アルゴリズム グラフ理論 ゲノム栄養学 サーバ管理 デザイン デバイス ミニマリズム モバイル 信仰 声楽 情報建築 技能士 投資 政治 文学 日曜数学 本

Archive

Copyright © 2025 temp.

Omega WordPress Theme by ThemeHall