| rdfs:comment
| - Aproximační algoritmy je druh algoritmů používaných při řešení optimalizačního problému, kdy nepožadujeme nutně optimální řešení, ale spokojíme se i s řešením, které je optimálnímu velmi blízké. (cs)
- Ein Approximationsalgorithmus (oder auch Näherungsalgorithmus) ist in der Informatik ein Algorithmus, der ein Optimierungsproblem näherungsweise löst. Viele Optimierungsprobleme lassen sich mit exakten Algorithmen vermutlich nicht effizient lösen. Für solche Probleme kann es sinnvoll sein, wenigstens eine Lösung zu finden, die einer optimalen Lösung möglichst nahekommt.Als Maß für die Bewertung von Approximationsalgorithmen benutzt man die sogenannte Güte des Algorithmus. (de)
- 근사 알고리즘(approximation algorithm)은 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘을 의미한다. 이 알고리즘은 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해를 계산할 수 있다. 근사 알고리즘은 NP-완전 문제등 현재 알려진 빠른 최적화 알고리즘이 없을 문제에 대해 주로 사용된다. (ko)
- 近似アルゴリズム（きんじアルゴリズム、英: approximation algorithm）とは、組合せ最適化問題の近似解を得るためのアルゴリズムを言う。近似解とは、実行可能解（かつ問題の何らかの制約を満たす解）ではあるが、正解（厳密解）ではないものを言う。これは組合せ最適化問題の正解（すなわち最適解）であることが（厳密には）保証されないところの解を得るものである。なお、問題を変形した近似問題に対する正解を得るアルゴリズムも、元の問題に対する近似アルゴリズムと言える。 (ja)
- 在计算机科学和运筹学中，近似算法（英語：Approximation algorithm）是指能为最优化问题寻找近似解的算法，该类算法找到的近似解与最优解之间的差值需能证明不超过某个值。由于人们普遍猜测P≠NP，许多优化问题因此无法在多项式时间内得到精确解决。进而，理論計算機科學领域内自然而然地出现了试图在多项式时间复杂度内得到近似最优解的近似算法。在绝大多数情况下，近似算法得到的近似值位于最优解到最优解乘以某个特定的值之间，这个特定的值被称作近似比。不过，也有一些算法得到的近似值是在最优解到最优解加某个特定的值之间。 近似算法的设计及分析过程中都包含一系列的数学证明，以保证其最差情况效率仍可接受。这点也是它与模拟退火等启发式算法之间的不同之处，启发式算法通常能够找到一个比较好的近似解，但其设计及分析之初往往并不涉及最差情况效率的证明。 (zh)
- In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as (en)
- En ciencias de la computación e investigación de operaciones, un algoritmo de aproximación es un algoritmo usado para encontrar soluciones aproximadas a problemas de optimización. Están a menudo asociados con problemas NP-hard; como es poco probable que alguna vez se descubran algoritmos eficientes de tiempo polinómico que resuelvan exactamente problemas NP-hard, se opta por encontrar soluciones no-óptimas en tiempo polinomial. A diferencia de las , que usualmente solo encuentran soluciones razonablemente buenas en tiempos razonablemente rápidos, lo que se busca aquí es encontrar soluciones que está demostrado son de calidad y cuyos tiempos de ejecución están acotadas por cotas conocidas. Idealmente, la aproximación mejora su calidad para factores constantes pequeños (por ejemplo, dentro d (es)
- En informatique théorique, un algorithme d'approximation est une méthode permettant de calculer une solution approchée à un problème algorithmique d'optimisation. Plus précisément, c'est une heuristique garantissant à la qualité de la solution qui fournit un rapport inférieur (si l'on minimise) à une constante, par rapport à la qualité optimale d'une solution, pour toutes les instances possibles du problème. (fr)
- Nell'informatica e nella ricerca operativa, un algoritmo di approssimazione è un algoritmo usato per trovare soluzioni approssimate a problemi di ottimizzazione. Gli algoritmi di approssimazione sono spesso associati a problemi NP-difficili; poiché è improbabile che ci possano essere algoritmi esatti efficienti in tempo polinomiale che risolvono problemi NP-difficili, ci si accontenta di soluzioni subottimali in tempo polinomiale. Diversamente dall'euristica, che di solito trova soluzioni ragionevolmente buone in tempi ragionevolmente veloci, in questo caso si vogliono soluzioni di qualità dimostrabile e tempi di esecuzione con limiti dimostrabili. Idealmente, l'approssimazione è ottimale fino a un piccolo fattore costante (ad esempio entro il 5% della soluzione ottimale). Gli algoritmi di (it)
- Algorytmy aproksymacyjne – algorytmy służące do znajdowania przybliżonych rozwiązań problemów optymalizacyjnych. Stosuje się je zwykle do rozwiązywania problemów, dla których nie są znane szybkie algorytmy znajdujące rozwiązanie dokładne, na przykład dla problemów NP-zupełnych. (pl)
- Em ciências da computação e pesquisa operacional (PO), algoritmos de aproximação são algoritmos usados para encontrar soluções aproximadas em problemas de otimização. Algoritmos de aproximação são geralmente associados com problemas NP-difíceis, já que estes problemas não podem ser resolvidos em tempo polinomial. Também em alguns problemas resolvidos em tempo polinomial no qual o tamanho da entrada pode fazer com que mesmo algoritmos polinomiais sejam custosos, estão sendo cada vez mais usados algoritmos de aproximação. (pt)
- Аппроксимационный алгоритм — в исследовании операций алгоритм, использующийся для поиска приближённого решения оптимизационной задачи. Концепция аппроксимационного алгоритма была формализована в 1972-м году в статье Гарея, Грэхэма и Ульмана, а позднее Джонсоном.Аппроксимационные алгоритмы часто связаны с NP-трудными задачами, поскольку для них вряд ли найдётся эффективный алгоритм точного решения за полиномиальное время, так что имеет смысл попробовать найти близкое оптимальному решение.В отличие от эвристических алгоритмов, дающих достаточно хорошие решения за приемлемое время, аппроксимационные алгоритмы обеспечивают доказуемое качество решения в заранее определённых границах времени. В идеале аппроксимация даёт решение, отличающееся от оптимального на некоторый небольшой множитель (напр (ru)
- В дослідженні операцій під апроксимаційним алгоритмом розуміють алгоритм, що використовується для пошуку наближеного розв'язку оптимізаційної задачі. Концепція апроксимаційного алгоритму формалізовано 1972 року в статті , Грема і Ульмана, а пізніше Джонсоном. Апроксимаційні алгоритми часто пов'язані з NP-складними задачами, оскільки для них навряд чи знайдеться ефективний алгоритм точного розв'язування за поліноміальний час, так що є сенс спробувати знайти близький до оптимального розв'язок. (uk)
|
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
![[RDF Data]](/fct/images/sw-rdf-blue.png)