Bah les recherches en profondeur et en largeur c'est vraiment quand t'as pas d'autres idées, parce que bon niveau optimisation c'est vraiment pas top...
En général pour trouver une bonne heuristique on relaxe une ou plusieurs contraintes du problème, dans le but d'avoir une fonction qui minimise la distance à la solution.
@++