Property |
Value |
dbo:abstract
|
- 計算機科学において、多項式時間近似スキーム(英: polynomial-time approximation scheme、PTAS)は(大抵NP困難であるような)最適化問題に対する近似アルゴリズムの一種である。 PTASは最適化問題のインスタンスとパラメータ を入力として受け取り、多項式時間内に最適解の 倍以下の解を求めることのできるアルゴリズムである(最大化問題の場合は 倍以上)。例えば、ユークリッド距離に基づく巡回セールスマン問題では、最適解の長さを としたとき、高々 の解を見つけることができる。 PTASの実行時間は、 を固定すると、問題の大きさ の多項式であることが求められるが、 に対しては定められていない。このため、実行時間が や オーダーであっても、PTASである。 (ja)
- 計算機科学において、多項式時間近似スキーム(英: polynomial-time approximation scheme、PTAS)は(大抵NP困難であるような)最適化問題に対する近似アルゴリズムの一種である。 PTASは最適化問題のインスタンスとパラメータ を入力として受け取り、多項式時間内に最適解の 倍以下の解を求めることのできるアルゴリズムである(最大化問題の場合は 倍以上)。例えば、ユークリッド距離に基づく巡回セールスマン問題では、最適解の長さを としたとき、高々 の解を見つけることができる。 PTASの実行時間は、 を固定すると、問題の大きさ の多項式であることが求められるが、 に対しては定められていない。このため、実行時間が や オーダーであっても、PTASである。 (ja)
|
dbo:wikiPageExternalLink
| |
dbo:wikiPageID
| |
dbo:wikiPageLength
|
- 3762 (xsd:nonNegativeInteger)
|
dbo:wikiPageRevisionID
| |
dbo:wikiPageWikiLink
| |
prop-ja:wikiPageUsesTemplate
| |
dct:subject
| |
rdfs:comment
|
- 計算機科学において、多項式時間近似スキーム(英: polynomial-time approximation scheme、PTAS)は(大抵NP困難であるような)最適化問題に対する近似アルゴリズムの一種である。 PTASは最適化問題のインスタンスとパラメータ を入力として受け取り、多項式時間内に最適解の 倍以下の解を求めることのできるアルゴリズムである(最大化問題の場合は 倍以上)。例えば、ユークリッド距離に基づく巡回セールスマン問題では、最適解の長さを としたとき、高々 の解を見つけることができる。 PTASの実行時間は、 を固定すると、問題の大きさ の多項式であることが求められるが、 に対しては定められていない。このため、実行時間が や オーダーであっても、PTASである。 (ja)
- 計算機科学において、多項式時間近似スキーム(英: polynomial-time approximation scheme、PTAS)は(大抵NP困難であるような)最適化問題に対する近似アルゴリズムの一種である。 PTASは最適化問題のインスタンスとパラメータ を入力として受け取り、多項式時間内に最適解の 倍以下の解を求めることのできるアルゴリズムである(最大化問題の場合は 倍以上)。例えば、ユークリッド距離に基づく巡回セールスマン問題では、最適解の長さを としたとき、高々 の解を見つけることができる。 PTASの実行時間は、 を固定すると、問題の大きさ の多項式であることが求められるが、 に対しては定められていない。このため、実行時間が や オーダーであっても、PTASである。 (ja)
|
rdfs:label
|
- 多項式時間近似スキーム (ja)
- 多項式時間近似スキーム (ja)
|
owl:sameAs
| |
prov:wasDerivedFrom
| |
foaf:isPrimaryTopicOf
| |
is dbo:wikiPageWikiLink
of | |
is owl:sameAs
of | |
is foaf:primaryTopic
of | |