Algorithmique avancée-EMI
Transféré par
El Yazid atouAlgorithmique avancée-EMI
Transféré par
El Yazid atouAlgorithmique avancée
Problèmes Récursifs
Dr. Yahya Hanine
1
Introduction
• Une procédure est dite récursive si, et seulement si, elle fait appel à elle-même, soit directement
soit indirectement
• La récursivité est une technique de résolution de problème utilisée en informatique.
• Elle permet d’écrire des solutions courtes pour des problèmes complexes : on réduit le problème
initial à un problème similaire mais de taille plus petite.
• Elle permet de trouver des solutions élégantes et claires à certains problèmes
2
Exemple
• (vision itérative) Un escalier de hauteur h c’est : une séquence de h marches
• (vision récursive) Un escalier de hauteur h c’est : une marche suivie d’un escalier de
hauteur h − 1
3
Exemple (suite)
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Exemple – Le problème du voyageur
Un postier décide d’effectuer un voyage entre différentes villes qu’il ne connaît pas. Son but est de
choisir le chemin le moins dangereux. Pour choisir son chemin, il s’informe auprès des assurances sur
les différentes valeurs des polices d’assurance de vie entre les différentes routes possibles du voyage.
Le trajet du postier est composé de 4 étapes (voir figure) et il doit arriver à la ville numérotée 10 en
partant de la ville numérotée 1. Les autres numéros représentent les villes susceptibles d’être traversées.
Les arcs entre ces noeuds représentent les différents trajets possibles et les valeurs 𝑐𝑐𝑖𝑖𝑖𝑖 au-dessus des arcs
représentent le prix de la police d’assurance vie relatif au trajet décrit par l’arc.
Le chemin le moins dangereux est celui qui admet la plus petite valeur de la police d’assurance vie 31
Exemple – Le problème du voyageur
Exemple : Si le voyageur empreinte le trajet 1 → 2 → 6 → 9 → 10 , le coût total de la police d’assurance est 13
• Soit 𝑥𝑥𝑛𝑛 (𝑛𝑛 = 1, … , 4) les variables de décisions relatives à chacune des 4 étapes. Le chemin à suivre par le voyageur est
1 → 𝑥𝑥1 → 𝑥𝑥2 → 𝑥𝑥3 → 𝑥𝑥4 avec 𝑥𝑥4 = 10.
• Soit 𝑓𝑓𝑛𝑛 (𝑆𝑆, 𝑥𝑥𝑛𝑛 ) le coût total de la police d’assurance vie pour le reste des étapes sachant que nous somme à l’état S de
l’étape n et que la destination choisie est 𝑥𝑥𝑛𝑛 .
• Etant donné S et n, soit 𝑥𝑥𝑛𝑛∗ la valeur de 𝑥𝑥𝑛𝑛 qui minimise 𝑓𝑓𝑛𝑛 (𝑆𝑆, 𝑥𝑥𝑛𝑛 ) et soit 𝑓𝑓𝑛𝑛∗ (𝑆𝑆) la valeur minimale de
𝑓𝑓𝑛𝑛 𝑆𝑆, 𝑥𝑥𝑛𝑛 . (𝑓𝑓𝑛𝑛∗ 𝑆𝑆 = 𝑓𝑓𝑛𝑛 (𝑆𝑆, 𝑥𝑥𝑛𝑛∗ )).
• L’approche de la programmation dynamique repose sur l’idée qu’un chemin ne peut être optimal que si chacune des ses
composantes est elle même optimale. La démarche de la programmation dynamique consiste à étudier d’abord les sous
32
problèmes qui se situent chronologiquement les derniers et sur un principe de retour en arrière.
L’objectif est donc de trouver la valeur de 𝑓𝑓1∗ 1 . Pour l’avoir, la programmation dynamique va essayer d’évaluer avec une
procédure de chaînage en arrière 𝑓𝑓4∗ (𝑠𝑠), 𝑓𝑓3∗ (𝑠𝑠), 𝑓𝑓2∗ (𝑠𝑠) et enfin 𝑓𝑓1∗ 1 .
A chaque étape, on va essayer d’évaluer pour chaque état s, la valeur de 𝑓𝑓𝑛𝑛 (𝑆𝑆, 𝑥𝑥𝑛𝑛 ) pour chaque destination 𝑥𝑥𝑛𝑛 possible,
puis de retrouver la meilleure destination 𝑥𝑥𝑛𝑛∗ (celle qui correspond au plus petit coût 𝑓𝑓𝑛𝑛 (𝑆𝑆, 𝑥𝑥𝑛𝑛 ) ) et aussi la valeur de
𝑓𝑓𝑛𝑛∗ (𝑆𝑆) .
33
Exemple – Le problème du voyageur
34
Exemple – Le problème du voyageur
35
Exemple – Le problème du voyageur
36
Exemple – Le problème du voyageur
La valeur de 𝑓𝑓1∗ 1 = 11 représente le coût total minimal de la police d’assurance vie.
37
Exercice 1.
Un automobiliste doit se rendre de Séville (Espagne) à Strasbourg (France). Il a décidé d’effectuer le voyage en quatre jours
et d’en profiter pour rendre visite à quelques amis. Afin de limiter les risques d’accident dus à la fatigue et de disposer d’un
maximum du temps auprès de ses amis, il aimerait minimiser la durée de sa plus longue étape journalière. Notre conducteur
a des amis à Madrid, Valence et Barcelone en Espagne et à Toulouse, Bordeaux, Lyon et Paris en France. La figure ci-
dessous présente les différentes étapes qu’il envisage ainsi que les estimations des temps de trajet.
La durée de chaque trajet est donnée en regard de l’arc associé.
Déterminer l’itinéraire optimal que notre voyageur doit emprunter afin de minimiser la durée de sa plus longue étape journalière.
38
39
40
41
42
43
44
45
46
47
48
49
Problème du voyageur de commerce
50
Problème du voyageur de commerce
51
Problème du voyageur de commerce
52
Problème du voyageur de commerce
53
Problème du voyageur de commerce
Problème du voyageur de commerce
Problème du voyageur de commerce
Problème du voyageur de commerce
Problème du voyageur de commerce
Problème du voyageur de commerce
Exercice
Un voyageur de commerce doit passer une et une seule fois par 4 villes et revenir à son point de départ (𝑥𝑥0 = 1) en
ayant parcouru la distance la plus petite possible. Déterminez le circuit hamiltonien de longueur minimale pour ce
graphe, en justifiant chaque étape.
Tableau des distances entre villes
1 2 3 4
1 0 6 2 7
2 3 0 5 4
3 5 6 0 4
4 9 8 2 0
59
