¿Diferencia entre algoritmo heurístico y de aproximación?

Tengo un problema con respecto a la siguiente situación.

Tengo dos conjuntos de números como este:

index/pos     0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15 
Array 1(i):   1   2   3   4   7   5   4   3   7   6   5   1   2   3   4   2
Array 2(j):   4   4   8  10  10   7   7  10  10  11   7   4   7   7   4

ahora supongamos que la segunda matriz es muy difícil de calcular pero he notado que si agrego

A [i] + A [i + 1]

en la matriz 1 obtengo el número muy cercano al número A [j] en la matriz 2.

¿Es mi solución una heurística o aproximación?
Si tuviera una razón para creer que nunca superaré el valor de A [j] por + -x con este algoritmo y puedo probarlo, ¿mi solución sería heurística o aproximación?

¿Existe alguna literatura que trate con preguntas heurísticas versus aproximaciones para problemas de clase P donde la solución se puede lograr en tiempo polinómico pero la entrada es demasiado grande para que un algoritmo de tiempo polivinílico sea práctico?

gracias

approximation heuristics usuario6697
fuente

Primero debe definir lo que desea aproximar para juzgar si su enfoque es aproximado.

Dan

¿Cuál es exactamente el problema de optimización que está tratando de resolver? Una vez que se sabe eso, si demuestra límites, su heurística se convierte en una aproximación. Además, los únicos problemas (clásicos, es decir, sin transmisión) en P que tienen algoritmos de aproximación (que yo sepa) son los algoritmos de flujo máximo.

Nicholas Mancuso

ok, entonces lo que deseo calcular son los números dentro de la segunda matriz. pero esto lleva demasiado tiempo, sin embargo, descubrí que si agrego dos valores consecutivos de la matriz 1, obtengo algo correcto y puedo demostrar que la estimación siempre estará dentro de + -x. alg inicial para calcular A [j] es O (n ^ 100)

usuario6697

Entiendo que desea calcular los números en la segunda matriz, pero cuál es la formulación del problema de optimización. Dado que X calcula Y bajo las restricciones de Z. Decir que desea calcular alguna función arbitraria no ayuda.

Nicholas Mancuso

¡Su solución es un ejemplo perfecto de una heurística!

Björn Lindqvist

Respuestas:

Una heurística es esencialmente una corazonada, es decir, el caso que usted describe ("Me di cuenta de que está cerca", no tiene pruebas de que lo sea) es una heurística. Como está resolviendo el problema del vendedor ambulante comenzando en un vértice aleatorio y yendo al más cercano que aún no ha visitado cada paso. Es una idea plausible , que no debería dar una solución tan mala. En este caso, se puede demostrar que no siempre dará una buena solución.

Un algoritmo de aproximación se entiende generalmente para dar una solución aproximada, con algún tipo de garantía de rendimiento (es decir, los que resuelve TSP, y el coste total no es nunca fuera a más de un factor de 2, o mejor aún, que resuelve TSP y, dependiendo de <algunos parámetros que se pueden variar> la solución nunca es peor que la óptima en más de un factor $1 + \epsilon$ , dónde $\epsilon$ depende de <parámetros>).

vonbrand
fuente

Usó una muestra incorrecta, TSP es difícil de aproximar, por lo que no hay PTAS para TSP y tampoco hay aproximación 2 para TSP es fácil de mostrar si hay tiempo polinomial 2-aproximación para TSP hay un algoritmo de tiempo polinómico para resolver el problema del ciclo hamiltoniano , Creo que te refieres a TSP métrico, que es un caso especial pero todavía no hay PTAS en este caso (y se demostró que es imposible tener PTAS excepto P = NP). Sugeriría elegir el embalaje del contenedor para hablar de esto. (o cualquier otro problema más simple).

@SaeedAmiri, fue solo para fines ilustrativos. Quizás no sea el mejor ejemplo (como usted dice), pero el problema es fácil de entender. Gracias por el comentario.

vonbrand

Entonces, si entiendes que este es un ejemplo incorrecto, ¿por qué no lo arreglas?

@SaeedAmiri Creo que está totalmente bien. Recuerda que no sabemos si por ejemplo

P = N P

$\mathsf{P}=\mathsf{NP}$ , para lo cual se puede basar la dureza de aproximación.

Juho

@Juho, por lo que sé, está totalmente mal incluso sabiendo que no sabemos

P = N P

$P=NP$ , el punto principal es que puede estar en dirección de reverencia (

P \neq N P

$P\not =NP$ ), Por lo que no deberíamos usar muestras malas, deberíamos usar muestras que sabemos que son correctas independientemente de cosas que no sabemos.

Puedes ver esta muy interesante respuesta sobre heurística en Wikipedia:

"Una heurística es una técnica diseñada para resolver un problema más rápidamente cuando los métodos clásicos son demasiado lentos. El objetivo de una heurística es producir una solución lo suficientemente rápida como para resolver el problema en cuestión".

La heurística podría derivar de la teoría o la experiencia experimental, pero los algoritmos de aproximación tienen una base sólida de teoría (solución demostrable).

Reza
fuente

En cuanto a su última pregunta, no existe una teoría separada para los algoritmos de aproximación para problemas que se pueden resolver en tiempo polinómico. De hecho, podría ser que $\mathsf{P}=\mathsf{NP}$ . Algunos ejemplos de algoritmos de aproximación para problemas en $\mathsf{P}$ incluyen algoritmos para álgebra lineal numérica y geometría computacional. Vea la pregunta Algoritmos de aproximación para problemas en P para más información.

Juho
fuente