Manuel d'Intelligence Artificielle
Manuel d'Intelligence Artificielle
D'INTELLIGENCE
ARTIFICIELLE
Manuel
d'intelligence artificielle
Modèles et métamodèles
Guy Caplat
[Link]
Première édition
ISBN 978-2-88074-819-7
©Presses polytechniques et universitaires romandes, 2009
Tous droits réservés
Reproduction, même partielle, sous quelque forme
ou sur quelque support que ce soit,
interdite sans l'accord écrit de !'.éditeur.
Imprimé en Italie
AVANT-PROPOS
Origines
Ce manuel est issu pour l ' essentiel d ' enseignements donnés au Département Infor
matique de l'INSA de Lyon, de 1 985 à 2003 , aux niveaux bac+3 et bac+4,
d'enseignements en DEA (niveau bac+5) à l 'Université Lyon 2 jusqu' en 2004, ainsi
qu ' au Département Informatique de l 'Université de Biskra, enseignements
s 'appuyant sur des activités connexes de recherche et de formation continue.
Objectifs
Ce livre a pour but de présenter les grandes lignes de l ' intelligence Artificielle. Il
s 'adresse aux informaticiens, aux cogniticiens, éventuellement aux psychologues
cognitivistes ayant des bases en informatique, mais prioritairement aux étudiants de
second cycle.
L' intelligence Artificielle couvre un très grand nombre de sujets, et cet ouvrage,
qui se veut essentiellement didactique, présente et articule les principaux aspects de
cette dicipline. Mais il ne s ' agit pas d' une encyclopé[Link] la question, qui couvri
rait tous les sujets fondamentaux de l ' intelligence artificielle.
Afin de faciliter la mise en perspective de l ' intelligence Artificielle, l 'exposé
des concepts suivra grosso modo l 'ordre historique, ce qui devrait mettre en lumière
l 'aspect dialectique de la progression de cette discipline : à une époque donnée, une
dominante s ' impose qui règle une partie de la question ; l'époque suivante sera mar
quée par l' émergence d'un des principaux aspects jusque-là négligés, qui appellera
une nouvelle dominante . . .
« Un cours sans exemple est un squelette » disait Francisque Salles. Deux par
ties pratiques suivront des exposés plus généraux, afin de donner vie aux concepts
présentés.
Restrictions
On attachera une grande importance à la distinction symbolique/sub-symbolique. De
même que la psychologie cognitive ne traite pas en soi des réflexes ou des émotions,
l ' intelligence Artificielle envisagée ici ne traitera pas en principe de la Reconnais
sance de Formes, discipline plus biophysique, connexe mais distincte.
Plan proposé
L' introduction traite brièvement de l ' intelligence, du naturel et de l ' artificiel selon H.
Simon, des positions relatives de la Psychologie Cognitive et de l ' intelligence Artifi
cielle, et des limites de cette dernière.
La partie A rappelle les grandes lignes de l 'approche algorithmique de
l ' lntelligence Artificielle (I.A.), basée sur la manipulation d' arbres et la programma
tion fonctionnelle, et donne des éléments concernant sa pratique, sur la base du lan
gage Scheme.
La partie B du livre est consacrée à une approche logique classique, illustrée par
l ' emploi de Prolog, elle aborde les logiques non standard et débouche sur la question
VI Manuel d'intelligence Artificielle
Partie Chapitre
INTRODUCTION l .INTRODUCTION
A-APPROCHE ALGORITHMIQUE 2. ÉNUMÉRATION & COMPLEXITÉ
3. ESPACE D'ÉTAT ET MÉTAPHORE DU
LABYRINTHE
4. MÉTHODES DE RÉDUCTION
5. RÉSEAUX SÉMANTIQUES
6. NOTIONS D'APPRENTISSAGE
A2-ÉLÉMENTS PRATIQUES : 7. BASES DU LANGAGE SCHEME
SCHEME 8. PREMIÈRES APPLICATIONS
9. VERS L'IA EN SCHEME
B-APPROCHE LOGIQUE
B 1 -APPROCHE LOGIQUE 1 O. CALCUL DES PROPOSITIONS
CLASSIQUE 1 1 . LOGIQUE DES PRÉDICATS
B 2 -PROGRAMMA TION LOGIQUE 12. ÉLÉMENTS DE PROLOG
1 3. COMPLÉMENTS DE PROGRAMMATION
LOGIQUE
B 3 - LOGIQUES NON-STANDARDS
B 3A - EXTENSIONS ALGÉBRIQUES 14. LOGIQUES MULTIVALUÉES
1 5. LOGIQUES FLOUES
B 3B- EXTENSIONS 1 6. LOGIQUES NON MONOTONES OU RÉVISABLES
INFÉRENTIELLES 1 7. LOGIQUES MODALES
1 8. LOGIQUES D'ORDRE SUPÉRIEUR
B4- SYSTÈMES À BASE DE 1 9. INTRODUCTION AUX SYSTÈMES-EXPERTS
CONNAISSANCES 20. SYSTÈMES EXPERTS : DÉVELOPPEMENT
2 1 . INGÉNIERIE & GESTION DES CONNAISSANCES
C-APPROCHE GRAMMATICALE 22 . FORMALISMES GRAMMATICAUX
D-FORMALISMES OBJETS 23. LANGAGES À CLASSES
24. LANGAGES À PROTOTYPES
E-SYSTÈMES MULTl-AGENTS 25. AGENTS & SYSTÈMES MULTI-AGENTS
26. LES SYSTÈMES MULTl-AGENTS
27. ARCHITECTURE DES SMA
F-MÉTA-CONNAISSANCES 28. MÉTACONNAISSANCES RÉACTIVES ET
PROACTIVES
G-QUELQUES GRANDES RÉALISATIONS 29. TRAITEMENT DES LANGUES NATURELLES
30. AUTRES SYSTÈMES INTELLIGENTS
SPÉCIALISÉS
H-AU-DELÀ DE L'IA 3 1 . LE PROJET ROBOTIQUE
32. VIE ARTIFICIELLE
1-CONCLUSION
TABLE DES MATIÈRES
AVANT-PROPOS .................................................................. V
CHAPITRE 1 Introduction
1.1 L'intelligence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1 .2 Le Naturel et l 'Artificiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1 .3 Psychologie cognitive et Intelligence Artificielle . .. .................. 2
1 .4 Bref historique de!'Intelligence Artificielle . . . . .
....... ..... ............ 2
1 .5 Positionnement de! 'Intelligence Artificielle . . . . . . . . ... .. .. .. ............ 6
1 .6 Limites de! ' Intelligence Artificielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1 .7 Référence ................................................................................... 9
B2-PROGRAMMATION LOGIQUE
1 2. 1 3 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
1 2 . 1 4 Indications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
1 2. 1 5 Références .
........................................... .............................. 277
1 3 .5 Coroutinage . . . . . . . . . . . . . . .
..... . . .. .. . .
.. . . . .. .. ........ .... . . . . 29 1 . ... .... ........ .. .
1 3 .6 Modules . ..
..................................... ... . . . 292
................... ........ . ....
1 3 .9 Exercices . . . .
.................... .................... ... ............................. 307
13. l0 Indications . . .. . . ..
........... ... ..... . .. . . ........ . . 308
................... .............
B3A-EXTENSIONS ALGÉBRIQUES
1 5 .6 Aspect inférentiel .
............. .... ................. ..... ........ ... . . . . . . . .339
. ...
15 . 1 2 Références . .
. .................. ............................... ......... ........... . . 349
XIV Manuel d'intelligence Artificielle
B3B-EXTENSIONS INFÉRENTIELLES
17. l l Exercices . . .. . .. . .
................. ... .... . ...... ........... 393
. .. ......................
17.13 Références . . . . .. . .
.. .. .. ............ ........... . ..
.... .. .......... ...... . 395
.......... .
18.4 La réification . . .. .
................. ... .......... . 399
... ...................... .........
18.6 Exercice . . . ..
... .. .................................. . .401
.................. ..............
19.11 Métarègles .. . .. . . . .
.. ..... . . . . . . . ... . . . . .416
......... .......... ... ... . .... .. .... ...... .
20.9 Causes des défauts des SE ... .. . ... .... . . . .... . . . .430
... . .. .. .... ....... . . . . . ..
20.10 Maintenance . . . . . .. ..
... . .. ................. .. . . ........ . . .431 ............ . ...... .. ...
21.7 Scénario d 'usage et communication .. . .. ... .. . .. .443 ..... .. . ... .... .... ..
21.11 Vers une société de la connaissance . .... . . . .469 ... ...... .... . .... .......
22.2 Rappels sur les grammaires formelles . . . . . .....476 . ...... ...... ...... .. .
25.8 Références . . . ..
.. ..... .... .... . . . . . .. .. .
........ .... . ... . ... . 574
....... ..... ...........
27.8 Exploitation . .. . .
...... ... . . 623
.. . ............................................... ..... .
27.10 Exercice . . ..
.... . .. . .... ..
............. ..... .... . . . . 628
................. ..... .. .. .... ....
PARTIE 1-CONCLUSION
INTRODUCTION
1.1 L'INTELLIGENCE
L ' intelligence est ici abordée comme la faculté de bien employer et de bien gérer ses
connaissances. Nous classerons ses manifestations en quatre niveaux :
• Compréhension d 'une situation.
• Résolution de problème dans un cadre connu ; c ' est le cas des « problèmes
cheur » : l 'existence de la solution n' est pas certaine, et le système dans lequel
raisonner est à déterminer parmi les systèmes connus, voire comme système
nouveau.
• Résolution de problème en univers changeant ; c'est le cas des « problèmes
1 .2 LE NATUREL ET L'ARTIFICIEL
Rappelons ici l ' impact de la distinction posée par Herbert Simon entre Sciences du
Naturel et Sciences de l' Artificiel, les premières tournées vers l 'observation de la
nature, les secondes vers la construction de systèmes abstraits 1•
En tant qu ' activité humaine, l ' intelligence relève manifestement des premières.
Dans les secondes, H. Simon met au premier rang les mathématiques, mais aussi
la construction de machines, conçues abstraitement pour un besoin donné avant
d' être réalisées, et dont la réussite tend à prouver une certaine maîtrise du réel,
comme la pertinence des connaissances exploitées.
La dualité présentée n' est pas totalement exclusive, dès lors que les Sciences du
Naturel entendent dépasser le stade de la description et de la classification, pour
acquérir une valeur prédictive . . .
humain ou non ; outre des raisons purement pratiques, on peut aussi considé
rer que l ' esprit humain n'a probablement pas le monopole de l ' intelligence, et
gagnerait à être aidé par d' autres formes d ' intelligence.
1.4.1 Origines
Divers auteurs eurent l ' idée de machines mimant l 'activité mentale humaine, no
tamment Descartes et ses animaux-machines, ou La Mettrie et son homme-machine
(1748).
La pensée comme logique mécanisable a inspiré d'abord Leibniz, Boole (The
Laws of Thinking, 1854), puis Whitehead et Russel, avec leur Principia Mathematica
(1910).
Plus près de nous, Alan Turing inventa le concept de machine universelle ainsi
qu'un test d' intelligence d'une machine. On doit également des apports importants à
Godet (théorème d" incomplétude, 1930), Tarsky, Herbrand ou Church (théorème
d' indécidabilité, 1934 ; le Lambda-calcul).
Mais l ' intelligence en action ressort également de l 'heuristique, discipline qui
s 'attache à la découverte de solutions. Etudiée sporadiquement depuis l 'Antiquité,
cette logique de la découverte, sous la forme de résolution de problèmes, intéressa
les mathématiciens, longtemps avant les psychologues.
On attribue à Pappus d 'Alexandrie le premier exposé de la méthode analytique
dite « du problème résolu ». Au XVIIIe siècle, Leibniz distingue un art de la décou
verte (heuristique) d'un art de la justification (logique) et Clairault propose une ap
proche constructive des mathématiques dans un traité où la plupart des théorèmes
sont établis par le lecteur lui-même, en résolvant des exercices judicieusement com
posés et organisés. Au XIX0 siècle, des ouvrages tels que 2000 exercices de géomé-
Introduction 3
trie possèdent des chapitres transversaux proposant des méthodes pour traiter certai
nes classes de problèmes, et ramener par exemple des problèmes d 'optimisation à des
constructions « avec la règle et le compas ». Vers 1965, Polya met la résolution de
problèmes au centre de sa méthode pour l ' enseignement des mathématiques, les
activités constructives lui semblant préférables aux exposés logico-déductifs pour la
découverte de cette discipline.
Ainsi , les Britanniques purent communiquer à l 'état-major soviétique les plans allemands pour la déci
sive bataille de Koursk.
4 Manuel d'intelligence Artificielle
Informatique
Informatique numérique Informatique symbolique
intensive extensive Intelligence Artificielle
1 1
Calcul scienti- Gestion, Statisti- Ingéniérie des Robotique Vie artificielle
fi que ques connaissances
Sous l ' influence notamment de Tektronix, le tracé d'un dessin avait longtemps été perçu comme une
opération globale dont la structure détaillée reflétait celle du dessin ; changer le dessin , c'était alors
changer le programme de dessin. La nouvelle tendance supposait une opération de traçage unique, abs
traite, s'appuyant sur quelques opérations de traçage élémentaire, le tracé à faire étant piloté par une
structure de données (arbre) décrivant les singularités du tracé : pour changer le dessin , il suffit mainte
nant de changer son arbre descriptif.
6 Manuel d'intelligence Artificielle
1.5.1 Objectifs
L'intelligence Artificielle (IA) limite parfois son obj ectif à l ' interprétation d'une
situation ou d'un texte. Plus souvent, il s'agit d'une activité constructive, fonction
d'une situation et d'un obj ectif, de type « résolution de problèmes » :
4 Agissant de concert dans un atelier, pour l 'aménagement d'une station sur Mars . . .
Introduction 7
Linguistique
Psychologie Intelligence Génie Logiciel
Psychologie Cognitive Artificielle Informatique
Mathématiques Discrètes
niveaux
Psychologie Intelligence Artificielle Informatique
symbolique
subsymbolique Neurosciences Reconnaissance de Formes Electronique digitale
concerne la verbalisation de cette expertise : ceux qui savent ne savent pas touj ours
le dire, ceux qui peuvent et savent dire n ' en savent pas toujours assez. De plus, toute
profession partage des non-dits à expliciter. Une seconde difficulté concerne la
transcription de cette expertise verbalisée dans le fonnalisme retenu, plus ou moins
adéquat.
Plus gravement, après toute une carrière dans le domaine, Pitrat se demandait si
l 'homme est assez intelligent pour réussir ce proj et d' Intelligence Artificielle.
1 .7 RÉFÉRENCE
Collectif IRIT, 2002, L 'Intelligence Artificielle, mais enfin, de quoi s 'agit-il ?, Les
livrets du Service Culture UPS, n° 3, disponible sur [Link]/livret-IA
A-Approche
algorithmique
«La procédure est la forme la plus achevée de connaissance. »
Terry Winograd
Cette partie, d' inspiration la plus ancienne, repose notamment sur des algorithmes
énumérant des solutions potentielles, qui constituent un niveau 0 de l 'intelligence
Artificielle.
Les représentations cognitives exploitées seront souvent à base de graphes, et
généralement se ramèneront en dernière analyse au concept de liste, ou suite finie de
valeurs :
• si les valeurs sont élémentaires, une liste pourra représenter un vecteur, une
phrase, un itinéraire ;
• si une valeur peut être une liste, les listes de listes représenteront parfois des
tables et des matrices, mais plus souvent des listes associatives décrivant des
répertoires, des dictionnaires, des plans d' action, des arbres ou des graphes.
ÉNUMERATION ET COMPLEXITÉ
2.2 COMPLEXITÉ
(Voir Froidevaux 1993, ch. 2 ; Gondran 1985, ch. 10).
14 A-Approche algorithmique
(2.2)
Par exemple, une fonction f(n) = 7n2 - 5n + 3 sera dite en n2, car on aura finale
ment f(n) � n2•
Enumération et complexité 15
Classes de complexité
La relation <:::: structure en classes les fonctions considérées, classes qu 'on désignera
par O(r), où r est le représentant le plus simple possible du comportement asymptoti
que à l ' infini.
Le tableau 2 . 1 indique quelques-unes de ces classes, avec des applications dont
elles représentent classiquement la durée.
k
De 0( 1 ) à O(n ), ces classes sont dites P : c'est l 'ensemble des classes polynô
miales, correspondant aux degrés faibles à des processus praticables.
'
En Intelligence Artificielle, on peut aussi rencontrer des fonctions 0(2"), 0(2" ),
O(n ! ) ou O(n"). Elles sont souvent la marque d'une explosion combinatoire, et en ce
sens des procédés voraces en temps et/ou en espace.
EXEMPLE.
Considérons le cas du représentant de commerce devant parcourir n villes de façon à
minimiser la distance totale parcourue. En supposant qu 'il s ' interdit de passer deux
fois dans la même ville, il peut choisir l 'une des n villes comme première ville, l ' une
des n- 1 villes restantes comme deuxième ville, l 'une des n-2 villes restantes comme
troisième ville . . . d'où n! parcours possibles ; les évaluer prend un temps en n ! , ex
pression dont les effets dévastateurs ont été soulignés tableau 1 . 1 . •
2.2.3 Problèmes P
Edmons a posé en 1 965 qu 'on parlerait de problème de type P si on connaît pour le
résoudre un processus n de complexité P(olynômiale).
Ce processus peut être bâti directement, ou par la composition d'un nombre fixe
de processus de complexité P.
2.2.4 Problèmes NP
On appelle algorithme non déterministe un algorithme comportant des étapes de
choix.
On parle d'un algorithme de type NP si c'est un algorithme non déterministe qui
se ramène à un algorithme de classe P quand on fait systématiquement le bon choix.
16 A-Approche algorithmique
Réductibilité
Un problème Q sera réductible à un problème P s ' i l existe une fonction g de com
plexité polynômiale telle que pour toute solution x de P, g(x) soit solution de Q. Et
on dira P et Q faiblement équivalents s' ils sont mutuellement réductibles. Si on dé
couvre un jour qu 'un problème présumé NP possède en fait un processus résolvant
de complexité P, alors tous les problèmes qui lui sont réductibles bénéficieront du
même progrès. Ainsi, L. Khachian a montré en 1 979 que les problèmes de program
mation linéaire, qu'on croyait jusque-là de type NP, étaient en fait de type P . . .
Problèmes NP-durs
On dira que P est un problème NP-dur si tout problème Q de NP est réductible à P. Il
suffirait donc de s ' intéresser aux problèmes NP-durs pour résoudre les problèmes
NP, à condition de ne pas renvoyer les problèmes NP à des problèmes plus com
plexes qu' eux . . .
Problèmes NP-complets
On dira que P est un problème NP-complet s ' i l est NP-dur et NP. Tous les problèmes
NP-complets sont faiblement équivalents entre eux. Et il suffirait qu 'un problème
NP-complet soit de classe P pour que tous le soient.
Un grand nombre de problèmes connus, tels que le problème du voyageur de
commerce, ont été caractérisés comme NP-complets, ce qui veut dire que les solu
tions connues sont onéreuses à établir, avec une faible probabilité d'amélioration
drastique.
2.2.5 Heuristiques
Soit un problème, qu' on sait résoudre par
un processus absolu n trop complexe (trop
onéreux). Soit maintenant H un processus �
Q
0
Q
approché, moins complexe, fournissant -
seulement des solutions quasi optimales : H
sera dit heuristique pour le problème. En
cas de multiplicité, les heuristiques peuvent
être ordonnées entre elles sur le double
critère de la complexité ou coût d 'une part,
de la qualité des résultats obtenus d 'autre
part. Les heuristiques dominantes seront les
processus réalistes à employer, représentant
les meilleurs compromis coût/qualité. Les
heuristiques dominées pourront être négli
gées en première analyse, sauf circonstances
particulières mettant en échec des prédic n312 2" n !
tions trop générales. Complexité>>
EXEMPLE.
Pour le problème des nombres pythagoriques, il y a 3 variables et une équation : on
peut se contenter d 'énumérer des couples :
• soit les couples (q, r) possibles, en testant si q2 + r2 est un carré parfait.
Normalisations
Certains problèmes peuvent se régler « à une homothétie près » , et il peut arriver
qu 'un système en (X, Y, Z, T, U) où U joue un rôle de paramètre directeur, puisse se
ramener à un problème en (x, y, z, t), où x = XIU, y = YIU, z = ZIU, t = TIU.
Ce procédé s'étend facilement à une évaluation multi-critère, dès lors que l ' on
conserve à tout moment l ' ensemble des solutions dominantes parmi celles déj à ren
contrées.
La communication entre générateur, filtre(s) et trieur permet un certain parallé
lisme entre les divers processus.
On peut ainsi obtenir des réponses de qualité croissante au cours de
l ' énumération, et rendre le processus de recherche interruptible si, après la première
solution rencontrée, le trieur édite toute solution reçue au moins aussi bonne que la
meilleure déjà connue.
Dans de nombreux problèmes pratiques, où l ' on cherche les solutions les plus
intéressantes soumises à divers impératifs,
• les impératifs fixeront les contraintes d 'admissibilité (filtrage) ;
• au-delà, les souhaits serviront de base au classement par ordre d'intérêt (tri final).
20 A-Approche algorithmique
2.4.2 Exemples
Conception d'une caisse en carton
On veut définir une caisse en carton devant contenir n = p · q · r boîtes de l dm l dm ·
·l dm, à découper dans une feuille de L · W dm. On retient le dessin de la figure 2.4.
I"<
� min( P,Q)/2 ..
�
...
Soit, pour une feuille de l ,2m sur 0,8 m : L= l 2, W=8, et 3 combinaisons (au
lieu de 288).
p q r n= p ·q·r
3 2 6 36
4 1 7 28
5 0 8 0
Fig. 2.5 Découpe d'une caisse en carton : principaux cas.
Enumération et complexité 21
Le programme brut :
pour w de 0 à 1 OO faire
pour x de 0 à 1 OO faire
pour y de 0 à 1 OO faire
pour z de 0 à 1 OO faire
si c3 et c4 alors . . .
devient :
pour y de 0 à 48 faire
pour x de 0 à 80 - 5y/3 faire
pour w de 0 à min( 1 OO, 240 - 5y - 3x) faire
pour z de 0 à 90 - y -xfaire
ce qui gagne un facteur 5 sur les seuls couples (x, y) et élimine les tests.
Escalade
Il s ' agit d'un processsus de génération cherchant à s ' inspirer directement de
l ' obj ectif poursuivi.
Soit à trouver le meilleur n-uple parmi les cas possibles, au sens d'une fonction
f représentant un gain, un objectif. . . La méthode d 'escalade consiste, partant d 'un x
admissible, à répéter « si y est le voisin admissible de x maximisant l 'amélioration
d = f(y)-f(x), et si d>O, considérer y comme nouvel x ».
Elle atteint au moins un sommet ou optimum local, et le maximum de la fonc
tion f si f est convexe sur le domaine considéré.
2.5 EXERCICES
2.5.2 Déterminants
Montrer que le calcul du déterminant d'une matrice n·n est en O(n ! )
2.5.3 Maison
Un particulier consulte un architecte pour la construction d'une maison. Plusieurs
options lui sont offertes : maison de plain-pied ou à Ull' étage, un patio, une terrasse,
un garage. Ses goûts et le budget imposent :
• un étage ou une terrasse, mais pas les deux ;
• s ' i l y a un patio, la maison doit être de plain-pied et/ou avoir une terrasse ;
Vérifier que le nombre de profils possibles est ici f(9, 26 ), défini par
objet a b c d e f g
volume 5 4 5 4 1 2 3
poids 4 3 3 5 3 2 1
utilité 6 5 7 8 9 IO 8
• Dans le cas ci-dessus à 7 obj ets, on s ' intéresse d'abord aux solutions ayant un
volume total de 20 au plus. Montrer que les plus utiles comportent 5 ou 6 ob
jets, mais qu' i l n ' y a pas de solution à 7 obj ets 5 • Montrer qu 'il existe une solu
tion à 6 objets d'utilité 48.
• On s ' intéresse ensuite aux solutions ayant un volume total de 20 au plus ET
un poids total de 1 7 au plus. Montrer qu' i l existe une solution d'utilité 47.
2.6 INDICATIONS
Pour 2.5. 1
Voir (Frécon 2002).
Pour 2.5.2
Raisonner par récurrence, en définissant un déterminant à partir de ses mineurs.
Pour 2.5.3
eVt
Introduisons des variables propositionnelles : e po4r un étage, g pour ..., e v-, t
un garage, p pour un patio, t pour la terrasse. La spécification est gVp
transcrite sous forme d'une conj onction de clauses. -, g v-, p
De deux choses l'une : ou la maison est de plain-pied (-, e) ou elle a -, p v-, e v t
un étage (e). e v -, g
-, e satisfait les clauses en -, e, et dans les autres neutralise e. -, t v -, g
Finalement,
• si la maison est de plain-pied
Pour 2.5.4
Enumération brute. On applique simplement la méthode « produire et valider ». Un
générateur énumère les triplets (i, j, k) représentant un repas r = (ei, Pi • dk). A chacun
des mets correspond un triplet (lipides, protides, glucides) ; on fait 3 évaluations par
repas, du style
lipides(r) = lipides(ei) + lipides( Pi ) + lipides(dk>
�t on vérifie que chacune est correcte ; si oui, ( ei, Pi • dk) est retenu ; ce triplet est
�ej eté dès qu 'une valeur calculée pour le repas dépasse le seuil fixé. Cette énuméra
:ion peut être assez longue, car si i e l, j e J, ke K, on a II®J®KI cas à examiner, soit
1 000 solutions potentielles pour Ill = IJI = IKI = 1 O.
Pour 2.5.5
12
�e nombre de tirages est a priori de 269 � 5 ,4 · 1 0 • Le nombre de tirages ne com
9 9
Jrenant que des consonnes serait de 20 � 5 1 2 · 1 0 , soit 9% des tirages. La réduction
1 ' est pas importante. Selon le nombre de lettres différentes dans un tirage, celui-ci
tdmet jusqu'à 9! = 3 62 880 permutés, qui doivent tous mener aux mêmes solutions.
:.: idée ici est d'associer la réponse « bijoutier» (et ses anagrammes) aux myriades de
irages permutés qui devraient y mener, tels que « urtoij ieb », via un même profil
Enumération et complexité 25
Pour 2.5.6
Avec n obj ets, il y a 2" sous-ensembles à tester comme solutions potentielles (ici, 1 2 8
1
cas ; comme 2 0 :=:; J 0 3 , compter u n facteur 1 000 pour 1 0 obj ets).
Il n'y a pas de solution à 7 obj ets, car le volume total serait de 24. Pour trouver
une solution admissible, il faut enlever un ou plusieurs obj ets pour un volume 4 ou
plus. Il suffit d'enlever a, b, c ou d ; b est Je moins utile des obj ets ou combinaison de
volume 4 : n' enlever que lui donne un volume admissible pour une utilité de 48.
Cette solution {a, c, d, e, f, g} maximise l ' utilité pour le volume, mais son poids
est de 1 8. {b, c, d, e, f, g} est par contre hi-admissible (volume et poids), pour une
utilité de 47.
D 'un point de vue théorique, c ' est un problème d'optimisation linéaire à varia
bles binaires. Une énumération heuristique serait pilotée par les utilités relatives
(utilité par unité de volume, de poids . . . )
2.7 RÉFÉRENCES
Cocco S., Dubois O., Mandler J., Monasson R., 2002, A la rescousse de la
complexité calculatoire, Pour la Science n°295 , pp. 2- 1 0.
Frécon L., 2002, Eléments de mathématiques discrètes, Presses polytechniques et
universitaires romandes, Lausanne.
Froidevaux C., Gaudel M.C., Soria M . , 1 993, Types de données et algorithmes,
Ediscience Inti, Paris.
Gondran M. et Minoux M., 1 985, Graphes et algorithmes, Eyrolles, Paris.
Wikipedia, encyclopédie en ligne.
CHAPITRE 3
Dans un graphe <X, U>, on appelle chemin une suite (x0 , X i . x2 . . • ,xn) telle que
pour tout i : (xi. Xi+ i ) E U. Dire le chemin de taille n indique qu 'il est formé de n
arcs consécutifs (cf par exemple (Frécon 2002)).
Soit, dans le graphe d' état, un chemin (x = x 0 , X i . x2 . . • , xn = y ). La suite a i , a2 • • • ,
an des marques µ(xi-i . x;) = ai lues le long du chemin dénotera une séquence ou un
plan d'action assurant que le système passe de l ' état x à l ' état y en n étapes.
On appelle circuit un chemin {x0 , x i . x2 • • . , Xn = x0) finissant au point de départ.
Un arc (x y) appartenant à un circuit correspondra à une action réversible (une
suite d'actions pourra ramener à son état initial), un arc n ' appartenant à aucun circuit
correspondra à une action irréversible.
EXEMPLE.
Le Taquin est un j eu qui comporte p·q cases, toutes occupées sauf une par un j eton
numéroté 6 •
Convenons de coder 0 la case vide. A une configuration du 1 2 3
taquin correspond un arrangement des nombres de 0 à p·q-1 , 4 13 12 11
ici 5 14 15 10
(0 l 2 3 ; 4 1 3 1 2 1 1 ; 5 14 1 5 I O ; 6 7 8 9). 6 7 8 9
Fig. 3.1 Taquin.
Il y a donc (p·q) ! configurations possibles. •
Les actions possibles sont les glissements . Un jeton adjacent à la case vide peut
glisser dans cette case : dans le cas ci-contre, le j eton 1 (ou le j eton 4) peut venir
dans la case vide, son ancien emplacement devenant vide.
Attacher les glissements aux j etons suggère 4·p· q actions possibles en théorie,
soumises à des contraintes liées à la position de la case vide, si bien qu ' à tout mo
ment seules 2 à 4 d ' entre elles sont effectivement possibles.
Il sera plus simple de considérer qu 'on fait glisser la case 0 : des 4 actions théo
riques (nord, ouest, sud, est) il y en aura touj ours 2 à 4 de possibles, chacune réversi
ble.
r� 1 ro 1
1 2 1 2 1 0 2
Espace d'Etat
Par analogie avec les graphes, on appelle solution élémentaire une solution sans
circuit, c ' est-à-dire ne passant pas deux fois par le même état. Une solution élémen
taire existe dès lors qu' une solution existe.
C ' est le cas de toute solution si le graphe d'état est sans circuit. Pour un graphe
d 'état quelconque, se limiter aux solutions élémentaires présente deux avantages :
• dès lors que X est fini, la recherche de chemin (i.e. de solution) élémentaire
est un processus fini (qui échappe donc à l ' effet labyrinthe) ;
• dès lors qu ' un coût strictement positif est associé à chaque arc ou action, tou
tes les solutions optimales sont élémentaires (par l ' absurde) .
Méthodes globales
Les méthodes globales travai llent sur une description de l ' ensemble du graphe. Ce
sont essentiellement des méthodes matricielles : un espace d ' état à n configurations
étant décrit par une matrice n· n, la recherche de chemin se ramène à un calcul de
fermeture transitive, de fait une somme de produits de matrices à valeur dans un
dioïde.
La complexité est en O(n2) en ce qui concerne l ' espace de travail nécessaire.
Ainsi, 1 Gigaoctet de mémoire de travail peut contenir au plus une matrice 3 1 600 ·
3 1 600 si chaque case se contente d ' un octet.
3
La complexité des traitements est en O(n ) pour les produits de matrice, et glo
3 4
balement en O(n Iog2n) = o(n ).
Cette approche est uti lisée en Recherche Opérationnelle, mais en Intelligence
Artificielle elle est généralement considérée comme trop gourmande en espace de
travail lorsque n devient grand.
30 A-Approche algorithmique
Méthodes locales
Les méthodes locales reposent sur l ' idée d ' une navigation dans un graphe d ' état,
qu 'on supposera en général fini, mais fréquemment immense.
Pour ce faire, on essaie de ne pas représenter en mémoire de travail la totalité du
graphe, présumé immense, mais seulement une partie uti le aussi réduite que possible.
La progression de la recherche amène à distinguer trois parties dans le graphe :
• une partie déjà explorée, dont on gardera en mémoire la plus petite trace pos
sible,
• une partie active ou frange d'exploration, formée des sommets en cours de
traitement en mémoire de travail,
• une partie encore virtuelle, formée des sommets non encore traités - et, si
possible, non représentés.
EXEMPLE.
Soit à établir votre filiation en tant que descendant probable de Charlemagne. En
supposant qu 'on dispose de la documentation nécessaire,
• une méthode directe consisterait à regarder si vous êtes un enfant, un petit
enfant, un arrière-petit enfant de Charlemagne, ou plus généralement si vous
faites partie du cône de ses descendants ;
• une méthode inverse consisterait à regarder si Charlemagne est votre père,
grand-père, arrière-grand-père, ou plus généralement si Charlemagne fait par
tie du cône de vos ascendants. •
L ' application menaçant d ' être très lourde, quelle méthode serait préférable ?
Posons que le problème porte sur k générations ; il faudrait envisager de l ' ordre de ak
k
ascendants dans le premier cas, d descendants dans l ' autre, où en moyenne a<2<d ;
en effet :
• a = 2 en principe, mais a<2 si l ' on prend en compte les unions consanguines,
qui font que deux conj oints partagent des ancêtres ;
• d = 2 pour un strict renouvellement des générations, et d > 2 en cas
d ' expansion démographique d ' une population.
k k
On peut donc penser que a < d , et que la seconde méthode serait moins lourde
que la première .
Espace d'état et métaphore du labyrinthe 31
Méthodes révocables
Les méthodes révocables procèdent au moins partiellement par essais et erreurs.
Elles progressent sous certaines hypothèses à la recherche de l ' objectif ; en cas
d ' échec, elles régressent vers le dernier choix effectué : la possibilité exploitée en
dernier ayant échoué, on l ' abandonne ; s ' i l reste une possibilité inexploitée à ce ni
veau, on repart en avant ; sinon, on poursuit la régression j usqu ' au dernier point de
reprise laissant une possibilité inexploitée ; si la régression ramène au point de départ
sans autre possibilité, l ' échec est définitif.
Cette approche très « humaine » n ' est pas à l ' abri d ' errements ; elle suppose
d ' établir clairement les impasses et, autant que possible, de les anticiper ; face à une
alternative
• elle aura la lourdeur d ' une énumération brute si elle ne sait pas discerner la
meilleure possibilité,
• elle sera d ' autant plus efficace qu 'elle saura discerner la possibilité la plus
prometteuse . . .
·-·· -
0,\
1 1
- ·
-··
· -··-··- ··-·
Méthodes irrévocables
Les méthodes irrévocables supposent une progression linéaire basée sur une forte
capacité prédictive :à chaque situation présentant une alternative, on exploite seule
ment la possibilité la plus prometteuse.
Dans le meilleur des cas, on peut se permettre un processus de décision assez
lourd, du fait du nombre réduit d ' étapes. La plupart du temps, on obtiendra seule
ment une heuristique, dont la qualité dépendra du bonheur de la prédiction.
Techniquement, les algorithmes incarnant des méthodes irrévocables sont sou
vent appelés algorithmes-gloutons (ils ne rej ettent j amais ce qu ' ils consomment) .
32 A-Approche algorithmique
Méthodes aveugles
Les méthodes aveugles sont des méthodes énumératives n ' exploitant que la topolo
gie du problème, sans s ' intéresser davantage aux données spécifiques. S imples à
programmer mais lourdes à l ' exécution , elles donnent souvent des résultats médio
cres.
Méthodes pilotées
Au contraire, les méthodes pilotées ou méthodes heuristiques tentent de tirer partie
des données du problème à chaque décision. Plus spécifiques que les méthodes
aveugles, elles peuvent se révéler très efficaces .
Méthodes complètes
Les méthodes complètes sont les méthodes qui fournissent une solution s ' B y en a
une.
En particulier, dans un graphe fini, on pourra souvent établir que l ' algorithme
considéré est fini :
• parce qu ' il ne cherche que des chemins élémentaires (en nombre fini),
• ou parce qu ' i l recherche des chemins minimaux avec une fonction obj ectif
strictement croissante au long des chemins,
• ou parce qu ' il recherche des chemins maximaux avec une fonction obj ectif
strictement croissante au long des chemins dans des graphes sans circu it. . .
Méthodes admissibles
· Les méthodes admissibles sont des méthodes complètes qui fournissent une solution
optimale s ' i l y a une solution.
Méthodes &-optimales
Les méthodes &-optimales sont des méthodes complètes qui fournissent une solution
approchant l ' optimale à mieux que e près s ' il y a une solution. Il est souvent très
utile de qualifier une méthode heuristique comme méthode e-optimale.
3 .4 PRINCIPALES MÉTHODES
Procédé
Un niveau 0 est formé du sommet (resp . des sommets) de départ.
Partant du niveau n - 1, le niveau n est formé de tous les successeurs non encore
rencontrés des sommets du niveau n - 1. On s ' arrête à ce niveau :
• si l ' on a atteint le (resp. un des) sommet-obj ectif (succès) : il y a alors au
moins une solution de taille n, et le(s) chemin(s) cherché(s) s ' obtien(nen)t en
remontant du sommet-obj ectif atteint au niveau 0;
• a contrario, si le nouveau niveau est vide, auquel cas il n ' existe aucun chemin
(de l à F) .
EXEMPLE.
On considère le plateau de la figure 3.5, où on suppose chaque case liée aux seuls
sommets adj acents dans les 4 directions principales (N, 0, S, E) . Y a-t-i l un chemin
de b à y ?
On explore par niveaux le graphe d ' adj acence G1 associé au plateau, à raison d ' un
sommet par case et d ' une arête par adj acence.
niveau sommets
0 b
1 a, c
2 g, h , d
3 k, m, i , e
4 q, 1, s, n , f
5 u , r, w, o , j
6 v, x , p
7 y,t
Propriétés
La recherche par niveau est une méthode complète, aveugle, directe et irrévocable.
Elle fournit touj ours une solution la plus simple possible (resp. les solutions les plus
simples possibles), c ' est-à-dire ayant une taille minimale (un minimum d ' arcs). Les
sommets plus éloignés du départ que l ' obj ectif ne sont pas considérés (comme ici z).
REMARQUES
• Si les arcs sont porteurs de coûts ou de distance, les chemins les plus simples
ne sont pas forcément les plus courts ou les moins chers .
• La recherche par niveaux se comporte comme une propagation d ' onde.
34 A-Approche algorithmique
Complexité
Supposons qu ' un sommet ait en moyenne b successeurs nouveaux 7 ; on appelle b
facteur de branchement de la méthode. En tout, à la profondeur p, on devrait consi
dérer de l ' ordre de :
l + b + b2 + . . . + bP sommets
.
O(min(bP, N)).
La méthode est donc réputée vorace en mémoire, car il est possible que ni N
sommets ni bP ne soient installables en mémoire de travai l .
La complexité en temps est d e même e n O(min(bP, N)), où p n e dépasse pas l a
taille d u chemin le plus simple.
EXEMPLE.
Considérons un j eu comportant 1 030 configurations, et supposons à chaque étape 20
coups possibles. Si, pour gagner, on veut anticiper les coups suivants, on est amené
à envisager d ' abord 20 coups, leurs 20 · 20 = 400 successeurs, leurs 8000 succes
1
seurs etc. Comme 20P = l 0 •3P, à la profondeur 7 on en est au milliard de configura
tions . •
Procédé
Un niveau 0 est formé du sommet (resp. des sommets) de départ.
( ! ) . Partant du niveau n - l, on sélectionne un premier sommet s de ce niveau,
et on forme le niveau n, ou frange F, à l ' aide de tous les successeurs du sommet
s non encore rencontrés.
On s ' arrête à ce niveau si F contient le (resp. un des) sommet-objectif (succès) :
il y a alors au moins une solution de taille n, formée de tous les sommets actuel
lement sélectionnés.
Si F est vide, on a un échec local : s est une impasse, on le retire du niveau n -
b est égal à la sortance moyenne si le graphe est sans circuit (généalogie, ordonnancement . . . ), inférieur
sinon.
Espace d'état et métaphore du labyrinthe 35
EXEMPLE.
On reprend le cas précédent (fig. 3.5) où on suppose chaque case liée aux seules cases
adjacentes dans les 4 directions principales (N, 0, S, E). Y a-t-il un chemin de b à y ?
Explorons en profondeur le graphe d ' adj acence G1 associé au plateau. La recherche
se faisant en aveugle, on prendra ici à chaque niveau les sommets par ordre alphabé
tique.
niveau sommets
0 b
a, c
2 g
3 k
4 1, q
5 m, r
Fig.3.6 Niveaux de b à y pour une recherche en profondeur (en 6 h, n
Complexité
Supposons qu ' un sommet ait en moyenne b successeurs nouveaux ; on appel le b
facteur de branchement de la méthode. En tout, à un moment donné, chaque niveau
ne contient que O(b) sommets, soit un empilement du genre :
1 + b + b +. . .+ b sommets
et pour un graphe à N sommets, l ' espace de travail nécessaire au p-ième niveau serait
en
O(min(b · p, N)).
La méthode est donc réputée économe en mémoire, car généralement b·p << N.
La complexité en temps en temps reste en O(min(bP, N)), où la profondeur at
teinte p peut dépasser la tai lle du chemin le plus simple.
36 A-Approche algorithmique
EXEMPLE.
Considérons un j eu comportant 1 030 configurations, et supposons à chaque étape 20
coups possibles. Si, pour gagner, on veut anticiper les p coups suivants, on n ' aura à
tout moment que b·p configurations en mémoire, soit de l ' ordre de 1 40 configura
tions pour une profondeur 7, qu ' on développera et réduira peut-être très longue
ment. . . •
Optimisation progressive
Une exploration en profondeur peut être modifiée pour poursuivre l ' énumération des
solutions au-delà de la première ; ici, on combine cette idée avec celle d ' une explora
tion en profondeur bornée par une valeur-limite L excessive au départ ; à chaque
solution trouvée, L est alignée sur cette dernière solution, de façon à obtenir une
suite de chemins de taille (resp. longueur) décroissante. Cet algorithme
• est interruptible dès qu ' une première solution est trouvée,
• est admissible si on le laisse aller à son terme,
• peut donner assez rapidement des so lutions raisonnables, les chemins succes
sifs correspondant à des améliorations « par la fin ».
Méthode BF*
La frange est initialisée à l ' aide d'un triplet formé du nœud de départ, d'un marqueur
vide et d'un marqueur O. (S'il y a plusieurs nœuds de départ, on les fait précéder par
un nœud unique fictif s, lié à chaque sommet de départ effectif par un arc de coût
nul.)
A chaque étape,
• on prélève dans la frange un triplet (y, x, f ) de marqueur minimal,
y
• si y est le but, le chemin cherché finit en (x y) et est de valeur f : on reconsti
y
tue le chemin complet par chaînage sur x ;
• sinon, pour chaque successeur z de y non encore traité, on forme un triplet (z,
y, fJ
- on l ' ajoute à la file si elle ne contient pas de triplet en z ;
- si la file contient un triplet (z, y l , f ,), on ne garde que (z, y, f,) si f,< f,, et
on ne garde que (z, y l , f ,) sinon 8 .
Cette méthode du meilleur d 'abord est un exemple de méthode pilotée, directe
et irrévocable, mais il est difficile de caractériser les performances d' un procédé
aussi général sans autre hypothèse.
Nous examinerons donc deux cas particuliers avant une discussion plus géné
rale.
Notons d'abord que ce procédé se ramène à une recherche par niveau si
l ' indicatrice est la taille (ou nombre d ' arcs) du chemin déjà parcouru. Plus générale
ment, si l ' indicatrice est une longueur ou un coût, on retrouve une méthode prudente
mais admissible connue comme algorithme de Dijkstra-Moore.
Méthode prudente DM
Il s ' agit d'une méthode BF avec f=g, qui favorise le sommet « le moins coûteux
jusqu ' ici », méthode admissible, mais pas toujours rapide.
Une première version de l ' algorithme correspondant, dit de Dijkstra-Moore, a
été publiée dès 1 959.
EXEMPLE. Reprenons le graphe précédent, où on suppose chaque sommet lié aux
sommets adjacents dans les 4 directions principales (N, 0, S, E) avec une distance de
5, augmenté de liaisons aux sommets adjacents dans les 4 directions auxiliaires (NO,
SO, SE, NE) avec une distance de 7.
Les arcs diagonaux, de coût distinct, distingueront la méthode DM d'une re
cherche par niveaux.
8 Ainsi, de deu chemins menant à z l 'un par y et l'autre par y l , on garde trace du plus
x intéressant.
38 A-Approche algorithmique
Le principe de l 'évolution de la frange est donné ci-après (le triplet souligné est
le triplet sélectionné avant d' être retiré de la frange ; ses successeurs utiles apparais
sent dans la frange suivante).
Dans un graphe de grande taille, on peut considérer que cette méthode se
confine à une sphère utile de rayon à peine supérieur à la distance minimale cher
chée, sans se focaliser particulièrement sur un objectif, d ' où une certaine lenteur.
Méthode gloutonne G
Il s ' agit d'une méthode BF avec f = h, où h indique le nœud le plus prometteur, abs
traction faite du chemin parcouru.
EXEMPLE. On reprend le graphe précédent, où on suppose chaque sommet lié aux
sommets adjacents dans les 4 directions principales (N, 0, S, E) avec une distance de
5, augmenté de liaisons aux sommets adjacents dans les 4 directions auxiliaires (NO,
SO, SE, NE) avec une distance de 7.
Ici, pour trouver un chemin de longueur minimale, on prend comme indicatrice
une estimation de la longueur séparant le sommet courant n de la cible, la distance
euclidienne entre centres des cases correspondantes. C ' est une estimation optimiste
de la longueur du chemin qui les sépare,
• exacte entre deux points alignés selon l ' une des 8 directions, s ' i l n ' y a pas
d 'obstacle,
• minorante sinon.
On amorce l ' algorithme avec un triplet (b,_, 25), puisque d2(b, y) = 25.
Espace d'état et métaphore du labyrinthe 39
Fig. 3.9 Evolution de la frange pour une recherche d'un chemin de b à y (graphe G 1 ), méthode du
meilleur d'abord , version DM {f = g).
(b,(),25)
(a , b, 28)(g, b, 25), (h, b, 1 8), (c, b, 23)
(a, b, 28), (g, b, 25), (c, b, 23), ( 1 , h, 1 8), (m , h, 1 4), (n , h, 1 1 ), (i, h, 1 6), (d , h, 2 1 )
(a, b, 28), (g, b, 25), (c , b, 23), (!, h, 1 8), (m, h, 1 4), (i, h, 1 6), (d, h, 2 1 ), (s, n , 1 1 ), (o , n , 1 0 )
(a , b, 28), (g, b, 25), (c, b, 23), ( 1, h, 1 8), (m, h, 1 4), (i, h, 1 6), (d, h, 2 1 ), (s , n , 1 1 ), (t, o , 7), (p , o ,
l i ), u. o, 1 6)
(a, b, 28), (g, b, 25), (c, b, 23), (1, h , 1 8), ( m, h, 1 4), ( i, h, 1 6), (d , h, 2 1 ), (s, n , 1 1 ), (p, o, 1 1 ), (j,
o, 1 6), (y, t, 0), (z, t, 5)
Fig. 3.1 1 Evolution de la frange pour une recherche d'un chemin de b à y (graphe G 1 ), méthode du
meilleur d'abord, version G ( f = h).
Optimalité
Dans une classe donnée, on dira un algorithme optimal s ' i l domine tous les autres
algorithmes de sa classe.
Algorithmes A*
Hart, Nilsson et Raphaël ont défini en 1 968 une importante classe d' algorithmes BF,
dits algorithmes A * (Pearl 1 990 ; Farreny 2002).
La fonction f utilisée pour la sélection d'un nœud n est du type f(n) = g(n)+
h(n), où :
• g(n) est le coût du sous-chemin déjà parcouru, du sommet de départ s au
parcourir.
Enoncé
La frange est initialisée à l ' aide d'un triplet formé du nœud de départ, d'un marqueur
vide et d'un marqueur O. (S 'il y a plusieurs nœuds de départ, on les fait précéder
d'un nœud unique fictif s, lié à chaque sommet de départ effectif par un arc de coût
nul.)
A chaque étape,
• on prélève dans la frange un triplet (y, x, f ) de marqueur minimal ;
y
Espace d ' état et métaphore du labyrinthe 41
Comme avec la première méthode DM, le chemin trouvé est bien optimal : c 'est
(b h m s x y), de longueur 29. Mais cette fois le nombre d 'étapes est réduit, intenné
diaire entre les deux méthodes DM et G. L ' algorithme A* concilie ainsi une efficaci
té relative avec l ' obtention d'une solution optimale.
Discussion
Soit g*(n) le coût minimal des chemins allant du sommet initial s au sommet n, et
h*(n) le coût minimal des chemins allant du sommet n à l 'ensemble final F ; pour un
chemin particulier P allant de s à F via n, on aura toujours
gp (n) � g*(n) et hp(n) � h*(n)
• f*(n) = g*(n)+h*(n) est alors le coût optimal pour l 'ensemble des chemins
passant par n,
• si C* est le coût minimal de s à F :
f*(s)=h*(s) = C* = min b e F {g*(b) } ;
• si n appartient à un chemin minimal, f*(n)=C* ; mais si n n 'appartient pas à
un chemin optimal, f*(n)>C* (par l 'absurde).
9 Ainsi, de deuK chemins menant àn l 'un par y et l ' autre par y 1 , on garde trace de celui ayant le plus faible coût.
42 A-Approche algorithmique
(b,Q,25)
(a, b, 33Xg, b, 32), (h, b, 25), (c, b, 28)
(a, b, 33Xg, b, 32), (c, b, 28XI, h, 32) (m, h, 26) (n, h, 25) (i, h, 28Xd, h, 35)
(a, b, 33Xg, b, 32), (c, b, 28) (1, h, 32) (m, h, 26) (i, h, 28Xd, h, 35Xs, n, 32Xo, n, 29)
(a, b, 33Xg, b, 32), (c, b, 28) (1, h, 32) (i, h, 28Xd, h, 35) (s, n, 32) (o, n, 29Xr, m, 35) (s, m, 28)
(a, b, 33Xg, b, 32), (1, h, 32) (i , h, 28) (d, h, 35) (0, n, 29Xr, m, 35) (s, m, 28) (i, c, 28) (d, c, 3 1 )
(a, b, 33Xg, b, 32), (1, h, 32) (o, n, 29Xr, m, 35) (s, m, 28) (i, c, 28) (d, c, 31) (o, i, 29Xe, i, 39)
(a, b, 33Xg, b, 32), (1, h, 32) (o, n, 29Xr, m, 35) (i, c, 28) (cl, c, 3 l ) (o, i, 29Xe, i, 39) (v, s, 39) (w, s, 32) (x, s, 29)
(a, b, 33)(g, b, 32), (1, h, 32) (0, n, 29) (r, m, 35) (d, c, 3 1 ) (0, i, 29) (e, i, 39) (v, s, 39) (w, s, 32) (x, s, 29)
(a, b, 33Xg, b, 32), (1, h, 32) (r, m, 35) (d, c, 3 1 ) (o, i, 29) (e, i, 39) (v, s, 39) (w, s, 32) (x, s, 29) (t; o, 33)(p, o, 35)(j, o, 42)
(a, b, 33Xg, b, 32), (1, h, 32) (r, m, 35) (d, c, 3 1 ) (e, i, 39) (v, s, 39) (w, s, 32) (x, s, 29) (t, o, 33)(p, o, 35)(j, o, 42)
(a, b, 33Xg, b, 32), (1, h, 32) (r, m, 3S) (d, c, 3 1) (e, i, 39) (v, s, 39) (w, s, 32) (t, o, 33) (p, o, 35) (j, o, 42) (y, x, 29)
Fig. 3.13 Evolution de la frange pour une recherche d'un chemin de b à y (graphe G l ), méthode du meil
leur d'abord , version A *=BF* (f = g + h).
Diffic ultés
L 'expérience montre que dans beaucoup de problèmes, les algorithmes A* passent
une bonne partie de leur temps à discriminer des chemins de coûts peu différents.
Cela peut les empêcher de trouver la solution optimale cherchée dans le temps impar
ti, alors même que l ' idée d'une fonction heuristique h sous-entend qu' on était prêt à
troquer un peu de qualité contre une nette accélération.
Cette constatation a posé la question du bien-fondé de la relation f= g + h.
Si on pose f = g, l 'algorithme DM reste admissible (h = 0) mais s 'apparente à
une recherche par niveaux, qui souffre d 'un manque de focalisation sur l ' obj ectif. Si
on prend f = h (algorithme G), le chemin parcouru est négligé, et les décisions prises
ne reposent que sur l ' estimation de ce qui reste à faire : cela se révèle adapté si les
solutions sont nombreuses et h une estimation de qualité ; sinon, le nombre de cas à
Espace d'état et métaphore du labyrinthe 43
examiner se multiplie, g n 'étant plus là pour rappeler qu 'on s 'égare quand le chemin
déj à parcouru devient beaucoup trop long.
Algorithmes P(w)*
Afin d'ajuster l ' influence des termes g et h, Pohl a proposé en 1 970 d'utiliser une
fonction indicatrice pondérée f-v(n)=( l -w) · g(n) + w·h(n). Au-delà des cas étudiés que
l ' on retrouve, l ' idée est maintenant de doser conservatisme (w-7 0) et aventurisme
(w-7 1 ) (Pearl, 1 990).
Si h est admissible, on montre que les algorithmes P(w) sont toujours admissi
bles pour w s l /2 ; au-delà, tout dépend des écarts entre h et h* : on peut gagner en
rapidité, mais on peut perdre l ' admissibilité 10 , et on peut même voir le nombre de
nœuds à traiter croître.
{ {
f ( n ) = g(n ) + h ( n ) · l + & t- � )}
d )
Algorithmes IDA*
Ils reprennent globalement la stratégie « par approfondissements successifs ». Mais
le cœur de l ' itération n ' est plus une simple recherche en profondeur : c ' est un algo
rithme utilisant le même genre d ' indicatrice que les algorithmes A*, en privilégiant
le développement du nœud le plus profond, pour autant que son indicatrice soit infé
rieure à un seuil S ; en cas de dépassement, l ' algorithme effectue une reprise arrière
dans le style des recherches en profondeur. L'algorithme IDA* est admissible. Sa
complexité en espace est celle d'une recherche en profondeur. Mais il peut échouer
IO
Donc, l ' optimal ité de la solution trouvée.
44 A-Approche algorithmique
pour une valeur insuffisante de S, et doit alors être relancé. Sa complexité dans le
temps est sensiblement celle de la dernière passe, qui peut être longue.
Cependant, des campagnes d' essais assez exhaustives (sur des problèmes de
taquin) ont montré qu 'il était significativement plus efficace que les algorithmes
antérieurs (Farreny 2002).
3.4.4 Elagage
Quelle que soit la méthode retenue, elle est souvent encore trop lourde. Comment
réduire le nombre de nœuds à traiter, si possible sans perte de propriétés ?
Soit h(n) une estimation optimiste du coût h*(n, F) du sous-chemin restant à
parcourir, et de même H(n) une estimation pessimiste de h*(n, F), de telle façon que
l ' on ait toujours h(n) ::; h*(n, F) ::; H(n).
Soient alors x et y deux sommets de la frange en attente de traitement : si
H(x)<h(y), traiter x rend le traitement de y sans objet, puisqu'une solution en y serait
nécessairement pire que toute solution en x. Cette remarque, à l ' origine de la techni
que d'élagage ou pruning, allège parfois considérablement les recherches, car ne pas
traiter x évite d 'énumérer l'arbre des possibilités de racine x.
EXEMPLE.
Soit à régler un problème de déplacement entre deux sommets a et z d'une grille,
trame de l ' espace de recherche (ville, circuit imprimé . . . ).
La distance euclidienne d2(,) ou distance à vol d'oiseau sera toujours une borne
inférieure de la distance à parcourir.
Avec un plan en grille parfait, sans autre contrainte, la distance d 1 (,) ou distance par
blocs représentera la longueur à parcourir entre deux points ; ce sera une majoration
de cette distance si au plan en grille strict s ' ajoutent des liaisons diagonales.
Une recherche de chemin avec élagage pourrait donc utiliser ici
h(n) = d2(n, z) ::; h*(n,z) ::; H(n) = d 1 (n, z). •
11
En décembre 2005, Ubisoft a investi 20M€ dans le développement du jeu King Kong, d'après le film de
Peter Jackson ; les ventes de certains jeux ont atteint 600 M$ en Amérique du Nord.
Espace d'état et métaphore du labyrinthe 45
la somme des distances d1 que chaque j eton n doit parcourir pour passer de sa
place dans c 1 à la place souhaitée dans c2•
gné /perdu ;
• les méthodes maxmin ou negmax s ' appliquent si les gains varient avec les is
sues.
46 A-Approche algorithmique
Mais il faut bien noter que de nombreux jeux classiques (échecs, go) sont d'une
complexité suffisante pour qu 'un effet d' horizon s' oppose à ces procédés.
Grundy avait ainsi défini sa fonction de marquage : tout sommet terminal est
marqué 0, tout autre sommet est marqué du plus petit entier positif qui ne marque pas
un de ses successeurs, soit
g( X ) = min ( }. ! - { g(y) 1 YE f (x) } )
Cette fonction n ' existe pas toujours e t n 'est pas touj ours unique, mais ces ex
ceptions restent rares. Sinon, on vérifie facilement que l 'ensemble des sommets x de
marque g(x)=O constitue le noyau du graphe considéré.
Donc, il existe une stratégie non perdante (gagnante si le j eu est fini) pour tout
j eu à 2 joueurs dont le graphe admet une fonction de Grundy.
Le procédé s 'étend aux jeux ayant des configurations terminales perdantes ou
pièges, qu' i l suffit de marquer 1 (Frécon 2002).
EXEMPLE.
2 joueurs partent d'un tas de N j etons. Chacun retire à son tour Je nombre de j etons
qu' i l veut, pourvu que ce soit un carré parfait ( 1 , 4, 9, 1 6 . . . ). Celui qui prend le der
nier j eton a gagné. Y a-t-il une stratégie gagnante ? •
Tableau 3.2 Jeu : configurations atteintes en fonction de la configuration initiale et du coup joué.
0 1 2 3 4 5 6 7 8 9 10 li 12 13 14 15 16 17 18
-1 0 1 2 3 4 5 6 7 8 9 10 Il 12 13 14 15 16 17
-4 0 1 2 3 4 5 6 7 8 9 IO Il 12 13 14
-9 0 1 2 3 4 5 6 7 8 9
-16 0 1 2
g 0 1 0 1 2 0 1 0 1 2 0 1 0 1 2 0 1 0 1
Espace d'état et métaphore du labyrinthe 47
Maxmin et Negmax
On s ' intéresse ici aux jeux, négociations, voire aux procédures judiciaires civiles
opposant deux adversaires, le processus étant modélisé par un graphe sans circuit, et
48 A-Approche algorithmique
se terminant par des gains et/ou pertes pouvant différer à chaque issue, un gain étant
une somme reçue de l ' adversaire, une perte une somme qu ' on lui donne.
On suppose chacun jouant au mieux de ses intérêts, tout choix maximisant les
gains de celui qui le fait, et on désire définir ces choix au mieux lorsque ces deux
j oueurs alternent leurs choix, qui deviennent ainsi interdépendants.
La procédure MaxMin pose qu'un premier joueur (Max) maximise ses gains,
tandis que l ' autre minimise ses gains du point de vue du premier joueur. De même,
les cas terminaux sont valués en fonction du gain pour le premier joueur.
L 'évaluation maxmin, tabulée ci-après, se fait en pratique en développant un
arbre d'évaluation mimant une navigation en profondeur dans le graphe.
A= max( B , C , D ) 70
B = min ( E, F ) 50
C = min (F , G ) 50
D = min (G , H ) 70
E = 1 00
F = max ( ! , J ) 50
G = max (J , K) 70
H = 80
! = 50
J = -200
K =70
Effet d'horizon
La stratégie ci-dessus est la plus sûre si la totalité des positions accessibles de la
position considérée est calculable, ce qui peut l ' être en droit sans l ' être en fait, en
nécessitant par exemple une mémoire finie beaucoup plus grande que la mémoire
disponible, ou un temps de calcul excessif, comme par exemple pour les échecs. Les
positions terminales étant valuées sur une échelle E des gains, on effectuera à chaque
fois le calcul du coup à jouer en horizon limité (ou, si l'on veut, profondeur bornée) ;
la valeur attribuée aux sommets des confins qui ne seraient pas terminaux est alors
une estimation (heuristique) de la valeur de la position atteinte, au sens de l ' échelle
des gains.
Naturellement, le résultat est d 'autant meilleur que la profondeur-limite est plus
grande et l 'heuristique plus heureuse ; à ressources égales, deux écoles s ' affrontent :
• les uns préfèreront des heuristiques minutieusement établies (« d'un grand ré
• pour les jeux à deux joueurs : kriegspiel (échecs masqués), bataille navale, be
3 .6 EXERCICES
3.6.1 Filiation
Reprenons la question d'établir votre filiation en tant que descendant probable de
Charlemagne (§ 3 . 3 .2).
Admettre (2000 - 800)/3 0= 40 générations.
Supposer que a=2 ; en l ' absence d'unions consanguines, combien auriez-vous
d 'ascendants vivant en l ' an 800 ? A combien devrait se réduire a pour que vous
n ' ayez que 5 . 000.000 d 'ascendants vivant en 800 ?
Combien vaut d, si ces 5 000 000 d 'ascendants ont aujourd 'hui 300 000 000 de
descendants ?
Les conclusions demeurent-elles sur la méthode à employer ?
3.6.4 Jeu l
2 j oueurs partent d'un tas d e N jetons. Chacun retire à son tour l e nombre d e j etons
qu 'il veut, de l à k. Celui qui prend le dernier j eton a gagné.
Montrer qu 'il existe un noyau formé des configurations multiples de k+ l . Ex
pliciter la stratégie gagnante.
3.6.9 La Coupe
Les deux joueurs arrivés en finale savent que, si l 'un d'eux gagne, il touchera
700 000 oros, et son concurrent malheureux 1 00 000 ; et que s ' ils font match nul, ils
auront chacun X oros.
Si les deux « pros » décident de faire front commun contre les organisateurs en
partageant les gains, qu ' ont-ils intérêt à faire ?
Connaissant ce risque, si les organisateurs « veulent du spectacle », qu' ont-ils
intérêt à faire ?
domaine.
3.6. 13 Solitaire
On considère un j eu à un joueur (et environnement passif) formé de N cases (N > 30)
comportant au départ chacune un fichet. Pour jouer :
• si nécessaire, on enlève un fichet ;
• tout sommet marqué 0 est une impasse au sens large (i.e. est terminal perdant,
3.6. 14 Taquin
Entre deux configurations x et y d 'un même j eu de taquin, on définit deux estima
tions du nombre de mouvements à faire pour passer de x à y :
• h 1 (x, y) = « nb de jetons de x mal placés par rapp01t à y » ;
• h2(x, y) = « somme des distances par blocs d 1 (i, j) entre chaque j eton i de x et
sa position j dans y ».
Laquelle de ces deux estimations informerait le mieux un algorithme A* ?
points qu 'il a su employer de lettres, si son mot est licite et au moins aussi long que
celui de son adversaire.
On s ' intéresse à un logiciel d ' aide aux arbitres, qui pour un tirage donné devrait
produire la meilleure (resp. les meilleures) solution(s) possible(s). Ce logiciel explo
rerait un arbre des possibles, partant du tirage à traiter.
L'ordre des lettres n'ayant finalement pas d' imp011ance, on décide dans le logiciel
de remplacer chaque tirage t par son « profil » p(t) formé des mêmes lettres mises par
ordre alphabétique, les tirages équivalents étant ainsi des tirages de même profil.
On dispose
• d'un lexique, auquel est associé une fonction d' extraction L(p) qui renvoie :
3.6. 1 7 Pousse-pion
Le j eu se déroule dans un quadrillage (genre N2). On considère un pion dans une
case assez loin de l ' origine. Chacun des 2 joueurs peut à son tour pousser le pion
situé en (k, n) :
• à gauche en (k-i, n),
• en bas en (k, n-i),
• en diagonale vers (k-i, n-i),
pour autant que i, choisi supérieur à 0, ne fasse pas sortir le pion du quadrillage.
Le joueur qui amène le pion en (0, 0) a gagné.
Expliciter une stratégie gagnante.
54 A-Approche algorithmique
La stratégie maxmin (resp. negmax) est la plus sûre si l 'adversaire joue au mieux,
mais ne lui laisse aucune chance de se tromper. De ce point de vue, considérons le
cas
max(A, B), où A= l OO, et B = min ( 1 00, 1 50, 300)
Les stratégies mentionnées supposent qu 'il est indifférent de jouer A ou B. On
convient de noter B = 1 00+ (lu « 1 00 et plus »), pour noter qu'il est marginalement
plus intéressant de jouer B (au cas où l 'adversaire se tromperait). De même on posera
max( l OO, 75)= 1 00- etc . . .
Explorer les règles de calcul nécessaires aux différents cas de figure (change
ment de signe, max et min).
Montrer que, sans risque aucun, on laisse ainsi une « chance marginale à la
chance » d ' obtenir un jeu aussi sûr quoique marginalement plus brillant qu'avec les
stratégies maxmin (resp. negmax) pures.
3.6. 1 9 Le coursier
Soit un coursier devant desservir divers sites A, . . ., L. Les liaisons entre sites sont
données par un graphe formé d' arêtes pour les liaisons bidirectionnelles, et d' arcs
pour les liaisons à sens unique. A chaque site est attachée une liste (éventuellement
vide) des objets en partance, avec pour chacun sa destination.
Envisager d'abord le problème en supposant que le nombre total d ' objets est
assez faible, et que le coursier peut en transporter « un nombre suffisant à la fois ».
Pour simplifier, on s ' intéressera à la taille du chemin parcouru pour aller de A à A,
en acheminant tous les obj ets.
Envisager ensuite le problème en supposant (a) que le nombre total d ' obj ets est
assez important, (b) que le coursier peut en transporter au plus k (par exemple, 3 ou
5) à la fois (c) qu 'on connaît un circuit hamiltonien (i.e. un itinéraire fermé passant
par chaque site une fois et une seule, tel que (A B G C F D E L K J 1 H A)) de Ion-
Espace d'état et métaphore du labyrinthe 55
gueur totale minimale. Supposer que pendant les déplacements du coursier, de nou
velles demandes apparaissent, tandis que l ' état du réseau se modifie : du fait
d'accident et/ou de réparations, ce11aines liaisons deviennent inopérantes, restreintes
à un sens ou bidirectionnelles. Si le coursier est très occupé (trafic important et/ou
heuristiques malheureuses) certains obj ets risquent de rester en souffrance ; comment
améliorer la gestion globale si on indique pour chaque objet une date & heure de
dépôt ? comment améliorer et diversifier les services en indiquant pour chaque obj et
une date & heure de livraison promise ?
3.6.20 Décodage
Un camarade de lycée doit vous rendre visite ; il vous a envoyé le message chiffré
suivant :
27748667 1 726334 1 6434 1 2632 1 86 1 428328 1
qui doit, comme autrefois, se référer au code du clavier téléphonique, avec la
convention :
touche 2 3 4 5 6 7 8 9
ca1·actère a d g j .m p \V
b e h k Il q Il X
c f 0 V y
z
Esquisser un graphe des interprétations, à raison d'un noeud par chiffre et d'un
arc par caractère. Que signifie un chemin ?
Evaluer grossièrement leur nombre.
Déterminer les impasses, le chemin le plus probable, et le message correspon
dant.
Connaisssant la langue employée, peut-on tirer partie de la fréquence des carac
tères ? de la probabilité d' apparition d'une lettre, relativement à la précédente ?
3.7 INDICATIONS
Pour 3.6.2
Dans un tel réseau, on cherchera un chemin de durée minimale, qui peut être une
recherche en profondeur bornée à 3 0 (<<3000) si on compte 2 minutes entre deux
arrêts, afin de respecter les contraintes tarifaires, pour un ticket simple, à 60 pour un
ticket double. De fait, le diamètre de 54, correspondant au chemin élémentaire de
plus grande taille, suggère de réduire la seconde borne de 60 à 54. La qualité des
solutions supposera (a) de procéder par approfondissements successifs, limités à la
profondeur 30, ou par optimisation progressive, pai1ant d'une profondeur 3 0 ; (b)
pour les correspondances, de leur assigner une durée forfaitaire accrue d'une durée
égale à la fréquence de la nouvelle ligne empruntée, afin de tenir compte des fré
quences et raretés.
56 A-Approche algorithmique
Pour 3.6.3
On prend comme sûreté d'un chemin le produit des probabilités d'arriver au bout de
chaque segment. A cette sûreté s = p 1 p2•
•
p11 on peut associer un risque s'exprimant
• • •
Pour 3.6.4
Si le joueur A reçoit un multiple non nul de k+ l , et joue n (de l à k), B peut riposter
en jouant k+ 1-n, et atteindre ainsi 0 (il a gagné) ou ramener A à un nouveau multiple
non nul de k+ l : B enferme A dans le noyau, formé des multiples de k+ l .
EXEMPLE.
Si on prend de l à 4 allumettes, le noyau est formé des multiples de 5. Alors, si le
j oueur A reçoit un multiple non nul de 5 , par exemple 20, et j oue n (de l à 4), B
riposte en jouant 5 - n, et atteint ainsi 1 5 , puis aux tours suivants l 0, 5 et enfin 0 : B
gagne en se ramenant systématiquement aux multiples de 5 . •
Pour 3.6.5
Classer les nombres premiers modulo 4, et s ' inspirer du 3 .7.4.
Si on reçoit 44 jetons (=0 mod 4), jouer . . . n ' importe quel nombre premier pas
trop grand (de l à 1 3 par exemple ; on a peut-être déjà perdu).
Si on reçoit 43 jetons (=3 mod 4), jouer tout nombre premier congru à 3 modulo
4 : 43 (c'est gagné ! ), 3 1 , 23, 1 9, 1 1 , 7 ou 3 .
S i o n reçoit 4 2 jetons (=2 mod 4), jouer 2 .
S i o n reçoit 4 1 j etons (= l mod 4), jouer tout nombre premier congru à l modulo
4 : 4 1 (c'est gagné ! ), 37, 29, 1 7, 1 3 , 5 ou l .
Que vous suggère la conjecture de Goldbach ?
Pour 3.6.6
Voir théorème des 4 carrés.
Pour 3.6.7
Supposons que 2 joueurs partent d'une file de N jetons. Le premier joueur partage en
deux la file qu'il reçoit, puis chacun à son tour partage en 2 l'une des files qu 'il re
çoit. Celui qui isole le dernier jeton a gagné.
Il y a finalement N- 1 séparations possibles ; faites dans un ordre quelconque,
elles donnent 2N- I configurations. Toutes les configurations à k séparations ( 1 <k<N)
sont issues de configuration à k- 1 séparations et mènent à des configurations à k+ l
séparations. La configuration à N- l séparations est unique, terminale et gagnante.
De même, quand les 2 joueurs partent de tas, on voit que la seule chose qui
importe est le nombre de tas, de l à N. Le premier joueur recevra donc successive
ment l , 3, 5, 7 . . . tas pour en faire 2, 4, 6 . . . Et le second joueur recevra successive
ment 2, 4, 6 . . . tas et rendra 3, 5, 7 . . . tas.
Espace d'état et métaphore du labyrinthe 57
Le noyau est donc formé des configurations dont le nombre de tas est de même
parité que N. Le premier joueur gagne si N est pair, car N fait alors partie des nom
bres de tas qu 'il peut atteindre. Joué sur une table avec divers objets, le jeu peut
sembler varié, alors qu ' en fait il n ' admet aucune initiative efficace.® !
12
C'est une version allégée du treillis de divisibilité d'atomes {2, 3, 5 } , et de maximum N.
58 A-Approche algorithmique
Mais en rajoutant en queue de la file les successeurs d'un profil, on explore par
niveaux la liste des profils : on n 'aborde les profils de longueur n-1 que lorsque tous
les profils de longueur n ont échoué, la première solution trouvée est donc la meil
leure ou une des meilleures possibles, et le procédé est non seulement complet mais
admissible.
Contenus de F :
abcopu
abcop abcou abcpu acopu bcopu
abcou abcpu acopu bcopu 1 abco abcp abop acop bcop
abcpu acopu bcopu 1 abco abcp abop acop bcop al9ee abcu abou acou
bcou
acopu ...
-L ( acopu ) = « acoup »
no 0 1 2 3 4 5 6 7 8 9 IO 11
étape a b g f d e 1 k j i h a
>d î 1 1 1
1 !
>l î 3 3 3 3 3
3 !
"'
>i î 2 2 2 2 2 2 2
..
CJ) 2 !
"'
t: 2 2 2 2 2 2!
Q
>a î
1:1.
2
3.8 RÉFÉRENCES
Binmore K., Jeux et théorie des jeux, De Boeck Université, Bruxelles ; traduction de
Binmore K., 1 992, Fun and Gomes ; a Text on Game Theo1y, DC Heath,
Lexington (USA) .
Cousineau G. & Maury M., 1 995, Approche fonctionnelle de la programmation, ch.
8, Graphes et résolution de problèmes, Ediscience Inti, Paris.
Farreny H., 1 995, Recherche heuristiquement ordonnée, Algorithmes et propriétés,
Masson.
60 A-Approche algorithmique
MÉTHODES DE RÉDUCTION
4. 1 PRINCIPE
On veut ici résoudre les problèmes en fonction d'une analyse les ramenant par étapes
à des problèmes plus élémentaires, jusqu 'à des problèmes qu 'on sait résoudre, en vue
de planifier une solution du problème global.
La hiérarchie de problèmes obtenue combine deux opérations :
·
• la conjonction, qui ramène un problème à un ensemble de sous-problèmes
lution de l ' un d' eux suffisant à résoudre le problème initial, les autres consti
tuant des solutions de rechange.
On peut formaliser cette approche algébriquement, ou à l'aide de graphes
ET/OU.
On appelle graphes ET/OU des graphes G = <X, U> ayant deux types de sommets :
les sommets ET, et les sommets OU. On distingue les sommets ET par une barre
unissant leurs arcs sortants.
~
El E2 E3 E' Alternative /Noeud OU
E4
� ES E6
Fig. 4.1 Graphe ET/OU pour « cet examen comporte 4 épreuves : 3 épreuves obligatoires, plus une à
choisir parmi 3 options ».
Sur les problèmes terminaux, on peut avoir des renseignements binaires (solu
tion connue ou non), n-aires (degré de difficulté), numériques (délai ou coût).
Selon la nature de ces renseignements, on attachera aux sommets ET et OU des
procédés d 'évaluation permettant de conclure au mieux d' abord sur les problèmes
correspondants puis sur le problème global.
Si tous les sommets terminaux sont renseignés a priori, on fera la synthèse des
renseignements par une méthode ascendante.
Une méthode descendante sera préférable si tous les cas terminaux ne peuvent
être renseignés a priori .
On suppose l ' analyse du problème faite, et les sommets terminaux sont renseignés a
priori . A pmtir de là, une stratégie ascendante consiste à évaluer les sommets dont
tous les successeurs sont terminaux, puis successivement tous les sommets dont tous
les successeurs sont valués. S ' il n'y a pas de circuit, le problème initial est lui-même
évalué en un temps fini.
La justification de cette valeur finale sous-tend Ie(s) plan(s) d ' action souhaita
ble(s).
0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0
Mais pour le OU ? Si P peut être résolu par une tâche de coût [a b] ou une tâche
de coût [ c d] , laquelle choisir ?
• Une règle optimiste retiendra la tâche ayant la plus petite borne minimale, afin
de laisser « une chance à la chance » et, en cas d ' égalité, la tâche ayant la plus petite
borne maximale ; ainsi, on préfèrera [ 1 00 500] à [ 1 00 600] mais aussi à [200 400] .
• Une règle pessimiste, recommandée en ingéniérie 1 3 , voudra qu 'on retienne la
tâche ayant la plus petite borne maximale, afin de « minimiser le désastre » 14 et, en
cas d 'égalité, la tâche ayant la plus petite borne minimale ; ainsi, on préfèrera
[ 1 00 500] à [200 600] comme à [200 500), mais on lui préférera [200 400] .
Considérons maintenant un problème PO et son analyse, comme définis par les 3
premières colonnes du tableau 4.3. A partir de là, on peut évaluer les sommets dont
tous les successeurs sont terminaux (phase 1 ). Puis successivement tous les sommets
dont tous les successeurs sont valués (phases 2 et 3). Ainsi, PO apparaît comme fai
sable pour un coût [ 1 1 0 1 80] .
13
L'ingénieur est sensé être un « pessimiste actif ».
14 Ou « s'en sortir au mieux si tout tourne mal ».
Méthodes de réduction 65
On suppose que l ' analyse du problème a produit un graphe ET/OU, sans que les
sommets terminaux soient renseignés a priori. A partir de là, une stratégie descen
dante consiste à parcourir ce graphe en profondeur de façon à recueillir les valeurs
terminales quand elles seront nécessaires pour évaluer les nœuds rencontrés, un
nœud étant évaluable au pire quand tous ses successeurs sont évalués.
Ce processus, en principe très lourd, peut être élagué : un nœud est de fait éva
lué dès qu 'un de ses successeurs possède une valeur absorbante pour l ' opération
associée au dit nœud : faux pour ET, vrai pour OU, + w pour max et + dans : . , 0 pour
min dans :� +, -w pour min dans : . . .
Par exemple, si une conjonction doit être établie, elle est impossible dès qu 'un
de ses termes est impossible ; et, quand une alternative se présente, elle devient une
solution dès qu ' une de ses possibilités est elle-même une solution.
Dans ces conditions, le processus d 'évaluation s 'accélère mais, de plus, compte
tenu de ce qui est déjà connu, des impasses sont possibles sans perte d'information et
la valeur de certains terminaux peut ne pas être nécessaire, ce qui est intéressant si
elle est difficile ou lente ou coûteuse à déterminer.
4.5 EXEMPLES
• des opérations attachées aux ET et OU, définies au regard de la nature des va
4.5. 1 Comportements
On peut représenter le comportement d 'un animal supérieur par une conjonction
entre (a) une fonction vitale et (b) un souhait, obj ectif ou désir commandant toute
autre activité.
Vi vre
enSécurité
paFroid
paSoif seRégaler
p
a� /
satiété manger
sortie trop-plein
0 0 vide
0 1 pleine sorlie bouchée !
1 0 mi-pleine
1 1 pleine
tive.
A ces écritures nous associerons le graphe de la figure 4.4.
De tels graphes peuvent mêler actions et conditions. Pour le faire avec une
certaine cohérence, les terminaux ayant été qualifiés, on admettra :
• qu 'une séquence est une action si toutes ses étapes sont des actions, et une
condition sinon ;
• qu'une alternative à n branches doit comporter d' abord n 1 conditions,
-
satiété?
phrase
! \!:;!,
�
�"'°�'""
sttjet verbe complément
li_// • ��
adjectif « banc » « chat » « papillon » « notaire »
�)" '1'
« gros » «joli » « vieux »
(verbe « dort » )
( complément (prépo s i t i on « sur » )
( groupe-nominal ( article « le » )
( sui te_nominale (nom_commun « banc » ) )
On aurait ici :
le � article ( suite nominale � groupe nominal )
vieux � adj ect i f ( nom commun � suite qua l i fiée )
chat � nom commun (� suite qua l i fiée � suite nominale � groupe
nominal � suj et )
dort � verbe ( complément � phra s e )
sur � prépo s i t ion (groupe nominal � complément )
le � article ( suite nominale � groupe nominal )
banc � nom commun (� suite nominale � groupe nomi nal �
complément � phrase )
Les homonymies, les polysémies, les mots « mis pour » compliquent évidem
ment la situation : « le » peut être un pronom (le voudrais-je . . . ), « vieux » peut être
nominal (le vieux dort sur le banc), etc. C ' est ce qu 'on observe dans les construc
tions ambiguës qui font le miel des linguistes, comme « les poules du couvent cou
vent » ou « la vieille ferme la porte ».
d'arrivée. Chacune de ces situations est définie par une liste de traits (attribut,
valeur). A partir de ces listes le problème peut se définir comme une liste de
différences qualitatives à réduire.
• On dispose d ' opérateurs, dont chacun a pour propriété de réduire au moins
eux-mêmes hiérarchisés.
La stratégie GPS est alors la suivante :
• on cherche la différence principale à réduire dans le problème posé, et la liste
moins recommandé, jusqu'à trouver un cas adapté ; l ' application d'un opéra-
Méthodes de réduction 73
EXEMPLE.
Je suis au Département Informatique de l ' INSA de Lyon, et je dois rencontrer un
collègue du Département MA de l ' EPFL à Lausanne.
Nous ne sommes ni dans le même bâtiment ni dans le même établissement ni dans la
même commune ni dans la même agglomération ni dans le même pays, mais dans
deux pays limitrophes, à distance moyenne.
L 'opérateur de transport recommandé est alors le train.
Pour cela, je dois me rendre à la gare associée à l ' INSA de Lyon, soit la gare de
Lyon-Part-Dieu, qui n ' est ni dans l ' établissement ni dans la même commune mais
dans la même agglomération (sous-problème amont).
L 'opérateur de transport alors recommandé est le tramway, qui m' emmène du pied
du bâtiment Informatique de l ' INSA de Lyon à la gare de Lyon-Part-Dieu. Pour cela,
je me rendrai d'abord à pied à la station de tramway . . .
Je peux ainsi prendre le train pour Lausanne (problème central) qui me laisse à la
gare de Lausanne-CFF. Il me reste à aller de la gare de Lausanne-CFF au Départe
ment MA de l ' EPFL, qui ne sont pas dans la même commune mais dans la même
agglomération (sous-problème aval). L' opérateur de transport alors recommandé est
le métro, qui m'emmène de la gare de Lausanne-CFF à l ' entrée de l ' EPFL à Ecu
biens. De là au Département MA de l ' EPFL, je finis à pied. •
GPS fut abandonné pour des raisons matérielles :
• disparition du langage support, supplanté par Lisp ;
• complexité pour l ' adaptation à une nouvelle application : révision des tables
Strips
Fikes, Nilsson, Hart et Sacerdoti ont développé à l 'Université de Stanford en 1 97 1
un système de planification pour le robot Shakey, robot radiocommandé 1 5 à capteurs
tactiles et vision réduite. L'univers de raisonnement était formé de boîtes, de salles et
de portes. Les opérateurs étaient définis en termes de préconditions, et d'actions de
deux types : génération et effacement de relations. La planification est réalisée à
l 'aide d'un démonstrateur de théorèmes.
Par rapport à GPS, on note une orientation logique, remplaçant tables et procé
dures ; la situation est à tout moment définie par une conjonction de faits ; la planifi
cation découle d'un but défini par une conjonction de relations : les opérateurs étant
élus selon leur capacité à engendrer les conditions non satisfaites, les préconditions
d'un opérateur élu deviennent de nouveaux sous-buts.
Abstrips
Sacerdoti, en 1 974, a présenté un habillage de Strips permettant une planification
hiérarchique, ou par raffinements successifs, afin d'éviter de construire en détail des
solutions devant finalement échouer pour des raisons assez évidentes.
La planification découle d'un but défini par une conjonction de relations pondé
rées. Un problème de niveau n reçoit une solution de niveau n, bâtie en ne tenant
compte que des prédicats de ce niveau ou d'un niveau antérieur. Une solution de
niveau n est considérée comme un problème de niveau n+ l : la/les solutions de ce
nouveau niveau habille(nt) la solution antérieure, dont elles constituent un raffine
ment réaliste. Le dernier niveau épuise la conjonction initiale de relations formant le
but, tous poids confondus.
Autres planifications
D'autres travaux ont été développés en termes de planification. Par exemple, le
temps est géré par instants ou évènements chez McDermott, et en termes
d' intervalles chez Allen. La robotique tend à privilégier une planification réactive,
sensible aux évolutions de l 'environnement, capable de moduler ou reconstruire un
plan en cours d' exécution, en fonction des aléas de cette exécution.
4.8 COORDINATION
Lorsque la réduction d'un problème P renvoie à une autre version P' du même pro
blème, la méthode de réduction implique des récursivités, directes ou indirectes, La
convergence du procédé suppose alors :
• que P' soit « plus simple » que P,
• que cette réduction ramène à un ou plusieurs cas élémentaires qu'on sache ré
soudre directement.
Soit P = TC(x), où P désigne le problème concret, TC une version générique de P,
et x la spécialisation de TC correspondant à P. Alors, on aura P' = TC (x'), et la condi
tion de convergence de la réduction sera remplie dès lors que x' sera un obj et, un j eu
de paramètres etc. similaire à x mais plus simple, les transformations successives
x-+ x'-+ x" . . . qui pourraient intervenir ramenant finalement P(x) à l ' un des cas
élémentaires qu 'on sait résoudre directement.
Plus généralement, la fragmentation d'un problème en sous-problèmes similai
res plus faciles à résoudre peut s ' appliquer récursivement pour n'avoir qu 'à résoudre
des problèmes élémentaires. Elle calque en général une relation de récurrence liant
données et résultats, chaque problème élémentaire ne s ' adressant plus qu' à une partie
des données.
Cette stratégie peut mener à des procédures récursives ou à d' autres formes
algorithmiques, pour autant que les données intermédiaires soient convenablement
stockées et transmises.
76 A-Approche algorithmique
disques phases
1 1 -- - 1 -
2 1 1
2 -- 21 - - 12 -- 2
3 1 1
2 2 1 1 2 2
3 -- 31 - 312 3-2 -3 2 132 1 3- -3 -
.. .
N Â - Â Â- Â
1 2 3 1 23 1 23 1 23
Performances
Soit T(n) la complexité temporelle d'un problème de taille n, problème subdivisé en
a sous-problèmes de taille nib, et soit S(n) un temps additionnel lié à la distribution
des données et à la synthèse des résultats. Alors,
T(n) = aT(n/b) + S(n)
mesure la complexité au pire du problème subdivisé. Dans le cas où n=b\ (Froide
vaux et al. , 1 994, p. 545) montrent que :
le tri parfusion
On remarque d' abord qu ' il est facile d ' interclasser deux suites déjà triées dans
l ' ordre croissant ; le processus est linéaire.
Au-delà de quelques éléments, le principe du tri par fusion d'une table est de trier
séparément la moitié inférieure et la moitié supérieure de la table, puis d' interclasser les
deux demi-tables triées. On se trouve dans le cas ci-dessus avec S(n)= O(n), et finale
ment T(n)=O(n log n), alors qu'on pouvait craindre un temps en n2•
4. 1 0 EXERCICES
4. 10.1 Organisation 1
On considère le problème PO défini par la table ci
contre, dans laquelle on associe à chaque problème ...
.=
0 :::1
terminal un « niveau de difficulté », noté 0 pour = "
., .... e
instantané, 1 pour facile, 2 pour moyen, 3 pour i=.. ..
"C:I :a
difficile, 4 pour très difficile.
0 P l vP2
On posera ET(d l , d2) = max (d l , d2) et
1 P3AP4AP5
OU(d l , d2) = min (d l , d2). 2 P6AP7AP8
En déduire de proche en proche la difficulté
des problème non-terminaux. 3 terminal 1
Quelle est la difficulté de PO ? 4 P9vP I O
5 P I OvP I 1
Quel « plan d' action » pour le résoudre au
mieux ? 6 P l 2vP l 3
7 P l 3AP 1 4
8 P 1 5vP 1 6
4. 1 0.2 Organisation 2
9 terminal 2
Obtenir certaines pièces administratives suppose 10 terminal 3
souvent d ' en produire plusieurs autres (avec par Il terminal 4
fois des alternatives), le schéma se répétant pour 12 terminal 2
chacune des pièces manquantes. On considère le 13 terminal 1
graphe ET/OU correspondant à l ' obtention d'un 14 terminal 0
acte A, sachant que : terminal
15 1
• pour A, il faut produire les pièces B, C, D,
16 terminal 2
et E (ou F) ;
• pour C il vous faut les pièces F, G, H ;
4. 1 1 INDICATIONS
Pour 4.8. 1
0 P l vP2 1
1 P3/\P4/\P5 3
2 P6/\P7/\P8 1
3 terminal 1
4 P9vP J O 2
5 P I OvP l 1 3
6 P l 2vP13 1
7 Pl3/\Pl4 1
8 P15vP 1 6 1
9 terminal 2
10 terminal 3
11 terminal 4
12 terminal 2
13 terminal 1
14 terminal 0
15 terminal 1
16 terminal 2
Pour 4.8.2
Avec F (demandé pour C), E (donc K, L, M) devient inutile. On se ramène à
A ..,. BACADAF, C ..,. FAGAH, H ..,. DAF, dont les terminaux sont B, D, F, G. L ' obten
tion de A demande 3 stades : celle de H, celle de C, celle de A. 2 mois devraient
suffire.
4. 1 2 RÉFÉRENCES
Buchanan B . , Sutherland G., Feigenbaum E., 1 969, Heuristics Dendral : A program
for generating explanatory hypotheses in organic chemistry, Machine Intel
ligence. // DENDRAL réalise l 'analyse automatique des spectres de masse
pour déterminer la structure moléculaire du corps chimique étudié, à partir des
masses atomiques et des valences.
Fikes, R. E. & Nilsson N.J. , 1 97 1 , STRIPS, A New Approach to the Application of
Theorem Proving, Artificial Intelligence, vol. 2.
Froidevaux Ch. , Gaudel M.F., Soria M., 1 994, Types de données et algorithmes,
Ediscience Inti, Paris.
CHAPITRE S
RÉSEAUX SÉMANTIQUES
5 .1 ORIGINES
1 6 Voir
.
Eco ( 1 988, pp. 97-102) pour des exemp 1 es p1us importants.
.
82 A-Approche algorithmique
animal
rationnel irrationnel
peu� respirer
ANIMAL -
__
r....._
�
peu
� branchies
est_! manger
/ t(
--
a
/ est_!
__ /
/ OISEAU POISSON
� '
[Link]
; '
voler
eut
/
est_l
est_ ! "' t
est_!
peu
� ger
ROUGE-
AUTRUCHE
_peut�
courir
1
REQUrn
_peut
� mordre
GORGE "'
\
e �
�
plastron rouge
dangereux
palles longues
C ' est un réseau de concepts, connectés par des arcs marqués, du nom des rela
tions entre concepts liés. La signification d'un concept est alors donné par
l 'ensemble des relations qu 'il a avec les autres concepts. Il y a deux sortes de rela
tions : les relations d'appartenance catégorielle, notée est_l , et des propriétés (est,
a, peut . . . ).
Réseaux Sémantiques 83
cuisine
Fig. 5.3 Réseau sémantique de « Alfred donne à Charles un livre dans la cuisine ».
Ce réseau concrétise la propriété bien connue : toute relation n-aire peut être
considérée comme la conjonction de n relations binaires.
Les phrases plus complexes sont en général traitées à partit d'un énoncé princi
pal simple, centré sur le verbe principal, et dont les actants et circonstants sont eux
mêmes l'objet d'énoncés auxiliaires. La phrase « Kiki le merle blanc a son nid dans
le grand marronnier derrière la maison » engendre une suite de triplets :
merle
�
est!
/ marronnier
Kiki -est-- blanc �
--- est!
possède
" /
$002 -es� grand
$OO 1 _dans�
'-
"'
!..,.
est
derrière
"""
nid maison
Fig. 5.4 Réseau sémantique de « Kiki le merle blanc a son nid dans le grand marronnier derrière la
maison ».
Le nid et le marronnier étant supposés uniques sans avoir de nom propre, ils se
voient attribuer un nom caché qui permet d'articuler définition et spécificités.
On raisonne de même au niveau des textes. Pour toute nouvelle phrase on forme
son réseau. On le juxtapose au réseau antérieur si elle est indépendante. Sinon, on
attache au réseau antérieur le nouveau réseau en fonction de la résolution des réfé
rences de la nouvelle phrase aux phrases antérieures.
Réseaux Sémantiques 85
Questions
Identification Réponse
forme textuelle triplets
Fig. 5.5 Interrogation du réseau sémantique de « Kiki le merle blanc . . . derrière la maison ».
Fig. 5.6 « Lola est une autruche. Une autruche est un oiseau. Un oiseau possède un plumage ».
NOTES
• Le principe d'économie cognitive s'applique maintenant sur une base statisti- ·
que : si la plupart des hyponymes d'une même entité X partagent une propriété, il
suffit d' indiquer cette propriété au niveau de !'hyperonyme commun X, quitte à
renseigner spécifiquement les hyponymes déviants ; la propriété sera retrouvée quand
nécessaire en combinant les principes d'héritage et d'exception.
• Héritage et exception peuvent se retenir en considérant que le principe
d'héritage s 'applique, sauf si une information locale (immédiate, présumée certaine)
contredit une propriété plus globale (déduite, donc plus hypothétique).
Réseaux Sémantiques 87
Représentation erronée
Ce sera en particulier le cas lors du codage littéral d' idiotismes, comme « il fait
beau », où « il » ne désigne pas un acteur, « fait » désigne pour une fois un état. . . :
« il fait beau » doit ici être entendu comme « le temps (météo) est beau ».
Réseau insuffisant
Il est rare qu'un texte se suffise à lui-même et que sa compréhension ne fasse pas
implicitement appel à d'autres connaissances, ce qu'Umberto Eco exprime en disant
que, pour être bien compris, le mot en son contexte renvoie à l 'encyclopédie plus
qu' au dictionnaire.
De ce point de vue, le réseau utile pourrait être formé du réseau issu du texte
sous étude, augmenté de connaissance générales et particulières :
• on parlera de connaissances de sens commun s'il s'agit des connaissances
présumées partagées par tous, telles que « le merle est un oiseau ; un oiseau a
deux pattes » ; elles commandent les réponses de bon sens ;
• à l 'opposé, on parlera de connaissances pragmatiques, s ' il s'agit de connais
sances spécifiques partagées par les acteurs, caractéristiques d'un milieu,
d'une profession, d'une école de pensée . . . ; elles commandent les réponses
« techniques ».
On peut considérer comme connaissances pragmatiques le fait de savoir :
• que « le chef de l 'Etat », « le chef des Armées », « le président de la Républi
que » . . . désignent en général le même personnage et, à telle époque, tel indi
vidu ;
• que, dans un plan, si D l est perpendiculaire à D2, et D2 à D3, et D3 à D4,
alors Dl est parallèle à D3, et D2 à D4, et D l est perpendiculaire à D4.
5.2.7 Normalisation
Normalisation du vocabulaire
Pour une bonne représentation, il importera de normaliser un vocabulaire interne
univoque, suffisamment réduit (pour faciliter l'unification) et suffisamment riche
(pour ne pas appauvrir l'application), effort portant sur les concepts et sur les rela
tions.
On peut considérer comme extrême la proposition de Schank de ramener le
système verbal de l'anglais à 1 4 verbes ( 1 2 connus et 2 artificiels), de nombreux
autres verbes engendrant à eux seuls un sous-réseau, mais on doit s'en inspirer pour
une base raisonnable, loin des milliers de verbes d'une langue naturelle.
Normalisation du réseau
Des textes équivalents pourraient mener à des réseaux différents (et donc à des résul
tats variables) selon leur degré de redondance et d'explicitations des connaissances
liées au contexte.
Pour unifier ces cas, le plus simple est d'ôter des réseaux sémantiques toutes les
relations déductibles de celles qui sont conservées, en enrichissant le mécanisme
d'unification des compositions de relations correspondantes (Kazar 96).
Cette conven
8-- � �
tion vise à démêler arbre
les situations com
support support
plexes en les hiérar
chisant.
Soit à représen
ter un arbre durant couronne
8- �
gnant une vista re été
groupant 4 espaces
dont chacun repré support couleu1� e
sente l'état de la
couronne durant la
E)- �
automne
saison correspon
dante (fig. 5 .7). support - coulem �
Fig. 5.7 Représentation par un réseau sémantique partitionné de « l 'arbre durant les saisons ».
Fig. 5.8 Réseau sémantique partitionné pour « Jean dit que Pierre est plus âgé que Marie ».
90 A-Approche algorithmique
5. 7 CARTES COGNITIVES
5. 7 . 1 Au sens strict
Ce concept de cal'te cognitive, attribué à E. Tolman ( 1 948), désigne la représentation
mentale qu'un individu se fait de l 'organisation de l 'espace où il se trouve.
Réseaux Sémantiques 91
Cette représentation mentale implique que l ' individu est capable d'inférer les
relations, distances et directions liant différents points de l 'espace sans en avoir eu
une expérience directe. Ainsi l ' individu peut-il atteindre un but en passant par un
chemin qu'il n'a jamais emprunté auparavant.
Des expériences de psychologie cognitive ont montré que cette carte cognitive
est construite grâce à la perception visuelle.
5.7.2 Métaphoriques
Par analogie, on parle de carte cognitive dans des domaines non spatiaux dont on se
donne une image spatiale, comme la résolution de problèmes, les relations parenta
les, les analyses statistiques . . .
Dans ces domaines, la navigation dans la carte cognitive figure les migrations
qu'on est amené à faire d'un concept à l 'autre par association d' idées (cf mode
d'emploi de certains moteurs de recherche).
Cette notion de carte cognitive est donc utile aussi bien pour faciliter la naviga
tion dans un thésaurus, une fond documentaire que pour faciliter la conception et/ou
la planification d'activités didactiques (Saadani 2000).
5.8 EXERCICES
5.8.2 Représentation 1
Montrer que l'on peut gérer un réseau sémantique en utilisant une table de chaînes
lexique[*] et une table de triplets d'entiers /ait[*, 3} , avec la convention :
fait[n, *J =(k, l, m) H (lexique[k}, lexique[l}, lexique[m}) est le nième fait.
EXEMPLE.
Soit (Jules, aime, Agathe) le 1 7e fait, lexique[45]= « jules », lexique[37]= « aime »,
lexique[ 1 17]= « Agathe » ; alors (Jules aime Agathe) a pour représentation :
fait[l 7, *] = (45 , 37, 1 1 7) . •
Compléter la convention pour les « noms cachés ». Expliquer le principe d'une
interrogation. Montrer que l ' on peut ainsi traiter même des questions comme :
• « Qui aime Agathe ? »
• « Quelles sont les relations de Jules avec Agathe ? », avec par exemple une
réponse multiple comme « Jules aime Agathe » et « Jules agace Agathe ».
92 A-Approche algorithmique
5.8.3 Représentation 2
Montrer que l'on peut gérer un réseau sémantique en utilisant une liste L de listes
associatives, telle que si (Jules aime Agathe) est un fait, alors L comporte une sous
Iiste
assoc(L, 'Jules)= (Jules . . . (aime Agathe) . . . ).
Etudier le principe d'une interrogation. Montrer que l ' on peut ainsi traiter des
questions comme « Jules aime qui ? ». Précaution à prendre pour qu'une question
comme « Quelles sont les relations de Jules avec Agathe ? » puisse entraîner une
réponse multiple comme « Jules aime Agathe » et « Jules agace Agathe ».
Montrer que pour traiter une question comme « Qui aime Agathe ? », la repré
sentation de (Jules aime Agathe) doit se dédoubler avec un triplet inverse, L devant
maintenant comporter une liste (Agathe . . . (inv:aime Jules) . . . ).
5.8.4 Etre
On considère des phrases comme « Jean est boulanger », « Un boulanger est un
artisan » . . . Le verbe « être » a-t-il le même sens dans les deux cas ? Peut-il être codé
par une même relation « estl » ou doit-on distinguer une relation
« est lie/ membreDe » et une relation « sorteDe I ç; » ? Impact en termes de silence
et de bruit. Revoir la question en rapport avec d'autres langues.
5.8.5 Kozon
On se pose la question d'un logiciel de dialogue en langue naturelle, formé d'un
analyseur transformant les phrases lues en requêtes normalisées, et d'un exécutif
gérant un réseau sémantique selon ces requêtes.
Comment ce logiciel doit-il réagir lorsqu'il reçoit :
• une phrase déclarative comme « Jean est boulanger », « Jean a 37 ans », « un
boulanger est un artisan » ?
• une phrase interrogative comme « Qui est Jean ? » ?
• une phrase impérative comme « lister les artisans » ?
Comment prendre en compte l 'héritage dans les interrogations ?
L' analyseur doit-il réagir différemment aux phrases :
• « un boulanger est un artisan », « chaque boulanger est un artisan », « tout
boulanger est un artisan », « les boulangers sont des artisans », « tous les bou
langers sont des artisans » ?
• « lister les artisans», « donner la liste des artisans », « qui est artisan ? »,
« quels sont les artisans ? » ?
Comment ce système doit-il traiter les phrases comme « donner la liste des arti
sans de plus de 40 ans » ?
Pour 5.8.1
Oui, du général (vertébré) au particulier (oiseau/mammifère) puis (autruche / humain
/ rat).
Non, mais nous avons encore une hiérarchie (il n'y a pas de circuit).
Si l 'homme est un mammifère bipède, l 'ornithorynque est à placer comme
mammifère ovipare : il fait exception, les mammifères étant en principe vivipares. Si
on étend le réseau aux poissons, on aura un problème similaire avec l 'exocet, ou
poisson volant.
Pour 5.8.2
Cette représentation est plus facilement gérable par des langages à table, et serait
utilisable en Basic ou en Fortran par exemple.
Pour 5.8.3
Cette représentation est plus facilement gérable par des langages à liste, et serait
utilisable en Lisp, Scheme, Logo, Cami par exemple.
Pour 5.8.4
Cette ambiguïté du verbe être a été étudiée notamment par Lesniewski et par Grize.
Pour 5.8.5
L' idée est que l 'analyseur transforme les phrases en requêtes que l 'exécutif exécute.
Ces requêtes devraient être de trois types :
• assertions : + ( concept! relation concept2), issues des phrases déclaratives ;
• demandes : ?(X Y Z) pouvant comporter 1 , 2 ou 3 variables, issues de ques
tions ou bien d'ordres comme « lister/donner/visualiser »
• retraits : -(concept! relation concept2), issus d'ordres de maintenance comme
« ôter/ enlever/ supprimer . . . », à ne pas confondre avec une simple négation.
La « liste des artisans » peut être réduite (requête simple ?(X est! artisan)) ou
étendue par héritage par
?(X est!* artisan) = ?(X est! Y,l E T ?(Y = artisan) O U ?(Y est!* artisan).
Pour 5.8.6
Constituer un réseau partitionné, sur la base d'un espace par pays. Aller de A à B se
présente alors comme un raffinement du plan consistant à aller de PA à P8.
5 .10 RÉFÉRENCES
Eco U ., 1 988, Sémiotique et philosophie du langage, PUF, Paris ; traduction de Eco
U., 1 984, Semiotica efilosofia del langagio, Einaudi, Turin (1).
Fadhil A., Haarslev V., 2005, GLOO: a graphical query langage for OWL
ontologies, First OWL Experiences and Directions Workshop, Galway.
94 A-Approche algorithmique
Karp P.D., Lowrance J.D. , Strat T.M., Wilkins D.E., 1 994, The Grasper-CL
Management system, Lisp and Symbolic Computation, n°5 , Kluwer, Boston
(USA) , pp. 245-273 .
Kazar O., 1996, Conception et réalisation d 'un modèle de réseau sémantique,
Mémoire de magister, Université de Constantine (DZ) , pp. 6-45.
Keenan J.M., 1982-200 1 , Memcog, Semantic Memory , Denver University (USA).
Nicolle A., Beust P., Perlerin V., 2002, Un analogue de la mémoire pour un agent
logiciel interactif, In Cognito (F).
Saadani L. & Bertrand-Gastaldy S., 2000, Cartes conceptuelles et thésaurus: essai
de comparaison entre deux modèles de représentation issu de diff érentes
traditions disciplinaires, in Les Dimensions d'une Science de l'Information
Globale, Actes du XXVIII• Congrès annuel de I 'Association canadienne des
sciences de l ' information.
Tesnière L., 1959, Eléments de syntaxe structurale, Librairie Klincksieck, Paris,
rééd. 1 98 5 .
Vaillant P., 1 997, PVI : Prothèse Vocale Intelligente, ch. i n Interactions entre
modalités sémiotiques: de l 'icône à la langue, thèse, Université Paris XI
(Orsay).
CHAPITRE 6
NOTIONS D'APPRENTISSAGE
6.1 INTRODUCTION
En vue d'écrire des programmes intelligents, ne faudrait-il pas préférer à des pro
grammes qui savent - dotés d'une intelligence a priori - des programmes qui ap
prennent, programmes qui, capitalisant sur l 'expérience, manifesteraient une intelli
gence croissante au fil des exécutions ? On pourrait peut être ainsi esquiver un im
portant effort de conception, qui se révèle souvent trop limité pour des utilisateurs
dont le niveau d'exigence est souvent lui-même croissant.
La psychologie cognitive pose depuis longtemps cette question, alors même que
la théorie classique de l ' algorithmie, basée sur la notion d' invariance de comporte
ment des algorithmes, rendait cette question taboue, au nom de la reproductibilité des
tests, de la sécurité de fonctionnement. . .
Selon H. Simon : « L'apprentissage dans un système est indiqué par les chan
gements qu'il subit. Ces changements sont adaptatifs dans le sens où ils rendent
possible au système de réaliser une même tâche, ou des tâches tirées d'une même
population, d'une façon plus efficace et plus efficiente la prochaine fois qu'elle sera
réalisée ».
Ce chapitre voudrait montrer que la chose est possible à un premier niveau,
même si récemment des dispositifs plus avancés ont été utilisés (chap. 1 6 ou
§ 28.3 .2, 28.4.3, sect. 32. l )
\_ ________________________ _
I'[,]
Evolution
De partie en partie, on peut suivre l'évolution de l 'apprentissage au moyen d'un
vidage symbolique de la table I, représentant l 'état des connaissances, puis après
quelques parties par l 'affichage de l 'évolution du rapport parties gagnées/parties
jouées pour le programme. Ce rapport doit tendre vers une asymptote définie par les
conditions de début de partie (N tiré au hasard ? qui commence ?).
Le système apprend à jouer « par la fin », et remonte lentement, de partie en
partie, vers le milieu puis le début de jeu. ·
Si les bonifications sont importantes et les pénalisations faibles, on peut
s 'attendre à un comportement brillant mais peu sûr. Inversement, si les bonifications
sont faibles et les pénalités impotiantes, on peut s 'attendre à un jeu fiable mais peu
inspiré.
Ce genre de programme s 'adapte bien à l ' introduction de finales perdantes ou
de finales nulles ; dans ce dernier cas, le style de jeu final dépendra du type de rétri
bution (bonification ou pénalisation) associé aux parties nulles.
Comportement général
On souhaite faire évoluer de tels programmes d'un fonctionnement balbutiant vers
un fonctionnement idéal présumé unique.
Dans les situations réelles, où l'environnement est moins stable, et l 'existence
d'un fonctionnement optimal stationnaire non garantie, un système apprenant sera :
• adaptatif voire instable s'il privilégie les faits nouveaux,
• peu adaptatif voire rigide si les nouveautés altèrent trop peu ses certitudes,
• parfois à contre-pied d'un environnement trop changeant.
Notion d'apprentissage 99
Cependant, cet apprentissage revient toujours à apprendre par cœur ce qui doit
être fait (ou évité) dans une situation précise déjà rencontrée; il s 'accommode mal
d'utilisations variées et/ou d'un espace d'état trop riche.
6.4.2 Classifieurs
On s ' intéresse au classement automatique de divers objets; par référence à une liste
d'attributs fixée, un objet x est spécifié par un descripteur, liste de x; valant soit 0 soit
l selon l 'absence ou à la présence pour l 'objet de l 'attribut a; de même rang.
Disposant de N obj ets, pour lesquels on possède le descripteur et le nom de la
classe associée, on se propose de bâtir un classifieur, trieur capable d'associer en
suite à tout nouveau descripteur, la classe de l 'objet correspondant.
Un premier classifieur (le Perceptron) a été défini par Rosenblatt en 1 958. Il
suppose qu 'un objet x appartient à une classe Ci si une somme pondérée des compo
santes x; de son descripteur est strictement positive, pour un jeu de poids caractéristi
que de la classe. Soit :
xeCj l:wij·x; >0
f-7
Exploitation
A titre expérimental, l 'apprentissage peut se confondre avec l 'exploitation, et porter
sur les N objets disponibles. Si tout va bien, la matrice W devrait se stabiliser, et les
classements erronés se raréfier progressivement; mais cela supposera toujours un
utilisateur qualifié.
Le plus souvent, on distinguera un premier groupe d'objets destiné à
l'apprentissage, suivi d'une utilisation du classifieur sans précaution ni qualification
particulière. Une utilisation sereine supposera en fait, entre apprentissage et exploita
tion, un « jeu de test », second groupe d'objets servant à valider l 'apprentissage.
1 00 A-Approche algorithmique
Validation
Un système de classement sera dit :
• correct, si les exemples proposés sont classés correctement;
• complet, s'il rend compte de tous les exemples;
• consistant, s ' il n'y a pas d'erreur de classement.
La complétude n'est possible que si l 'ensemble des classes recouvre l'ensemble
des objets possibles, afin qu'à chaque objet corresponde une classe au moins - quitte
à créer une classe des inclassables. D'autre part, le classement d'un objet est unique
(sans ambiguïté) ssi les classes sont disj ointes.
Discussion
Cette approche peut donner deux types d'erreurs :
• Au départ, le système peut « battre la campagne » s'il n'a pas encore traité
assez d'échantillons, et/ou si l 'heuristique d'ajustement est inadéquate.
• Par la suite, un taux d'erreur subsiste
- si l 'équivalence de classification utilisée n'est pas parfaite - il s'agit alors
d'un biais de modélisation 18,
- s'il y a des erreurs d'étiquetage pour certains échantillons.
On parle de surapprentissage lorsque, paradoxalement, les deux dernières er
reurs devenant prédominantes, l 'erreur totale ne décroît plus avec de nouveaux
échantillons. C'est le cas si les échantillons ayant servi à l 'apprentissage ne sont pas
représentatifs : par une adaptation trop étroite, le système perd alors en exactitude (et
en généralité) ce qu'il gagne en précision .
. D 'autre part, cette approche n'est applicable simplement que si les composantes
x; forment un système redondant facilitant la séparation des classes. Sinon, chaque
classe doit être considérée comme un polyèdre dans l 'espace des critères : les règles
de décision linéaires du type évoqué ne servent plus qu'à positionner l 'objet x par
rapport à un hyperplan-frontière, et c'est la combinaison logique de telles conditions
(réalisée par une nouvelle somme pondérée) qui décide alors de la classe.
6.4.3 Intérêt
De tels classifieurs sont fréquemment utiles :
• en informatique documentaire (Beney 2008),
• pour le classement de clients ou prospects en vue d'opérations publicitaires
et/ou commerciales,
• en olfaction artificielle (identification automatique d'odeurs) . . .
18
Que l'on peut corriger par exemple en passant d'un perceptron à un réseau neuronal multi-couches,
correspondant à une définition des classes plus ambitieuse, pouvant utiliser des fonctions de décision
non linéaires.
Notion d'apprentissage 101
6.5.1 Présentation
Nous avons vu qu'un apprentissage permet l 'adaptation d'un classifieur à un système
de classes disjointes supposées bien définies, par l 'adaptation de règles de décision
décidant de l 'appartenance de l 'objet sous examen.
Au-delà, des cas plus difficiles peuvent être abordés, où l 'exploitation d 'hypo
thèses vraisemblables dans des situations nouvelles sera consolidée par apprentis
sage, afin de rendre plus sûrs ces raisonnements empiriques.
Il s'agit alors de bâtir par induction les règles de décision utiles.
tion actuelle de C,
• la définition de chaque autre classe G doit être réduite si x appartient à un
NOTES
• Les extensions de définitions (2>2 ' , 3> 3 '> 3 ' ' , . . . ) constituent des formes
d' induction ayant pour but de privilégier la simplicité, quitte à être contredites
)
(cas 4).
• Elles correspondent aux inductions
visant à remplacer des règles de déci si A & B & C alors Z
sion similaires menant à une même si A & B & D alors Z � si A & B alors Z
conclusion par une règle généralisa si A & B & E alors Z
.
trice, comme dans l 'exemple ci
contre (Kodratoff 1 986).
• Des erreurs résiduelles systématiques peuvent découler d'un système de blocs
inadéquats, basés par exemple sur des attributs trop peu discriminants.
1 02 A-Approche algorithmique
a a a a a
>
a a a
2 2' 3
a a a a a a a
a a a .. a
Approche simple
Dans une première approche, la collection de cas n'est pas hiérarchisée : la collection
des cas connus correspond à un ensemble de classes disjointes, regroupant des cas
· similaires. Trouver la classe de C, c'est alors trouver le genre de solution à lui appli
quer. Toutefois, ces classes ne sont pas définies en elles-mêmes ou par leurs frontiè
res, mais par un ou plusieurs de leurs membres, représentatifs ou non. Le classement
est alors réalisé sur la base de proximités, le cas le plus proche étant présumé le plus
similaire.
Si l ' analogie permet la construction d'une solution adéquate, le système est
renforcé par l 'enregistrement du couple (S, C), extension implicite de la classe de C;.
Si l 'analogie provoque une construction de S par analogie avec Si qui échoue du
fait d ' inconsistances, il s'agit alors d'un échec interne, et on passe à une analogie
C ;:::; C k moins vraisemblable a priori ; si celle-ci se révèle productive, le couple (S, C)
enregistré étendra cette fois la classe de Ck.
Le cas le plus délicat est celui où la construction de S par analogie avec S; réus
sit, la solution obtenue se révélant à l'usage sans intérêt pratique : il faut alors corri
ger S jusqu'à obtenir une solution S' opérationnelle, telle que (C, S') mérite d'être
mémorisé.
Approche hiérarchisée
L'approche précédente suppose trop souvent un domaine étroit et une mémorisation
considérable - issue d'un long apprentissage. On peut améliorer la situation en carac-
Notion d'apprentissage 1 03
térisant les cas similaires à solutions similaires comme formant une classe définie par
un couple générique (cas, solution), noté par exemple (f, I:). Si C apparaît comme un
cas particulier de r, on peut alors supposer que S(C) est une spécialisation similaire
de E. Il n'est plus alors utile de conserver tous les cas particuliers de r.
La richesse du procédé vient de sa faculté de faire surgir les cas génériques
comme abstraction des cas connus. Ce qui suppose, outre un apprentissage du type
précédent :
• une capacité d'induction/abstraction pour dégager les cas génériques, puis
éventuellement d'autres cas plus génériques les regroupant,
• en cas de rejet d'une solution construite, une capacité d'analyse du niveau de
responsabilité, pour une reprise ou une restructuration minimale,
• une éventuelle capacité d'allègement de ce qui a été mémorisé.
6.6 CONCLUSIONS
Jeux
Les jeux d'échecs ont été une grande source d ' inspiration, avec des succès variables.
Pitrat a développé un système de jeu pour les échecs doté de capacités
d'apprentissage, et pour le langage de représentation de connaissances employé, un
compilateur produisant du C, compilateur lui-même doté de capacités d'appren
tissage. Le résultat devint à la longue très impressionnant, du fait d'une compilation
de plus en plus efficace d'un jeu qui s'était lui-même profondément amélioré (Pitrat
1 990).
Acquisition de connaissances
L'apprentissage a été mis très tôt au service de la gestion des connaissances.
Dès 1 965, le système Dendral (spectrométrie de masse), ancêtre des systèmes
experts, se proposait d'idendifier des molécules sur la base de leur masse molécu
laire, des masses atomiques et des valences des éléments, et d'exceptions connues.
Peu efficace aux masses élevées, il fut complété par Meta-Dendral ( 1 972), système
d'acquisition de connaissances par apprentissage qui explore des possibilités et en
gendre des règles expliquant les données de spectroscopie utilisées, ou étend les
règles et contraintes utilisées par Dendral.
En 1 979, le système Teiresias, de Davis, permit de mettre en évidence des er
reurs ou des lacunes dans une base de connaissances de Mycin. Avec Teiresias,
1 04 A-Approche algorithmique
Bilan
L'apprentissage peut être lent dans son évolution du fait :
• d'un environnement peu coopératif, médiocre ou instable,
• d'une capacité d'exploitation insuffisante des informations reçues,
• d'une capacité d'anticipation insuffisante dans des situations nouvelles.
L'apprentissage peut être lent d'utilisation s'il tend à mobiliser un excédent de
connaissances concrètes qu'il ne sait pas suffisamment fédérer et élaguer.
L'apprentissage peut enfin être globalement incertain du fait :
• d'un environnement peu coopératif, médiocre ou instable,
• d'une incapacité épistémologique à découvrir les risques de régressions de
l ' environnement comme de lui-même.
Comme on le verra (chap. 28), l 'apprentissage permet de faire d'autant mieux
face au manque de connaissances qu'il dispose de méta-connaisances puissantes lui
faisant retirer un maximum de chaque expérience.
6.7 EXERCICES
6.7.4 Pronostics
On considère un loto sportif, dont les paris sont ainsi organisés : si l 'équipe A ren
contre l 'équipe B, le parieur marque :
• 1 , s'il parie sur une victoire à domicile (de l 'équipe qui reçoit) ;
6.8 INDICATIONS
1 1 2 3 1
1 ----'---+ o; 3 ----'---+ 2; 4 -=-n; s -=-n; 7 ----'---+ 6 . . .
état 2 3 4 5 6 7
trait
1 + +
2
3
4
Pour 6.7.5
(Cornuéjols 2002)
6.9 RÉFÉRENCES
Beney J., 2008, Classification superv1see de documents, coll. Traitement de
! 'Information, Hermès/Lavoisier, Paris.
Buchanan B., Sutherland G., Feigenbaum E., 1 969, Heuristics Dendral : A program
for generating explanatory hypotheses in organic chemistry. Machine Intel
ligence.
Cornuéjols A., Miclet L., Kodratoff Y., 2002, Apprentissage artificiel, concepts et
A lgorithmes, Eyrolles, Paris.
Dietterich, T. G., 1 986, Learning at the knowledge level, Machine Learning, 1 (3 ,
pp. 287-3 1 6.
Fuchs B., 1 997, Représentation des Connaissance pour le Raisonnement à partir de
cas : le système Rocade, thèse d'informatique, Université Claude Bernard,
Lyon, 1 97 p.
Garcia F., Apprentissage par renforcement : Introduction, 52 p., [Link]
Kodratoff Y., 1 986, Leçons d 'apprentissage symbolique, Cepadues, Toulouse.
Notion d'apprentissage 1 09
7. 1 PRINCIPES DE SCHEME
Il n'y a qu'unejigure algorithmique : l 'évaluation d'expression.
Les données sont des arbres binaires, réduits à des atomes (chaîne, symbole,
entier, rationnel, flottant), ou formés d'une paire d'arbres.
Hormis les constantes et variables, l 'écriture des expressions se ramène à des
appels de fonction, y compris pour les opérateurs usuels. Tout appel de fonction f(x,
y) se code (fx y). De même x + y se code (+ x y), et x + y + z se code (+ x y z).
Cette notation, dite « notation préfixée de Cambridge » accepte des opérateurs à
arité 1 9 variable en contrepartie des parenthèses exigées. Des primitives, soumises
aussi à la notation fonctionnelle, permettent de créer des variables globales et des
fonctions ; pour ces dernières, le concept d'expression conditionnelle rend la récursi
vité possible, et par là toute l 'algorithmie.
1
9 Nombre d'arguments.
1 14 A2 - Eléments pratiques : Scheme
Le symbole lu
7.4.1 Nombres
Les représentations des nombres sont exactes (entiers, rationnels) ou approchées
(flottants, représentation dite inexacte en Scheme). Les opérations sur 3 arguments et
plus se font de gauche à droite
> (- 1 2 3)
-4
Entiers
Suite de chiffres décimaux, éventuellement signée, de type fixnum jusqu'à
1 .073 .74 1 .823, de type bignum au-delà.
> (- 8 -5 -7 )
20
Rationnels
Paire d'entiers séparés par une barre « / ». Il s ' agit de nombres exacts, de type «frac
tion », dont la forme normale est la fraction irréductible.
EXEMPLES
> 3/11
3/1 1
> (/ 3 11) opération
3/11 résultat rationnel exact
> (+ 3 / 1 0 3/ 8 )
27/40
> (+ 3/10 3/8 3/40)
3/4 ; réduction automatique d e 3 0 / 4 0
; ; un robinet remplit la piscine en 3 heures , un autre en 5h
; ; combien faut-il de temps en ouvrant les deux ?
,, en heures :
> ( / 1 (+ 1 / 3 1 / 5 ) )
15/8
; ; e n minutes
(/ 60 (+ 1 / 3 1 / 5 ) ) )
225/2
; ; soit 1 1 2mn30s ou lh52mn3 0 s . •
Flottants
Les rationnels inexacts sont de fait des nombres virgule flottante double précision, dits
de type flonum. Ils comprennent : les constantes infinies « +inf 0 » et « -inf.O » , et
les écritures avec partie décimale fractionnaire et/ou facteur de cadrage.
> (/ 4 5 . 0)
0.8
> (/ 4 . 0 5)
0.8
> fo1 0 . 00e5
1000000
( le préfixe #e impose une représentation exacte, donc i c i entière
#i imposerait une représentation inexacte de type flonum) .
>10 . 00e5
1000000 . 0
7.4.2 Booléens
Ils sont notés #t pour true (vrai) et #fpourfalse (faux).
(boo/ean? obj ) rend #t si obj est soit #t soit #f, et rend #f sinon.
(boolean? # t ) � #t (boolean ? #f) � #t
(boolean? 0 ) � #f
et de même :
( real ? 3 ) � #t ( real ? #elel O ) � #t
( rational? 6 / 1 0 ) � #t ( integer? 8 / 5 ) � #f
( integer? 3 . 0 ) � #t ( integer? 8 / 4 ) � #t
En réalité, l a plupart des usages (if, cond, and, or. . . ) considèrent tij" comme tel,
et assimilent toute autre valeur à #t.
(not obj) rend #t si obj est faux, #/sinon.
Ainsi :
( not # t ) � #f ( not # f ) � #t ( not 3 ) � # f
(and b l b 2 . . . ) est évalué de gauche à droite, e t a pour valeur l a première valeur #f
rencontrée - l 'évaluation est alors abandonnée - et sinon la valeur du dernier terme.
( and ( 2 2 )
= (> 2 1 ) ) � #t ( and (= 2 2) (< 2 1 ) ) � #f
( and 1 2 3 ) � 3
(or b l b2 . . . ) est évalué de gauche à droite, et a pour valeur la première valeur #t
rencontrée - l 'évaluation est alors abandonnée - et, sinon, la valeur du dernier terme.
(or ( 2 2 ) ( > 2 1 ) )
= � #t (or ( = 2 2 ) ( < 2 1 ) ) � #t
( or # f # f # f ) � #f (or # f # f 1 4 3 ) � 143
7.4.3 Caractères
Notés #\a, #\b, #\c . . . c'est-à-dire par eux-mêmes pour les caractères usuels, et via
leur nom pour les caractères de service, comme dans :
# \backspace # \ l inefeed #\newline # \nul
# \page # \ return # \ rubout # \space
ou encore par leur code octal, de 0008 à 3778 (resp. 0 à 255) , soit par exemple #\o40
pour un blanc (32 1 0).
7.4.4 Chaînes
Suite de caractères entre doubles apostrophes. On peut également en construire à
l ' aide des fonctions de conversion : number->string, symbol->string, list->string . . .
7.4.5 Symboles
On appelle symbole une suite de caractères constituant sa propre valeur littérale, par
opposition aux noms de variables ou de fonction. De façon générale, on accepte
comme symbole toute séquence de lettres, chiffres et caractères spéciaux pris dans
Bases du langage Scheme 1 17
Construction
Par l 'opérateur cons, à 2 arguments exclusivement.
> (abra . cadabra )
undef ined idenfier : abra
> ' ( abra . cadabra ) , , paire constante
(abra . cadabra )
> ( cons ' abra 'acadabra ) , , cons , constructeur d' une paire
(abra . cadabra )
Extraction
car rend la partie gauche d'une paire, cdr la partie droite
> ( car ( cons 'a 'b) )
a
> ( cdr ( cons 'a 'b) )
b
7.5.2 Arbres
Les arbres binaires généralisent les paires pointées : il s'agit
• soit d'atomes : arbre vide, noté nul/, ou donnée élémentaire ;
• soit de paires dont chacun des éléments gauche et droit est un arbre.
1 18 A2 - Eléments pratiques : Scheme
EXEMPLE
> ' ( ( a . b) ( c . d) )
( (a . b ) ( c . d) ) en fait, ( ( a b) c d) voir les listes
> ( cons ' ( a . b ) ' ( c d) )
( (a . b) . (c d) ) en fait , ( ( a b) c d) voi r les li stes
> ( car ( cdr ( cons ' ( a . b) ' ( c . d) ) ) )
c
•
753 . . Listes
On appelle liste une notation allégée des arbres, qui sont peu exploités comme ar
bres binaires p ius ou moins équilibrés, mais souvent comme arbres étendus à droite.
L' idée centrale est de noter maintenant (a b c) ce qui devrait au sens du paragra
phe précédent se noter (a . (b . (c . null))), la liste vide devenant implicite lorsqu'elle
j oue un rôle de butoir à droite.
Alors
• (a) signifie (a . null) et réagit en tant que tel aux car et cdr ;
• (le chat est sur le banc) remplace avantageusement
- la notation de principe (le .(chat .(est .(sur . (le . (banc. null)))))
- la chaîne « le chat est sur le banc », dont les mots ne sont pas isolés.
Construction
On peut évidemment utiliser cons, mais aussi list qui le généralise en ajoutant un
butoir nul!, et append qui allonge une liste existante, ou encore des conversions
type->list.
> ( cons 'a ( cons 'b ( cons 'c nul l ) ) )
( l ist ' a 'b ' c )
> ( list ' a 'b ' c )
( list ' a 'b ' c )
> ( l ist 1 2 3 4 )
( list 1 2 3 4 )
> ( l ist (list ' a ' b ' c ) ( l ist ' x ' y ) )
( list ( l ist 'a 'b ' c ) ( list 'x 'y) )
> ( append ( l ist ' a 'b ' c ) ( list 'x 'y) )
( list 'a 'b ' c 'x 'y)
> ( s tring->list "abcxy" )
( list #\a # \b # \ c #\x #\y)
Extracteurs physiques
(list-tail liste k) retourne la sous-liste obtenue en omettant les k premiers éléments
de la liste ; il y a erreur s'il y a moins de k éléments dans la liste.
De plus,
(list-ref liste k) = (car (list-tail liste k)
Cette écriture retourne le k-ième élément de la liste, numérotés 0, 1 , . . Ainsi
. :
Extracteur logique
(member obj Iist) est un quasi-prédicat qui retourne la première sous-liste de la
liste commençant par obj. Si obj n'existe pas dans la liste, le résultat est #f (faux), et
non la liste vide.
EXEMPLE
> (member 'a ' ( w x c v a z e r t y) )
(a z e r t y)
> (member ' ( a) ' (w x c a b z ( a z) c q) )
H
> (member ' ( a ) ' (x c ( a ) v b n ) )
( ( a) v b n ) •
Observateur
length rend le nombre d'éléments d'une liste, compté au premier niveau.
( length ' (a b c d) ) � 4
( length ( l ist (+ 2 5 ) ( * 3 9 ) ) ) � ( length ( list 7 2 7 ) ) � 2
( length ' ( a (b ( c d e ) ) f ) ) � 3
7.6.3 Fonctions
Forme cond
L'écriture
(cond (cond l exprl ) (cond2 expr2) . . . (else expm) )
signifie :
si cond l alors exprl sinonSi cond2 alors expr2 sinonS i . . . sinon expm.
Comme il s'agit d'une expression, celle-ci est a priori indéfinie en l 'absence de
branche else.
En fait chaque clause (condition expression) peut être de la forme (condition e 1
e2 . . . en ). Dans ce cas, si 'condition' est vrai, e 1 , e2, . . . en sont évaluées successive
ment, la valeur de en étant la valeur finalement rendue.
De plus, une expression cond est utilisable dès que ses conditions sont définies
de la première jusqu'au cas utile inclus. En matière de prototypage, ceci facilite les
essais d'applications incomplètes . . . Mais pour stabiliser une application, cela mon
tre qu'un jeu d'essais sera facilement incomplet.
Forme if
(if condition expressionSiVrai expressionSiFaux ) est une forme brève pour :
(cond (condition expressionSiVrai) (else expressionSiFaux) ).
La forme if exige des expressions pures, et n'accepte pas de séquence en tant
que telle. Pour tourner cette contrainte,
(cond (condition e l e2 e3) (else e4 e5 e6) )
devrait être remplacée par
1 22 A2 - Eléments pratiques : Scheme
7.6.4 Polymorphisme
On peut écrire des fonctions réagissant en fonction de la nature des arguments. Ainsi
la fonction :
( define double ( lambda ( chose)
( cond ( ( nul l ? chose ) ( ) )
( ( number? chose ) ( * 2 chose ) )
( else ( l ist chose chose ) )
)))
donnera à l 'exécution
> (double ( ) )
()
> (double 4 ) ; ; second cas
8
> (double ' a ) ; ; tiers cas
(a a)
> (double ' (b l a) )
( (b l a) (b l a) )
> (double " aha" )
( " aha " "aha" )
7. 7 RÉCURSIVITÉ
tion de la fonction.
Une fonction récursive est valide si les cas de régression sont tels qu'un appel
quelconque se ramène toujours en un nombre fini d 'étapes à un cas de la plage
d'arrêt : on dit alors la récursivité convergente. Sinon, la fonction n'est que partiel
lement définie.
Factorielle
(define fact ( lambda ( n )
( cond ( (< n 0 ) " fact l ' argwnent doit être positi f " )
; ; o n blinde
( (= n 0 ) 1 ) ;; 0 ! = 1
( else ( * n ( fact ( - n 1 ) ) ) )
; ; sinon fact ( n ) = n* fact ( n- 1 )
)))
> ( fact 2 4 )
6204 4 8 4 0 1 7 3 32 3 9 4 3 93 6 0 0 0 0
L e devin
"choisissez un nombre entre 0 et 1 0 0 0 "
" j e vais essayer de le deviner en 1 0 questions "
(define question ( lambda ( nwnero inf sup)
; ; (display ( list inf sup ) )
( cond ( ( < inf sup ) (bis section nwnero inf
( quotient ( + inf sup ) 2) sup) )
( ( = inf sup) (display ( list " j ' ai trouvé ! c ' est" inf) ) )
( else (display ( list ' Q nwnero "erreur · "
inf " > " sup ) ) ) ) ) )
(define bissection ( lambda ( nwnero inf milieu sup)
, , si le nombre est dans [ inf sup ] , est-il dans [ inf milieu- 1 ]
, , ou dans [milieu sup ] ? ?
( cond ( (< inf mil ieu )
(display ( list 'Q nwnero
" : le nombre est-il plus grand ou égal à" milieu ) )
[ i f ( eq? ( read) ' oui )
( question ( + nwnero 1 ) mi lieu sup)
( question ( + nwnero 1) inf ( - mil ieu 1 ) ) ) ]
(else ; ; inf = milieu = sup- 1 , une dernière question
(display ( list ' Q nwnero " : le nombre est-il égal à" milieu ) )
( i f ( eq? ( read) ' oui ) ( question (+ nwnero 1 ) milieu mi lieu)
( question ( + nwnero 1) sup sup) ) )
)))
(define j eu ( lambda ( ) ( question 1 0 1 0 0 0 ) ) )
( j eu )
@Xecute !I
Welcome...
"choisissez un nombre entre 0 et 1 0 0 0 " ; ; j ' ai choisi 7 7 7
1 24 A2 - Eléments pratiques : Scheme
))
, , test pour savoir si un arbre est réduit à un atome :
( define feui lle? ( lambda ( chose) ( not (pair? chose ) ) ) )
@Xecute !I
Bienvenue ...
> ( compte ( ) )
0
> ( compte ' a )
1
> ( compte ' ( a b c ) )
3
Prédicats Signification
(zero? z) (= 0 z)
(positive? x) (< 0 x)
(negative? x) (> 0 x)
(odd? n) n est-il impair ?
(even? n) n est-il pair ?
(< x y z . . . ) (and (< x y)(< y z) . . . )
(= X y Z . . . ) (and (= x y)(= y z) . . . )
(> X y z) (and (> x y)(> y z) . . . )
(<= X y z)
...
(>= X y z)
...
Prédicats numériques
Ils sont donnés tableau 7.4.
Les comparateurs de caractère ont une forme ( chark ? car l car2), où k désigne
un comparateur d'entiers, avec pour définition :
(chark ? car l car2) = (k (char->integer car i ) (char->integer car2))
Par exemple,
(char<=? a b) - (<= (char->integer a) (char->integer b))
et symétriquement, si x et y sont des entiers de [O 255] :
(<= x y) = (char<=? (integer->char x) (integer->char y))
7 .9 ÉQUIVALENCES
Les tests eq? et equal? décident de l 'équivalence entre objets quelconques.
• eq ? est une version allégée : il décide correctement de l 'équivalence entre ob
jets élémentaires, mais utilisant si possible la comparaison entre pointeurs plu
tôt qu'entre objets, il trouvera différentes deux données identiques d 'origines
différentes ;
• equal? est une version récursive « totale », capable de comparer deux arbres
- ou structures chaînées - au risque de se faire piéger si une donnée comprend
une liste circulaire.
Exemples d'équivalences :
> ( eq? 5 5 )
#t
> ( equal ? 5 5 )
#t
> ( eq? 5 ( + 2 3 ) )
#t
> ( equal? 5 ( + 2 3 ) )
#t
> (eq? ' (a b c ) ( list ' a 'b ' c ) )
#f
> (equal ? ' (a b c ) ( list ' a ' b ' c ) )
#t
> ( de fine x ( list ' a 'b ' c ) )
> ( eq? x x)
#t
7 . 10 EXEMPLES
;; I xk · Yk = X; · Y; + L xk · Yk
k=i k=i+l
( else ( + (* ( car x) ( car y) )
(proScal ( cdr x) ( cdr y) ) ) )
l ))
IExecuteï:J
Bienvenue... .
(proscal ' ( 1 2 3 4 5 ) ' ( 5 6 7 8 ) )
; ; seuls contribuent les 4 premiers nombres de x
70
> (proscal ' ( 1 2 3 4 ) ' ( 5 6 7 8 ) )
70
Bases du langage Scheme 1 29
7.10.3 Primalité
Il s'agit de définir un test (premier? N) décidant si l 'entier N est premier.
On utilise :
• (remainder n p) qui donne le reste de la division de n par p,
( cond ( (null ? E l ) () )
( (member ( car El ) E2 ) ( diff ( cdr El ) E2 ) )
1 premier élément de El interdit si présent dans E2
1
7. 1 1 EXERCICES
7.11.4 Simplification
Réécrire la fonction f9 l définie ci-après sous la forme la plus simple possible.
(define f91 ( lambda ( n )
( cond ( ( < n 0 ) ( f91 ( + n 7 ) ) )
( ( > n 1 3 ) ( f9 1 ( - n 3 ) ) )
(else 9 1 ) )
))
7. 1 2 INDICATIONS
Pour 7.11.1
(define écrire ( lambda (phrase)
( cond ( ( null ? phrase) (display # \ . ) )
(else (display ( car phrase ) )
(display # \ space ) ( écrire ( cdr phrase) ) ) ) ) )
Comparer l 'effet de écrire à celui de display ou write.
Pour 7.11.3
En dernière analyse, les fib() sont fournis par une arborescence binaire dont chaque
nœud est un +, et chaque feuille soit un 0 soit un 1 (à 50/50) ; le nombre d 'additions
1 32 A2 - Eléments pratiques : Scheme
Pour de 7.11.5
En simulant l 'exécution de f9 1 pour divers arguments, on vérifiera que la fonction
donnée est invariante, et finalement équivalente à
(define f91 ( lambda ( n ) 9 1 ) )
de grandeur sont incertains, et les petits nombres plus probables que les grands, on
prend la moyenne géométrique (inf * sup) 'h comme valeur intermédiaire entre inf et
sup, plutôt que la moyenne arithmétique (inf + sup)/2. Ainsi, l ' intervalle [ 1 OO 1 0000]
est-il partagé en [ 1 OO 1 000] et [ l 000 1 0000] (chaque décade supposée équiprobable)
plutôt que [ 1 00 5050] et [5050 1 0000] .
• Les deux méthodes coincident sur les petits intervalles : la première est alors
plus légère.
• Plus le cadrage est fin (et donc long) plus la finition est rapide . . . un équilibre
PREMIÈRES APPLICATIONS
8. 1 COMPLÉMENTS
Trace
La mise au point des fonctions est facilitée par des affichages intermédiaires qu' on
peut obtenir par (display valeur), la valeur pouvant être une liste, comme dans :
(display (list 'nomFonction pari par2 par3)).
Pour aller à la ligne, (newline) remplace avantageusement (display #\newline).
Lorsque la mise au point est achevée, ne pas enlever ces affichages, mais les
basculer en commentaires ( ;; --) afin de faciliter les évolutions ultérieures . . . et leur
mise au point, qui doit montrer d'abord que l 'évolution est non régressive : ce qui
marchait marche encore.
Parenthèses
Il faut, surtout en fin de fonction, des lots de parenthèses. DrScheme autorise éga
lement les paires de crochets et les paires d'accolades, dont il vérifie l 'appariement.
On peut s'en servir pour clarifier, en suivant une convention fixe. Comparer :
(cond ( (eq? ( car suite ) u ) ( chiffre 1 ( cdr suite) u q d) )
( (eq? ( car suite ) q) ( chi ffre 5 ( cdr suite ) u q d) )
(else ( cons 0 suite ) )
peut se poser de rechercher dans l ' aide en ligne si elle est prédéfinie et com
ment . . . alors qu'elle a été introduite dans un recoin de votre application !
• avec la convention ci-dessus, si une fonction liste->ensemble est fautive, vous
savez immédiatement qu'elle relève de votre projet, et que vous l ' avez définie
(documentée ?) quelque part.
Une application qui n'émettrait que des erreurs en français peut alors être consi
dérée comme correctement blindée, en ce sens qu'aucune erreur ne remonte du ni
veau applicatif/francophone au niveau générique/anglophone sous-j acent avant
d'avoir été interceptée.
Noter que ces variables sont locales à la forme let, qui crée et initialise chaque
variable, exécute le traitement, puis finalement liquide ces variables. Une variable
locale est justifiée si elle est employée au moins deux fois.
Indentation d 'arbres
La fonction display affiche tout obj et licite ; mais l 'affichage à la queue-leu-leu des
éléments d'un arbre complexe peut le rendre illisible. Peut-on clarifier l'affichage de
ces arbres ?
Dans cette solution, la fonction joli sort sur une ligne les atomes ou (sous-)listes
courtes ; les (sous-)listes plus longues sont détaillées élément par élément, avec une
indentation accrue. On a par exemple :
(define j ol i ( lambda (arbre )
( sor 0 arbre ) ) )
(define sor ( lambda ( n arbre )
; ; n représente une colonne de départ
( cond ( (atome ? arbre ) ( sorligne n arbre ) ) , , atome
( (< (nb arbre ) 7 ) ( sorligne n arbre ) )
, , liste courte
; ; s inon , l iste multiligne ( 1 élément / ligne )
(else ( tab n ) (display " ( " ) ( sor 0 ( car arbre ) )
( sorsuite ( + 1 n ) ( cdr arbre ) )
( s orligne n " ) " )
))))
(define sorsui te ( lambda ( n arbre )
( cond ( ( nul l ? arbre ) ( ) )
( (atome ? arbre ) ( sorligne n arbre ) )
(else ( sor n ( car arbre ) )
( s orsuite n ( cdr arbre ) )
))))
; ; outillage réu t i l i sable ===================================
(define sorl i gne ( lambda ( n . blancs truc ) (tab n . blancs )
(display truc ) ( newline ) ) )
(define tab ( lambda ( n ) (display (make-string n # \ space ) ) ) )
; ; tabulation
(define nb ( lambda ( liste) ; ; nb d' atomes dans liste
( cond ( ( nul l ? liste) 0 )
( (atome ? liste) 1 )
(else ( + ( nb ( car liste) ) ( nb ( cdr liste) ) ) ) ) ) )
(define a tome ? ( lambda (truc) ( not (pair? truc) ) ) )
; ; variable de test =======================================
(define v . 4 0 6 ' ( (marque peugeot ) (modele 4 0 6 ) ( depuis 1 9 8 7 ) (places
4) (vitesse max 1 4 5 ) ( utac (1 9) (2 1 2 ) (3 8 ) ) ) )
Essai
Une exécution donnera :
Bienvenue dans DrScheme ...
> ( j oli V . 4 0 6 )
>
( (marque peugeot)
(modele 4 0 6 )
(depuis 1 9 8 7 )
(places 4 )
138 A2 - Eléments pratiques : Scheme
(vitesse max 1 4 5 )
( utac ; ; sous-liste complexe , détaillée sur plusieurs lignes
( 1 9)
(2 12)
(3 8)
)
)
> (j oli ' ( * (+ a b c) (+ d e f) ) )
(*
( + a b c)
( + d e f)
)
Ad hoc ou standard ?
On pourra vérifier que joli réalise sensiblement ce qu' on peut attendre de la fonction
officielle pretty-print. Si nous en ignorons l 'existence - elle est plus agréable que
fondamentale - il peut être plus rapide de construire joli que de (re)trouver pretty
print dans la documentation. On pourra également construire une fonction joli si
nous souhaitons une version modifiée de pretty-print, au-delà de l ' ajustement de ses
paramètres. Par contre, si pretty-print convient, son usage à la place de joli allègera
le code et facilitera la communication de l ' application.
( define G ' ( (a b c) (b c d) ( c d e ) (d e f) ( e f g) ( f g a) (g a b) ) )
;; graphe symétrique à 2 6 sommets de sortance 2 à 6 , inspiré du
clavier AZERTY
(define K ' ( (a z q) ( z e s q a) (e r d s z) ( r t f d e ) (t y g f r)
(y u h g t ) (u i j h y) ( i o k j u) (o p 1 k i ) (p m 1 o)
(q a z s w) ( s q z e d x w) (d s e r f c x s )
(f d r t g v c) (g f t y h b v) ( h g y u j n b )
(j h u i k n ) ( k j i o 1 ) ( 1 k o p m ) ( m p 1 ) (w q s x)
(x w s d c ) ( c x d f v) ( v c f g b) ( b v g h n) ( n b h j) ) )
Programmation
Un des problèmes est de rendre certains calculs collectifs : si (z e s q a) désigne (e s
q a) comme liste des successeurs de z, comment former une liste ((e z) (s z) (q z) (a
z)) ? et comment reformer (e s q a) à partir d'une telle liste ?
Le premier problème est résolu par une construction
(map (lambda (x) (list x 'z)) '(e s q a)) -? ((e z) (s z) (q z)(a z))
et le second par une construction
(map car '((e z) (s z) (q z) (a z)) -? (e s q a)
map, appelée par (mapfonc liste), forme la liste des résultats obtenus en appli
quant/one à chacun des postes de la liste : d'où l 'exemple. D ' autre part/one n'a pas
besoin d'être un nom-de-fonction, mais doit avoir pour valeur un corps-de-fonction,
ce qui est aussi le cas si jonc est une forme lambda. D ' où le fonctionnement
(map (lambda (x) (list x 'z)) '(e s q a)) -? ((e z)(s z)(q z)(a z))
où la forme lambda est appliquée à chacun des postes de la liste, et forme autant de
listes terminées par z, collectées en une même liste finale. Ainsi
(map cadr '((a b) (d e) (g h))) -? (b e h)
(map (lambda (n) (expt n n)) '(l 2 3 4 5)) -? (1 4 2 7 256 3125) .
Finalement, nous proposons pour la recherche par niveau :
(define chemin ( lambda ( départ arrivée graphe )
( i f ( and '( assoc départ graphe ) ( assoc arrivée graphe ) )
[ let ( ( file (pistes départ arrivée graphe ( )
( l ist ( list départ ) ) ) ) )
(display ( l ist ' file ' obtenue file) ) ( newl ine )
( reverse (défaire départ arrivée file ) )
l
( l ist ' s orrunet départ ' ou arrivée ' hors 'graphe graphe )
)))
(define pi s tes ( lambda ( départ arrivée graphe traités visités )
; ; (display ( list ' D : départ 'A : arrivée 'G : graphe ' T : traités
; ; 'V : vis ités ) ) ( newline )
[ cond ( (nul l ? visité s ) "pas de solution " )
( (eq? ( caar visité s ) arrivée ) ( append traités visités ) )
(else (pistes départ arrivée graphe
( append traités ( l ist ( car vis ités ) ) )
; ; avancée d' un poste dans la file
( append ( cdr visité s )
( successeurs ( caar visité s ) graphe
(map car ( append traités visités ) ) )
))
l ))
(define successeurs ( lambda ( sommet graphe rencontrés )
, , (display ( l ist ' suce sommet ) ) ( newline )
(map (lambda (x) (l i s t x sommet) )
(diff ( cdr ( as soc sommet graphe ) ) rencontré s )
)))
1 42 A2 - Eléments pratiques : Scheme
on le retire du niveau n - 1 ;
- si ce niveau n - 1 contient au moins un sommet, on en sélectionne un et on
repart en avant ;
- si ce niveau n 1 se trouve vidé, on régresse au niveau n-2
-
Pro grammation
;; « chemin » blinde l ' opération, un sommet hors-graphe pouvant
;; induire une recherche longuement infructueuse avant diagnostic) ,
;; et introduit une l iste d' interdits vide
;; pour la véritable recherche , e ffectuée par cheminO
(de fine chemin ( lambda ( départ arrivée graphe )
( i f (and (assoc départ graphe ) (assoc arrivée graphe ) )
( reverse ( cheminO départ arrivee graphe ( ) ) )
(list ' sommet départ ' ou arrivée 'hors ' graphe graphe )
)))
(define chemin O ( lambda (départ arrivée graphe parcourus)
; ; parcourus doit éviter les bouclages
[ i f ( eq? départ arrivée) ( cons arrivée parcourus )
(poss ibles ( successeurs départ graphe parcourus )
arrivée graphe ( cons départ parcourus ) )
l))
;; le plus récent sommet de départ introduit un niveau de succes
seurs possibles
(define possibles ( l ambda (niveau arrivée graphe piste )
;; (display ( list niveau arrivée piste) )
; ; trace si nécessaire
( i f (or ( null ? niveau ) (> (length pi s te) 8) ) ( )
, , le test de longueur a pour but d' accélérer le processus
; ; et de favoriser un chemin raisonnable ; alternative :
;; ou le premier sommet du niveau donne une solution ,
;; ou s ' i l mène à une impasse , on es saie le reste du niveau
;; solution! , variable locale à ( let ... )
( let ( ( solution! ( cheminO
( car niveau ) arrivée graphe piste ) ) )
( i f ( nul l ? solution ! )
(pos sibles ( cdr niveau ) arrivée graphe piste )
solution! )
))))
; ; les succes seurs utiles sont ceux donnés par le graphe , sauf ceux
déj à parcourus
(define successeurs ( lambda ( sommet graphe interdits )
(diff ( cdr ( as soc sommet graphe ) ) interdits )
))
; ; reprise d' un classique
(define diff ( lambda (El E2 ) ( cond ( (null ? El ) ( ) )
( (member ( car E l ) E2 ) ( diff ( cdr E l ) E2 ) )
(else ( cons ( car E l ) (diff ( cdr E l ) E2 ) ) )
)))
On obtient ainsi :
Bienvenue ....
> (chemin 'a 'g G)
( (b c) g ( a ) ) ( ( c d) g (b a ) ) ( (d e ) g ( c b a ) ) ( (e f) g (d c b a ) ) ( ( f
g) g ( e d c b a) ) ( (g) g ( f e d c b a ) )
(a b c d e f g)
> ( chemin ' a ' g K)
( ( z q) g ( a ) ) ( ( e s q) g (z a ) ) ( (r d s) g ( e z a ) ) ( ( t f d) g (r e z
a) ) ( ( y g f) g ( t r e z a ) ) ( (u h g) g ( y t r e z a ) ) ( ( i j h) g (u y t
1 44 A2 - Eléments pratiques : Scheme
r e z a ) ) ( ( o k j ) g (i u y t r e z a ) ) ( (p 1 k) g (o i u y t r e z
a) ) ( ( k j ) g ( i u y t r e z a) ) ( (j o 1 ) g ( k i u y t r e z a) ) ( ( j ) g
( i u y t r e z a ) ) ( (h k n) g ( j i u y t r e z a ) ) ( ( ) g ( i u y t r e z
a ) ) ( ( j h) g (u y t r e z a ) ) ( (h i k n) g ( j u y t r e z a ) ) ( (g n b) g
(h j u y t r e z a ) ) ( ( i k n) g ( j u y t r e z a ) ) ( ( o k) g ( i j u y t
r e z a) ) ( (k n) g (j u y t r e z a) ) ( (i o 1) g ( k j u y t r e z
a ) ) ( (n ) g ( j u y t r e z a ) ) ( (b h) g ( n j u y t r e z a ) ) ( ( ) g ( j u y
t r e z a) ) ( (h) g (u y t r e z a ) ) ( (g j n b) g (h u y t r e z a ) )
(a z e r t y LI h g)
> (chemin 'a 'n G)
( sommet a ou n hors graphe ( ( a b c) (b c d) (c d e) (d e f) ( e f g)
(f g a) ( g a b) ) )
> (chemin 'a 'n K)
( ( z q) n ( a ) ) ( ( e s q) n ( z a ) ) ( ( r d s ) n ( e z a ) ) ( ( t f d) n ( r e z
a ) ) ( ( y g f ) n ( t r e z a ) ) ( (u h g) n ( y t r e z a ) ) ( ( i j h) n (u y t
r e z a ) ) ( ( o k j ) n ( i u y t r e z a ) ) ( (p 1 k) n (o i u y t r e z
a) ) ( ( k j ) n ( i u y t r e z a) ) ( ( j o 1 ) n ( k i u y t r e z a) ) ( ( j ) n
( i u y t r e z a ) ) ( (h k n) n ( j i u y t r e z a ) ) ( ( ) n ( i u y t r e z
a ) ) ( ( j h) n (u y t r e z a ) ) ( (h i k n) n ( j u y t r e z a ) ) ( (g n b) n
(h j u y t r e z a ) ) ( ( i k n) n ( j u y t r e z a ) ) ( ( o k) n ( i j u y t
r e z a) ) ( ( k n) n ( j u y t r e z a ) ) ( ( i o 1 ) n ( k j u y t r e z
a ) ) ( (n ) n ( j u y t r e z a) )
(a z e r t y LI j n)
8.4.4 Comparaison
La méthode par niveau fournit par nature les Tableau 8.1 Complexité des recherches
chemins les plus simples. Mais si k est le nombre par niveau et en profondeur.
moyen de successeurs utiles pour un sommet,
développer n niveaux demande une place mé Sommets Taille du chemin
moire en k0 pour la méthode par niveaux, en k·n obtenu
....
seulement pour la recherche en profondeur : on ::J
<lJ
X
::J "O
préfère donc cette dernière - aux résultats sou "'
<lJ
c
<lJ ., > ..8
vent médiocres et obtenus lentement - lorsqu'on t: •<lJ ..c 0
"' ï:i ....
> o. o.
o. ....
sait ou l'on craint que la mémoire soit insuffi . ., 'E"' "' c
"O � o. .,
sante.
a g G 3 7
a g K 5 9
8.5 JEU DE NIM DÉTERMINISTE a n G / /
a n K 7 9
Le jeu de Nim se joue à 2 joueurs, avec un tas de - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
jetons. A chaque partie, chaque j oueur a le droit de prendre à son tour de 1 à k je
tons. Celui qui prend le dernier jeton a gagné.
Analyse du jeu
Si le but est de laisser 0 jeton, on se convaincra facilement que tout autre multiple de
k + 1 est une position gagnante au sens suivant : le j oueur retirant un nombre p de
j etons ( 1 $; p $; k), l 'autre joueur pourra toujours en retirer k + l - p, se ramenant ainsi
soit à 0 (partie gagnée) soit au multiple de k+ l immédiatement inférieur.
Premières applications 1 45
Si Nim vous propose 26 jetons, et que chacun peut retirer de 1 à 7 jetons, devez
vous commencer ? Oui : en retirant 2 j etons, nim en reçoit 24, multiple de 8. Quoi
qu'il fasse, vous vous ramènerez à 1 6, 8 puis O . . .
Si Nim vous propose 24 jetons, et que chacun peut retirer de 1 à 5 jetons, devez
vous commencer ? 24 est multiple de 6, il n'y a rien à faire pour bien commencer :
déclinez l'offre, et laissez nim se débrouiller . . . s'il le peut.
D 'une partie sur l 'autre, pour mettre un peu de sel, le jeu ci-après ajuste k,
l ' incrémentant si le joueur a gagné, le décrémentant sinon.
Compléments Scheme
En entrée, read convertit la première représentation externe d 'objet Scheme trouvée
sur le flot d'entrée en l 'objet Scheme correspondant - et pointe ensuite sur la pre
mière position au-delà de cette représentation dans ce flux.
(random k) fournit un nombre tiré « au hasard » dans [O, k-1 ]
Solution Scheme
(define nim ( lambda ( )
(partie 5 ) ) )
(define partie ( lambda ( k)
(affiche-règles k)
(display " Partons d' un tas de " )
( let ( (gagnant ( j eu k ( + 1 1 ( random ( * 5 k) ) ) ) ) )
( newl ine )
(display ( i f ( eq? gagnant ' lui )
"Bravo ! Vous ave z gagné . " "J' ai gagné . " ) )
(newline )
(display "Encore une partie ? " )
( i f (eq? ( read) ' oui )
( i f ( eq? gagnant ' lui ) (partie ( + k 1 ) )
(partie ( - k 1 ) ) ) ; ; moi
(display " au revoi r . . . " )
)))
(define affiche-règles ( lambda ( k)
(display ( list
"Le j eu de Nim se j oue à 2 j oueurs avec un tas de j etons . "
" Pour cette partie, chaque j oueur en prendra à son tour de 1 à " k
" . Celui qui prendra le dernier j eton a gagné . " #\newline )
)))
(define jeu ( lambda ( k N)
(display ( list N " j etons . Voulez-vous commencer? " ) )
( i f ( eq? ( read) ' oui ) ( aLui k N) ( aMoi k N) )
))
(define aLui ( lambda ( k N)
(newline )
( let ( ( J ( l ireNbJetons (min k N) ) ) )
( i f ( J N) ' lui ( amoi k ( - N J) ) )
=
))
1 46 A2 - Eléments pratiques : Scheme
))))
( define lireNbJetons ( lambda (plafond)
(display "Combien prene z-vous de j etons ? " )
( let ( ( J ( read) ) )
( cond ( ( and ( integer? J) ( > J 0 ) ( <= J plafond) ) J)
; ; J entier correct
(else ( display
"Réponde z par un nombre entier de 1 à " )
( display plafond) ( display " . " )
( l ireNbJetons plafond ) )
))))
8.6.1 Analyse
Si je dois rendre 37 oros, et que j ' ai 2 pièces de 1 0, 5 et 2 oros, et 3 de 1 oro, je
rends :
min(37 : 1 0, 2) = 2 pièces de 10 oros, reste 1 7 oros
min( l 7 : 5 , 2) = 2 pièces de 5 oros, reste 7 oros
min(7 : 2, 2) = 2 pièces de 2oros, reste 3 oros
min(3 : 1 , 3)= 3 pièces de 1 oro, et le tour estjoué !
Ce procédé déterministe simple peut être mis en échec. Si j e dois rendre 26 oros,
et que j ' ai 2 pièces de 1 0 oros, 2 de 5 oros et 3 de 2 oros, j 'obtiens :
min(26 : 1 0, 2) = 2 pièces de 1 0 oros, reste 6 oros
min(6 : 5 , 2) = 1 pièce de 5 oros, reste 1 oro,
queje n 'arrive pas à rendre.
Or il est clair que 26 = 2* 1 0 + 3 *2 : la monnaie peut et doit être rendue, mais
cette solution doit être bâtie par essais et erreurs : s ' il reste 6 oros à rendre :
• si je rendais 1 pièce de 5 oros, il me resterait 1 oro à rendre, et je ne pourrais
pas ;
• si je ne rends pas de pièce de 5 oros, il me reste 6 oros à rendre que je rends
> ( rendre 2 . 7 0 )
(1 * 2 . 0 + 1 * 0 . 5 + 1 * 0.2)
> ( rendre 3 . 1 0 )
" impossible"
> ( rendre 3 . 5 0 )
" impossible"
> ( rendre 4 . 1 0 )
(2 * 2 . 0 + 1 * 0 . 1 )
> ( rendre 6 )
(3 * 2 . 0)
> ( rendre 5 . 95 )
( 1 * 5 . 0 + 1 * 0 . 5 + 1 * 0 . 2 + 1 * 0 . 1 + 3 * 0 . 05 )
8 .7 EXERCICES
8.8 INDICATIONS
Pour 8.7.1
Fib3 1 crée une variable locale à chacun des niveaux 2 à n, mais demande un temps
de calcul proportionnel à n seulement, car chaque appel à fib3 l en engendre au plus
un autre.
Premières appl ications 1 49
« n » peut être assez grand pour que les temps de calcul de fib ou fib2 soient
ob servables - car ils sont en 1 ,62" - sans que celui de fib3 , qui est en n, le soit : pour
n>20, le rapport dépasse 1 000.
Pour 8.7.2
Définir le format de T, puis l 'initialisation de T par G. Expliciter puis exploiter les
relations :
(a x b 357) • (x y 1 8) = (a y b 375).
min( (a x b 357), (a x c 370) )= (a x b 357)
CHAPITRE 9
Ce chapitre a pour but de montrer que scheme (ou lisp) est un moyen en principe
suffisant - bien qu'un peu léger - pour couvrir l 'intelligence Artificielle, ou du
moins en donner un avant-goût. Les exemples sont variés, et leur intérêt devrait se
renforcer à la lecture du reste de l 'ouvrage.
9.1.1 Analyse
Une variable globale Dico contiendra l'arbre des connaissances, de type binaire
étiqueté :
(attribut sousArbreOui sousArbreNon)
Supposons que votre animal soit gros, sans que ce soit un éléphant : vous pen
siez à un dinosaure. Le jeu vous demande une qualité distinctive du dinosaure (par
rapport à l'éléphant) ; si vous répondez « disparu », on doit effectuer la transforma-
tion : (gros éléphant rat) � (gros (disparu dinosaure éléphant) rat).
En vue d'une nouvelle exécution, la fonction set! mettra à jour Dico en lui assi
gnant le résultat de substituer, fonction qui construit une copie de Dico dont la
feuille « éléphant » est remplacée par le nouveau triplet.
9.2.1 Analyse
Comme expliqué dans la section 9.3, les positions gagnantes seront les multiples de
5+ 1 = 6. Cette connaissance a priori n'est plus exploitée par le programme. On va au
contraire demander à nimApp de retrouver cette propriété en gérant ses essais et
erreurs.
Pour cela, une liste globale listeG, vide au départ, contiendra par la suite la liste
des positions présumées gagnantes, d'après les parties déjà jouées. Dans un cas plus
sérieux, listeG pourrait être un fichier. D ' autre part, deux listes, jeuLui et jeuMoi,
assurent le suivi d'une partie : nimApp note dans jeuLui les positions attein
tes/rendues par l 'adversaire, et dans jeuMoi celles atteintes/rendues par nimApp.
Celles-ci sont définies ainsi : si nimApp reçoit N jetons et peut jouer de 1 à k jetons
(où k= min (N, 5)), il regarde si une des positions N- 1 à N-k est connue gagnante
(par listeG), et si oui il l 'atteint en retirant le nombre correspondant de jetons. En fin
de partie, listeG est mis à j our : on lui retire les positions atteintes par le perdant,
présumées enregistrées à tort, et on lui ajoute celles atteintes par le gagnant, présu
mées sûres ; nimApp apprend ainsi le jeu par la fin. Certaines positions présumées
gagnantes pourront donc être remises en cause. Cependant, les valeurs enregistrées
seront de plus en plus sûres, le niveau du j eu étant lentement relevé. L 'apprentissage
sera considéré comme réussi si la liste des positions gagnantes, progressivement
complétée, ne contient à la longue que des multiples de 6.
Ce jeu est plus évolué que Zanimos, dont l 'apprentissage était exclusivement
additif. Ici, des positions apprises gagnantes à tort pourront être remises en cause par
l 'expérience. Cette version assez simple gère les positions gagnantes plutôt que de
qualifier des paires (situation, trait). Nous utilisons de fait une métaconnaissance :
dans les jeux auxquels on peut assigner une fonction de Grundy, le gain de la partie
est lié à la situation atteinte plutôt qu' au mouvement fait. Sinon, tout ce qui est fait
ici avec des listes plates devrait être fait avec des listes associatives, l 'apprentissage
serait beaucoup plus lent, et ne pourrait être accéléré que par l 'introduction d 'un
mécanisme inductif.
1 54 A2 - Eléments pratiques : Scheme
9.2.3 Solution
( include " . . \ \maCollec\ \ensembles . scm" )
; ; ------- importe textuellement di ff et union
; ; un mécani sme plus raffiné exploite des modules
(de fine nouvell eLigne ( lambda (msg)
( newline ) (display msg) ) )
(de fine l i s teG () ) ; ; positions présumées gagnantes
(de fine j euLui () ) , , coups de l ' adversaire
( de fine j e uMoi () ) ; ; coups du programme
(de fine nimApp ( lambda ( ) (partie 5 2 ) ) ) ; ; le j eu lui-même
( define partie ( lambda ( k niv)
(affiche-règles k)
( se t ! j euLui ( ) )
( se t ! j euMoi ( ) )
( nouvelleLigne " Partons d' un tas de " )
( let ( (gagnant ( j eu k ( + k niv ( random ( * niv k) ) ) ) ) )
; ; varions les départs
(nouvelleLigne ( i f ( eq? gagnant ' lui)
"Bravo ! Vous avez gagné . " "J' ai gagné . " ) )
( se t ! listeG ; ; m . à . j . liste gagnante
( i f ( eq? gagnant ' lui)
(union j euLui ( diff listeG j euMoi ) )
(union j euMoi ( diff listeG j euLu i ) ) ) )
( nouvelleLigne
( list "posi tions présumées gagnan tes : " listeG) )
; ; trace apprentis sage
( nouvelleLigne "Encore une partie ? " )
( i f ( eq? ( read) ' oui ) (partie 5 ( + niv 1 ) )
(display " Dommage . . . Au revoi r . " )
))
(define a ffiche-règles ( lambda ( k )
(display " Le j eu de Nim se j oue à 2 j oueurs "
" avec un tas de j etons . Pour cette partie , "
" chaque j oueur en prendra à son tour de 1 à " )
(display k)
(display " . Celui qui prendra le dernier j eton a gagné . " )
(nouvelleLigne "Ce programme est à apprentissage "
" aye z la patience de m' apprendre à gagner ! " ) ) )
Vers l ' IA en Scheme 1 55
9.3.1 Cadrage
Le principe est d' identifier les mots et les groupements remarquables de mots, en
supposant que la phrase se conforme à une grammaire simple. Ici, nous supposerons
la phrase organisée en sujet, verbe, complément, sujet et complément renvoyant au
groupe nominal qu'on supposera réduit à un déterminant suivi d'un nom.
En pratique, nous nous donnons la grammaire suivante, inspirée de 4.7.2:
(define gramma ire
' ( (phrase seq suj et verbe complement
( suj et seq groupeNominal)
(verbe alt "est" " était" " sera " )
( complement seq preposition groupeNominal )
(groupeNominal seq determinant nom)
(determinant alt " l e " " la " " le s " "un" "une " "des" "ce"
" cet " " cette " " ces" "chaque " " tout " )
(nom alt "banc " " chat " " chatte" "chien "
" chienne " " tapi s " )
(preposition alt " sur" " sous " "dans" "devant"
"derrière " )
))
Cette liste est formée de sous-listes de structure
(notion développement)
le développement étant formé d'un connecteur alt/seq suivi d'une liste d'éléments :
• ait préfixe une alternative, satisfaite dès qu'un de ses éléments est rencontré,
• seq préfixe une séquence, qui n'est reconnue que si chacun de ses éléments
• soit on pose que la grammaire est une structure de données ; on écrit alors
des fonctions de navigation dans cette structure et de confrontation au texte ;
modifier la grammaire, c'est modifier la structure de données ; seul un chan
gement de catégorie de la grammaire peut exiger une modification de
l 'analyseur.
La trace utilise write plutôt que display afin de rendre apparente la distinction
symbole/notion et terminal/chaîne. On écrit :
(define mo t (} ) ; ; global pour réduire les passages de paramètres
(define tes t( lambda (notion ) ; ; pour une notion isolée
(write ( l ist ' test notion ' ? mot ) )
( cond ( ( nul l ? mot ) (motSuivant ) ( test notion ) )
( ( and ( null ? notion ) ( equal? mot " stop" ) ) ( ) )
( ( terminal ? notion)
( i f ( equal? notion mot ) (trace mot ) # f ) )
(else ( suite notion ( assoc notion grammaire ) ) ) ) ) )
; ; assoc récupère dans gramma i re la règle développant la notion
(define sui te ( lambda ( notion devt )
; ; (write ( list ' - > ( cdr devt ) ' ? mot ) )
( i f ( null ? devt )
(display ( list 'notion notion " non définie " ) )
[ case (cadr devt )
( ( alt) (trace ( l ist notion (alternative ( cddr devt ) ) ) ) )
( ( seq) (trace ( l ist notion ( sequence ( cddr devt ) ) ) ) )
(else (display ( l ist ' notion notion " mal dé finie " ) )
)) ) )
Vers l ' IA en Scheme 1 59
))
(define a l terna t i ve ( lambda (devt )
( write ( list ' alternative devt ' ? mot ) )
( i f ( nul l ? devt ) # f
( let ( ( rep ( test ( car devt ) ) ) )
( i f rep (begin (motSuivant ) rep)
( alternative ( cdr devt ) ) )
)))
(define notion ? ( lambda ( truc ) ( symbol? truc ) ) )
(define terminal ? ( lambda (truc) ( string? truc ) ) ) ; ; symbol * string
(define mo tSui vant ( lambda ( ) ( newline ) (display 'mot?
( se t ! mot ( symbol->string ( read) ) )
))
(define trace
( lambda (truc)
(display '>> ) ( write truc ) ( newl ine )
; ; à mettre derrière des points-virgule pour rendre trace transparent
truc ) )
(define ana lyse ( lambda () ( se t ! mot ( ) ) ( test 'phrase ) ) )
9.3.3 Utilisation
Le lancement se fait par (analyse). Les mots sont à rentrer un à la fois, en réponse à
l 'invite mot ? Après le dernier mot, taper stop à la demande suivante.
Bienvenue... .
> (analyse)
(test phrase ? () )
mo t ?l e
( test phrase ? " le " ) ( sequence ( suj et verbe complement ) ? " le " ) ( test
suj et ? " le " ) ( sequence ( groupenominal ) ? " le " ) ( test groupenominal ?
"le " ) ( sequence (determinant nom) ? " le " ) ( test determinant ?
" le" ) (alternative ( " le " " la " " le s " "un" "une " "de s " " ce " " cet"
"cette " " ces " " chaque " " tout " ) ? " le " ) ( test " le " ? " le " ) >> " le "
mo t ?cha t
>> (determinant "le" )
( sequence (nom) ? " chat " ) ( test nom ? " chat " ) ( alternative ( "banc"
"chat " " chatte " " chien" " chienne " " tapi s " ) ? " chat " ) ( test "banc" ?
"chat " ) ( alternative ( " chat " " chatte" " chien" " chienne " " tapis " ) ?
"chat " ) ( test " chat " ? " chat " ) >>"chat "
mo t ?est
>> (nom " chat " )
( sequence ( ) ? "est" ) >> (groupenominal (determinant " le " nom " chat " ) )
( sequence ( ) ? "est " ) >> ( suj et ( groupenominal ( determinant " le " nom
"cha t " ) ) )
( sequence (verbe complement ) ? "est " ) ( test verbe ? "est " ) ( alternative
( "e st" " était " " sera" ) ? "est " ) ( test "est" ? "est " ) >>"est"
1 60 A 2 - Eléments pratiques : Scheme
mo t ?sur
>> (verbe "est " )
( sequence ( complement ) ? " sur" ) ( test complement ? " sur" ) ( sequence
(preposition groupenominal ) ? " sur" ) ( test preposition ?
" sur" ) (alternative ( " sur" " sous " "devant " "derrière " "dans " ) ?
" sur" ) ( test " sur" ? " sur" ) >>" sur"
mo t ?le
>> (preposition " sur" )
( sequence ( groupenominal ) ? " le " ) ( test groupenominal ? " le " ) ( sequence
(determinant nom) ? "le" ) ( test determinant ? " le " ) ( alternative ( " le"
" la " " les " "un" "une " "de s " "ce" " cet" " cette " " ces " "chaque " " tout " )
? " le " ) ( test " le " ? " le " ) >> " le "
mo t ?ban c
>> (determinant "le" )
( sequence ( nom) ? "banc" ) ( test nom ? "banc " ) ( alternative ( "banc"
" chat " " chatte " " chien" " chienne " " tapis " ) ? "banc " ) ( test "banc " ?
"banc " ) >>"banc"
mo t ?s top
>> ( nom "banc " )
( sequence ( ) ? " s top" ) >> ( groupenominal ( determinant " le " nom "banc" ) )
( sequence ( ) ? " s top" ) >> ( complement (preposition " sur" groupenominal
(determinant " le " nom "banc" ) ) )
( sequence ( ) ? " stop" ) >> (phrase ( suj et (groupenominal ( determinant
" le " nom " chat " ) ) verbe "est" complement (preposition " sur" groupeno
minal (determinant " le " nom "banc " ) ) ) )
(phrase
( suj et
( groupenominal (determinant " le " nom " chat " ) )
verbe
"est"
complement
(preposition " sur" groupenominal (determinant " le" nom "banc " ) ) ) )
9.5. l Présentation
DÉFINITION. On appelle calcul symbolique (automatique) ou calcul formel, toute
forme de calcul littéral automatique.
Un tel calcul semble possible puisque toute formule peut être représentée par
un arbre, et en tant que tel peut être construite et découpée.
Vers l ' IA en Scheme 161
De fait, les premiers travaux sur l e suj et remontent à 1 956 23 , mais s e sont déve
24
loppés à partir de 1 965 sur de grosses machines (MacSyma, MIT) , puis sur micro
ordi nateur à partir de 1 976 (Université de Hawaï).
Cette technique est beaucoup employée en physique théorique, car elle permet
d'envisager des solutions génériques et/ou d'échapper aux imprécisions des métho
des numériques dont on peut ainsi retarder et réduire l 'usage.
9.5.2 Analyse
L'assimilation opérateur� fonction suggère d 'associer à toute formule infixée une
représentation par un arbre correspondant à cette formule sous forme préfixée :
a - x*y - z 7 -a* xyz -
-+ (- (- a (* x y)) z) à la lisp/scheme.
Variables et constantes constitueront les feuilles, et les nœuds seront de type
binaire étiqueté :
(opérateur opérandeGauche opérandeDroit).
Réduire
Une des difficultés est l 'aspect luxuriant des réponses obtenues par ces traitements
automatiques : l ' application systématique de certaines formules se fait sans autres
inconvénients que la multiplication des 0 et des 1 . On ne peut donc faire grand-chose
sans procédure de réduction, servant à clarifier des réponses par ailleurs exactes (-+
réduire ).
On n'utilise ici que quelques stratégies assez primitives, mais susceptibles de
déclencher d'autres réductions :
• évaluation des opérations aux opérandes constants -7
remplacement d 'une sous-expression par une constante,
• s ' il y a un opérande constant, essai d'exploitation comme élément neutre ou
absorbant pour l 'opérateur,
•exploitation d' idempotences et d'autres effets (op x x) :
(max x x)-+ x, (min x x)-+ x, (- x x) -+ 0, (/ x x)-+ 1 . . .
règles d'autant plus efficaces qu'elles exploitent un test d'égalité entre arbres préala
blement réduits. Ces stratégies utilisent des schémas généraux faciles à étendre si on
23 Par
Grace Hoppers, plus connue comme principale conceptrice du premier Cobol .
24
Voir aussi (Arditi 1 996, ch. 1 1 ) .
1 62 A2 - Eléments pratiques : Scheme
ajoute de nouveaux opérateurs. Pour ce qui est de reconnaître les éléments remar
quables, ceux-ci sont documentés en fonction de leur rôle dans une liste associative,
où l 'opérateur concerné joue Je rôle de clé. Dans la construction
(let ((cas (assoc op ' [(+ 0) (* 1 ) (- 0) (/ 1 )(/\ l )]))) ;; x + 0 =x . . .
si l 'opérateur est renseigné dans la liste entre [], assoc fournit à la variable locale cas
le couple (op élémentRemarquable) sinon #f. Si cas contient un couple, il ne reste
alors qu' à comparer élémentRemarquable et la valeur à tester.
Dans la fonction auxiliaire évaluation, on notera :
• le remplacement de notre symbole interne !\ par la fonction expt, fonction
Scheme d 'exponientiation,
• l'emploi de eval pour ranimer les noms de notions figés par quote pour être
transmis.
Substituer / Evaluer
Subst remplace par une formule g donnée toute occurrence d'une variable x dans une
formule f ; évaluer substitue de même une valeur à chaque occurrence d'une varia
ble, ce qui appelle une réduction.
Dériver
La fonction dériv dérive par rapport à une variable donnée une formule donnée ; les
arbres correspondants sont engendrés à / 'économie via reduire3, fonction auxiliaire
de réduire.
Réduire
(define reduire( lambda ( arbre )
[ i f ( atom? arbre ) arbre
; ; les feuilles sont irréductibles
; ; mai s un nœud est présumé triplet
( reduire3 ( car arbre )
( reduire ( cadr arbre ) ) ( reduire ( caddr arbre ) ) )
l))
(define reduire3 ( lambda ( op gauche droite )
, , traitement d' un noeud éclaté
( cond ( ( and ( number? gauche) ( number? droite ) )
( evaluation op gauche droite ) )
( ( eltNeutreGauche ? op gauche ) droite )
( (eltNeutreDroite? op droite ) gauche )
( (eltAbsorbantGauche ? op gauche ) gauche )
( ( eltAbsorbantDroite? op droite ) droite )
( (equal? gauche droite )
; ; op x x idempotences et autres
( case op
[ ( -) 0 ] ; ; x - x -> O
[ (/) lJ i i X / X -> l
[ (+) ( list ' * 2 gauche ) ] ; ; x + x -> 2 * x
[ (*) ( list ' " gauche 2 ) J ; ; x * x -> x " 2
[ (max min ) gauche ]
; ; max x x -> x , min x x -> x
[ else ( list op gauche droite ) ] ) )
(else ( list op gauche droite ) ) ) ) )
(define eva l ua ti on ( l ambda ( op valGauche valDroite )
( i f (equal? op ' " ) ( expt valGauche valDroite )
; expt , fonction Scheme d' exponentiation
( ( eva l op) valGauche valDroite ) )
))
1 64 A2 - Eléments pratiques : Scheme
Substituer / évaluer
Dériver
(define deri v ( lambda ( # ! par rapport à l # variable # l de l # arbre )
(display ( l ist "dérivée par rapport à " variable "
de " arbre ) )
[ cond ( (or (pair? variable) ( number? variable ) )
"évaluer : le second argument n ' est pas une variable " )
( ( atom? arbre ) ( i f ( equal ? arbre variable ) l 0 ) )
( (=· 1 ( length arbre ) ) ( deriv variable ( car arbre ) ) )
(else ( deriv3 variable ( car arbre )
( cadr arbre ) ( caddr arbre ) ) )
)))
(define deriv3 ( lambda ( x op u v)
( case op
[ ( - + ) ( reduire3 op (deriv x u ) ( deriv x v ) ) )
[ (*) ( somme (produit ( deriv x u ) v)
(produit u ( deriv x v) ) ) )
[ (/) (difference ( quotientR ( deriv x u) v)
( quotientR (produit u (deriv x v) ) ( carre v) ) )
( ( A expt ) ( somme (produit (produit v
(puiss u (difference v 1 ) ) ) ( deriv x u) )
(produit ( list ' log 'e u )
(produit (puiss u v) (deriv x v) ) ) ) ]
[ else ( list 'dérivée/ x ' de op u v ' ? ? ? ) ) )
))
;i création à l ' économie des arbres néces saires
===================