20
Virginie MATHIVET Concepts et implémentations en C# L’Intelligence Artificielle pour les développeurs

L'intelligence artificielle pour les développeurs

Embed Size (px)

DESCRIPTION

Concepts et implémentation en C#

Citation preview

  • LIn

    telli

    genc

    e A

    rtifi

    ciel

    le p

    our l

    es d

    vel

    oppe

    urs

    LIntelligence Artificielle pour les dveloppeurs Concepts et implmentations en C#Ce livre sur lIntelligence Artificielle sadresse particulirement aux dveloppeurs et ne ncessite pas de connaissances mathmatiques approfondies. Au fil des chapitres, lauteur prsente les principales techniques dIntelligence Artificielle et, pour chacune delles, les inspirations, biologiques, physiques voire mathmatiques, puis les diffrents concepts et principes (sans entrer dans les dtails mathmatiques), avec des exemples et figures pour chacun de ceux-ci. Les domaines dapplication sont illustrs par des applications relles et actuelles. Chaque chapitre contient un exemple dimplmentation gnrique, complt par une application pratique, dveloppe en C#. Ces exemples de code tant gnriques, ils sont facilement adaptables de nombreuses applications C#, que ce soit en Silverlight, sur Windows Phone, pour Windows 8 ou pour des applications .Net plus classiques. Les techniques dIntelligence Artificielle dcrites sont : Les systmes experts, permettant dappliquer des rgles pour prendre des dcisions

    ou dcouvrir de nouvelles connaissances. La logique floue, permettant de contrler des systmes informatiques ou mcaniques

    de manire beaucoup plus souple que les programmes traditionnels. Les algorithmes de recherche de chemin, dont le A* trs utilis dans les jeux vido

    pour trouver les meilleurs itinraires. Les algorithmes gntiques, utilisant la puissance de lvolution pour apporter des

    solutions des problmes complexes. Les principales mtaheuristiques, dont la recherche tabou, trouvant des optimums

    des problmes doptimisation, avec ou sans contraintes. Les systmes multi-agents, simulant des foules ou permettant des comportements

    mergents partir de plusieurs agents trs simples. Les rseaux de neurones, capables de dcouvrir et de reconnatre des modles, dans

    des suites historiques, des images ou encore des donnes.Pour aider le lecteur passer de la thorie la pratique, lauteur propose en tlcharge-ment sur le site www.editions-eni.fr, sept projets Visual Studio 2013 (un par technique dIn-telligence Artificielle), dvelopps en C#. Chaque projet contient une PCL, pour la partie gnrique, et une application WPF, pour la partie spcifique lapplication propose.Le livre se termine par une bibliographie, permettant au lecteur de trouver plus dinforma-tions sur ces diffrentes techniques, une sitographie listant quelques articles prsentant des applications relles, une annexe et un index.

    Virginie MATHIVETAprs un diplme dingnieur INSA et un DEA Documents, Images et Systmes dInformations Com-municants, Virginie MATHIVET a fait une thse de doctorat au sein du laboratoire LIRIS, en Intelli-gence Artificielle, plus prcisment sur les algorithmes gntiques et les rseaux de neurones. Elle est aujourdhui professeur permanent lEPSI de Lyon, o elle enseigne lIntelligence Artificielle ainsi que des matires lies au dveloppement (C#, PHP, Java, JS), la modlisation 3D ou les mthodologies de dve-loppement. A travers ce livre, elle partage sa passion pour le domaine de lIntelligence Artificielle et le met la porte des dveloppeurs pour quils puissent en exploiter tout le potentiel.

    Avant-proposIntroductionSystmesexpertsLogiquefloueRecherchedecheminsAlgorithmesgntiquesMtaheuristiquesdoptimisationSystmesmulti-agentsR-seauxdeneuronesBibliographieSitographieAnnexe

    Les chapitres du livre

    isbn

    : 978

    -2-7

    460-

    9215

    -0

    45

    Virginie MATHIVET

    Concepts et implmentations en C#

    LIntelligence Artificielle pour les dveloppeurs

    Tlchargementwww.editions-eni.fr.fr

    sur www.editions-eni.fr : b Un projet Visual Studio par

    chapitre, contenant la PCL et lapplication WPF illus-trant lexemple propos dans le chapitre.

    Pour plus dinformations :

  • 1Table des matires

    Avant-propos

    Introduction

    1. Structure du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

    2. Dfinir lintelligence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

    3. Lintelligence du vivant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

    4. Lintelligence artificielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

    5. Domaines dapplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

    6. Synthse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

    Chapitre 1Systmes experts

    1. Prsentation du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

    2. Exemple : un systme expert en polygones . . . . . . . . . . . . . . . . . . . . 302.1 Triangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302.2 Quadrilatres. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.3 Autres polygones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

    3. Contenu d'un systme expert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.1 Base de rgles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.2 Base de faits. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.3 Moteur d'infrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.4 Interface utilisateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

    Les exemples tlcharger sont disponibles l'adresse suivante :http://www.editions-eni.fr

    Saisissez la rfrence ENI de l'ouvrage DPINT dans la zone de rechercheet validez. Cliquez sur le titre du livre puis sur le bouton de tlchargement.

  • 2pour les dveloppeurs - Concepts et implmentations en C#

    LIntelligence Artificielle

    4. Types d'infrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.1 Chanage avant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

    4.1.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.1.2 Application un exemple . . . . . . . . . . . . . . . . . . . . . . . . . 40

    4.2 Chanage arrire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.2.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.2.2 Application un exemple . . . . . . . . . . . . . . . . . . . . . . . . . 42

    4.3 Chanage mixte. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

    5. tapes de construction d'un systme . . . . . . . . . . . . . . . . . . . . . . . . . 455.1 Extraction des connaissances. . . . . . . . . . . . . . . . . . . . . . . . . . . . 465.2 Cration du moteur d'infrences . . . . . . . . . . . . . . . . . . . . . . . . . 465.3 criture des rgles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475.4 Cration de l'interface utilisateur . . . . . . . . . . . . . . . . . . . . . . . . 47

    6. Performance et amliorations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486.1 Critres de performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486.2 Amlioration des performances par l'criture des rgles . . . . . . 496.3 Importance de la reprsentation du problme . . . . . . . . . . . . . . 50

    7. Domaines dapplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527.1 Aide au diagnostic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527.2 Estimation de risques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537.3 Planification et logistique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547.4 Transfert de comptences et connaissances . . . . . . . . . . . . . . . . 547.5 Autres applications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

    8. Cration dun systme expert en C# . . . . . . . . . . . . . . . . . . . . . . . . . 558.1 Dtermination des besoins. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568.2 Implmentation des faits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578.3 Base de faits. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618.4 Rgles et base de rgles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 628.5 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648.6 Moteur d'infrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 678.7 Saisie des rgles et utilisation. . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

  • 3Table des matires

    9. Utilisation de Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 769.1 Prsentation du langage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 779.2 Syntaxe du langage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

    9.2.1 Gnralits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 789.2.2 Prdicats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 789.2.3 Poser des questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 799.2.4 criture des rgles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 809.2.5 Autres prdicats utiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

    9.3 Codage du problme des formes gomtriques . . . . . . . . . . . . . 829.4 Codage du problme des huit reines . . . . . . . . . . . . . . . . . . . . . . 86

    9.4.1 Intrt du chanage arrire . . . . . . . . . . . . . . . . . . . . . . . . . 869.4.2 tude du problme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 869.4.3 Rgles appliquer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 879.4.4 Rgles de conflits entre reines . . . . . . . . . . . . . . . . . . . . . . 889.4.5 But du programme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 909.4.6 Exemples d'utilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

    10. Ajout dincertitudes et de probabilits . . . . . . . . . . . . . . . . . . . . . . . . 9110.1 Apport des incertitudes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9110.2 Faits incertains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9210.3 Rgles incertaines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

    11. Synthse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

    Chapitre 2Logique floue

    1. Prsentation du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

    2. Incertitude et imprcision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 962.1 Incertitude et probabilits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 962.2 Imprcision et subjectivit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 962.3 Ncessit de traiter l'imprcision . . . . . . . . . . . . . . . . . . . . . . . . . 97

  • 4pour les dveloppeurs - Concepts et implmentations en C#

    LIntelligence Artificielle

    3. Ensembles flous et degrs dappartenance . . . . . . . . . . . . . . . . . . . . . 983.1 Logique boolenne et logique floue . . . . . . . . . . . . . . . . . . . . . . . 983.2 Fonctions d'appartenance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 993.3 Caractristiques d'une fonction d'appartenance. . . . . . . . . . . . 1023.4 Valeurs et variables linguistiques . . . . . . . . . . . . . . . . . . . . . . . 103

    4. Oprateurs sur les ensembles flous . . . . . . . . . . . . . . . . . . . . . . . . . . 1044.1 Oprateurs boolens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1044.2 Oprateurs flous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

    4.2.1 Ngation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1064.2.2 Union et intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

    5. Cration de rgles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1105.1 Rgles en logique boolenne . . . . . . . . . . . . . . . . . . . . . . . . . . . 1105.2 Rgles floues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

    6. Fuzzification et dfuzzification. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1136.1 Valeur de vrit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1136.2 Fuzzification et application des rgles . . . . . . . . . . . . . . . . . . . 1156.3 Dfuzzification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

    7. Exemples dapplications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1217.1 Premires utilisations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1217.2 Dans les produits lectroniques. . . . . . . . . . . . . . . . . . . . . . . . . 1227.3 En automobile. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1227.4 Autres domaines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

    8. Implmentation dun moteur de logique floue. . . . . . . . . . . . . . . . . 1238.1 Le cur du code : les ensembles flous . . . . . . . . . . . . . . . . . . . . 124

    8.1.1 Point2D : un point d'une fonction d'appartenance . . . . 1248.1.2 FuzzySet : un ensemble flou . . . . . . . . . . . . . . . . . . . . . . 1258.1.3 Oprateurs de comparaison et de multiplication . . . . . . 1268.1.4 Oprateurs ensemblistes . . . . . . . . . . . . . . . . . . . . . . . . . 1278.1.5 Calcul du barycentre . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

    8.2 Ensembles flous particuliers. . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

  • 5Table des matires

    8.3 Variables et valeurs linguistiques . . . . . . . . . . . . . . . . . . . . . . . 1418.3.1 LinguisticValue : valeur linguistique . . . . . . . . . . . . . . . . 1418.3.2 LinguisticVariable : variable linguistique . . . . . . . . . . . . 142

    8.4 Rgles floues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1438.4.1 FuzzyExpression : expression floue. . . . . . . . . . . . . . . . . 1438.4.2 FuzzyValue : valeur floue. . . . . . . . . . . . . . . . . . . . . . . . . 1448.4.3 FuzzyRule : rgle floue . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

    8.5 Systme de contrle flou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1468.6 Synthse du code cr. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

    9. Implmentation dun cas pratique . . . . . . . . . . . . . . . . . . . . . . . . . . 151

    10. Synthse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

    Chapitre 3Recherche de chemins

    1. Prsentation du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

    2. Chemins et graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1602.1 Dfinition et concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1602.2 Reprsentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

    2.2.1 Reprsentation graphique . . . . . . . . . . . . . . . . . . . . . . . . 1612.2.2 Matrice dadjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

    2.3 Cot d'un chemin et matrice des longueurs . . . . . . . . . . . . . . . 165

    3. Exemple en cartographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

    4. Algorithmes nafs de recherche de chemins . . . . . . . . . . . . . . . . . . . 1684.1 Parcours en profondeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

    4.1.1 Principe et pseudo-code . . . . . . . . . . . . . . . . . . . . . . . . . . 1684.1.2 Application la carte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

    4.2 Parcours en largeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1744.2.1 Principe et pseudo-code . . . . . . . . . . . . . . . . . . . . . . . . . . 1754.2.2 Application la carte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

  • 6pour les dveloppeurs - Concepts et implmentations en C#

    LIntelligence Artificielle

    5. Algorithmes "intelligents" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1795.1 Algorithme de Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

    5.1.1 Principe et pseudo-code . . . . . . . . . . . . . . . . . . . . . . . . . . 1805.1.2 Application la carte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

    5.2 Algorithme de Dijkstra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1865.2.1 Principe et pseudo-code . . . . . . . . . . . . . . . . . . . . . . . . . . 1865.2.2 Application la carte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

    5.3 Algorithme A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1905.3.1 Principe et pseudo-code . . . . . . . . . . . . . . . . . . . . . . . . . . 1905.3.2 Application la carte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192

    6. Implmentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2006.1 Nuds, arcs et graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200

    6.1.1 Implmentation des nuds . . . . . . . . . . . . . . . . . . . . . . . 2006.1.2 Classe reprsentant les arcs . . . . . . . . . . . . . . . . . . . . . . . 2016.1.3 Interface des graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

    6.2 Fin du programme gnrique . . . . . . . . . . . . . . . . . . . . . . . . . . . 2036.2.1 IHM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2036.2.2 Algorithme gnrique. . . . . . . . . . . . . . . . . . . . . . . . . . . . 204

    6.3 Codage des diffrents algorithmes . . . . . . . . . . . . . . . . . . . . . . 2056.3.1 Recherche en profondeur . . . . . . . . . . . . . . . . . . . . . . . . . 2056.3.2 Recherche en largeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2076.3.3 Algorithme de Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . 2086.3.4 Algorithme de Dijkstra. . . . . . . . . . . . . . . . . . . . . . . . . . . 2096.3.5 Algorithme A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

    6.4 Application la carte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2126.4.1 Tile et Tiletype . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2136.4.2 Implmentation de la carte . . . . . . . . . . . . . . . . . . . . . . . 2156.4.3 Programme principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222

    6.5 Comparaison des performances. . . . . . . . . . . . . . . . . . . . . . . . . 226

    7. Domaines dapplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228

    8. Synthse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230

  • 7Table des matires

    Chapitre 4Algorithmes gntiques

    1. Prsentation du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233

    2. volution biologique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2342.1 Le concept d'volution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2342.2 Les causes des mutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2352.3 Le support de cette information : les facteurs . . . . . . . . . . . . . 2362.4 Des facteurs au code gntique . . . . . . . . . . . . . . . . . . . . . . . . . 2392.5 Le cycle de la vie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241

    3. volution artificielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2423.1 Principes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2423.2 Vue d'ensemble du cycle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244

    3.2.1 Phases d'initialisation et de terminaison . . . . . . . . . . . . . 2443.2.2 Phase de slection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2443.2.3 Phase de reproduction avec mutations . . . . . . . . . . . . . . 2453.2.4 Phase de survie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245

    3.3 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245

    4. Exemple du robinet. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2464.1 Prsentation du problme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2464.2 Initialisation de l'algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . 2464.3 valuation des individus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2474.4 Reproduction avec mutations . . . . . . . . . . . . . . . . . . . . . . . . . . 2474.5 Survie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2494.6 Suite du processus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250

    5. Choix des reprsentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2505.1 Population et individus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2505.2 Gnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2505.3 Cas d'un algorithme de rsolution de labyrinthe . . . . . . . . . . . 251

    6. valuation, slection et survie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2546.1 Choix de la fonction dvaluation . . . . . . . . . . . . . . . . . . . . . . . 2546.2 Oprateurs de slection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2556.3 Oprateurs de survie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256

  • 8pour les dveloppeurs - Concepts et implmentations en C#

    LIntelligence Artificielle

    7. Reproduction : crossover et mutation. . . . . . . . . . . . . . . . . . . . . . . . 2577.1 Crossover. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2577.2 Mutation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

    8. Domaines dapplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262

    9. Implmentation d'un algorithme gntique . . . . . . . . . . . . . . . . . . . 2649.1 Implmentation gnrique d'un algorithme . . . . . . . . . . . . . . . 264

    9.1.1 Spcifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2649.1.2 Paramtres. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2659.1.3 Individus et gnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2679.1.4 IHM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2699.1.5 Processus volutionnaire . . . . . . . . . . . . . . . . . . . . . . . . . 270

    9.2 Utilisation pour le voyageur de commerce . . . . . . . . . . . . . . . . 2759.2.1 Prsentation du problme . . . . . . . . . . . . . . . . . . . . . . . . 2759.2.2 Environnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2769.2.3 Gnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2799.2.4 Individus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2809.2.5 Programme principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2849.2.6 Rsultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

    9.3 Utilisation pour la rsolution d'un labyrinthe . . . . . . . . . . . . . 2879.3.1 Prsentation du problme . . . . . . . . . . . . . . . . . . . . . . . . 2879.3.2 Environnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2889.3.3 Gnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2959.3.4 Individus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2969.3.5 Programme principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3019.3.6 Rsultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302

    10. Covolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304

    11. Synthse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305

  • 9Table des matires

    Chapitre 5Mtaheuristiques d'optimisation

    1. Prsentation du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307

    2. Optimisation et minimums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3082.1 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3082.2 Le problme du sac dos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3082.3 Formulation des problmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3092.4 Rsolution mathmatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3112.5 Recherche exhaustive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3122.6 Mtaheuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

    3. Algorithmes gloutons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313

    4. Descente de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316

    5. Recherche tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

    6. Recuit simul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321

    7. Optimisation par essaims particulaires . . . . . . . . . . . . . . . . . . . . . . . 323

    8. Mta-optimisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325

    9. Domaines dapplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325

    10. Implmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32710.1 Classes gnriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32710.2 Implmentation des diffrents algorithmes . . . . . . . . . . . . . . . 329

    10.2.1Algorithme glouton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32910.2.2Descente de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32910.2.3Recherche tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33110.2.4Recuit simul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33210.2.5Optimisation par essaims particulaires . . . . . . . . . . . . . . 333

    10.3 Rsolution du problme du sac dos . . . . . . . . . . . . . . . . . . . . 33510.3.1Implmentation du problme . . . . . . . . . . . . . . . . . . . . . 33510.3.2Algorithme glouton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34310.3.3Descente de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34410.3.4Recherche tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34610.3.5Recuit simul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348

  • 10pour les dveloppeurs - Concepts et implmentations en C#

    LIntelligence Artificielle

    10.3.6Optimisation par essaims particulaires. . . . . . . . . . . . . . 35110.3.7Programme principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354

    10.4 Rsultats obtenus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356

    11. Synthse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360

    Chapitre 6Systmes multi-agents

    1. Prsentation du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

    2. Origine biologique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3642.1 Les abeilles et la danse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3642.2 Les termites et le gnie civil . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3662.3 Les fourmis et l'optimisation de chemins . . . . . . . . . . . . . . . . . 3672.4 Intelligence sociale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368

    3. Systmes multi-agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3683.1 L'environnement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3683.2 Les objets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3693.3 Les agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369

    4. Classification des agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3704.1 Perception du monde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3704.2 Prise des dcisions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3704.3 Coopration et communication . . . . . . . . . . . . . . . . . . . . . . . . 3714.4 Capacits de l'agent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372

    5. Principaux algorithmes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3735.1 Algorithmes de meutes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3735.2 Optimisation par colonie de fourmis . . . . . . . . . . . . . . . . . . . . 3745.3 Systmes immunitaires artificiels . . . . . . . . . . . . . . . . . . . . . . . 3765.4 Automates cellulaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377

    6. Domaines dapplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3796.1 Simulation de foules. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3796.2 Planification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3806.3 Phnomnes complexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380

  • 11Table des matires

    7. Implmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3817.1 Banc de poissons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381

    7.1.1 Les objets du monde et les zones viter . . . . . . . . . . . . 3827.1.2 Les agents-poissons. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3847.1.3 L'ocan. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3927.1.4 L'application graphique . . . . . . . . . . . . . . . . . . . . . . . . . . 3957.1.5 Rsultats obtenus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399

    7.2 Tri slectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4017.2.1 Les dchets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4017.2.2 Les agents nettoyeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4047.2.3 L'environnement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4087.2.4 L'application graphique . . . . . . . . . . . . . . . . . . . . . . . . . . 4127.2.5 Rsultats obtenus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416

    7.3 Le jeu de la vie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4177.3.1 La grille . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4187.3.2 L'application graphique . . . . . . . . . . . . . . . . . . . . . . . . . . 4217.3.3 Rsultats obtenus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424

    8. Synthse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426

    Chapitre 7Rseaux de neurones

    1. Prsentation du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429

    2. Origine biologique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430

    3. Le neurone formel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4323.1 Fonctionnement gnral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4323.2 Fonctions d'agrgation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4333.3 Fonctions d'activation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434

    3.3.1 Fonction "heavyside" . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4343.3.2 Fonction sigmode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4353.3.3 Fonction gaussienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435

    3.4 Poids et apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436

  • 12pour les dveloppeurs - Concepts et implmentations en C#

    LIntelligence Artificielle

    4. Perceptron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4374.1 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4374.2 Condition de linarit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438

    5. Rseaux feed-forward. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439

    6. Apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4406.1 Apprentissage non supervis . . . . . . . . . . . . . . . . . . . . . . . . . . . 4406.2 Apprentissage par renforcement . . . . . . . . . . . . . . . . . . . . . . . . 4426.3 Apprentissage supervis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442

    6.3.1 Principe gnral. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4426.3.2 Descente de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4436.3.3 Algorithme de Widrow-Hoff . . . . . . . . . . . . . . . . . . . . . . 4456.3.4 Rtropropagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445

    6.4 Surapprentissage et gnralisation . . . . . . . . . . . . . . . . . . . . . . 4476.4.1 Reconnatre le surapprentissage . . . . . . . . . . . . . . . . . . . 4486.4.2 Cration de sous-ensembles de donnes . . . . . . . . . . . . . 449

    7. Autres rseaux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4507.1 Rseaux de neurones rcurrents . . . . . . . . . . . . . . . . . . . . . . . . 4507.2 Cartes de Kohonen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4507.3 Rseaux de Hopfield . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451

    8. Domaines d'application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4518.1 Reconnaissance de patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4528.2 Estimation de fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4528.3 Cration de comportements . . . . . . . . . . . . . . . . . . . . . . . . . . . 452

    9. Implmentation d'un MLP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4539.1 Points et ensembles de points . . . . . . . . . . . . . . . . . . . . . . . . . . 4539.2 Neurone. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4579.3 Rseau de neurones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4599.4 IHM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4639.5 Systme complet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4639.6 Programme principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467

  • 13Table des matires

    9.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4689.7.1 Application au XOR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4689.7.2 Application Abalone . . . . . . . . . . . . . . . . . . . . . . . . . . . 4709.7.3 Amliorations possibles . . . . . . . . . . . . . . . . . . . . . . . . . . 472

    10. Synthse du chapitre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472

    Bibliographie

    1. Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475

    Sitographie

    1. Pourquoi une sitographie ?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479

    2. Systmes experts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479

    3. Logique floue. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481

    4. Algorithmes gntiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483

    5. Recherche de chemins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484

    6. Mtaheuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485

    7. Systmes multi-agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486

    8. Rseaux de neurones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488

    Annexe

    1. Installation de SWI-Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491

    2. Utilisation de SWI-Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492

    Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495

  • 159

    Chapitre 3

    Recherche de chemins

    Recherche de chemins1. Prsentation du chapitre

    De nombreux domaines font face un problme de recherche de chemins, ap-pel "pathfinding" en anglais. On pense tout d'abord aux GPS et aux logicielsde recherche d'itinraires (en voiture, en train, en transport en commun...),voire aux jeux vido dans lesquels les ennemis doivent arriver sur le joueur parle chemin le plus court.

    La recherche de chemins est en ralit un domaine bien plus vaste. En effet, denombreux problmes peuvent tre reprsents sous la forme d'un graphe,comme l'enchanement des mouvements dans un jeu d'checs.

    La recherche d'un chemin dans ce cas-l peut tre vue comme la recherche dela suite des mouvements faire pour gagner.

    Ce chapitre commence par prsenter les diffrents concepts de thorie desgraphes, et les dfinitions associes. Les algorithmes fondamentaux sont en-suite prsents, avec leur fonctionnement et leurs contraintes.

    Les principaux domaines dans lesquels on peut utiliser cette recherche de che-mins sont alors indiqus et un exemple d'implmentation des algorithmes enC# est prsent et appliqu une recherche de chemins dans un environne-ment en 2D.

    Le chapitre se termine par une synthse.

  • E

    dit

    ions

    EN

    I -

    All r

    ights

    rese

    rved

    160pour les dveloppeurs - Concepts et implmentations en C#

    L'Intelligence Artificielle

    2. Chemins et graphes

    Un chemin peut tre vu comme un parcours dans un graphe. Les principauxalgorithmes se basent donc sur la thorie des graphes.

    2.1 Dfinition et concepts

    Un graphe est un ensemble de nuds ou sommets (qui peuvent reprsenterpar exemple des villes) lis par des arcs, qui seraient alors des routes.

    Voici un graphe qui reprsente des gares et les liens qui existent entre ces gares(en train, sans changement) :

    Les gares de G1 G6 sont donc les nuds. L'arc allant de G5 G6 indique laprsence d'un lien direct entre ces deux gares. Il est not (G5, G6) ou (G6, G5)selon le sens voulu.

    Par contre pour aller de G1 G6, il n'y a pas de lien direct, il faudra passer parG4 ou G5 si on ne souhaite qu'un changement, ou par G2 puis G3 avec deuxchangements.

  • 161Recherche de cheminsChapitre 3

    Un chemin permet de rejoindre diffrents sommets lis entre eux par des arcs.Ainsi, G1-G2-G3-G6 est un chemin de longueur 3 (la longueur est le nombred'arcs suivis).

    On parle de circuit lorsqu'on peut partir d'un nud et y revenir. Ici, le graphecontient de nombreux circuits, comme G1-G4-G5-G1 ou G4-G5-G6-G4.

    L'ordre d'un graphe correspond au nombre de sommets qu'il contient. Notreexemple contient 6 gares, il s'agit donc d'un graphe d'ordre 6.

    Deux nuds sont dits adjacents (ou voisins) s'il existe un lien permettantd'aller de l'un l'autre. G5 est donc adjacent G1, G4 et G6.

    2.2 Reprsentations

    2.2.1 Reprsentation graphique

    Il existe plusieurs faons de reprsenter un graphe. La premire est la repr-sentation graphique, comme celle vue prcdemment.

    L'ordre et le placement des nuds ne sont pas importants, cependant on vachercher toujours placer les sommets de faon rendre le graphe le plus li-sible possible.

    Le graphe est dit orient si les arcs ont un sens, reprsentant par exemple desrues sens unique dans une ville. Si tous les arcs peuvent tre pris dans lesdeux sens, on dit alors que le graphe est non orient, ce qui est gnralementle cas de ceux utiliss pour la recherche de chemins.

    2.2.2 Matrice dadjacence

    Les reprsentations graphiques ne sont pas toujours trs pratiques, en particu-lier quand il s'agit d'y appliquer des algorithmes ou de les rentrer dans un or-dinateur.

    On prfre souvent utiliser une matrice, appele matrice d'adjacence.

  • E

    dit

    ions

    EN

    I -

    All r

    ights

    rese

    rved

    162pour les dveloppeurs - Concepts et implmentations en C#

    L'Intelligence Artificielle

    Remarque

    Une matrice est une structure mathmatique particulire qui peut tre vueplus simplement comme un tableau deux dimensions.

    Dans cette matrice, l'absence d'arc est reprsente par un 0, et sa prsence parun 1.

    Dans l'exemple des gares, on a donc une matrice de 6 par 6 (car il y a 6 gares) :

  • 163Recherche de cheminsChapitre 3

    On voit sur le graphe qu'il existe un lien entre G1 et G4. La case correspondantau trajet de G1 vers G4 contient donc un 1, tout comme celle de G4 G1 (letrajet est double sens). On a alors la matrice suivante :

    De mme, il existe un arc de G1 vers G2 et G5 mais pas vers G3 ou G6. Onpeut donc complter notre matrice :

  • E

    dit

    ions

    EN

    I -

    All r

    ights

    rese

    rved

    164pour les dveloppeurs - Concepts et implmentations en C#

    L'Intelligence Artificielle

    On fait de mme pour tous les autres nuds et les autres arcs :

    Il ne reste que la diagonale. Elle reprsente la possibilit d'aller d'un nud lui-mme, c'est ce qu'on appelle une boucle. Ici il n'y a pas de trajet direct allantd'une gare elle-mme, on remplit donc par des 0 cette diagonale.