翻訳と辞書 Words near each other ・ カーマンライン ・ カーマン・ライン ・ カーマ・スートラ ・ カーマ・スートラ/愛の教科書 ・ カーマ・スートラ・レコード ・ カーマ・ポリス ・ カーマーカーのアルゴリズム ・ カーマーカーの内点アルゴリズム ・ カーマーカーの内点法 ・ カーマーカーの射影変換法 ・ カーマーカーアルゴリズム ・ カーマーカー法 ・ カーマーカー特許 ・ カーマーゼン ・ カーマーゼンの黒本 ・ カーマーゼンシャー ・ カーミシュリー ・ カーミット ・ カーミット (プロトコル) ・ カーミットのどろんこ大冒険 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク カーマーカーアルゴリズム ： ミニ英和和英辞書 カーマーカーアルゴリズム[かー] ===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ カー ： [かー] 　【名詞】 1. car　2. (n) car ・ ー ： [ちょうおん] 　(n) long vowel mark (usually only used in katakana) カーマーカーアルゴリズム （ リダイレクト：カーマーカーのアルゴリズム ） ： ウィキペディア日本語版 カーマーカーのアルゴリズム[ちょうおん] カーマーカーのアルゴリズム () とは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文は停止条件を満たすとループを抜ける。〕, $\backslash gamma$. $k\; \backslash leftarrow\; 0$ do while ''stopping criterion'' not satisfied $v^k\; \backslash leftarrow\; b-Ax^k$ $D\_v\; \backslash leftarrow\; \backslash operatorname(v\_1^k,\backslash ldots,v\_m^k)$〔行列の対角成分を代入。〕 $h\_x\backslash leftarrow\; (A^TD\_v^A)^c$ $h\_v\backslash leftarrow\; -Ah\_x$ if $h\_v\; \backslash ge\; 0$ then〔条件を満たす場合は、戻り値"unbounded"を返す。〕 return unbounded end if $\backslash alpha\; \backslash leftarrow\; \backslash gamma\backslash cdot\; \backslash min\backslash$ $x^\backslash leftarrow\; x^k\; +\; \backslash alpha\; h\_x$ $k\backslash leftarrow\; k+1$ end do 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「カーマーカーのアルゴリズム」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Karmarkar's algorithm 」があります。 スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.