問題
n個の宝を探す宝探しゲームをする。ノーヒントで宝iを探せる確率はp[i]
G[i][j]=Yならばi番目の宝が見つかればi番目の宝にj番目の宝の場所も記されているのでj番目の宝も見つけられる。
見つけられる宝の個数の期待値を求める問題。
解法
i番目の宝が見つかる確率をp[i]とおく。
G'[i][j]を「iからjまで連結しているならば1」として隣接行列を作る。
この時p[i]は「1- (iに到達できるnodeがどれも見つからない)」なので余事象で簡単に計算できる。
理論計算機科学 (Thoerotical Computer Science) の色んな定理やアルゴリズムを紹介していきます. 基本的には日本語の資料がほとんどないような知見を解説していきます.
凸解析のツールの一つとして凸共役という概念があります. $I\subseteq \mathbb{R}$上で定義された実関数$f$の凸共役とは \[ f^*(a) = \sup_{x\in I}\{ax - f(x)\} \] で定義されます. 通常は$I=\mathbb{R}$...
0 件のコメント:
コメントを投稿