Discussion :

[louis.hache]

Bonjour,

J'essaie d'apprendre par moi même l'intelligence artificielle en me basant sur le livre "Artificial Intelligence : a modern approach" par Russel & Norvig. Très bien, je m'enfile à peu près 400 pages tel un lecteur assidu mais je me demande si j'ai bien compris ce que j'ai lu alors je décide de faire des exercices. Mais voilà que ça cloche.

J'ai trouvé un exercice qui en gros dit :
Prenons un graphe non orienté ({A,B,C}, {(A,B),(B,C)} et {1,2} un set de couleur. Suggerez comment modéliser ce problème comme un problème de satisfaction de formule en logique propositionnelle (SAT). L'encodage doit être assez général pour marcher avec n'importe quel type de graph et nombre de couleurs. Montrez comment les algo DPLL & WalkSAT peuvent être appliqués blabla.

Très bien, j'ai quelques notions sur la logique propositionnelles, les CNF tout ça mais je ne vois pas comment modéliser ce problème du tout.

En vous remerciant d'avance,

Louis

[Franck Dernoncourt]

As-tu jeté un coup d'oeil au manuel de solution ?
http://qazviniau.files.wordpress.com...n-approach.pdf (enfin ce genre de liens tend à disparaître rapidement)

[louis.hache]

Merci beaucoup pour le lien, ça pourrait me servir.

Le seul problème est que je sors cet exercice de je ne sais plus quel cours d'une faculté quelconque dont je ne pourrais me souvenir et non du livre. J'ai du mal à visualiser la chose. Actuellement rien ne se déclenche dans mon cerveau brouillé donc ça m'intrigue encore plus.

[Franck Dernoncourt]

J'ai déjà croisé ce genre de problème, les slides en PJ te donneront peut-être des pistes.

[davcha]

Bonjour,

J'essaie d'apprendre par moi même l'intelligence artificielle en me basant sur le livre "Artificial Intelligence : a modern approach" par Russel & Norvig. Très bien, je m'enfile à peu près 400 pages tel un lecteur assidu mais je me demande si j'ai bien compris ce que j'ai lu alors je décide de faire des exercices. Mais voilà que ça cloche.

J'ai trouvé un exercice qui en gros dit :
Prenons un graphe non orienté ({A,B,C}, {(A,B),(B,C)} et {1,2} un set de couleur. Suggerez comment modéliser ce problème comme un problème de satisfaction de formule en logique propositionnelle (SAT). L'encodage doit être assez général pour marcher avec n'importe quel type de graph et nombre de couleurs. Montrez comment les algo DPLL & WalkSAT peuvent être appliqués blabla.

Très bien, j'ai quelques notions sur la logique propositionnelles, les CNF tout ça mais je ne vois pas comment modéliser ce problème du tout.

En vous remerciant d'avance,

Louis

C'est moi ou l'énoncé est incomplet ? Quel est le problème à modéliser ? 3-coloration ?

[Franck Dernoncourt]

Plus généralement http://en.wikipedia.org/wiki/Graph_coloring je pense, mais je laisse l'OP apporter des précisions.

[louis.hache]

Non non l'énoncé est correct, c'était un sujet d'examen en fait. C'est typiquement de la coloration de graphe.

[louis.hache]

Personne n'a donc une idée de modèle pour représenter ce problème ? Quels littéraux choix, quelle clauses, donc en fait quel modèle ? L'IA n'est pas du tout ma spécialité de base et j'ai du mal à trouver l'élément déclencheur.

[Franck Dernoncourt]

PJ ?

[louis.hache]

Merci pour ces réponses. Et oui, effectivement, c'est quasiment ça au niveau du sujet.