| Information | |
|---|---|
| has gloss | eng: In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact algorithms solving NP-hard problems, one settles for polynomial time sub-optimal solutions. Unlike heuristics, which usually only find reasonably good solutions reasonably fast, one wants provable solution quality and provable run time bounds. Ideally, the approximation is optimal up to a small constant factor (for instance within 5% of the optimal solution). Approximation algorithms are increasingly being used for problems where exact polynomial-time algorithms are known but are too expensive due to the input size. |
| lexicalization | eng: Approximation algorithms |
| lexicalization | eng: approximation algorithm |
| lexicalization | eng: R-approximation algorithm |
| subclass of | (noun) a precise rule (or set of rules) specifying how to solve some problem algorithm, algorithmic program, algorithmic rule |
| has instance | e/Domination analysis |
| has instance | e/Karloff-Zwick algorithm |
| has instance | e/L-reduction |
| has instance | e/Minimum k-cut |
| has instance | e/Polynomial-time algorithm for approximating the volume of convex bodies |
| has instance | e/Polynomial-time approximation scheme |
| has instance | e/Property testing |
| Meaning | |
|---|---|
| Czech | |
| has gloss | ces: Aproximační algoritmy je druh algoritmů používaných při řešení optimalizačního problému, kdy nehledáme nutně optimální řešení, ale spokojíme se i s řešením, které je optimálnímu velmi blízké. |
| lexicalization | ces: Aproximační algoritmy |
| German | |
| has gloss | deu: Ein Approximationsalgorithmus ist in der Informatik ein Algorithmus, der ein Optimierungsproblem näherungsweise löst. |
| lexicalization | deu: Approximationsalgorithmus |
| Esperanto | |
| lexicalization | epo: Proksimumaj kalkuladaj algoritmoj |
| Persian | |
| has gloss | fas: الگوریتم های تقریبی برای مسائل P نیز استفاده میشوند ولی به ازای ورودی های بزرگ خوب عمل نمیکنند. |
| lexicalization | fas: الگوریتمهای تقریبی |
| French | |
| has gloss | fra: Un algorithme dapproximation est une heuristique garantissant à la qualité de la solution fournie un rapport inférieur (si lon minimise) à une constante, par-rapport à la qualité optimale d'une solution, pour toutes les instances possibles du problème. |
| lexicalization | fra: algorithme d'approximation |
| Hebrew | |
| has gloss | heb: אלגוריתם קירוב (approximation algorithm באנגלית) הינו אלגוריתם שמוצא פתרון שאינו הפתרון האופטימלי לבעיה נתונה, אלא פתרון שקרוב לפתרון האופטימלי. |
| lexicalization | heb: אלגוריתם קירוב |
| Japanese | |
| has gloss | jpn: 近似アルゴリズム（きんじアルゴリズム）とは、最適化問題の近似解を得るための多項式時間アルゴリズムのこと。近似解とは、実行可能解（問題の制約を満たす解）ではあるが最適解とは限らない解のことを指す。 |
| lexicalization | jpn: 近似アルゴリズム |
| Korean | |
| has gloss | kor: 근사 알고리즘(approximation algorithm)은 어떤 최적화 문제에 대한 근사해를 구하는 알고리즘을 의미한다. 이 알고리즘은 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해를 계산할 수 있다. 근사 알고리즘은 NP-완전 문제 등 현재 알려진 빠른 최적화 알고리즘이 없을 문제에 대해 주로 사용된다. |
| lexicalization | kor: 근사 알고리즘 |
| Polish | |
| has gloss | pol: 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. |
| lexicalization | pol: Algorytm aproksymacyjny |
| Castilian | |
| has gloss | spa: 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 heurísticas, que usualmente sólo 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. |
| lexicalization | spa: Algoritmo de aproximacion |
| lexicalization | spa: algoritmo de aproximación |
| Thai | |
| has gloss | tha: ในศาสตร์ด้านวิทยาการคอมพิวเตอร์นั้น ขั้นตอนวิธีการประมาณ เป็นวิธีการหนึ่งที่ใช้สำหรับจัดการกับปัญหาการหาค่าเหมาะที่สุดประเภทเอ็นพี-ฮาร์ด เนื่องจากเป็นที่เชื่อกันว่าไม่มีขั้นตอนวิธีใดที่มีประสิทธิภาพ (ทำงานได้รวดเร็ว) ที่สามารถแก้ไขปัญหาเอ็นพี-ฮาร์ดได้คำตอบที่เที่ยงตรง จึงได้เกิดความพยายามที่จะหาคำตอบที่อาจจะไม่ถูกต้องที่สุด แต่สามารถหาได้ในเวลาโพลิโนเมียล ข้อแตกต่างของขั้นตอนวิธีประเภทนี้กับฮิวริสติก (ซึ่งมักเป็นการหาคำตอบที่ดีในระดับหนึ่งโดยใช้เวลาไม่มากนัก) ก็คือ ขั้นตอนวิธีประมาณต้องการคำตอบที่สามารถพิสูจน์ได้ว่าดีเพียงใด และพิสูจน์ได้ว่ามีขอบเขตการใช้เวลาไม่เกินเท่าใด ขั้นตอนวิธีในอุดมคติมักจะต้องผิดไปจากคำตอบจริงไม่เกินค่าคงที่ค่าหนึ่ง (เช่น คลาดเคลื่อนไม่เกิน 5%) |
| lexicalization | tha: ขั้นตอนวิธีการประมาณ |
| Chinese | |
| lexicalization | zho: 近似算法 |
Lexvo © 2008-2025 Gerard de Melo. Contact Legal Information / Imprint