¿Existe un método general para evaluar la optimización de un algoritmo de optimización?

¿Existe un método general para evaluar la optimización de un algoritmo de optimización, por ejemplo, un algoritmo que resuelva un problema NP-hard o NP-complete?

El único método que se me ocurrió hasta ahora es comparar los resultados del algoritmo con las soluciones óptimas ya conocidas.

Si no, ¿existen métodos específicos para algunos problemas especiales?

EDITAR Para aclarar: por optimismo me refiero a lo cerca que está el resultado de un resultado óptimo de soluciones.

Depende del tipo de problema.

Si hay un esquema de aproximación de tiempo polinomial (PTAS) para el problema (por ejemplo, TSP euclidiano), puede obtener una solución que sea arbitrariamente cercana a la solución óptima en tiempo polinomial. Eso significa que, para cada e > 0, hay un algoritmo de tiempo polinómico que encontrará una solución aproximada a su problema, que está garantizado dentro de (1+ e ) de la solución óptima. En ese caso, simplemente compararía la complejidad de tiempo de ejecución / memoria para dos algoritmos para los mismos valores de e . Si un algoritmo puede hacer las mismas "garantías de optimización" que el otro, pero a un menor tiempo de ejecución / costo de memoria, entonces probablemente sea el mejor algoritmo.

Si el problema es APX, pero no PTAS , es decir, si hay algoritmos de aproximación de tiempo polinomial que garantizan producir soluciones que están dentro de un factor constante de la solución óptima, entonces puede comparar ese factor constante. El que tenga el factor más bajo producirá las mejores soluciones (pero a menudo a costa de un mayor tiempo de ejecución / costos de memoria)

Si el problema no está en ninguna de esas clases, entonces creo que lo mejor que puede hacer es comparar sus soluciones para un conjunto de problemas aleatorios, o para problemas con soluciones óptimas conocidas.

No creo que haya una forma general de hacerlo, pero ciertamente hay métodos para hacerlo.

Tomemos, por ejemplo, el problema SET-COVER. Para aquellos que no conocen el problema es el siguiente:

Dado un conjunto de elementos B={1,2,...,m}y una serie de subconjuntos S_1, S_2, ..., S_ncuya unión es B. Está tratando de encontrar el número mínimo de estos subconjuntos de modo que la unión aún esté B. Un ejemplo típico de este problema en el mundo real es cuando le dan una colección de vecindarios y está tratando de encontrar los lugares óptimos para ubicar escuelas, de modo que cada vecindario tenga servicio a menos de cierta distancia dde la escuela más cercana. En este caso, Bes el conjunto de barrios y se S_xcompone de todos los conjuntos dentro dde la ciudad x.

Usted demuestra que este problema es NP-COMPLETO. Sin embargo, existe una solución simple y codiciosa en la que eliges repetidamente el conjunto S_icon la mayor cantidad de elementos descubiertos. Y puedes probar que este algoritmo funciona bien .

Si el algoritmo óptimo consiste en kconjuntos, el algoritmo codicioso consistirá en no más que k ln(n)conjuntos donde ln es el logaritmo natural.

El problema de determinar si un programa tiene 'rendimiento de optimización' A o 'rendimiento de optimización' B para casi cualquier definición de 'rendimiento de optimización' es indecidible en general (prueba a continuación). Esto implica que no existe un método único que siempre pueda decirle qué tan óptimo es un algoritmo.

Sin embargo, existen métodos que a menudo se aplican al analizar algoritmos de aproximación. A menudo, los algoritmos de aproximación son evaluados por sus garantías sobre qué tan lejos está su solución de la solución óptima. Daré un ejemplo de problema y aproximación, que probaré usando el método de 'límite inferior', que es un método muy comúnmente utilizado para probar proporciones.

El problema en cuestión es el problema de 'Carga de camiones': tenemos muchos camiones idénticos (tantos como queramos), cada uno capaz de transportar una carga que pesa como máximo T. Tenemos n objetos que deseamos cargar en estos camiones para transporte. Cada objeto i tiene un peso w_i, donde w_i <= T (por lo que no hay elementos que no puedan caber en un camión, incluso por sí mismos). Los artículos no se pueden dividir en partes. Nos gustaría llenar los camiones para que necesitemos la menor cantidad posible de camiones. Este problema es NP-completo.

Hay un algoritmo de aproximación muy fácil para este problema. Simplemente comenzamos a cargar un camión con artículos, hasta que el camión está tan lleno que el siguiente artículo no cabe. Luego tomamos otro camión y cargamos este camión con este artículo que no cabía en el camión anterior. No cargamos más artículos en este camión: en su lugar, tomamos un camión nuevo, lo llenamos con muchos artículos nuevamente hasta que ya no cabe, colocamos ese último artículo en su propio camión nuevamente y así sucesivamente.

Este algoritmo es una llamada aproximación 2 para el problema: utiliza como máximo el doble de camiones que la solución óptima necesitaría. El 'a lo sumo' es crucial: podríamos tener suerte y encontrar la solución óptima, pero al menos no lo haremos tan mal.

Para probar esto, primero definimos un límite inferior en la cantidad óptima de camiones que necesitamos. Para esto, imagine que se nos permite cortar elementos en partes: podríamos llenar fácilmente todos los camiones, excepto el último por completo. La cantidad de camiones que necesitaríamos si lo hiciéramos es un límite inferior para la cantidad de camiones que necesitamos para la pregunta original: en el 'mejor' caso, la solución óptima siempre llena cada camión por completo, en cuyo caso el número de camiones es igual, pero si las soluciones óptimas dejan los camiones sin llenar, entonces solo puede necesitar más camiones.

Ahora miramos nuestro algoritmo de aproximación. Tenga en cuenta que en cada paso, nosotros (parcialmente) llenamos dos camiones. También tenga en cuenta que, por cómo funciona el algoritmo, los artículos en el primer camión y el artículo en el segundo camión juntos no pueden caber en el primer camión, por lo que su suma es al menos T. Esto significa que en cada paso, cargamos al menos una carga completa valor del camión de artículos en dos camiones. Ahora compare esto con nuestro límite inferior: en ese caso, cargamos un camión completo de artículos en un camión. En otras palabras, nuestro algoritmo de aproximación calcula (en tiempo lineal) una solución que se parece mucho a nuestra 'solución' de límite inferior, pero utiliza dos camiones en lugar de uno. Por lo tanto, utilizamos como máximo el doble de camiones que el algoritmo óptimo, porque utilizamos como máximo el doble de camiones que nuestro límite inferior en el algoritmo óptimo.

Este algoritmo proporciona una aproximación de factor constante: es como máximo 2 veces más malo que la solución óptima. Algunos ejemplos de otras medidas: como máximo C más que la solución óptima (error aditivo, bastante infrecuente), como máximo c log n veces peor que la solución óptima, como máximo cn veces tan malo como la solución óptima, como máximo c 2 ^ (dn) veces tan malo como la solución óptima (muy malo; por ejemplo, el TSP general solo admite algoritmos con este tipo de garantías).

Por supuesto, si desea estar seguro de que el factor que prueba es el mejor factor que puede probar, debe intentar encontrar instancias en las que la solución que le brinda su algoritmo sea tan mala como sea posible.

También tenga en cuenta que a veces usamos algoritmos de aproximación en problemas que no son NP-hard.

Aprendí esto (entre muchos más) en el curso de algoritmos de aproximación en mi universidad.

Prueba de indecidibilidad: deje que P sea un problema y A y B sean algoritmos de aproximación para P donde A y B no tienen la misma 'óptima' para alguna definición sensata de 'óptima', y donde el tiempo de ejecución de A y B es omega (1) (estrictamente más lento que el tiempo constante, es decir, se vuelven más lentos para instancias más grandes) y donde A y B siempre se detienen.

Sea D un programa que afirme que puede calcular lo siguiente: dado que algún programa C calcula una aproximación para P, decida si es tan bueno como A o tan bueno como B para entradas suficientemente grandes (por lo tanto, puede usar esto para categorizar programas de acuerdo a su optimidad).

Entonces podemos usar D para resolver el problema de detención. Sea E un programa y F una entrada para este programa. Usaremos D para decidir si E se detendrá en la entrada F.

Diseñamos un programa G que hace lo siguiente: dada una entrada S para el problema P, ejecuta E en F y A en S en paralelo: ejecuta E por un tiempo, luego A, luego E nuevamente y así sucesivamente. Si E se detiene en F, deja de ejecutar A y en su lugar ejecuta B en S y devuelve el resultado de B. Si A se detiene antes de que E se detenga, devuelve el resultado de A.

El uso de D en G ahora decide si E se detiene en F: si E se detiene en F, entonces para entradas suficientemente grandes S, E se detiene en F antes de que A se detenga en S (porque el tiempo que tarda E en detenerse no depende del tamaño de la entrada, a diferencia de A). Por lo tanto, D informa que G tiene las características de optimización de B. Si E no se detiene en F, D informará que G tiene las características de optimización de A.