Algorithmie Résolu/Fermé

Question

Bonjour,

J'aurais besoin de savoir s'il un algorithme existe déjà pour résoudre mon problème (ou si je dois en chercher un moi-même, ce que je n'espère pas).

Je dispose de couples de valeurs (a, b) connus avec, pour tous les couples, a > 0 et b < 0.
De chacun de ces couples je voudrais choisir au mieux a ou b, tel qu'à la fin, la somme de tous ceux qui ont été choisis soit la plus petite possible (positive). Bien évidemment j'aimerais éviter de faire toutes les sommes possibles puis sélectionner la "bonne". Tous comme les algos de plus court chemin.

Par exemple :
(1, -1)
(2, -1)
(7, -12)

Il y a 6 sommes possibles, mais celle qui me convient dans cet exemple est 5 (en faisant -1 + -1 + 7). Je l'ai trouvé en faisant les 6 sommes, mais j'aimerais ne pas faire comme ça justement ... parce que là il n'y a que 3 couples, mais avec beaucoup de couples ça devient vite l'horreur :) (complexité exponentielle 2^n).

Tous les algos du genre (plus court chemin et compagnie) portent les noms de ceux qui les ont inventés "algorithme de toto", "algorithme de bidule", ... ce n'est pas explicite, et c'est pourquoi je ne trouve pas si cet algo que je demande existe.

Est-ce que quelqu'un aurait une idée ? :)
Sinon je pense que ça doit se faire "à la Dijkstra", mais si quelqu'un l'a déjà fait ça me conviendrait bien, je n'aurais qu'à pisser le code :).

KX · Answer

Je vais réfléchir à ton problème, mais je ne connais pas d'emblée de solution...
J'ai essayé de formaliser ton problème, dis moi si jamais il y avait une erreur :

On a n couples (a1,b1) (a2,b2) ... (an,bn) avec pour tout i : ai>0 bi<0
Et on cherche les ci (avec ci=ai ou bi) tels que s=somme(ci,i=1..n) soit positif et minimal

artragis · Answer

Bonjour, je vais te l'avouer je ne comprends pas ton problème... tu dis que tu as fait -1+-1+7 mais pourquoi?
la somme minimale positive aurait été -1+1+2 non?
ici j'ai pris a1+b1+a2 
si j'ai faux, dis le moi parce que là je n'ai pas pigé ton problème. N'hésite pas à redire quoi. (ps si tu dis vrai, que c'est de complexité 2^n, alors avec 3 couples tu as 8 sommes possibles et non 6)

bizu53 · Answer

Je pense que cela doit se résoudre en utilisant les écarts a-b de chaque couple. En traitant les couples dans l'ordre de celui ayant le plus grand écart vers le plus petit. Et de voir si on peut "compenser" le nombre avec ce qu'il reste. Cela me paraît être une bonne méthode mais je n'ai pas testé beaucoup de cas pour l'affirmer.

Pour reprendre mon exemple de tout à l'heure ça ferait commencer par 
7 qu'on pourrait compenser au max par -2
ou alors -12 qu'on pourrait compenser au max par +3

On élimine ainsi directement "l'étude" avec le -12 car la somme finale serait forcément négative.

Vous y voyez un problème à cette proposition d'algo ? Ou en voyez-vous un plus efficace encore ?

KX · Answer

Je ne sais pas trop ce que ça vaut mais regarde ce que ça peut te donner si tu choisis à chaque fois celui dont la valeur absolue est la plus faible, en repérant bien lequel tu as choisis.

Puis à la fin si ton résultat est positif je dirais que c'est forcément le résultat attendu (à démontrer)
Et si ton résultat est négatif, il faut que tu affines en cherchant parmi les valeurs négatives que tu as prises lesquelles pourrais tu exclure (c'est à dire choisir le positif à la place) pour compenser ta somme et qu'elle devienne positive

artragis · Answer

Moi je propose un truc qui pourait peut être marcher : tu pars de la somme de tous les a (1, -1) (2, -1) (7, -12) 1+2+7=10 puis tu enlèves le plus grand a pour mettre le b qui lui correspond 1+2-12=-9 comme c'est pas bon, on laisse le plus grand a, maintenant on va remplacer le a intermédiaire 1-1+7=7 tiens on a une somme positive plus petite que la somme de tous les a... essayons de remplacer le plus petite a par son b -1-1+7=5, c'est encore plus petit... et on tombe sur le bon résultat je prends des autres couples (10;-3) (3;-1) (5;-2) 10+3+5=18 remplacement du 10 -3+3+5=5... ha... remplacement du 5 -3+3-2=-2... on garde le 5 remplacement du 3 -3-1+5=1... on peut pas mieux de toutes façon... apparement ça marcherait... j'écris donc un niveau général de l'algorithme : 1) ranger les couples dans l'ordre décroissant des a 2)faire la somme des a qu'on appellera S 3)maintenant les remplacements ==>tant que iS prend une nouvelle valeur : on lui enlève la valeur de a[i] et on lui ajoute b[i] ==>si S<0 alors on enlève b[i] et on ajoute a[i] fin si fin tant que je sais pas si c'est vraiment bon mais c'est une piste selon moi

KX · Answer

J'essaye de voir comment marche ton algorithme dans le cas général Mais j'ai des difficultés à l'étape 2... n=4 (a1,b1) (a2,b2) (a3,b3) (a4,b4) Étape 1 : élimination éventuelle a1/b1 (2 opérations) a1+b2+b3+b4<0 donc on garde b1+a2+a3+a4>0 donc on garde Étape 2 : élimination éventuelle (a1+a2)/(a1+b2)/(b1+a2)/(b1+b2) (4 opérations) Commençant par a1 : (a1+a2)+b3+b4<0 donc on garde (a1+b2)+a3+a4>0 donc on garde // problème ici Commençant par b1 (b1+a2)+b3+b4<0 donc on garde // et ici (b1+b2)+a3+a4>0 donc on garde Dans la mesure où on mélange les a et les b comment choisir si on les garde quand ils sont <0 ou >0 ?

KX · Answer

Le problème avec les complexités c'est qu'il faut toujours se placer dans le pire cas.
Quand tu dis que les 4 opérations pourrait n'être que 2, je suis d'accord, mais au pire cas il y en a 4...
Et donc au pire cas tu arrive à O(2^n), bien sûr tu n'atteindras jamais 2^n mais pour des n grands tu auras quand même une complexité exponentielle !

KX · Answer

J'ai uneidée d'algorithme en O(n.log n) même s'il ne marche pas tel quel...
Tu tris tes couples comme le proposait artragis (c'est là qu'on a le n.log n)

Tu prends un "couple-somme" que tu initialise en faisant le calcul sur les deux premiers couples...
Puis pour chaque couple suivant tu fais le calcul suivant entre le couple somme et le couple regardé

exemple : 

(6; -2) 
(5; -9)
(7; -8)
(15; -11)

(6,-2) et (5,-9) => on prends 5 et -2 on obtient un couple-somme (6+5,-2-9)=(11,-11)
(11,-11) et (7,-8) => on prends 7 on obtient un couple-somme (11+7,-11-8)=(18,-19)
(18,-19) et (15,-11) => on prends -11 on obtient un couple-somme (18+15,-19-11)=(33,-30)

Et là j'obtiens 5 / -2 / 7 / -11, alors je sais que c'est pas positif, mais en changeant la façon de faire le tri ou la façon de calculer le couple-somme... y a peut-être moyen de le faire en O(n.log n)

KX · Answer

(6,-2) et (5,-9) => on prends 5 et -2 car 5-2>0 alors que 6-9 non
(11,-11) et (7,-8) => on prends -8 car 11-8>0 alors que 7-11 (autant pour moi je me suis trompé)
(18,-19) et (15,-11) => on prends -11 car 18-11>0 alors que 15-19 non...

En fait c'est la façon de calculer la couple-somme qu'il faut changer, en ne prenant que ceux qu'on a séléctionné avant ça ferait

(6,-2) et (5,-9) => on prends 5 et -2 d'où (5,-2)
(5,-2) et (7,-8) => on prends 7 d'où (12,-2)
(12,-2) et (15,-11) => le problème c'est que 15-2 et 12-11 sont tous deux positifs...

Je vais travailler l'idée... je vais peut-être trouvé (l'ordre du tri doit jouer aussi...)

bizu53 · Answer

Pour un exemple pas mal à tester :
(100; -1)
(1; -50)
(12; -3)
(10; -60)

La somme min est 100-60-50+12=2 (et non -1+1-3+10=7).
Il élimine toutes mes idées d'algo à tendance abusive de "recherche de minimum".

KX · Answer

Je vais partir du problème initial et avec quelques transformations le transformer en un autre problème qui doit avoir déjà été résolu...

on a (a1,b1), (a2,b2)... (an,bn)
soit S=a1+a2+...+an
et c1=a1-b1, c2=a2-b2, ... cn=an-bn

Rechercher pour chaque couple (ai,bi) lequel de ai ou bi choisir, ça revient à chercher une somme de ci (avec chaque ci pris 0 ou 1 fois) tel que cette somme se rapproche de S
Si on utilise c1 alors c'est qu'on a pris b1 et non a1, idem pour c2.. cn
Le résultat final sera alors la différence entre S et la somme des ci

Exemple : (100,-1)=>101 / (1,-50)=>51 / (12,-3)=>15 / (10,-60)=>70 / S=123
On cherche à obtenir 123 en sommant 101,51,15 et 70
Par exemple en faisant 51+70=121
Donc on a pris 100, -50, 12, -60 (ce que tu trouvais précédemment)
Et le résultat obtenu est 123-121=2 !

Il reste "plus qu'à" trouver un algorithme qui permette de trouver une telle somme de ci, mais ça ressemble un peu à la partie chiffre du jeu "Des chiffres et des lettres" et c'est pourquoi je pense que l'algorithme doit déjà exister...

bizu53 · Answer

Waouh ! En cherchant à optimiser mon code je me suis aperçu d'une chose. En fait j'étais trop dans la vision "arbre de recherche de solution" mais je me suis rendu compte (du fait des coupures systématiques) que c'est super simple, seulement fallait y penser ^^. En considérant les couples (pi; ni) (p de positif et n de négatif) Au début je faisais dans mon arbre p0+somme(ni) et n0+somme(pi) (car p0+somme(pi) et n0+somme(ni) étaient obligatoirement éliminés du fait du tri initial). Mais en construisant mon arbre je ne fais rien d'autre que chercher quel p_i (ou n_i) compense "trop". C'est tellement simple que même à la main ça le devient :) Par exemple : Avec (15; -11) /26 (7; -8) /15 (5; -9) /14 (1; -2) /3 (1; -1) /2 Je fais p0+n1+n2+n3+n4 = -5 C'est donc trop compensé de 5, donc je regarde les écarts pour avoir la plus petite somme supérieure ou égale à 5 => 2+3, des couples 4 et 5, donc je change mon choix pour 4 et pour 5. Ce qui me fait p0+n1+n2+p3+p4 = 0 Je fais de même en partant de n0 n0+p1+p2+p3+p4 = 3 C'est trop compensé de 3, donc je regarde les écarts pour avoir la plus grande somme inférieure ou égale à 3 => 3, du couple 3, donc je change mon choix pour 3 Ce qui me fait n0+p1+p2+n3+p4 = 0 aussi. Pour un autre exemple où il n'y a qu'une solution : (100; -1) /101 (10; -60) /70 (1; -50) /51 (12; -3) /15 p0+n1+n2+n3 = 100-113 = -13, je change donc de choix pour le 3 (puisque 15 est le minimum >= 13) p0+n1+n2+p3 = -13+15 = 2 Je regarde en partant de n0 n0+p1+p2+p3 = -1+23 = 22, je change donc de choix pour le 3 aussi (puisque 15 est le max <= 22) n0+p1+p2+n3 = 22-15 = 7 2<7 donc c'est p0+n1+n2+p3 la somme minimale :) Je ne sais pas la complexité de cette méthode mais je ne pense pas qu'on puisse trouver mieux :) edit : bon, avec un nombre important de couples il faut également faire un autre petit algo pour trouver la "meilleure" somme selon le cas en fonction des écarts.

Algorithmie

12 réponses

Discussions similaires