approche - Page 2

Oui c'est pas linéaire, mais en explicitant x = abs(y) comme x>=y et x>=-y on s'en sort. Y a des trucs non-linéaires où tu peux feinter comme ça en ajoutant des variables avec des contraintes: abs, max, min, etc...

edit: et au fait, un programme linéaire en nombre entiers comme ça, ça fait déjà du branch&bound dans la babasse. Il fait des simplex avec la contrainte d'integrité relachée à chaque noeud. Ce que je voulais dire c'est qu'on pourrait lui montrer un algo branch&bound qui résoud directement son problème plutôt que le PLNE lui correspondant (vu qu'il a pas l'air d'être à l'aise en R.O.)

( tant qu'on a des trucs linéaires par morceaux on arrive à bricoler quoi ? -- tu m'excuses j'ai séché les cors de prog. linéaire)

oui ça doit être ça.

Euh, le linéaire par morceaux, c'est équivalent au linéaire mixed-integer, donc si tu penses te passer des contraintes d'intégralité des variables en introduisant des valeurs absolues, c'est mal parti, tu n'as pas simplifié le problème du tout.

À moins que tu ne puisses prouver P=NP, ce qui m'étonnerait , tout algorithme pour résoudre ce problème sera forcément exponentiel dans le pire des cas.

Kevin Kofler (./34) :
donc si tu penses te passer des contraintes d'intégralité des variables en introduisant des valeurs absolues

non, c'est pas ça. ce que je dis c'est qu'on peut faire:

minimiser abs(x)
sous (contraintes)

en faisant:

minimiser e
sous (contraintes) ET e >= x ET e >= -x

Kevin Kofler (./34) :
À moins que tu ne puisses prouver P=NP, ce qui m'étonnerait , tout algorithme pour résoudre ce problème sera forcément exponentiel dans le pire des cas.

Ben le simplex est exponentiel dans le pire des cas (en pratique je crois qu'il faut vraiment faire exprès ... )

very > le simplex est polynomial

PL normal: simplex
PLNE : branch&bound avec des simplex à chaque noeud

non c'est exponentiel dans le pire des cas. (tu vois bien que notre problème là est NP-complet ... )

En pratique c'est souvent "rapide", s'too.

hmmm... en fait je pense qu'on peut pas généraliser ça à tout ce qui est linéaire par morceau, je pense qu'il faut aussi que la fonction soit convexe.

./38 > En fait, le simplex ne marche qu'avec des variables réeles, c'est un truc qui se balade de sommet en sommet dans le polyèdre explicité par les contraintes.
Et dans notre cas c'est pas le simplex qui résoud, c'est un truc plus global qui lance le simplex plein de fois: il fait un branch&bound. Donc dans le pire des cas, il fera 2^n calculs oui, mais le simplex en soit est polynomial.

Ha ça doit être l'habitude d'utiliser simplement 'simplex' pour le méta-simplex

Sinon pour la convexité j'y ait pensé aussi, en fait je crois qu'il faut que la fonction délimite une partie convexe du plan (au dessus ou en dessous), donc qu'elle soit soit convexe, soit concave, mais pas un peu des deux. (par ce que bon à un - près ça revient au même )

onur> l'algo du simplexe n'est pas polynomial (mais il y a des algos polynomiaux pour la PL à variables réelles)

Méthodes de points intérieurs.

ok, je crois que me souvenir que simplex est polynomial mais que c'est pas démontré, c'est ca?

Non, pour un système dégénéré, le simplex est démontré être exponentiel.

En fait y a pas un unique algo mais une famille d'algos ; les plus courants sont exponentiels, et on ne sait pas s'il y en a des polynomiaux, c'est peut-être à ça que pensait Onur.

Pollux > ça a l'air plus détaillé en français ( http://fr.wikipedia.org/wiki/Problème_du_sac_à_dos )

En fait, cest pas tout à fait le knapsack, si?
dans le sac à dos, on maximise la valeur du sac, là il veut minimiser sa distance à N.

ah oui pardon j'ai lu ./1 un peu trop vite... ("s'approcher uniquement par additions" m'avait évoqué "suite croissante" et donc inférieure à N)

tu peux quand même l'encoder dans deux instances du pb du sac à dos (un pour les solutions <=N et un pour les >=N) donc c'est fondamentalement la même chose, mais bien sûr si tu prends un algo genre programmation dynamique c'est plus simple de l'étendre au pb de ./1 sans le couper en deux ^^

On est d'accord.

Je n'ai pas lu vos pages. L'algo auquel je pense trouverait la solution en (N-1)+(N-2)+...+(N-(N-1)) tests. Ca fait bien N(N-1)/2 opérations ?
On a bien un truc grosso-modo exponentiel.

Sur une liste de 10 nombres, on aurait besoin de 45 opérations. Les algos que vous proposez font mieux ?

oui ca fait qlqchose comme N(N-1)/2, mais c'est pas tellement exponentiel ^^

ça fait N(N–1)/2 oui, donc c'est pas du tout exponentiel (N n'est pas en exposant ), c'est quadratique, mais c'est louche, aussi

Thibaut, sont-ce des paires de nombres que tu essaies d'additionner là? Pour résoudre le problème, il faut aussi prendre en considération les sommes de plus de deux nombres!

Oui oui.

Jyaif : Ca s'approche de N². C'est pas ça un algo exponentiel ? On appelle ça un algo quadratique ?

n^2 est un algo quadratique.
2^n est un algo exponentiel.

oui exponentiel ça veut dire que N est en exposant.
Quadratique veut dire que N est au carré, cubique qu'il est au cube, polynomial que la complexité est de l'ordre d'un polynôme en N (ce qui revient en fait à être O(N^k) pour un certain k, les autres puissances n'étant pas significatives)

Moi je pense à un truc comme ça:

On trie le tableau d'entrée par ordre décroissant (n log(n)) jusque là on est bon.
On déclare deux variables où on met:
meilleurSol == la meilleure solution trouvée (c'est une liste qui est un sous-ensemble de la liste de début)
meilleurSolVal == la valeur de cette solution (la somme des nombres qu'il y a dedans)


f(i) {
si (i> tableauDuDebut.length) return;
On regarde l'élément n° i, est-ce que son ajout à meilleurSol donne une meilleure solution? (est-on plus proche de N?)
Si oui, on dit meilleurSol = meilleurSol + {premier élément}, et appelle f(i+1)
si non, return;
}

au début, on appelle f(0)
... un truc du genre.

Bon, le fait de mettre dans l'ordre décroissant ne sert à rien, je pensais encore au cas où on ne doit pas dépasser N et éliminer la solution et la suite du tableau à partir de l'indice i+1, si jamais ca dépassait N.

Mais bon, grosso modo l'idée est là, je pense que tu peux t'en sortir avec un truc comme ça.

On ne fait pas un parcours linéaire du tableau dans ce cas ? Autrement dit, on ne testerait que N solutions parmi N(N-1)/2

si, il manque qq chose en effet (jy pensais sous la douche là )

il faut pas appeler seulement f(i+1), mais aussi f(i+2), f(i+3)... jusqu'à f(tableauDeDepart.length)

edit: bon cest pas bien au point encore.