翻訳と辞書
Words near each other
・ カーマ・スートラ
・ カーマ・スートラ/愛の教科書
・ カーマ・スートラ・レコード
・ カーマ・ポリス
・ カーマーカーのアルゴリズム
・ カーマーカーの内点アルゴリズム
・ カーマーカーの内点法
・ カーマーカーの射影変換法
・ カーマーカーアルゴリズム
・ カーマーカー法
カーマーカー特許
・ カーマーゼン
・ カーマーゼンの黒本
・ カーマーゼンシャー
・ カーミシュリー
・ カーミット
・ カーミット (プロトコル)
・ カーミットのどろんこ大冒険
・ カーミット・シントロン
・ カーミット・ビーハン


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

カーマーカー特許 : ミニ英和和英辞書
カーマーカー特許[かー]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

カー : [かー]
 【名詞】 1. car 2. (n) car
: [ちょうおん]
 (n) long vowel mark (usually only used in katakana)
特許 : [とっきょ]
 【名詞】 1. special permission 2. patent 
: [きょ, もと]
  1. (adv) under (esp. influence or guidance) 

カーマーカー特許 ( リダイレクト:カーマーカーのアルゴリズム ) : ウィキペディア日本語版
カーマーカーのアルゴリズム[きょ, もと]
カーマーカーのアルゴリズム () とは1984年ナレンドラ・カーマーカーにより発見された線形計画問題の解法である。このアルゴリズムは、しばしば、カーマーカー法 (Karmarkar's method) とも呼ばれる。また、このアルゴリズムを発明とする特許米国日本で出願されたので、請求特許は時折カーマーカー特許 (Karmarkar's patent) とも呼称される。
カーマーカーのアルゴリズムは、線形計画問題における適度に効率が良い多項式時間アルゴリズムとしては初のものである。も多項式時間アルゴリズムであるが、実際の効率は良くない。
カーマーカーのアルゴリズムは内点法の一種である。内点法は単体法とは異なり、想定解が実行可能集合
"feasible set"。または"feasible region"(「実行可能領域」)とも呼ばれる。"feasible"は「許容」、「制約」などとも訳される。を参照。
〕の境界には存在せず、実行可能集合の内部を通って最適解optimal solution)に漸近する。それだけではなく、このアルゴリズムは、以前のアルゴリズムに比べ、有限小数を繰り返し利用することによる最適解への漸近処理を改善しており、かつ、有意なデータでもって最適解へ収束させる〔
〕。
== アルゴリズム ==
行列 Aベクトル b に対し、以下のな線形計画問題を考える。
: maximize ''c''''T''''x''
: subject to ''Ax'' ≤ ''b''.
すなわち、
: 条件 ''Ax'' ≤ ''b'' の下で、
: ''c''''T''''x'' を最大にするベクトル ''x'' を求める。
このアルゴリズムはその時点での最適化実行可能方向 (feasible direction toward optimality) を決定し、因子γは 0 < γ ≤ 1 の範囲でスケールバックする。
カーマーカーのアルゴリズムは複雑である。アフィン・スケーリング法と呼ばれる簡略化されたバージョンが、カーマーカーとは別の人物により提案、解析されている〔
〕。このアルゴリズムは以下のように簡潔に示される。ただし、アフィン・スケーリング・アルゴリズムは実用上効率が良いが、多項式時間アルゴリズムではない。
Input: A, b, c, x^0, ''stopping criterion''〔停止条件。アルゴリズムのとおり、while文は停止条件を満たすとループを抜ける。〕, \gamma.
k \leftarrow 0
do while ''stopping criterion'' not satisfied
v^k \leftarrow b-Ax^k
D_v \leftarrow \operatorname(v_1^k,\ldots,v_m^k)〔行列の対角成分を代入。〕
h_x\leftarrow (A^TD_v^A)^c
h_v\leftarrow -Ah_x
if h_v \ge 0 then〔条件を満たす場合は、戻り値"unbounded"を返す。〕
return unbounded
end if
\alpha \leftarrow \gamma\cdot \min\
x^\leftarrow x^k + \alpha h_x
k\leftarrow k+1
end do

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「カーマーカーのアルゴリズム」の詳細全文を読む

英語版ウィキペディアに対照対訳語「 Karmarkar's algorithm 」があります。




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.