Weblio辞書辞典>辞書･百科事典>ﾗｽﾍﾞｶﾞｽ法>ﾗｽﾍﾞｶﾞｽ法の1ﾍﾟｰｼﾞ目
ﾗｽﾍﾞｶﾞｽ法とは?
ｽﾎﾟﾝｻｰﾘﾝｸ
無料で債務整理相談《宇都宮》
栃木県宇都宮の高橋洋一司法書士事務所｡無料相談､夜間土日も対応可能
ｱﾒﾘｶの法律のABC
弁護士がｵﾝﾗｲﾝで待機中です｡どんな質問にも的確にお答えします｡
ﾗｽﾍﾞｶﾞｽ法（英: Las Vegas algorithm）は､間違った解を返さない乱択ｱﾙｺﾞﾘｽﾞﾑを指す｡
すなわち､解を返すときは常に正しく､正しい解が求められない場合は失敗を通知する｡
換言すれば､ﾗｽﾍﾞｶﾞｽ法は答え（解）については賭けをせず､計算に使用するﾘｿｰｽ量についてのみ賭けをする｡
単純な例としてﾗﾝﾀﾞﾑ化されたｸｲｯｸｿｰﾄがある｡
ﾋﾟﾎﾞｯﾄ値をﾗﾝﾀﾞﾑに選択するｸｲｯｸｿｰﾄではｿｰﾄ結果は常に正しい｡
一般に無作為な情報に対してﾗｽﾍﾞｶﾞｽ法を使う際には､定義上､実行時間の上限を設けることが多い｡
ﾗｽﾍﾞｶﾞｽ法で多項式時間で解けると期待される決定問題の複雑性ｸﾗｽを ZPP と呼ぶ｡
次のような性質がある｡
これは､ﾗｽﾍﾞｶﾞｽ法に属するｱﾙｺﾞﾘｽﾞﾑを構築する方法と密接に関係している｡RPｸﾗｽは､多項式時間の乱択ｱﾙｺﾞﾘｽﾞﾑがある決定問題のｸﾗｽであり､解が｢no｣であるときは常に正しいが､解が｢yes｣であるときは間違っている可能性がある｡
そのようなｱﾙｺﾞﾘｽﾞﾑが､ある問題とその補問題（｢yes｣と｢no｣が逆転した問題）について存在するとき､その2つのｱﾙｺﾞﾘｽﾞﾑを同時にかつ繰り返し実行するとする｡
すると､最終的にどちらかで間違いのない解が得られる｡
これが多項式時間を期待できるﾗｽﾍﾞｶﾞｽ法のｱﾙｺﾞﾘｽﾞﾑを構築する標準的な方法である｡
ﾗｽﾍﾞｶﾞｽ法には最悪実行時間の上限が存在しないことに注意されたい｡
ｽﾎﾟﾝｻｰﾘﾝｸ
ﾗｽﾍﾞｶﾞｽ のﾎﾃﾙ簡単予約
ﾈｯﾄで即時予約､安心の現地払い割引料金で幅広いﾎﾃﾙﾁｮｲｽ｡
ﾗｽﾍﾞｶﾞｽ発ｸﾞﾗﾝﾄﾞｷｬﾆｵﾝ
各種ｸﾞﾗﾝﾄﾞｷｬﾆｵﾝﾂｱｰｷｬﾝﾍﾟｰﾝ価格！見逃したら損！
楽に探せる!楽ﾜｰﾄﾞ
ﾍﾟｰｼﾞ(1/2)
次ﾍﾟｰｼﾞ≫