| dbo:abstract
|
- 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)
- 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 an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are also many approximation algorithms that provide an additive guarantee on the quality of the returned solution. A notable example of an approximation algorithm that provides both is the classic approximation algorithm of Lenstra, Shmoys and Tardos for scheduling on unrelated parallel machines. The design and analysis of approximation algorithms crucially involves a mathematical proof certifying the quality of the returned solutions in the worst case. This distinguishes them from heuristics such as annealing or genetic algorithms, which find reasonably good solutions on some inputs, but provide no clear indication at the outset on when they may succeed or fail. There is widespread interest in theoretical computer science to better understand the limits to which we can approximate certain famous optimization problems. For example, one of the long-standing open questions in computer science is to determine whether there is an algorithm that outperforms the 1.5 approximation algorithm of Christofides to the metric traveling salesman problem. The desire to understand hard optimization problems from the perspective of approximability is motivated by the discovery of surprising mathematical connections and broadly applicable techniques to design algorithms for hard optimization problems. One well-known example of the former is the Goemans–Williamson algorithm for maximum cut, which solves a graph theoretic problem using high dimensional geometry. (en)
- 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. L'intérêt de tels algorithmes est qu'il est parfois plus facile de trouver une solution approchée qu'une solution exacte, le problème pouvant par exemple être NP-complet mais admettre un algorithme d'approximation polynomial. Ainsi, dans les situations où l'on cherche une bonne solution, mais pas forcément la meilleure, un algorithme d'approximation peut être un bon outil. (fr)
- 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 del 5% de la solución óptima). Los algoritmos de aproximación están siendo cada vez más utilizados para resolver problemas donde los algoritmos exactos de tiempo polinomial son conocidos pero demasiado costosos debido al tamaño de la entrada. Un ejemplo típico para un algoritmo de aproximación es uno para resolver el problema de la cobertura de vértices de la teoría de grafos: encontrar una arista no cubierta y añadir sus dos puntos finales a la cobertura de vértice, y repetir hasta que ya no queden aristas. Es claro que la cobertura resultante será a lo más dos veces del largo de la solución óptima. Este es un con un factor de 2. Los problemas NP-hard varían mucho en su aproximación; algunos, tales como el problema de la mochila, pueden ser aproximados mediante cualquier factor superior a 1 (tal familia de algoritmos de aproximación se conoce como o PTAS). Otros, como el problema de la clique, son imposibles de aproximar dentro de cualquier constante, o incluso factor polinomiales, a menos que P = NP. Los problemas NP-hard frecuentemente pueden expresarse como programación entera (PE) y ser resueltos exactamente en tiempo exponencial. Muchos algoritmos de aproximación surgen de la relajación de la programación lineal (PL), propia de la programación entera. No todos los algoritmos de aproximación son adecuados para todas las aplicaciones prácticas. A menudo utilizan resolvedores (solvers) de IP, LP y programación semidefinida, estructuras de datos complejas o técnicas de algoritmos sofisticadas que tienden a dificultar los problemas de implementación. Además, algunos algoritmos de aproximación poseen tiempos de ejecución poco prácticos, incluso a pesar de ser polinómicos, como por ejemplo, del orden de O(n2000). Sin embargo, a pesar de esto último, existen problemas donde los altos tiempos de ejecución y costos de memoria pueden justificarse, tales como los relacionados con la biología computacional, ingeniería financiera, la planificación del transporte, y la gestión de inventario. En estos escenarios, se debe competir contra las correspondientes formulaciones de programación entera directa. Otra limitación de la aproximación es que esta solo es aplicable a los problemas de optimización, y no a los problemas de decisión en estado "puro", tales como SAT (a pesar de que es posible representar versiones de optimización para tales problemas, como el respectivo ). (es)
- 근사 알고리즘(approximation algorithm)은 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘을 의미한다. 이 알고리즘은 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해를 계산할 수 있다. 근사 알고리즘은 NP-완전 문제등 현재 알려진 빠른 최적화 알고리즘이 없을 문제에 대해 주로 사용된다. (ko)
- 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 approssimazione sono usati sempre di più per problemi dove gli algoritmi esatti in tempo polinomiale sono noti ma risultano troppo costosi a causa della dimensione dell'input. Un esempio tipico di un algoritmo di approssimazione è quello per la nei grafi: trovare uno spigolo scoperto e aggiungere "entrambi" gli estremi alla copertura dei vertici, finché non ne rimane nessuno. È chiaro che la copertura risultante è al massimo due volte più grande di quella ottimale. Questo è un con un fattore di 2. I problemi NP-difficili variano grandemente nella loro approssimabilità; alcuni, come il , può essere approssimato entro un qualsiasi fattore maggiore di 1 (tale famiglia di algoritmi di approssimazione è chiamata spesso schema di approssimazione in tempo polinomiale o PTAS). Altri sono impossibili da approssimare entro qualsiasi costante, o perfino fattore polinomiale, a meno che P = NP, come il . I problemi NP-difficili spesso possono essere espressi come programmi interi (integer programs, IP) e risolti esattamente in tempo esponenziale. Molti algoritmi di approssimazione emergono dal del programma intero. Non tutti gli algoritmi di approssimazione sono adatti per tutte le applicazioni pratiche. Spesso usano risolutori IP/LP/semidefiniti, strutture dati complesse o tecniche algoritmiche sofisticate che conducono a problemi di difficile implementazione. Inoltre, alcuni algoritmi di approssimazione hanno tempi di esecuzione poco pratici anche se sono in tempo polinomiale, ad esempio O(n2000). Tuttavia lo studio di algoritmi anche molto costosi non è una ricerca completamente teorica, in quanto possono fornire preziose intuizioni. Un esempio classico è il PTAS iniziale per il TSP euclideo dovuto a che aveva un tempo di esecuzione proibitivo; tuttavia entro un anno, Arora perfezionò le idee in un algoritmo in tempo lineare. Tali algoritmi sono validi anche in alcune applicazioni dove i tempi e il costo di esecuzione possono essere giustificati, ad es. biologia computazionale, ingegneria finanziaria, pianificazione dei trasporti e gestione degli inventari. In tali scenari, essi devono competere con le corrispondenti formulazioni IP dirette. Un'altra limitazione dell'approccio è che esso si applica soltanto ai problemi di ottimizzazione e non ai problemi di decisione "puri" come la soddisfacibilità, sebbene sia spesso possibile concepire versionsi di ottimizzazione di tali problemi, come il (Max SAT). L'inapprossimabilità è stata un'area di ricerca fruttuosa nel campo della teoria della complessità computazionale fin dal risultato del 1990 di Feige, Goldwasser, Lovasz, Safra e Szegedy sull'inapprossimabilità dell'insieme indipendente. Dopo che Arora et al. dimostrarono il un anno dopo, si è mostrato che gli algoritmi di approssimazione elaborati nel 1974 da Johnson per il Max SAT, la copertura degli insiemi, l'insieme indipendente e la colorazione raggiungono tutti il rapporto ottimale di approssimazione, assumendo P != NP. (it)
- 近似アルゴリズム（きんじアルゴリズム、英: approximation algorithm）とは、組合せ最適化問題の近似解を得るためのアルゴリズムを言う。近似解とは、実行可能解（かつ問題の何らかの制約を満たす解）ではあるが、正解（厳密解）ではないものを言う。これは組合せ最適化問題の正解（すなわち最適解）であることが（厳密には）保証されないところの解を得るものである。なお、問題を変形した近似問題に対する正解を得るアルゴリズムも、元の問題に対する近似アルゴリズムと言える。 (ja)
- 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. Istotą algorytmu aproksymacyjnego, tym co odróżnia go od algorytmu heurystycznego, jest związana z każdym takim algorytmem informacja o koszcie zwracanego rozwiązania w stosunku do rozwiązania optymalnego. Mianowicie koszt rozwiązania zwróconego przez algorytm aproksymacyjny jest nie większy (w przypadku problemu minimalizacyjnego) albo nie mniejszy (w przypadku problemu maksymalizacyjnego) od rozwiązania optymalnego pomnożonego przez pewną stałą. (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. Na prática, podemos não precisar da solução ótima do problema, uma solução boa obtida por um algoritmo de aproximação pode ser suficientemente e mais fácil de ser obtida. Uma outra saída para estes problemas são as Heurísticas, entretanto essas normalmente encontram soluções razoavelmente boas, com uma velocidade não muito boa. Idealmente, a aproximação é ótima até um pequeno fator constante (geralmente de 5% da solução ótima). Diferentes problemas NP-dificeis possuem níveis diferentes de aproximação. Por exemplo, o problema pode ser aproximado com qualquer fator maior que 1, já outros não podem ser aproximados dentro de qualquer constante ou fator polinomial, ao menos que P = NP, como, por exemplo, o problema clique. Um grupo de algoritmos de aproximação são chamados de Esquema de aproximação em tempo polinomial ou PTAS. Nem todos os algoritmos de aproximação são usuais na prática. Eles costumam usar estruturas de dados complexos ou sofisticadas técnicas algorítmicas que dificultam sua implementação. Além disso, alguns algoritmos de aproximação tem tempos de execução não viaveis, embora sejam de tempo polinomial, por exemplo, O(n2000). No entanto, o estudo de alguns algoritmos mesmo muito caros podem fornecer conhecimentos valiosos. Um exemplo clássico é o PTAS para o problema do caxeiro viajante euclidiano (PCV euclidiano, problema PCV utilizando distâncias euclidianas) concebido por Sanjeev Arora, que possui um tempo de execução de um ano, redefinindo os conceitos de algoritmo de tempo linear. Esses algoritmos são úteis em algumas aplicações onde os tempos de execução e de custo podem ser justificados, como por exemplo: biologia computacional, engenharia financeira, planejamento, transporte e gerenciamento de inventário. Outra limitação da abordagem é que ela se aplica somente a problemas de otimização e não a problemas de decisão em essência como o problema da satisfatibilidade, embora muitas vezes é possível conceber versões de otimização de tais problemas. (Max SAT). (pt)
- Аппроксимационный алгоритм — в исследовании операций алгоритм, использующийся для поиска приближённого решения оптимизационной задачи. Концепция аппроксимационного алгоритма была формализована в 1972-м году в статье Гарея, Грэхэма и Ульмана, а позднее Джонсоном.Аппроксимационные алгоритмы часто связаны с NP-трудными задачами, поскольку для них вряд ли найдётся эффективный алгоритм точного решения за полиномиальное время, так что имеет смысл попробовать найти близкое оптимальному решение.В отличие от эвристических алгоритмов, дающих достаточно хорошие решения за приемлемое время, аппроксимационные алгоритмы обеспечивают доказуемое качество решения в заранее определённых границах времени. В идеале аппроксимация даёт решение, отличающееся от оптимального на некоторый небольшой множитель (например, в пределах 5 %).Аппроксимационные алгоритмы всё чаще используются для решения задач, для которых известны точные алгоритмы, работающие за полиномиальное время, но работающие долго.Типичным примером аппроксимационного алгоритма может служить алгоритм решения задачи о вершинном покрытии в теории графов: найти непокрытое ребро и добавить обе его вершины к покрытию вершин, и так продолжать, пока все не будут покрыты.Ясно, что полученное покрытие может оказаться вдвое больше оптимального. Такое решение является аппроксимационным алгоритмом с постоянным коэффициентом 2. NP-трудные проблемы сильно различаются по возможности аппроксимации.Некоторые, среди которых, например, задача об упаковке в контейнеры, могут быть аппроксимированы с любым коэффициентом, большим 1 (это семейство алгоритмов называют приближённой схемой полиномиального времени, или PTAS).Другие задачи невозможно аппроксимировать ни с каким постоянным коэффициентом, или даже с полиномиальным коэффициентом (если P ≠ NP), и среди таких задач находится задача о максимальной клике. NP-трудные задачи часто можно выразить в терминах целочисленного программирования и решить в точности за экспоненциальное время. Многие экспоненциальные алгоритмы берут своё начало из целочисленной задачи. Не все аппроксимационные алгоритмы подходят для решения практических задач. Часто они используют в качестве подзадач ЦП/ЛП/полуопределённые задачи, сложные структуры данных или изощрённую технику программирования, что ведёт к сложности реализации.Некоторые аппроксимационные алгоритмы имеют неприемлемое время работы, хотя время и полиномиально (например, O(n2000)).Всё же изучение даже таких нереальных алгоритмов не преследует чисто теоретические цели, поскольку оно даёт возможность понять суть проблемы.Классический пример — начальный PTAS алгоритм для метрической задачи о коммивояжёре, принадлежащий Санджив Арора и имевший практически нереальное время работы. Однако, в течение года, Арора отточил идею до алгоритма, работающего за линейное время.Такие алгоритмы пригодны также для задач, в которых время работы и цена могут быть оправданы. К таким задачам относятся Вычислительная биология, , и . Другое ограничение связано с тем, что подход годится только для задач оптимизации, но не для «чистых» задач распознавания наподобие задачи выполнимости булевых формул, хотя часто бывает, что метод вполне применим для решения оптимизационных версий тех же задач, например, для (Max SAT). Невозможность аппроксимации является плодотворным полем исследований в области вычислительной сложности с тех пор, как в 1990 году Фейг (Feige), Голдвассер (Goldwasser), Ловаш (Lovasz), Сафра (Safra) и Шегеди (Szegedy) установили невозможность аппроксимации задачи нахождения максимального независимого множества вершин.Через год после того, как Арора (Arora) доказал теорему PCP, было доказано, что аппроксимационные алгоритмы Джонсона (Johnson) 1974-го года для задачи о выполнимости булевых формул, задачи о покрытии множества, задачи о независимом множестве и задача о хроматическом числе графа имеют оптимальный аппроксимационный коэффициент (в предположении, что P ≠ NP) (ru)
- В дослідженні операцій під апроксимаційним алгоритмом розуміють алгоритм, що використовується для пошуку наближеного розв'язку оптимізаційної задачі. Концепція апроксимаційного алгоритму формалізовано 1972 року в статті , Грема і Ульмана, а пізніше Джонсоном. Апроксимаційні алгоритми часто пов'язані з NP-складними задачами, оскільки для них навряд чи знайдеться ефективний алгоритм точного розв'язування за поліноміальний час, так що є сенс спробувати знайти близький до оптимального розв'язок. На відміну від евристичних алгоритмів, що дають досить хороші розв'язки за прийнятний час, апроксимаційні алгоритми забезпечують доказову якість розв'язку в заздалегідь визначених межах часу. В ідеалі апроксимація дає розв'язок, що відрізняється від оптимального на деякий невеликий множник (наприклад, у межах 5 %). Апроксимаційні алгоритми все частіше використовують для розв'язування задач, для яких відомі точні алгоритми, що працюють за поліноміальний час, але працюють довго. Типовим прикладом апроксимаційного алгоритму є алгоритм розв'язування задачі про вершинне покриття в теорії графів: знайти непокрите ребро і додати обидві його вершини до покриття вершин, і так продовжувати, поки всі не будуть покриті. Ясно, що отримане покриття може виявитися вдвічі більшим від оптимального. Таке розв'язування є апроксимаційним алгоритмом зі сталим коефіцієнтом 2. NP-складні задачі дуже відрізняються за можливістю апроксимації. Деякі, наприклад, задача про пакування в контейнери, можуть бути апроксимовані з будь-яким коефіцієнтом, більшим від 1 (це сімейство алгоритмів називають наближеною схемою поліноміального часу, або PTAS). Інші задачі неможливо апроксимувати ні з яким сталим коефіцієнтом, або навіть з поліноміальним коефіцієнтом (якщо P ≠ NP), і серед них задача про найбільшу кліку. NP-складні задачі часто можна виразити в термінах цілочисельного програмування та розв'язати точності за . Багато експоненційних алгоритмів беруть свій початок зі цілочисельної задачі. Не всі апроксимаційні алгоритми придатні для розв'язування практичних задач. Часто вони використовують як підзадачі ЦП/ЛП/, складні структури даних або витончену техніку програмування, що веде до складності реалізації. Деякі апроксимаційні алгоритми мають неприйнятний час роботи, хоча час і поліноміальний (наприклад, O(n2000)). Все ж вивчення навіть таких нереальних алгоритмів має не лише чисто теоретичну мету, оскільки воно дає змогу зрозуміти суть проблеми. Класичний приклад — початковий PTAS-алгоритм для метричної задачі про комівояжера , що мав практично нереальний час роботи. Однак, протягом року Арора розвинув ідею до алгоритму, що працює за лінійний час. Такі алгоритми придатні також для задач, у яких час роботи і ціна можуть бути виправданими. До таких задач належать обчислювальна біологія, фінансовий інжиніринг, і . Інше обмеження пов'язане з тим, що підхід годиться тільки для задач оптимізації, але не для «чистих» задач розпізнавання на зразок задачі здійсненності булевих формул, хоча часто буває, що метод цілком застосовний для розв'язання оптимізаційних версій тих самих задач, наприклад, для (Max SAT). Неможливість апроксимації є плідним полем досліджень в галузі обчислювальної складності відтоді, як у 1990 році , Голдвассер, Ловас, і встановили неможливість апроксимації задачі знаходження максимальної незалежної множини вершин. Через рік після того, як Арора довів теорему PCP, було доведено, що апроксимаційні 1974 року для задачі про здійсненність булевих формул, задачі про покриття множини, задачі про незалежну множину і задачі про хроматичне число графу мають оптимальний апроксимаційний коефіцієнт (у припущенні, що P ≠ NP) (uk)
- 在计算机科学和运筹学中，近似算法（英語：Approximation algorithm）是指能为最优化问题寻找近似解的算法，该类算法找到的近似解与最优解之间的差值需能证明不超过某个值。由于人们普遍猜测P≠NP，许多优化问题因此无法在多项式时间内得到精确解决。进而，理論計算機科學领域内自然而然地出现了试图在多项式时间复杂度内得到近似最优解的近似算法。在绝大多数情况下，近似算法得到的近似值位于最优解到最优解乘以某个特定的值之间，这个特定的值被称作近似比。不过，也有一些算法得到的近似值是在最优解到最优解加某个特定的值之间。 近似算法的设计及分析过程中都包含一系列的数学证明，以保证其最差情况效率仍可接受。这点也是它与模拟退火等启发式算法之间的不同之处，启发式算法通常能够找到一个比较好的近似解，但其设计及分析之初往往并不涉及最差情况效率的证明。 (zh)
|
| 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)
|
