Algorithme de séparation et évalutation

[nico3004]

Bonjour,
j'ai trouvé un document d'apparence très simple pour comprendre comment fonctionne l'algorithme "branch and bound" seulement, il y est donné un exemple que je ne parviens pas à comprendre. A quoi y correspondent les chiffres du bas de la page 3 ? Je saisis bien que ce sont les poids des arcs, mais je ne vois pas la logique de cette somme...
Voici le lien du document :
http://wwwens.uqac.ca/~rebaine/8INF...rshiver2005.pdf

Est-ce que quelqu'un y verrait plus clair que moi ?

[fatal_error]

salut,

déjà, tu t'es planté de lien...que voici

Ensuite, page 4 (^^), il est expliqué quelle est la procédure qui a été effectuée.
Pour la borne globale, cad au niveau 0 tu imposes aucune condition sur les arcs.
Au niveau 1, tu imposes une relation entre le noeud de départ, et le noeud courant (relation double).
Le reste tu laisses comme c'était, c'était déjà un optimum. (c'est pour ca que ya que deux groupe de parenthèses qui changent pour la borne inf de D).

L'idée de la somme, c'est que pour un liste de noeuds (E,C,A) mettons.
Tu vas regarder, lorsque tu rajoutes le plus petit chemin B à cette liste, donc après A, la nouvelle somme obtenue, pis pour tous les noeuds possibles (donc B, et D), tu keep (cad a priori c'est lui le plus intéressant) celui qui a la plus petite somme. Grossièrement, tu prends le noeuds le plus près de A quoi...

c'est un peu faire l'algo des plus proches voisins, qui est pas super (on est toujours loin de l'optimal, j'ai plus les chiffres, mais jme souviens de 20%, ca doit être la marge par rapport au meilleur chemin). En l'occurrence, ici, ca forcerait à backtracker beaucoup!

[nico3004]

sauf que je ne vois toujours pas quand il dit "à partir de E", à quels sommets correspondent ses "(3+4)+(4+4), etc."

[fatal_error]

ben fallait être plus précis lors de ton premier post...

tu as sauf erreur la matrice d'adjacence suivante :

la matrice est symétrique, j'ai remplacé par des x.
Tu peux partir de E ou de n'importe, on s'en tape...pour le min globale
mais mettons de E :
dans la colonne E, tu as les noeuds qui sont incidents/sortants.
tu prends les deux plus petits : 3 et 4
pour les autres, tu look aussi les lignes et tu prends les deux plus petits arcs.
pour D : tu as : (9, 7, 4, 8) en possibilité. Les plus petits sont 4 et 7
pour C : 4 et 4
pour B : 3 et 6
pour A : 5 et 5

[nico3004]

D'accord ! cette fois j'ai bien compris la façon d'obtenir une borne inférieure.

Est-ce que tu saurais aussi m'expliquer comment il procède dans son arborescence, à la figure 6.2 ? Cette fois encore, je ne vois pas à quoi correspondent les nombres à côté des sommets...

[fatal_error]

ben c'est les bornes inf calculées...

par exemple pour le chemin ECB, le nombre qui figure a coté de B, c'est genre :
tu préserves les liaisons EC-CB, et avec les nodes restants, ben tu prends le minimum...entrant et sortant
dans notre cas, ca donnerait donc :
E : 1 liaison vers C, et une autre ailleurs : donc respectivement 4, et 3
C : 1 liaison vers E, et une autre vers B : 4 et 7
B : 1 liaison vers C, et une autre ailleurs : 7 et 3
A : deux min : 5 et 5
D : deux min : 4 et 7
le total nous donne : (4+3) + (4+7) + (7+3) + (5+5) + (4+7) = 49, soit une borne inf de 24.5
apres tu fais pareil...pour les nodes qui suivent.
Donc par exemple, ECBA, tu gardes cque tas fait pour ECB, tu enleves la liaison B vers ailleurs, que tu remplaces par la liaison B vers A, pis pour A, tu imposes la liaison A-B, et le reste, tu fais la popote :we:


BEWARE : le calcul ne marche pas pour tous les nodes.
Donc soit j'ai faux, soit ya une boulette dans le poly...
A priori je dirais que j'ai faux, même si ce que j'aif ait me semble cohérent.

[nico3004]

En tout cas, ça m'a pas mal aidé à comprendre le raisonnement ! merci !