Suivez-nous sur X
|
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z,
ALL
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
Programmation : Scheme - les données
(Article écrit par Damien Guichard - avril 2004)
|
|
Scheme, ça donne - Partie 2
Rappel des bases du langage Scheme
Scheme est un langage de programmation élégant et expressif qui trouve de nombreuses applications dans
l'intelligence artificielle.
L'Amiga est depuis très longtemps équipé d'interpréteurs Scheme évolués et d'une étonnante compacité comme
Scheme.lha et SIOD.lha
qui conviendront à merveille pour tester les exemples qui suivent.
Un rapide rappel des commandes :
(define (succ n) (+ n 1)) ;; la définition de fonction "define"
(succ 0) ;; l'appel de fonction "(..)"
(define start 0) ;; la définition de variable "define"
(set! start 1) ;; l'affectation de variable "set!"
(define (min a b) (if (< a b) a b)) ;; la conditionnelle "if"
(begin (set! a b) (set! b c) c) ;; la séquence "begin"
|
Pour plus d'informations voir l'article précédent
dans Obligement n°43.
Plus de commandes
#t ;; le vrai
#f ;; le faux
(or a b) ;; le "ou" logique
(and a b) ;; le "et" logique
(abs x) ;; la valeur absolue
(quotient a b) ;; division entière: le quotient
(remainder a b) ;; division entière: le reste
(display "hello") ;; affiche un texte
(newline) ;; affiche un retour à la ligne
|
Par exemple la somme des "n" premiers entiers :
(define (integers-sum n)
(quotient (* n (+ n 1)) 2)
)
|
Les tableaux
(make-vector n) ;; renvoie un nouveau tableau indicé de 0 à n-1
(vector-ref a i) ;; renvoie l'élément d'indice "i" du tableau "a"
(vector-set! a i val) ;; affecte "val" à l'élément "i" du tableau "a"
(display a) ;; affiche le tableau "a"
|
Voici en plus une fonction qui permute les deux éléments "i" et "j" d'un tableau "a" :
(define (swap! a i j)
(define tmp 0)
(set! tmp (vector-ref a j))
(vector-set! a j (vector-ref a i))
(vector-set! a i tmp)
)
|
Et aussi une qui crée un tableau-interval qui contient tous les entiers de "a" à "b" :
(define (vector-interval a b)
(set! b (+ b 1))
(define result (make-vector (- b a)))
(define i 0)
(define (loop)
(if (< a b)
(begin
(vector-set! result i a)
(set! i (+ i 1))
(set! a (+ a 1))
(loop)
)
)
)
(loop)
result
)
|
Le moteur d'intelligence artificielle
C'est en fait une routine qui teste toutes les permutations possibles sur un ensemble d'éléments. De nombreux problèmes
mettent en jeu un échantillon d'éléments et une règle qui indique quelles permutations sont valides.
Ce qu'il nous faut c'est donc une routine qui, étant donnés un échantillon et une règle, affiche toutes les permutations valides.
L'échantillon est représenté par le tableau "the-array".
La règle est représentée par la fonction "partial-solution?".
(define (total-solution the-array partial-solution?)
(define (found-solution)
(display the-array)
(newline)
)
(define (search-solution)
(define i top)
(define (loop)
(if (< i (vector-length the-array))
(begin
(swap! the-array i top)
(if (partial-solution? the-array top)
(begin
(set! top (+ top 1))
(if (= top (vector-length the-array))
(found-solution)
(search-solution)
)
(set! top (- top 1))
)
)
(swap! the-array i top)
(set! i (+ i 1))
(loop)
)
)
)
(loop)
)
(define top 0)
(search-solution)
)
|
Comment procède cette routine ?
C'est en fait plus simple qu'il n'y paraît :
- On "swap!" deux éléments, et on teste la règle.
- Si la règle est encore vérifiée, alors on cherche l'élément suivant.
- Sinon on "swap!" à nouveau les deux éléments pour restaurer l'état antérieur, puis on retourne à l'étape 1.
- Quand on a trouvé tous les éléments on affiche le tableau avec "found-solution".
Ce moteur peut maintenant être réutilisé pour toutes sortes de problèmes de permutation.
Le problème des 8 reines
Il consiste à placer 8 reines sur un échiquier sans qu'aucune soit menacée de prise.
La règle qui valide une permutation des reines est donc une fonction qui renvoie vrai seulement si aucune reine est menacée.
L'échantillon est le tableau "the-array" qui contient la rangée de chaque reine, "top" est le nombre de colonnes à examiner :
(define (partial-queens-solution? the-array top)
(define q 0)
(define x 0)
(define dy 0)
(define result #t)
(set! q (vector-ref the-array top))
(set! x (- top 1))
(define (loop)
(if (>= x 0)
(begin
(set! dy (- q (vector-ref the-array x)))
(if (or (= (- x top) dy) (= (- top x) dy))
(set! result #f)
(begin (set! x (- x 1)) (loop))
)
)
)
)
(loop)
result
)
|
La fonction "queens-solutions" appelle le moteur de recherche avec l'échantillon et la règle appropriés au problème des "n" reines :
(define (queens-solutions n)
(total-solution
(vector-interval 1 n) partial-queens-solution?)
)
|
Le problème des 8 reines a 92 solutions :
Le problème de la pyramide
Il s'agit de créer une pyramide de chiffres consécutifs telle que chaque chiffre est la différence de ses deux
chiffres inférieurs, voici par exemple une pyramide à 4 étages :
Et maintenant la définition de la règle adéquate :
(define (partial-pyramid-solution? a top)
(define level 1)
(define (loop)
(if (<= (integers-sum level) top)
(begin (set! level (+ level 1)) (loop))
)
)
(loop)
(if (= top (integers-sum (- level 1)))
#t
(=
(vector-ref a (- top level))
(abs
(- (vector-ref a top)
(vector-ref a (- top 1))))
)
)
)
|
Il ne reste plus qu'à créer l'échantillon et appeler le moteur de recherche "total-solution" :
(define (pyramid-solutions n)
(total-solution
(vector-interval 1 (integers-sum n))
partial-pyramid-solution?)
)
|
Voyons ce que ça donne à 5 étages, ça peut prendre quelques longues minutes de calcul, mais ça vaut le coup :
:=> (pyramid-solutions 5)
#(5 4 9 7 11 2 8 1 12 10 6 14 15 3 13)
#(5 9 4 2 11 7 10 12 1 8 13 3 15 14 6)
()
|
Il y n'a qu'une seule solution (et son symétrique bien sûr) :
5
4 9
7 11 2
8 1 12 10
6 14 15 3 13
|
En fait, à partir de 6 étages le problème de la pyramide n'a plus de solution.
Pour aller plus loin
Les interpréteurs "Scheme.lha", "SIOD.lha", "scm.lha" et "UMBScheme212.lha", sont tous disponibles sur Aminet dans le répertoire /Dev/Lang.
Deux bons textes d'introduction à Scheme :
mitpress.mit.edu/sicp/
www.scheme.com/tspl2d/index.html
Plus de documentations sur Scheme :
www.schemers.org
www.cs.indiana.edu/scheme-repository/home.html
www.swiss.ai.mit.edu/projects/scheme
|
