Mathématiques 2: Géométrie
Les graphes
L'optimisation par les graphes
Heuristique du plus proche voisin
1. Heuristque du voisin le plus proche
L'heuristique du plus proche voisin consiste à :
• Choisir un sommet de départ X,
• Tant que tous les sommets ne sont pas encore visités
faire l’opération suivante
se rendre au sommet le plus proche pas encore visité.
Autrement dit :
• On fixe un sommet de départ,
• À partir de ce sommet, on joint un autre sommet
via une arête de plus petite valeur, en considérant toutes les arêtes
qui touchent ce sommet,
• On s'assure à la fin qu'on passé, une seule fois,
par tous les sommets du cycle simple obtenu.
2. Exemple
1. Le chemin le plus court
Partant du sommet M, quel est le cycle le plus court dans le graphe suivant:
• Sommet M: on prend le chemin le plus court parmis les quatre.
C'est donc O. MO = 200 km
• Sommet O: on prend le chemin le plus court parmis les trois,
car le sommet M a été déjà considéré. C'est donc T.
OT = 449 km
• Sommet T: on prend le chemin le plus court parmis les deux,
car O et M ont été déjà considérés. C'est donc N.
TN = 787 km
• Sommet N: le sommets T, O et M ont été déjà considérés.
Il n' y a pas d'autre choix que le sommet P.
NP = 507 km
• Sommet P: Tous les sommets ont été considérés, on revient
donc au point de départ M pour compléter le cycle.
PM = 447 km
Le cycle est donc: MOTNPM. Sa valeur est
MO + OT + TN + NP + PM =
200 + 449 + 787 + 507 + 447 = 2390 km.
2. Le chemin le plus long
Partant du sommet T, quel est le cycle le plus long dans le graphe suivant:
• Sommet T: on prend le chemin le plus long parmis les quatre.
C'est donc P. TP = 1041 km
• Sommet P: on prend le chemin le plus long parmis les trois,
car le sommet T a été déjà considéré. C'est donc O.
PO = 641 km
• Sommet O: on prend le chemin le plus long parmis les deux,
car P et T ont été déjà considérés. C'est donc N.
ON = 708 km
• Sommet N: le sommets T, P et O ont été déjà considérés.
Il n' y a pas d'autre choix que le sommet M.
NM = 595 km
• Sommet M: Tous les sommets ont été considérés, on revient
donc au point de départ T pour compléter le cycle.
MT = 544 km
Le cycle le plus long à partir de Toronto est donc: TPONMT. Sa valeur est
TP + PO + ON + NM + MT =
1041 + 641 + 708 + 595 + 544 = 3529 km.
