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.
Definición formal
Una instancia de un problema de optimización combinatoria puede ser descrito formalmente como una tupla donde
X es el espacio de soluciones (en el cual f y P están definidos)
William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver; Combinatorial Optimization; John Wiley & Sons; 1 edition (November 12, 1997); ISBN 047155894X.
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger, A Compendium of NP Optimization Problems.
Christos H. Papadimitriou, and Kenneth Steiglitz; Combinatorial Optimization: Algorithms and Complexity; Dover Pubns; (paperback, Unabridged edition, July 1998) ISBN 0486402584.
Datos:Q1333872
Multimedia:Combinatorial optimization / Q1333872
Marcha 27, 2023
optimización, combinatoria, optimización, combinatoria, rama, optimización, matemáticas, aplicadas, ciencias, computación, relacionada, investigación, operaciones, teoría, algorítmica, información, teoría, complejidad, computacional, también, está, relacionada. La optimizacion combinatoria es una rama de la optimizacion en matematicas aplicadas y en ciencias de la computacion relacionada con la investigacion de operaciones Teoria algoritmica de la informacion y teoria de la complejidad computacional Tambien esta relacionada con otros campos como la inteligencia artificial e ingenieria de software Los algoritmos de optimizacion combinatoria resuelven instancias de problemas que se creen ser dificiles en general explorando el espacio de soluciones usualmente grande para estas instancias Los algoritmos de optimizacion combinatoria logran esto reduciendo el tamano efectivo del espacio y explorando el espacio de busqueda eficientemente Los algoritmos de optimizacion combinatoria a menudo son implementados en lenguajes imperativos como C y C entre otros softwares inteligentes en lenguajes de programacion logicos tales como Prolog o incluso en lenguajes multi paradigma tales como Oz Mediante el estudio de la teoria de la complejidad computacional es posible comprender la importancia de la optimizacion combinatoria Los algoritmos de optimizacion combinatoria se relacionan comunmente con problemas NP hard Dichos problemas en general no son resueltos eficientemente sin embargo varias aproximaciones de la teoria de la complejidad sugieren que ciertas instancias ej pequenas instancias de estos problemas pueden ser resueltas eficientemente Dichas instancias a menudo tienen ramificaciones practicas muy importantes Indice 1 Definicion formal 2 Ejemplo de problemas 3 Metodos 4 Vease tambien 5 ReferenciasDefinicion formal EditarUna instancia de un problema de optimizacion combinatoria puede ser descrito formalmente como una tupla X P Y f e x t r displaystyle X P Y f mathrm extr donde X es el espacio de soluciones en el cual f y P estan definidos P es la factibilidad predicado Y es el conjunto de soluciones factibles f es la funcion objetivo extr es el extremo normalmente min o max Ejemplo de problemas EditarEl problema del vendedor viajero Programacion lineal El problema de las n reinas Metodos EditarLos metodos de busqueda heuristicos algoritmos metaheuristicos como los listados abajo han sido usados para resolver problemas de este tipo Busqueda local Simulated annealing GRASP Inteligencia de enjambre Busqueda tabu Algoritmos geneticos Optimizacion basada en colonias de hormigas Reactive searchVease tambien EditarOptimizacion discreta Algoritmos de busqueda Evolucion diferencialReferencias EditarWilliam J Cook William H Cunningham William R Pulleyblank Alexander Schrijver Combinatorial Optimization John Wiley amp Sons 1 edition November 12 1997 ISBN 047155894X Pierluigi Crescenzi Viggo Kann Magnus Halldorsson Marek Karpinski Gerhard Woeginger A Compendium of NP Optimization Problems Christos H Papadimitriou and Kenneth Steiglitz Combinatorial Optimization Algorithms and Complexity Dover Pubns paperback Unabridged edition July 1998 ISBN 0486402584 Datos Q1333872 Multimedia Combinatorial optimization Q1333872 Obtenido de https es wikipedia org w index php title Optimizacion combinatoria amp oldid 146185540, wikipedia, wiki, leyendo, leer, libro, biblioteca,
