翻訳と辞書
Words near each other
・ 多項式の重根
・ 多項式函数
・ 多項式列
・ 多項式基底
・ 多項式変換
・ 多項式方程式
・ 多項式時間
・ 多項式時間アルゴリズム
・ 多項式時間変換
・ 多項式時間帰着
多項式時間近似スキーム
・ 多項式時間還元
・ 多項式環
・ 多項式行列
・ 多項式補間
・ 多項式関数
・ 多項式階層
・ 多頭ノズル噴霧機
・ 多頭帯
・ 多頭条虫


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

多項式時間近似スキーム : ミニ英和和英辞書
多項式時間近似スキーム[たこうしきじかんきんじすきーむ]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

: [た]
  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はある固定されたεに対してn^の時間複雑度を持つ。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「多項式時間近似スキーム」の詳細全文を読む




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

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