| dbo:abstract
|
- في الرياضيات التطبيقية وعلم الحاسوب النظري، استمثال توافقي (بالإنجليزية: Combinatorial optimization) أو الحلول المثلى للمسائل المعدودة هو مجال يهتم بإجاد القيم لمتغيرات المسألة المعدودة. عادةً أي مسألة معدودة لإيجاد قيمها فلابد من البحث في كل الطرق للحل واختيار الأفضل، لكن هذه الطريقة هي طريقة مكلفة بالحاسب، لذلك هذا العلم أتى ليحلها بطرق مختلفة نظرياً وليس فيزيائياً. مثال: مسألة الرجل البائع لحلها عن طريق فرز كل الحلول الممكنة فلو كان عدد المدن هو 100، لاحتجنا إلى ملايين السنين لحلها، لذلك هناك طرق في هذا العلم لحلها بطريقة أسرع باستخدام تقنيات خوارزمية وغيرها. (ar)
- Kombinatorische Optimierung ist ein Zweig der diskreten Mathematik und spielt in vielen Bereichen einschließlich der Operations Research, der Informatik, der künstlichen Intelligenz und den Ingenieurwissenschaften eine wichtige Rolle. (de)
- Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead. Combinatorial optimization is related to operations research, algorithm theory, and computational complexity theory. It has important applications in several fields, including artificial intelligence, machine learning, auction theory, software engineering, applied mathematics and theoretical computer science. Some research literature considers discrete optimization to consist of integer programming together with combinatorial optimization (which in turn is composed of optimization problems dealing with graph structures), although all of these topics have closely intertwined research literature. It often involves determining the way to efficiently allocate resources used to find solutions to mathematical problems. (en)
- La optimización combinatoria es una rama de la optimización en matemáticas aplicadas y en ciencias de la computación, relacionada con la investigación de operaciones, Teoría algorítmica de la información y teoría de la complejidad computacional. También está relacionada con otros campos, como la inteligencia artificial e ingeniería de software. Los algoritmos de optimización combinatoria resuelven instancias de problemas que se creen ser difíciles en general, explorando el espacio de soluciones (usualmente grande) para estas instancias. Los algoritmos de optimización combinatoria logran esto reduciendo el tamaño efectivo del espacio, y explorando el espacio de búsqueda eficientemente. Los algoritmos de optimización combinatoria a menudo son implementados en lenguajes imperativos como C y C++ entre otros softwares inteligentes en lenguajes de programación lógicos tales como Prolog, o incluso en lenguajes multi-paradigma tales como Oz. Mediante el estudio de la teoría de la complejidad computacional es posible comprender la importancia de la optimización combinatoria. Los algoritmos de optimización combinatoria se relacionan comúnmente con problemas NP-hard. Dichos problemas en general no son resueltos eficientemente, sin embargo, varias aproximaciones de la teoría de la complejidad sugieren que ciertas instancias (ej. "pequeñas" instancias) de estos problemas pueden ser resueltas eficientemente. Dichas instancias a menudo tienen ramificaciones prácticas muy importantes. (es)
- L’optimisation combinatoire, (sous-ensemble à nombre de solutions finies de l'optimisation discrète), est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité. (fr)
- 응용수학과 전산학에서 조합 최적화는 최적화 문제의 일종으로서, 운용 과학, 알고리즘 이론, 계산 복잡도 이론과 관련되어 있고, 인공지능, 수학, 소프트웨어 공학과 영역이 겹친다. 조합 최적화에서는 일반적으로 어렵다고 보는 문제를 풀려고 한다. 어려운 문제들은 보통 문제 공간이 크기 때문에 조합 최적화 알고리즘은 문제 공간을 좁히거나 탐색 효율을 높이는 데 중점을 둔다. 계산 복잡도 이론의 연구 결과가 조합 최적화에서 쓸모있는 경우가 많다. 조합 최적화 알고리즘은 보통 NP-완전인 문제를 다루는데, 일반적으로 NP-완전 문제는 쉽게 풀 수 없다고 보고 있다. 그러나 복잡도 이론의 여러 근사에 따르면 몇몇 특수한 경우에는 효율적으로 풀 수 있다. 조합 최적화에서는 바로 이러한 경우에 대해 관심을 갖는다. 이런 경우는 중요하고 실용적인 응용을 할 수 있을 때가 많다. (ko)
- 組合せ最適化（くみあわせさいてきか、英: combinatorial optimization、組み合わせ最適化、または組み合せ最適化とも表記される）は、応用数学や情報工学での組合せ論の最適化問題である。オペレーションズリサーチ、アルゴリズム理論、計算複雑性理論と関連していて、人工知能、数学、およびソフトウェア工学などの交差する位置にある。組合せ最適化では、厳密解が簡単に求まる場合もあれば、そうでない場合もある。厳密解を求めるのが難しいと思われる問題を解くために、その問題の解空間を探索する場合もあり、そのためのアルゴリズムでは、効率的に探索するために解空間を狭めたりすることもある。 (ja)
- Комбинаторная оптимизация — область теории оптимизации в прикладной математике, связанная с исследованием операций, теорией алгоритмов и теорией вычислительной сложности.Комбинаторная оптимизация заключается в поиске оптимального объекта в конечном множестве объектов, чем очень похожа на дискретное программирование. Некоторые источникипод дискретным программированием понимают целочисленное программирование, противопоставляя ему комбинаторную оптимизацию, имеющую дело с графами, матроидами и похожими структурами. Однако оба термина очень близко связаны и в литературе часто переплетаются. Комбинаторная оптимизация часто сводится к определению эффективного распределения ресурсов, используемых для поиска оптимального решения. Во многих задачах комбинаторной оптимизации полный перебор нереален.Комбинаторная оптимизация включает в себя задачи оптимизации, в которых множество допустимых решений дискретно или может быть сведено к дискретному множеству. (ru)
- A Otimização Combinatória é um ramo da ciência da computação e da matemática aplicada que estuda problemas de otimização em conjuntos finitos. Em um problema de otimização temos uma função objetivo e um conjunto de restrições, ambos relacionados às variáveis de decisão. Os valores possíveis às variáveis de decisão são delimitados pelas restrições impostas sobre essas variáveis, formando um conjunto discreto (finito ou não) de soluções factíveis a um problema. O problema pode ser de minimização ou de maximização da função objetivo. A resposta para o problema de otimização, ou seja, o ótimo global, será o menor (ou maior) valor possível para a função objetivo para o qual o valor atribuído às variáveis não viole nenhuma restrição. Em alguns casos, chegamos a valores cuja alteração discreta não conduz a resultados melhores, mas que não são também o óptimo global - a essas soluções chamamos de ótimo local. Há muitas classificações possíveis para o problema de otimização, e algumas delas apresentarão métodos exatos e eficientes de resolução. Outras levarão à necessidade de métodos não-exatos (heurísticas), uma vez que sua formulação e/ou resolução exatas levariam a uma complexidade intratável. Como técnicas de soluções exatas - em especial com algoritmo polinomial para alguns problemas - temos, por exemplo:
* Algoritmos de grafos (ver Teoria dos grafos)
* Algoritmos gulosos
* Algoritmo simplex
* Branch e bound
* Programação dinâmica
*
* Programação com restrições Algumas das técnicas de obtenção de soluções aproximadas:
* Algoritmos genéticos
* Busca tabu
* Algoritmo da colônia de formigas
* Greedy Randomized Adaptive Search Procedures (GRASP)
* Redes neurais
* Simulated annealing (arrefecimento simulado) Entre as classificações possíveis, encontram-se: 1) Quanto à relação entre as variáveis de decisão na função objetivo e nas restrições:
* Programação linear
* Programação não linear 2) Quanto ao valor que podem assumir as variáveis:
* Programação real (nome não-utilizado, apenas posto aqui para diferenciação)
* Programação inteira
* Programação 0-1 (variáveis inteiras, com apenas dois valores possíveis)
* Programação mista (algumas variáveis reais e outras inteiras) 3) Quanto à natureza da função objetivo:
* Função convexa - Ótimo local é global (mais simples)
* Função côncava - Ótimo local não necessariamente Global (mais complicado de resolver) (pt)
- Комбінаторна оптимізація (англ. Combinatorial optimization) — розділ теорії оптимізації. Розглядає задачі оптимізації множина розв'язків яких дискретна або може бути зведена до дискретної. (uk)
- 组合最优化，在应用数学和理论计算机科学的领域中，组合优化是在一个有限的对象集中找出最优对象的一类问题。在很多组合优化的问题中，穷举搜索／枚举法是不可行的。组合优化的问题的特征是可行解的集是离散或者可以简化到离散的，并且目标是找到最优解。常见的例子有旅行商问题和最小生成樹。二维的例子，比如服装厂做衣服，衣服分成很多块，这些块需要从布料上切下来。怎么切，剩下的废布料最少？三维的例子，如集装优化。 组合优化的难处，主要是加进来，不同的下，不同部分的约束关系便不同，算法也就要调整。如果给定一个拓扑形态，组合优化往往就退化成一个的问题了。 (zh)
|
| rdfs:comment
|
- في الرياضيات التطبيقية وعلم الحاسوب النظري، استمثال توافقي (بالإنجليزية: Combinatorial optimization) أو الحلول المثلى للمسائل المعدودة هو مجال يهتم بإجاد القيم لمتغيرات المسألة المعدودة. عادةً أي مسألة معدودة لإيجاد قيمها فلابد من البحث في كل الطرق للحل واختيار الأفضل، لكن هذه الطريقة هي طريقة مكلفة بالحاسب، لذلك هذا العلم أتى ليحلها بطرق مختلفة نظرياً وليس فيزيائياً. مثال: مسألة الرجل البائع لحلها عن طريق فرز كل الحلول الممكنة فلو كان عدد المدن هو 100، لاحتجنا إلى ملايين السنين لحلها، لذلك هناك طرق في هذا العلم لحلها بطريقة أسرع باستخدام تقنيات خوارزمية وغيرها. (ar)
- Kombinatorische Optimierung ist ein Zweig der diskreten Mathematik und spielt in vielen Bereichen einschließlich der Operations Research, der Informatik, der künstlichen Intelligenz und den Ingenieurwissenschaften eine wichtige Rolle. (de)
- L’optimisation combinatoire, (sous-ensemble à nombre de solutions finies de l'optimisation discrète), est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité. (fr)
- 응용수학과 전산학에서 조합 최적화는 최적화 문제의 일종으로서, 운용 과학, 알고리즘 이론, 계산 복잡도 이론과 관련되어 있고, 인공지능, 수학, 소프트웨어 공학과 영역이 겹친다. 조합 최적화에서는 일반적으로 어렵다고 보는 문제를 풀려고 한다. 어려운 문제들은 보통 문제 공간이 크기 때문에 조합 최적화 알고리즘은 문제 공간을 좁히거나 탐색 효율을 높이는 데 중점을 둔다. 계산 복잡도 이론의 연구 결과가 조합 최적화에서 쓸모있는 경우가 많다. 조합 최적화 알고리즘은 보통 NP-완전인 문제를 다루는데, 일반적으로 NP-완전 문제는 쉽게 풀 수 없다고 보고 있다. 그러나 복잡도 이론의 여러 근사에 따르면 몇몇 특수한 경우에는 효율적으로 풀 수 있다. 조합 최적화에서는 바로 이러한 경우에 대해 관심을 갖는다. 이런 경우는 중요하고 실용적인 응용을 할 수 있을 때가 많다. (ko)
- 組合せ最適化（くみあわせさいてきか、英: combinatorial optimization、組み合わせ最適化、または組み合せ最適化とも表記される）は、応用数学や情報工学での組合せ論の最適化問題である。オペレーションズリサーチ、アルゴリズム理論、計算複雑性理論と関連していて、人工知能、数学、およびソフトウェア工学などの交差する位置にある。組合せ最適化では、厳密解が簡単に求まる場合もあれば、そうでない場合もある。厳密解を求めるのが難しいと思われる問題を解くために、その問題の解空間を探索する場合もあり、そのためのアルゴリズムでは、効率的に探索するために解空間を狭めたりすることもある。 (ja)
- Комбінаторна оптимізація (англ. Combinatorial optimization) — розділ теорії оптимізації. Розглядає задачі оптимізації множина розв'язків яких дискретна або може бути зведена до дискретної. (uk)
- 组合最优化，在应用数学和理论计算机科学的领域中，组合优化是在一个有限的对象集中找出最优对象的一类问题。在很多组合优化的问题中，穷举搜索／枚举法是不可行的。组合优化的问题的特征是可行解的集是离散或者可以简化到离散的，并且目标是找到最优解。常见的例子有旅行商问题和最小生成樹。二维的例子，比如服装厂做衣服，衣服分成很多块，这些块需要从布料上切下来。怎么切，剩下的废布料最少？三维的例子，如集装优化。 组合优化的难处，主要是加进来，不同的下，不同部分的约束关系便不同，算法也就要调整。如果给定一个拓扑形态，组合优化往往就退化成一个的问题了。 (zh)
- Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead. (en)
- La optimización combinatoria es una rama de la optimización en matemáticas aplicadas y en ciencias de la computación, relacionada con la investigación de operaciones, Teoría algorítmica de la información y teoría de la complejidad computacional. También está relacionada con otros campos, como la inteligencia artificial e ingeniería de software. Los algoritmos de optimización combinatoria resuelven instancias de problemas que se creen ser difíciles en general, explorando el espacio de soluciones (usualmente grande) para estas instancias. Los algoritmos de optimización combinatoria logran esto reduciendo el tamaño efectivo del espacio, y explorando el espacio de búsqueda eficientemente. (es)
- A Otimização Combinatória é um ramo da ciência da computação e da matemática aplicada que estuda problemas de otimização em conjuntos finitos. Em um problema de otimização temos uma função objetivo e um conjunto de restrições, ambos relacionados às variáveis de decisão. Os valores possíveis às variáveis de decisão são delimitados pelas restrições impostas sobre essas variáveis, formando um conjunto discreto (finito ou não) de soluções factíveis a um problema. O problema pode ser de minimização ou de maximização da função objetivo. A resposta para o problema de otimização, ou seja, o ótimo global, será o menor (ou maior) valor possível para a função objetivo para o qual o valor atribuído às variáveis não viole nenhuma restrição. Em alguns casos, chegamos a valores cuja alteração discreta nã (pt)
- Комбинаторная оптимизация — область теории оптимизации в прикладной математике, связанная с исследованием операций, теорией алгоритмов и теорией вычислительной сложности.Комбинаторная оптимизация заключается в поиске оптимального объекта в конечном множестве объектов, чем очень похожа на дискретное программирование. Некоторые источникипод дискретным программированием понимают целочисленное программирование, противопоставляя ему комбинаторную оптимизацию, имеющую дело с графами, матроидами и похожими структурами. Однако оба термина очень близко связаны и в литературе часто переплетаются. Комбинаторная оптимизация часто сводится к определению эффективного распределения ресурсов, используемых для поиска оптимального решения. (ru)
|
