Méthodes de résolution de problèmes

Programmation dynamique

Top-down

FCT TOP_DOWN(n) :
    memo <- structure de mémoïsation (tableau ou table de hachage)
    FCT REMPLIR(memo, i) :
        [Relation de récurence de la fonction sans mémoïsation sous forme récursive]
        RENVOYER memo_i
    FIN FCT
    RENVOYER REMPLIR(memo, n)
FIN FCT

Bottom-up

FCT BOTTOM_UP(n) :
    memo <- structure de mémoïsation (tableau ou table de hachage)
    [Initialisation des valeurs initiales ie les cas de base]
    [Relation de récurence de la fonction sans mémoïsation sous forme itérative (boucle)]
    RENVOYER memo_n
FIN FCT

Note : On doit connaître le nombre d'itérations à réaliser pour faire du bottom-up

Backtracking

On suppose avoir :

• une fonction racine() qui renvoie la construction initiale vide
• une fonction fils(construction partielle) qui renvoie la liste des constructions avec 1 élément en plus que celle en paramètre
• une fonction est_feuille(construction) qui détermine si la construction est complétée

FCT BACKTRACKING(construction) :
    SI est_feuille(construction) ALORS : //On vérifie si la construction est complète
        SI P(construction) ALORS : // On vérifie si la construction satisfait la propriété voulue
            S'arrêter avec cette construction comme solution
        SINON
            POUR CHAQUE construction_suivante dans fils(construction) FAIRE
                BACKTRACKING(construction_suivante)
        FIN SI
    FIN SI
FIN FCT

FCT RESOLUTION():
    BACKTRACKING(racine())
FIN FCT

Note : cette fonction ne comprend pas l'élagage de l'arbre