Sommaire

Implémentation

Dans un premier temps, on implémentera des algorithmes génériques, puis des classes héritant de ces classes mères permettent de résoudre le problème du sac à dos.

Deux versions du problème du sac à dos sont utilisées : la première est celle présentée comme exemple pour l’algorithme glouton (avec 16 objets) et la deuxième est une version plus complexe et aléatoire, qui permet de mieux comparer les différents algorithmes.

Une analyse des résultats obtenus est menée à la fin de cette partie.

1. Classes génériques

Il faut commencer par définir quelques classes ou interfaces très génériques. Celles-ci nous permettent de créer ensuite les différents algorithmes.

ISolution est une interface qui représente une solution potentielle à un problème donné. La seule obligation pour cette solution est d’avoir une propriété permettant de connaître sa valeur.

public interface ISolution {  
   double getValeur();  
}

Il est alors possible de définir un problème, là encore grâce à une interface IProbleme. On doit pouvoir obtenir une solution aléatoire (SolutionAleatoire), le voisinage d’une solution (Voisinage) et enfin la meilleure solution dans une liste fournie (MeilleureSolution). Toutes ces méthodes sont utilisées par plusieurs algorithmes. ...