La plupart des algorithmes qui concernent l’optimisation de combinaisons peuvent être divisés en deux catégories : les algorithmes complets qui trouvent la solution optimale, mais qui doivent éventuellement travailler en un temps exponentiel, et les algorithmes polynomiaux qui trouvent seulement une solution approchée. Ces derniers ont l’avantage de ne consommer que très peu de temps pour donner une solution. Entre ces deux catégories, il existe les algorithmes à temps quelconque ("anytime") qui ont la particularité de trouver une meilleure solution plus ils travaillent longtemps.

Les algorithmes présentés ici ont la particularité de partir d’une approche polynomiale. Ils sont ensuite améliorés pour donner un algorithme complet qui cherche une meilleure solution. Ces algorithmes sont appelés algorithmes complets à temps quelconque (" complete anytime algorithm "). Dans les méthodes de résolution, nous verrons ainsi deux algorithmes complets à temps quelconque : le " Complete Greedy Algorithm " et le " Complete Karmarkar-Karp ".

Considérons le problème suivant : Deux machines doivent se partager un travail constitué de plusieurs tâches dont on connaît le temps d’exécution. Dans le but d’effectuer cette tâche dans le temps le plus court, on veut repartir le travail de sorte que les temps de travail de chaque machine soient quasiment le même. Ce problème nécessite donc de répartir le travail, c’est donc un problème de répartition de nombres.

Prenons par exemple la suite d’entiers (8, 7, 6, 5, 4). On peut diviser cette suite en deux sous-suites (8, 7) et (6, 5, 4) dont la somme pour chaque sous-suite est égale à 15. La différence entre les deux suites est donc égale à 0. Cette solution est optimale, on a une partition parfaite. Si la somme totale des entiers est impaire, on aura alors une solution optimale pour une différence de 1.

L’algorithme le plus simple est de chercher toutes les solutions possibles , c’est-à-dire combiner les nombres de la liste de telle sorte que la somme de ces nombres soit la plus proche possible de la moitié de la somme totale. S’il y a N nombres dans la partition, il y a 2^n combinaisons possibles. La complexité est donc linéaire par rapport au nombre d’éléments. Cette approche est impraticable pour des problèmes de plus de 40 éléments à cause de la complexité en temps.

Horowitz et Sahni ont trouvé comment réduire le temps de résolution du problème de partition. Pour cela, ils ont réduits l’espace de travail en divisant l’espace de taille n en deux sous espaces de taille n/2.

Prenons un exemple avec comme ensemble initiale (4,5,6,7,8), on le divise en (4,6,8) et (5,7).

La seconde étape de l’algorithme est de calculer toutes les sommes possibles de nombres d’une liste :

(4,6,8) à 4+6=10
à 4+8=12
à 6+8=14
à 4+6+8=18
(5,7) à 5+7=12

On introduit ces sommes dans les ensembles dont elles sont issues. On obtient deux listes : (0,4,6,8,10,12,14,18) et (0,5,7,12). On remarque que l’on a introduit ‘0’, cela n’a aucune incidence sur le résultat, on peut ajouter ‘0’ dans une liste sans modifier la somme des éléments de celle-ci.

Le but de l’algorithme est de trouver deux ensembles dont la somme des éléments de chacun soient le plus proche possible, cela équivaut à trouver une liste de nombre dont la somme est égale à la moitié de la somme de tous les nombres.

Dans notre exemple on cherche donc une liste dont la somme des éléments est égale à (4+6+8+5+7)/2=15.

Nous allons utiliser nos deux sous-listes pour s’approcher de cette solution, l’une d’elle servira a augmenter la somme de notre ensemble, l’autre a diminuer. Pour cela, on place un ‘pointeur ‘ sur le début d’une liste, et un autre sur la fin de la seconde.

(0,4,6,8,10,12,14,18)

(0,5,7,12)

on calcule la somme des deux éléments pointés 0+12=12, on compare avec le nombre souhaité (12<15), il est donc nécessaire d’augmenter le premier pointeur.

(0,4,6,8,10,12,14,18)

(0,5,7,12)

On obtient le déroulement suivant :

Lorsque l’on trouve le résultat souhaité, on obtient le premier ensemble (7,8), le second est (4,6,8).

Dans notre exemple, on trouve 7 et 8 dans le premier ensemble, ces nombres faisaient partis de l’ensemble initiale. Si les nombres trouvés sont le résultat de somme, on remplace la somme par les nombres qui composent cette somme.

L ‘ensemble initiale étant divisée en deux listes de taille n/2, générer toute les sommes nécessite un temps d’ordre O(2^n/2), le tri nécessite O(2^n/2log(2^n/2)) ou O(n*2^n/2). La complexité générale est donc de O(n*2^n/2). Le réel problème est qu’il est nécessaire de posséder beaucoup de mémoire pour mémorise les additions (pas seulement le résultat, les nombres utilisés sont aussi importants) . Cependant le gain est intéressant, on passe d’un problème O(2ⁿ) à un problème O(2^n/2).

Il consiste à classer les nombres dans l'ordre décroissant. On utilise deux listes qui vont stocker les nombres. On place alors le plus grand nombre dans une de deux listes. Puis on place le nombre suivant dans la liste dont la somme totale est la plus petite. Et ainsi de suite jusqu'à la fin.

Par exemple, on prend la liste triée (8,7,6,5,4) ; on aura les états suivants :

[8] , [0] : (7,6,5,4)
[8] , [7] : (6,5,4)
[8] , [7,6] : (5,4)
[8,5] , [7,6] : (4)
[8,5,4] , [7,6]

En réalité seul la différence entre les deux sous-listes importe ; ce qui donne pour notre exemple :

8 : (7,6,5,4)
1 : (6,5,4)
5 : (5,4)
0 : (4)
4 : ( )

Cet heuristique est aussi appelé KK. Il s'agit d'un algorithme qui est de temps polynomial (asymptotiquement).

L'initialisation de l'algorithme se fait tout d'abord par le tri des nombres par ordre décroissant. Ensuite, nous considérons que placer deux nombres dans deux groupes va créer une différence entre la somme de ces deux groupes égales à la différence de ces deux nombres. Le but de l'algorithme est de réitérer ce procédé en commençant par les plus grands nombres. La différence trouvée sera considérer comme un nombre de la nouvelle liste à trier. On continu ce programme en utilisant les plus petits nombres jusqu'à ce qu'il ne reste qu'un seul nombre. Voici un exemple simple permetant de comprendre le fonctionnement.

Si l'on veut retrouver les deux sous-listes, il est nécessaire de mémoriser chaque opération intermédiaire.

{8,7,6,5,4}
{6,5,4,1=8-7}
{4,1,1=6-5}
{3=4-1,1}
{2=3-1}

Puis on remonte l'algorithme de bas en haut:

2=3-1
2=(4-1)-1
2=(4-1)-(6-5)
2=(4-(8-7))-(6-5)
2=4+7+5-8-6

On considère que tous les nombres positifs sont situés dans le même sous-ensemble, les autres sont situés dans l'autre sous-ensemble.

On a deux ensembles:
{7,5,4} à 7+5+4=16
{8,6} à 8+6=14

La différence est bien 2 (16-14=2)

L’algorithme est O(n*log(n), ce qui est un gain important. Cependant on remarque que cet algorithme ne donne pas la solution optimale.

L'algorithme Greedy ne donne pas la bonne solution ; pour qu'il trouve une solution optimale, nous allons utiliser un arbre binaire de profondeur N. A chaque noeud, on va placer le nombre dans la liste dont la somme est la plus petite (comme pour le Greedy). Si la solution optimale n’est pas trouvée, on remonte dans l’arbre et on place le dernier nombre placé dans l’autre liste. Puis tant que l'on n’a pas trouvé de solution dont la différence est 0 ou 1, on continue à tester le reste de l'arbre. A chaque feuille, on teste la solution obtenue afin de retourner une solution améliorée tout au long de la recherche dans l'arbre.

La solution est trouvée dans cet exemple au niveau de la feuille 4(4). Il n’est donc pas nécessaire de continuer le reste de l’arbre. On peut améliorer l'algorithme en vérifiant qu'aux noeuds où l'on augmente la différence des deux listes, on n'a pas la somme des nombres restants égale à la différence. On peut ainsi détecter plus rapidement la solution.

Le temps d’exécution de l'algorithme est au maximum de O(2ⁿ) puisque l'on cherche une solution dans un arbre binaire de profondeur n. L'espace occupé est de O(n) puisque l'on cherche une profondeur.

Il s'agit d'une extension de l'algorithme KK. A chaque cycle, l'heuristique KK place les deux plus grands nombres dans deux sous-ensembles distincts. Cela se caractérise par le fait que l'on fait la différence entre ces deux nombres. L'autre solution possible (et c'est la seule possible) consiste à placer les deux plus grands nombres dans le même ensemble. Cela va se caractériser par le fait que l'on va additionner les deux plus grands nombres.

Notre programme est l'arbre suivant:

Si on applique sur notre exemple initial, on obtient:

On remarque que la feuille la plus à gauche correspond à KK.

On obtient un arbre qui a un nombre de feuille exponentiel. On a en effet 2^n-2 feuilles (avec n: la taille de l'ensemble initial).

Cependant on peut optimiser le parcours de l'arbre. En effet, à chaque cycle, on peut vérifier que le plus grand élément d'un ensemble soit inférieur à la somme des autres. Si ce n'est pas le cas, alors la solution optimale consiste à séparer le plus grand élément de tous les autres ( c'est à dire que l'on effectue uniquement des soustractions). On va alors parcourir les noeuds les plus à gauche.

Bien sur, si l'on trouve une solution qui donne un delta de 0, alors le programme s'arrête.

Les algorithmes bruts étant longs à trouver une solution, les algorithmes polynomiaux ne trouvant pas toujours la meilleure solution, il nous parut évident que les algorithmes complets à temps quelconques étaient les plus intéressants à étudier. Il fut donc décidé d’implémenter les algorithmes " Complete greedy Algorithm " et " Complete Karmarkar-Karp ". Les deux algorithmes sont implémentés en C.

Une fois les algorithmes implémentés, il fut apporté quelques optimisation. Tout d’abord, au niveau de la définition des types : le but étant de tester les algorithmes sur des nombres entre 1000 et 10000, deux types de variables pouvaient être utilisés pour définir les nombres en mémoire. Le type " unsigned int " codé sur 16bits permettait ainsi de gagner en mémoire par rapport au type " double " codé sur 32 bits. On a ainsi pu remarqué que le programme fonctionnait environ deux fois plus vite pour le type " unsigned int " que pour le type " double ". Le type " unsigned int " fut donc choisit ; il permet de coder les nombres de 0 à 65535.

Une autre optimisation importante a été le test de fin de programme. Les différents programmes s’arrêtaient lorsque la différence entre les deux sous-listes étaient nulles. Cependant, on peut remarquer que si la somme de tous les nombres est paire, la différence ne peut être égale à 1. Si cette somme est impaire, delta optimal est 1. On a alors considéré la condition d’arrêt :

SI Delta_temporaire <= 1 ALORS Fin_Programme = 1
au lieu de
SI Delta_temporaire == 0 ALORS Fin_Programme = 1

Cette optimisation n’est efficace que si les nombres sont supérieurs à 1 (l’ensemble initial comporte des nombres entre 1000 et 10000)

On remarquera que dans notre arbre, chaque branche de gauche correspond à une soustraction, l'autre branche étant une soustraction. Une solution consisterait à effectuer un parcours récursif (profondeur d'abord). Cependant, il serait nécessaire de mémoriser tous les résultats intermédiaires, cela nuirait à l'efficacité du programme.

Une autre méthode consiste à non pas mémoriser les résultats intermédiaires, mais la feuille souhaitée. Pour cela étudions l'arbre des solutions et plus particulièrement les opérations nécessaires pour arriver à une feuille:

On remarque que si l'on code les opérations '-' et '+' par des bits, tels que '-'='0' et '+'='1' alors les opérations nécessaires pour obtenir une feuille correspondent au numéro de la feuille.

En utilisant cette propriété, nous allons utiliser une fonction CKK qui prends un entier en argument. Cet entier corresponds au numéro de la feuille étudiée, la fonction retourne un entier correspondant à la différence des deux sous-listes. On lance tout d'abord CKK(0) qui corresponds à KK, puis CKK(1),CKK(2) tout en mémorisant le meilleur résultat obtenu (principe des "anytime algorithm") et le numéro de la feuille correspondant.

Afin de ne pas parcourir les 2ⁿ feuilles, à chaque étape ( à chaque noeud) on vérifie que le plus grand nombre de la liste est inférieur à la somme de tous les autres. Si ce n'est pas le cas, alors on ne lance pas CKK(i+1) mais CKK(i+k) (avec k déterminé en fonction du noeud où le test à réussi) :

On a ainsi un programme qui n'utilise que des déplacements de bits et des opérations basiques (addition,soustraction), cela permet d'obtenir un résultat rapidement.

Lorsque l'on possède le nombre correspondant à une solution, on détermine facilement les opérations à utiliser sur la liste initiale pour obtenir les deux sous-listes finales. Pour cela, nous allons utiliser une nouvelle structure. Cette structure est composée d'un entier et de deux sous listes: caractérise par exemple deux sous listes {2,3} et {7} . On définit alors les opérations additions et soustractions par

avec g3 = g1 U g2 ; d3= d1 U d2 ; C= B+A

avec g3 = g1 U d2 ; d3= d1 U g2 ; C= |B-A|

A la fin de toutes les opérations d'addition et de soustraction, on obtient avec F, la différence entre les deux sous listes, 'g' une sous-liste et 'd' l'autre sous-liste.

Un premier programme utilisait uniquement les structures, on pouvait alors utiliser un algorhitme récurssif. Cependant cette solution s’est avérée inneficace, les opérations d’addition et de soustraction nécessitaient d’utiliser beaucoup mémoire. Ainsi, l’algorithme étai trop lent et nécessitait un espace mémoire important.

La solution d’un algorithme non récursif s’est imposé, on a fait le choix d’un programme qui effectue beaucoup d’opération, mais ces opérations sont basiques et extrèmement rapides.

Les algorithmes implémentés CGA et CKK trouvent tous les deux la solution optimale.

Nous avons utiliser un programme générant aléatoirement l’ensemble initiale (de taille variable). Puis nous avons appliquer nos différents programmes (CGA et CKK).

Nb : Le tableau représente les résultats pour 1000 itérations. Par exemple, pour un ensemble initial de 5 nombres, le programme calcul en moyenne 14.982 neoud (14592/1000).

La première colonne représente le nombre de noeuds nécessaires pour trouver la meilleure solution. Elle caractérise le nombre de calcul nécessaire.

La dernière colonne représente le nombre de cas

On remarque un pic pour un ensemble initial de taille 18. Cela veut dire qu si l’ensemble initial est plus petit, l’algorithme effectue moins de calcul (ce qui est logique). Si l’ensemble initial est supérieur, il y a plus de chance de trouver la solution optimale dans les premières itérations, l’algorithme effectue moins de calcul.

Nb : Les deux courbes ont été lissées (ce qui explique que l’on ait des résultats négatifs)

On remarque que pour des ensembles initiaux de taille importante, CKK est plus efficace que CGA.

Les résultats obtenus correspondent aux attentes, notamment aux implémentations réalisées par d’autres équipes.

On remarque que le CKK surpasse toujours le CGA, en effet le nombre de nœuds utilisé est toujours moindre dans le cas du CKK surtout pour une quantité de nombres supérieure à 20. Sur les graphes obtenus, on remarque deux régions qui dépendent de la quantité de nombre à partitionner. Pour des valeurs inférieures à 20, les algorithmes CGA et CKK se valent (léger avantage à CKK). Pour des valeurs supérieures à 20, CKK génère moins de nœuds que CGA. Cela est dû à l’algorithme lui-même car CKK supprime plus vite des cas impossibles. La rupture à 20 provient de l’espace des nombres choisis [1000-10000]. Quand 5 nombres sont choisis dans cet espace, il y a peu de chance que l’on puisse avoir une partition exacte. Tandis que si l’on en prend 50, il y a une très forte probabilité.

Si l’on voulait trouver une solution approchée en un temps déterminé, il faudrait d’abord voir la place mémoire désirée. En effet, pour des temps courts, les deux algorithmes donnent des résultats équivalents. Pour les implémentations réalisées en C, CKK prend moins de place que CGA.