C'est pas évident en fait :). Ce 7 n'est pas la valeur exacte, ce n'est qu'une borne supérieure qui suffit à donner l'ordre de grandeur. Je te fais une réponse un peu plus précise ci dessous mais qui suppose que tu as vu la vidéo suivante :): ua-cam.com/video/GzuD9bK3NUA/v-deo.html Les configurations possibles d'un sommet dépendent des h labels pair/impair + composantes connexes. Mais ces configurations sont contraintes par différentes propriétés (comme le fait que le nombre de labels impairs doit être pair mais il y en a d'autres) dont il faut tenir compte si on veut les dénombrer finement. On peut borner ce nombre de configurations (supérieurement) par une fonction de l'ordre de 7^h ce qui est suffisant pour indiquer un pire cas de la complexité. On peut faire le calcul exact mais pas avec une formule analytique simple (closed form). On peut néanmoins avoir une formule plus précise dans laquelle le 7 devient un (4 + racine(8)) soit environ 6.83. Cette formule est par ailleurs plus complexe ce qui n'est pas vraiment utile pour communiquer l'ordre de grandeur.
Excellente video pour étudiants en recherche opérationnelle
Très intéressant mais pourquoi l'espace des solutions O est une puissance de 7?
C'est pas évident en fait :). Ce 7 n'est pas la valeur exacte, ce n'est qu'une borne supérieure qui suffit à donner l'ordre de grandeur.
Je te fais une réponse un peu plus précise ci dessous mais qui suppose que tu as vu la vidéo suivante :): ua-cam.com/video/GzuD9bK3NUA/v-deo.html
Les configurations possibles d'un sommet dépendent des h labels pair/impair + composantes connexes. Mais ces configurations sont contraintes par différentes propriétés (comme le fait que le nombre de labels impairs doit être pair mais il y en a d'autres) dont il faut tenir compte si on veut les dénombrer finement.
On peut borner ce nombre de configurations (supérieurement) par une fonction de l'ordre de 7^h ce qui est suffisant pour indiquer un pire cas de la complexité.
On peut faire le calcul exact mais pas avec une formule analytique simple (closed form). On peut néanmoins avoir une formule plus précise dans laquelle le 7 devient un (4 + racine(8)) soit environ 6.83. Cette formule est par ailleurs plus complexe ce qui n'est pas vraiment utile pour communiquer l'ordre de grandeur.