「統計学関連なんでもあり」の過去ログ---027

★ 正確確率計算とNP問題 ★

1951.　正確確率計算とNP問題　uchan　2004/01/22 (木) 10:18
└1953.　Re: 正確確率計算とNP問題　青木繁伸　2004/01/22 (木) 10:24
　└1958.　Re^2: 正確確率計算とNP問題　uchan　2004/01/22 (木) 16:54
　　└1959.　Re^3: 正確確率計算とNP問題　青木繁伸　2004/01/22 (木) 18:38
　　　└1965.　Re^4: 正確確率計算とNP問題　uchan　2004/01/23 (金) 10:11

1951.　正確確率計算とNP問題　uchan　　2004/01/22 (木) 10:18

ExactTest(正確確率計算)のHPよく利用させてもらっています

以前自分で周辺和を固定した状態で全ての場合を計算しようとした事がありますがセル数が多くなるととたんに膨大な計算量となるようです
自分はしらみつぶし法で調べたのですが,効率がよいとされるネットワークアルゴリズムもセル数が多くなるとかなり時間がかかると聞いた事があります

そこで以前から疑問に思っていたのですが,正確確率計算というのはいわゆるNP問題というものに属するものなんでしょうか

　　　　　[このページのトップへ]

1953.　Re: 正確確率計算とNP問題　青木繁伸　　2004/01/22 (木) 10:24

> 正確確率計算というのはいわゆるNP問題というものに属するものなんでしょうか

私は NP 問題というのはよく知らないのですが，
http://www.is.titech.ac.jp/~watanabe/myhome/NP.html
を見ると，かなりおおざっぱな定義のように見受けられ，そのようなことならばそうなのかなと思うくらいです。
NP 問題であるから何なのかというのも，わかりません。

　　　　　[このページのトップへ]

1958.　Re^2: 正確確率計算とNP問題　uchan　　2004/01/22 (木) 16:54

> NP 問題であるから何なのかというのも，わかりません。
私も専門が医療系でしたのでNP問題は詳しくはないのですが,インターネットに接続していない環境でも正確確率を計算する必要性に迫られて青木先生のHPを参考に自分でアルゴリズムを考えたはじめ，2×2のFisherのTsetから一般化しようとするととたんに難しくなり,パズルを解くような感じで一時期はまったのがきっかけでした。

NP問題だとすると原理的に簡単な解法はないでしょうからいつかモンテカルロ法とかで組んでみようと思った訳です。

とりあえず今はネットワーク環境が職場に整っているのでExactTestのページを活用させてもらっています。

統計ソフトが職場に無いのが問題ですが．．．

ありがとうございました

　　　　　[このページのトップへ]

1959.　Re^3: 正確確率計算とNP問題　青木繁伸　　2004/01/22 (木) 18:38

> インターネットに接続していない環境でも正確確率を計算する必要性に迫られて

R にある fisher.test 関数は，ネットワークアルゴリズムを使っているのだと思いますよ。
http://aoki2.si.gunma-u.ac.jp/lecture/Cross/extended-fisher-r.html
ただですし，オフラインですし，最適ではないですか？

　　　　　[このページのトップへ]

1965.　Re^4: 正確確率計算とNP問題　uchan　　2004/01/23 (金) 10:11

> ただですし，オフラインですし，最適ではないですか？
早速ダウンロードしました
処理が軽そうで使いこなすと何でも出来そうですね
いろいろ試しながら使ってみます(英語の統計用語の勉強にもなります)

ありがとうございます
取り急ぎお礼まで

　　　　　[このページのトップへ]