|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 多 ： [た] 1. (n,pref) multi- ・ 多項式 ： [たこうしき] (n) polynomial ・ 式 ： [しき] 1. (n,n-suf) (1) equation 2. formula 3. expression 4. (2) ceremony 5. (3) style ・ 時 ： [とき] 1. (n-adv,n) (1) time 2. hour 3. (2) occasion 4. moment ・ 時間 ： [じかん] 1. (n-adv,n) time ・ 間 ： [けん, ま] 【名詞】 1. space 2. room 3. time 4. pause ・ 間近 ： [まぢか] 1. (adj-na,n-adv,n) proximity 2. nearness 3. soon 4. nearby ・ 近似 ： [きんじ] 1. (n,vs) approximate 2. proximate ・ 似 ： [に] (suf) takes after (his mother) ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana)
計算機科学において、多項式時間近似スキーム (polynomial-time approximation scheme, 以後PTASと呼ぶ) は(大抵NP困難であるような)最適化問題に対する近似アルゴリズムの一種である。 PTASは最適化問題のインスタンスとパラメータε > 0 を入力として受け取り、多項式時間内に最適解の 1 + ε倍以下の解を求めることのできるアルゴリズムである（最大化問題の場合は 1 - ε倍以上）。例えば、ユークリッド距離に基づく巡回セールスマン問題では、最適解の長さを''L''としたとき、高々(1 + ε)''L''の解を見つけることができる。〔Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.〕 PTASの実行時間は、εを固定すると、問題の大きさ ''n'' の多項式であることが求められるが、εに対しては定められていない。このため、実行時間が''O''(''n''1/ε) や ''O''(''n''exp(1/ε)) であっても、PTASである。 ==変形== ===決定的=== PTASアルゴリズムがある現実的な問題は、εを小さくすると多項式の指数部が劇的に大きくなってしまう(例えば''O''(''n''(1/ε)!)のように)。この問題に対処するひとつの方法が効率的な多項式時間近似スキーム (efficient polynomial-time approximation scheme, またはEPTAS)と呼ばれる、実行時間が ''c'' をεと独立な定数として、''O''(''n''''c'') であるようなアルゴリズムである。この場合、どのようなεを選んでも問題の大きさは実行時間に与える影響は等しくなる。しかし、''O''記法における定数はεに対して任意に大きくなりうる。これに対してより強い制約として、実行時間が問題の大きさ ''n'' と 1/ε両方の多項式時間であるものを完全多項式時間近似スキーム (fully polynomial-time approximation scheme または FPTAS) と呼ぶ。 ナップサック問題はFPTASがある問題の例である. 多項式的に有界な目的関数を持つどんな強度にNP困難な最適化問題も、P=NPでない限り、FPTASを持ち得ない。〔 しかし、逆は真ではない。例えば、P≠NPのとき、2つの制約をもつナップサック問題はFPTASを持たないが、たとえ目的関数が多項式的に有界の場合でも強度にNP困難ではない。 P=NPでない限り、FPTAS ⊊ PTAS ⊊ APXが成り立つ。すなわち、同じ仮定の下で、APX困難な問題はPTASを持たない。 別の決定論的なPTASの変形として、準多項式時間近似スキーム (quasi-polynomial-time approximation scheme または QPTAS) がある。QPTASはある固定されたεに対しての時間複雑度を持つ。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「多項式時間近似スキーム」の詳細全文を読む スポンサード リンク
|