Différence entre l'algorithme heuristique et l'approximation?

j'ai un problème concernant la situation suivante.

J'ai deux tableaux de nombres comme celui-ci:

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

supposons maintenant que le deuxième tableau est très difficile à calculer, mais j'ai remarqué que si j'ajoute

A [i] + A [i + 1]

dans le tableau 1 j'obtiens le nombre très proche du nombre A [j] dans le tableau 2.

Ma solution est-elle une heuristique ou une approximation?
Si j'avais une raison de croire que je ne dépasserai jamais la valeur de A [j] par + -x avec cet algorithme et que je peux le prouver, alors ma solution serait-elle une heuristique ou une approximation?

Existe-t-il une littérature traitant des questions heuristiques vs d'approximation pour les problèmes de classe P où la solution peut être obtenue en temps polynomial mais l'entrée est tout simplement trop grande pour qu'un algorithme de temps poly soit pratique.

Merci

approximation heuristics user6697
la source

Vous devez d'abord définir ce que vous voulez approximer afin de juger si votre approche est une approximation.

Dan

Quel est exactement le problème d'optimisation que vous essayez de résoudre? Une fois que cela est connu, si vous prouvez des limites, votre heuristique devient une approximation. De plus, les seuls problèmes (classiques, c'est-à-dire sans streaming) dans P qui ont des algorithmes d'approximation (que je sache) sont des algorithmes de flux max.

Nicholas Mancuso

ok donc la chose que je souhaite calculer sont les nombres dans le deuxième tableau. mais cela prend trop de temps, mais j'ai compris que si j'ajoute deux valeurs consécutives du tableau 1 ensemble, j'obtiens quelque chose de correct et je peux prouver que l'estimation sera toujours comprise entre + et x. alg initial pour calculer A [j] est O (n ^ 100)

user6697

Je comprends que vous souhaitez calculer les nombres dans le deuxième tableau, mais quelle est la formulation du problème d'optimisation. Étant donné que X calcule Y sous les contraintes de Z. Dire que vous voulez calculer une fonction arbitraire n'aide pas.

Nicholas Mancuso

Votre solution est un parfait exemple d'heuristique!

Björn Lindqvist

Réponses:

Une heuristique est essentiellement une intuition, c'est-à-dire que le cas que vous décrivez ("j'ai remarqué qu'il est proche", vous n'avez pas de preuve qu'il en est ainsi) est une heuristique. Tout comme la résolution du problème des vendeurs itinérants en partant d'un sommet aléatoire et en se rendant au plus proche pas encore visité à chaque étape. C'est une idée plausible , qui ne devrait pas donner une trop mauvaise solution. Dans ce cas, il peut être démontré qu'il ne donnera pas toujours une bonne solution.

Un algorithme d'approximation est généralement compris comme donnant une solution approximative, avec une sorte de garantie de performance (c'est-à-dire qu'il résout le TSP, et le coût total n'est jamais inférieur de plus d'un facteur 2; ou mieux encore, il résout le TSP et, en fonction de <certains paramètres pouvant être modifiés> la solution n'est jamais pire qu'optimale de plus d'un facteur , où dépend de <paramètres>). $1 + \epsilon$ $\epsilon$

vonbrand
la source

Vous avez utilisé un mauvais échantillon, TSP est difficile à estimer, donc il n'y a pas de PTAS pour TSP, il n'y a pas non plus d'approximation 2 pour TSP est facile à montrer s'il y a un temps polynomial 2-approximation pour TSP il y a un algorithme de temps polynomial pour résoudre le problème du cycle hamiltonien , Je pense que vous voulez dire le TSP métrique qui est un cas spécial mais il n'y a toujours pas de PTAS dans ce cas (et il est impossible d'avoir PTAS sauf P = NP). Je suggère de choisir l'emballage bin pour en parler. (ou tout autre problème plus simple).

@SaeedAmiri, c'était juste à des fins d'illustration. Ce n'est peut-être pas le meilleur exemple (comme vous le dites), mais le problème est facile à comprendre. Merci pour le commentaire.

vonbrand

Donc, si vous comprenez que c'est un mauvais exemple, pourquoi ne le corrigez-vous pas?

@SaeedAmiri Je pense que c'est très bien. N'oubliez pas que nous ne savons pas par exemple si , pour lequel la dureté d'approximation peut être basée.

P = N P

$\mathsf{P}=\mathsf{NP}$

Juho

@Juho, par ma connaissance est totalement faux même en sachant que nous ne savons pas , le point principal est peut-être est dans le sens inverse (

P = N P

$P=NP$

P \neq N P

$P\not =NP$ ), Nous ne devons donc pas utiliser de mauvais échantillons, nous devons utiliser des échantillons dont nous savons qu'ils sont corrects indépendamment des choses que nous ne savons pas.

Vous pouvez voir cette réponse très intéressante sur l' heuristique dans Wikipedia:

"une heuristique est une technique conçue pour résoudre un problème plus rapidement lorsque les méthodes classiques sont trop lentes. L'objectif d'une heuristique est de produire assez rapidement une solution suffisamment bonne pour résoudre le problème en question.".

L'heuristique pourrait dériver de la théorie ou de l'expérience expérimentale, mais les algorithmes d'approximation ont une base théorique solide (solution prouvable).

Reza
la source

Quant à votre dernière question, il n'y a pas de théorie distincte pour les algorithmes d'approximation des problèmes qui peuvent être résolus en temps polynomial. En fait, il se pourrait que $\mathsf{P}=\mathsf{NP}$ . Quelques exemples d'algorithmes d'approximation des problèmes dans $\mathsf{P}$ inclure des algorithmes d'algèbre linéaire numérique et de géométrie de calcul. Voir la question Algorithmes d'approximation pour les problèmes dans P pour plus.

Juho
la source