Algorithmie avancée

• Sites : bdupont.up8.site et jj.up8.site
• Mails : benjamin.dupont02(at)univ-paris8.fr et jj(at)up8.edu
• Mercredi 9/11 -> Choix des projets (monomes, pas 2 personnes qui font le même projet)

Notation

• Note final basé sur un projet individuel
  • Projet en lui-même
  • Rapport du projet
  • Soutenance sur la semaine 10
• TPs pas noté
  • Peut-être le premier, mais pas sûr
  • Rendre le premier TP par mail, les autres c’est pas sûr qu’ils seront à rendre
  • Rendre le TP sur les droites discrètes pour le 19/10

Cours

Tris

Exemple d’implantation de ces algorithmes ici

Complexité quadratique (\Theta(n^{2}))

Tri à bulle

f(n) = \Theta(n^{2}) si f\frac{n}{n^{2}} est bornée

Taille n :
\sum\limits_{k=1}^{n}k=\frac{n(n+1)}{2}=(n-1)+(n-2)+\dots+1

Tri par insertion

Complexité \Theta(nlog(n))

1+2+\dots+(n-1)=\frac{n(n+1)}{2}

Tri rapide et tri fusion

n base10 => binaire
_ _ _ _ _ _ \frac{n}{2}
_ _ _ _ _ 0 \frac{n}{4} (ou 1 à la place de 0)

n sur k bits
2^{k-1} \leq n \leq 2^{k}
\begin{aligned}a^{b} =& e^{ln(a)b} \\\ &e^{(h-1)ln(2)} \leq n \leq e^{ln(2)k} \\\ &(k-1)ln(2) \leq ln(n) \leq ln(2)k \\\ &(k-1) < \frac{ln(n)}{ln(2)} \leq k \end{aligned}

Suite de Fibonacci

Méthode de récursivité lourde \approx \Theta(2^{n})

Soit C_{n} k nombre d’opérations pour calculer F(n)
C_{n} = (1 +) C_{n-1} + C_{n-2}, la complexité c’est grosso-modo Fibonacci + 1, donc
C_{n} \simeq F(n)
Donc, F(n) = \frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^{n} + (\frac{1-\sqrt{5}}{2})^{n}) : ça fonctionne jusqu’à une certaines valeurs et après ça ne fonctionne plus.

Calcul matricielle

\begin{pmatrix} 1 & 1 \\\ 1 & 1 \end{pmatrix} avec \begin{pmatrix} 1 & 2 \\\ 3 & 4 \end{pmatrix} donne : \begin{pmatrix} 3 & 3 \\\ 7 & 7 \end{pmatrix}

La matrice est cachée dans ce système :
\left[\begin{array}{ll} F(n) = F(n-1) + F(n-2) \\\ F(n-1) = F(n-1) \end{array}\right.

Donnant :
\begin{array}{ll} \quad\quad F(n) = \\\ F(n-1) = \end{array} \begin{pmatrix} 1 & 1 \\\ 1 & 0 \end{pmatrix} \text{ avec } \begin{pmatrix} F(n-1) \\\ F(n-2) \end{pmatrix} \text{ donne } \begin{pmatrix} F(n-1) & F(n-2) \\\ F(n-1) \end{pmatrix}

Exponentiation rapide

a^{n} puissance rapide

si (n == 1)
	retourne a
sinon
	si n % 2 == 0
		x = puissance_rapide(a, n / 2)
		retourne x * x
	sinon
		x = puissance_rapide(a, n / 2)
		retourne a * x * x

a^{n} A^{n} puissance rapide

si (n == 1)
	retourne A
sinon
	si n % 2 == 0
		x = puissance_rapide(A, n / 2)
		retourne multiplication(x, x)
	sinon
		x = puissance_rapide(a, n / 2)
		retourne a * x * x

Triangle de Pascal (avec coefficient binomiaux) :
\begin{pmatrix} n \\\ k \end{pmatrix} = \begin{pmatrix} n - 1 \\\ k - 1 \end{pmatrix} + \begin{pmatrix} n - 1 \\\ k \end{pmatrix}

De la droite discrète

jj.up8.site/droites

Attention, j’ai probablement fait des erreurs en recopiant, de toute façon le prof l’a noté en gros sur son site

Table des matières

• Définition
• De l’évidence à la référence
• Améliorations
• PGCD
• Chercher ailleurs et autrement
  • “Sous les pavés”
  • Euclide et applications
    • Dulucq et Bourdin
    • Green et Pitteway
    • Berstel
  • Plages (Spans)
  • Récapitulation et algorithme rapide

Définition

En maths, une droite est un objet définie car il passe par 2 points et qu’il est infini dans les 2 sens.

En info, c’est un ensemble de pixels qui ont la qualité d’être proche de la droite réelle relativement proche de la droite réel (celle des maths), ces pixels forment un chemin biconnexe.

void droite (int x0, int y0, int x1, int y1) {
  for (int x = x0; x <= x1; x++) {
     flat yf = (float) (x - x0) * (y1 - y0);
     yf /= (x1 - x0);
     yf += y0;
     int y = (int) (yf + .5);
     affiche(x,y);
  }
}

\frac{x-x_{p}}{x_{q} - x_{p}} = \frac{y - y_{p}}{y_{q} - y_{p}}
y = y_{p} + \frac{(x-x_{p})(y_{q} - y_{p})}{x_{q} - x_{p}}

De l’évidence à la référence

|y-y_{n}| > |y+1 - y_{2}| \Rightarrow y++
y_{2} = \frac{x\times dy}{dx}
\underbrace{\left| y - \frac{x\times dy}{dx} \right|}_A > \underbrace{\left| y+1 - \frac{x\times dy}{dx} \right|}_B \Rightarrow y++
On a donc A > B \Rightarrow 0 > A+B

Il y ça aussi :
A + B < 0 \Rightarrow y++
2y + 1 - \frac{2x\times dy}{dx} < 0 \Rightarrow y++
\underbrace{2y\times dx + dx - 2x \times dx}_{\text{delta(x, y)}} < 0 \Rightarrow y++

delta(x+1, y)   = delta(x, y) - 2dy
delta(x+1, y+1) = delta(x, y) - 2dy - 2dx

En C :

void droitebr(int dx, int dy) {
    int delta, incD, incH;
    incH = dy << 1;
    delta = incH - dx;
    incD = delta - dx;
    for (int x = 0, y = 0; x <= dx; ++x) {
        affiche(x, y);
        if (delta > 0) {
            y++;
            delta += incD;
        } else {
            delta = incH;
        }
    }
}

Améliorations

Optimisation de l’algorithme en coupant en 2 le problème, et donc en faisant un pas de 2 dans la boucle-for. Pareil avec un pas de 3 et un pas de 4.

• Rappel pour la droitebr :
  \begin{cases} \text{delta}(x, y) = 2xdy - 2ydx - dx \\\\ \text{si delta} >= 0 \text{ alors } y++ \end{cases}

Alors pour le pas de 2 :
\text{delta}(x+2, y) = 2xdy + 2ydx + 4dy - dx
delta(x+1, y) = delta(x + 2, y) - 2dy

if (delta >= 0) {
	if (delta - 2dy >= 0) {

Pour le pas de 3, c’est toujours la même équation, on adapte juste l’équation avec un x+3, par contre il peut pas avoir 2 partie oblique consécutives (conséquence de propriété, cf. plus bas dans le cours).

On fait *4 pour y parce que on a un pas de 2 pour x, donc x croit 2 fois plus vite, donc pour y il faut *2 aussi, donc *4

Il y a ensuite le pas adaptaif, le prof explique ça comme quand on monte une pente, on fait des plus grands pas quand on monte, bah là c’est pareil mais à l’envers. Dans notre cas de la droite, on regarde si la pente est importante, dans ce cas on fait des petits pas, et si la pente est petite genre plate, on fait des grands pas.

PGCD

Angel et Morrison disent qu’ils peuvent tout simplifier et aller plus vite.
Avec y = \frac{x \times dy}{dx}, ils se demandent si ils pourrait pas simplifier en calculant le PGCD, par exemple si y = \frac{22}{6} = \frac{11}{3}.
Malheureusement 60% du temps on a un PGCD qui vaut 1, mais 40% du temps le PGCD c’est 10.

Chercher ailleurs et autrement

“Sous les pavés”

Citation de Wu

Sur 8 mouvements possible, seulement 2 sont utilisés

There are at most two basic directions and these ones can differ only by unity, modulo eight.

Sur ces 2 mouvements, l’un apparaît toujours de façon solitaire, l’autre apparaît de façon groupé (le prof appelle ça une plage)

One of these values always occurs “singly”.

Le pas solitaire est aussi bien répartie que possible, c’est à dire qu’ils peuvent pas être tous regroupés au même endroit, ils doivent être dispersés (autrement dit : les plages ont toutes la même longueur à 1 près)

Successive occurrences of the principal direction occurring singly are as uniformly spaced as possible.

Euclide et applications

Dulucq et Bourdin

Donc par exemple :

• |w| = dx

• |w|_{1} = dy

• |w|_{0} = dx-dy

• Nombre de plages = dy

• Longue plages = \begin{cases} \frac{dx-dy}{dy} \\\\ \frac{dx-dy}{dy} + 1 \end{cases}

  • Seulement des plages courtes : dyx \frac{dx-dy}{dy} \Rightarrow 0 utilisés
    Il en reste dx-dy - dyx \frac{dx-dy}{dy}, qui est le nombre de plages longues

  • \frac{dx-dy}{dy} \texttt{-=} \frac{dx}{dy}, le nombre de plages courtes est \frac{dx-dy}{dy}

• \varphi_{n}(0) = O^{n+1}1

• \varphi_{n}(1) = O^{n}1

• w(dxdy)=\varphi(w(p-q))

• n = \frac{dx-dy}{dy} ; p = dy ; q = dy - \frac{dx}{dy}

• \varphi_{m}(O) = 0\ 1^{m}

• \varphi_{m}(1) = 0\ 1^{m+1}

• w(x+dy) = \Psi_{n}(w(p, q))

• m = \frac{dy}{dx+dy} ; p = dx-dy ; q = dy-dy \mod (dx-dy)

Green et Pitteway

droite (dx, dy) {
	dx -= dy;
	s = "0";
	t = "1";
	while (dx != dy) {
		if (dx > dy) {
			dx -= dy;
			t = s . t;
		}
		else {
			dy -= dx;
			s = s . t;
		}
	}

	return ( s . t ) ^ dx;
}

Berstel

W   = 00100010001
W'  = 01000100010
W'' = 10010001000

C’est conjugés

• \exists f ; w'f = fw
• \exists g ; w'g = gw'
• |f| = l
• dy \times l + \frac{dx}{2} \equiv 0 (dx)
• 3\Delta l + \frac{11}{2} mod 11 = 0
• (3l + 5) mod 11 = 0
• l peut être égale à 2, -9, etc… le plus intéressant étant le plus petit, soit 2

Fraction continue
\frac{3}{11}= [0, 3, 1, 2], ça peut s’écrire aussi comme ça : a+\frac{1}{b+\frac{1}{c+\frac{1}{d+\frac{1}{e+\frac{1}{f+\frac{1}{g+\frac{1}{h+\frac{1}{i+\frac{1}{j+\frac{1}{k+\frac{1}{\dots}}}}}}}}}}},
Soit [a, b, c, d, e, f, g, h, i, j, k]

• \frac{dx}{dy}\Rightarrow 0

• \frac{v}{u} = \frac{1}{\frac{u}{v}} = \frac{1}{\frac{u}{v} + \frac{\frac{u}{v}}{v}}

• w_{0} = 0

• w_{1} = O^{u_{i-1}}1

• w_{2} = w^{u}\_{i-1} w_{i-2}, i impair

• w_{3} = w_{i-2} \times w^{u}_{i-1}, i pair

• w_{0} = 0

• w_{1} = 001

• w_{2} = 0001

• w_{3} = 00010001001

Plages (Spans)

• w_{0} = 0
• w_{dx} = 1
• w_{i} = w_{dx}\dots

\Rightarrow Symétrie interne

• w_{i}(u, v) = w_{v}(u, u-v) sauf pour w_{0} et w_{n} (le premier et le dernier)
  2dy > dx

Récapitulation et algorithme rapide

• PGCD
• Pas de 2
• Symétrie interne
• Plage
• Partie basse de l’octant
  \approx 20x \text{ bresenham}

Graphes : parcours et plus court chemin

Définition, notations

Un graphe est une structure de données non linéaires constituée de 2 types d’objets :

• des noeuds, ou sommets, contenus dans un ensemble S
• des arêtes, contenues dans un ensemble A, qui retient des sommets entre eux

Un graphe est dit orienté si toutes les arêtes sont équipées d’une certaine direction, indiquée par une flèche. Dans un graphe orienté, chaque arête a un sommet source et un sommet but (target)

Un graphe est dit pondéré si toutes les arêtes sont étiquetées par un nombre, encadrant généralement la distance entre 2 sommets. Ce nombre est appelé poids.

Dans ce cas, nous allons nous intéresser principalement à des graphes orientés et pondérés, par des poids entiers positifs (la positivité est indispensable pour l’algorithme de Dijkstra)

Parcours

Il existe plusieurs manières de parcourir / d’explorer un graphe, nous allons en voir 2 principales

Parcours en profondeur

• On part d’un sommet src = 1 à partir duquel on explore
• 1. On va créer une structure de pile (LIFO, Last In First Out) dans laquelle on va stocker les sommets parcourus
• 2. On cherche un voisin de l’élément en tête de pile (n’importe lequel, le premier que l’on rencontre), que l’on ajoute en tête de pile, et on répète tant que le nouveau sommet en tête de pile a toujours des voisins non utilisés
     
• 3. Lorsque ce n’est plus le cas, on dépile l’élément en tête, et on recherche un autre voisin du sommet précédent, et on l’ajoute en tête s’il y en a un ; sinon on dépile aussi, etc.
     
• On s’arrête lorsque la pile est vide. Au final, tous les sommets qui ont été stockés dans la pile ont été parcourus en partant de src = 1

Remarque

Évidemment, on parle de voisins non-déjà-parcourus, pour savoir ça, par exemple, on stoque dans un tableau de booléens pour savoir si le sommet à déjà été parcourus ou non.

Parcours en largeur

• On part d’un sommet src = 1 à partir duquel on explore
• 1. On va créer un structure de file (LIFO) dans laquelle on place src
• 2. On ajoute ensuite tous les voisins de src dans la file (idem, dans n’importe quel ordre), puis on supprime l’élément src
• On recommence ensuite avec le premier voisin en tête de file, on ajoute ses voisins à la fin, etc.
  
• 3. Si on arrive sur un sommet qui n’a plus de voisins non-déjà-parcouru, on le supprime de la file
     
• Le parcours s’arrête lorsque la file est vide. Tous les sommets qui ont été stockés dans la file ont été parcourus en partant de src = 1

Remarque

• Pour un graphe non-orienté, le graphe est connexe si et seulement si tous les sommets sont exploités à partir d’un parcours partant de n’importe quel sommet
• On peut dessiner l’ordre couvrant dans ce cas en gardant trace du parent à chaque ajout d’un sommet dans la file

Algorithme de Dijkstra

C’est un algorithme permettant de trouver le plus court chemin entre 2 sommets dans un graphe pondéré

Paramètres de l’algorithme :

• un graphe orienté pondéré avec des nombres positifs
• un sommet src à partir du quel on va renvoyer un tableau sous la forme

Avec d_{i} la distance de src au sommet s_{i} la plus petite

Initialisation

On crée un tableau de taille n qu’on remplit avec :

• INF/9999 pour les sommets différents de src
• 0 pour src

Traitement

Commençons par traiter le sommet src et tous ses arcs sortants
On va regarder toutes les arêtes sortantes de a, dans un ordre quelconque

• Arc de 0 vers 2, longueur 18, qui est mieux que la valeur précédente INF dans dist[2]
  \Rightarrow On change la valeur dist[2] en 18.
• Arc de 0 vers 4, longueur 3
  \Rightarrow On change la valeur dist[4] en 3.

• On va ensuite choisir un autre sommet
  • Peut on prendre n’importe lequel des deux rencontrés ? NON!!
  • \Rightarrow L’algorithme de Dijkstra impose de choisir celui qui est situé à la plus petite distance \rightarrow ici 4 !
• On traite donc 4 :
  • L’arc 4 \rightarrow 3 de longueur 2 permet de mettre 5 = dist[4] + 2 dans dist[3]
  • L’arc 4 \rightarrow 1 de longueur 10 permet de mettre 13 = dist[4] + 10 dans dist[1]
    À ce stade :

• On recomence avec le sommet non traité qui a la plus petite distance : 3
  • L’arc 3 \rightarrow 1 de longueur 1 permet de découvrir un chemin de longueur 6 = \textbf{dist[3] + 1} de 0 vers 1, qui est meilleur que le 13 précédent \Rightarrow on change donc dist[1] en 6

• On traite ensuite 1 :
  • L’arc 1 \rightarrow 0 permet de découvrir un chemin de longueur 14 de a vers a
    \Rightarrow Pas meilleur que le 0 précédent, donc on ne change rien
  • L’arc 1 \rightarrow 2 permet de découvrir un chemin de longueur 10 de a vers c, mieux que le 18 précédent
• On traite ensuite 2 :
  • Pas d’arc sortant \Rightarrow aucune modification
• On a alors traité tous les sommets, l’algorithme s’arrête et notre résultat est :

Commentaires

Pour savoir quels sommets ont étés parcourus ou non, on va initialiser un tableau de booléens (comme dit précédemment) contenant des 0, et on change la valeur à 1 lorsque le sommet est traité. Avant de traiter un nouveau sommet, il faut donc bien vérifier qu’il est toujours à 0 dans ce tableau.

• Comment sélectionner le sommet à la plus petite distance pour le traiter juste après ? Il y a plusieurs possibilités :
  • On peut écrire une fonction minDistance qui parcourt les sommets adjacents et sélectionne celui de plus petit poids

Exemple

#include <stdlib.h>

#define INF 9999

// S'il manque des trucs dans le code, c'est dans les exemples plus bas.

/* Fonction permettant de trouver le sommet à plus petite distance
parmis les sommets pas encore parcourus, sans utiliser de pile de priorité */
int minDistance(int dist[], int access[]) {
    int min = INF, min_index;
    int i;
    for (int i = 0; i < MAX_NOEUD; i++)
        if (access[i] == 0 && dist[i] <= min)
            min = dist[i], min_index = i;
    return min_index;
}

// TODO: Faire une fonction poour récupérer le poids? idk

/* Algorithme de Dijkstra */
void dijkstra(graphe *g, int src) {
    int n = g->vertices;

    int *dist = malloc(n * sizeof(int));
    int *acces = malloc(n * sizeof(int));

    int i, j, count;
    for (i = 0; i < n; i++) {
        dist[i] = INF;
        acces[i] = 0;
    }

    dist[src] = 0;
    for (count = 0; count < n - 1; count++) {
        int u = minDistance(dist, acces);
        acces[u] = 1;
        for (j = 0; j < n; j++) {
            if ((acces[j] == 0) && poids(/* u->j */) != 0 && dist[u] != INF &&
                dist[u] + poids(/* u->j */) < dist[j]) {
                dist[j] = dist[u] + poids(/* u->j */);
            }
        }
    }
}

• Sinon, il faut stocker les sommets adjacents dans une structure adaptée appellée file de priorité.
  C’est une file dans laquelleles tâches de plus petites valeur enfiler -> 16 15 12 5 -> défiler

Implémentation possibles :

1. Un tableau

   • Enfiler : Rajouter à la fin du tableau
   • Défiler : Parcourir toutes les tâches jusqu’à trouver le minimum.

2. Un tableau trié

   • Défiler : Retirer l’élément au début du tableau qui est le minimum
   • Enfiler : Il faut trouver où insérer l’élément à la bonne place

3. (Mieux) Un tas binaire
   C’est un arbre binaire presque complet (chaque niveau est rempli complètement sauf éventuellement le dernier) dans lequel chaque tâche est plus prioritaire que ses enfants
   -> La tâche la plus prioritaire (le minimum est la racine)
   

• Enfiler : On insère où il y a une place de libre, en veillant à garder la propriété de tas linéaire
  • si la tâche est moins prioritaire, on laisse
  • sinon, on échange avec le parent et on répète tant qu’il le faut
    
• Défiler :
  • On enlève l’évènement la plus prioritaire qui est à la racine
  • On place le dernier élément en bas à droite à la racine et on compose : \begin{cases} \text{racine} \\\\ \text{racine}(\text{fils}-\text{g}) \\\\ \text{racine}(\text{fils}-\text{d})\end{cases}
    Et on met le plus petit en haut
    
    Ces 2 opérations sont en \Theta(log(n)) : elles se font sur la hauteur d’une branche

Matrices d’adjacences

On peut encoder tout un graphe (orienté ou non, pondéré ou non), par une matrice de taille n\times n appelée matrice d’adjacence.
M[i][j] := \begin{cases} 1 \text{ s'il y a une arête de i vers j} \\\\ 0 \text{ sinon}\end{cases}

Remarque: il y a autant de 1 que de nombre d’arêtes dans le graphe.

On peut aussi définir une matrice d’adjacence pour un graphe non-orienté :

• Dans ce cas, s’il y a une arête de i vers j, il y en a aussi une de j vers i
  \Rightarrow M[i][j] = M[j][i] (la matrice d’ordonnance est symétrique)
  

Remarque: il y a 2x le nombre d’arêtes que de 1.

• Idem pour un graphe pondéré :
  \Rightarrow M[i][j] = \begin{cases} \text{poids(i}\rightarrow\text{j) s'il y a une arête de i vers j} \\\\ 0 \text{ sinon}\end{cases}
  

Remarque: nombre de coefficients non nuls vaut le nombre d’arêtes

#define MAX_NOEUD 15

typedef struct graphe {
    int vertices;
    int adj[MAX_NOEUD][MAX_NOEUD];
} graphe;

/* Fonction qui crée un graphe vide (sans arêtes) à n sommets. */
graphe *newgraph(int n) {
    graphe *grph;
    grph = malloc(sizeof(*grph));
    if (grph == NULL) {
        fprintf(stderr, "Erreur : Probleme creation Graphe.\n");
        exit(EXIT_FAILURE);
    }
    grph->vertices = n;
    int i, j, w;
    float v;
    srand(time(NULL));
    for (i = 0; i < MAX_NOEUD; i++) {
        for (j = 0; j < MAX_NOEUD; j++) {
            grph->adj[i][j] = 0;
        }
    }
    return grph;
}

/* Affiche le nombre de sommets et la matrice d'adjacence */
void display(graphe *grph) {
    printf("Nombre de sommets : %d. \n", grph->vertices);
    printf("Matrice d'adjacence : \n");
    int i, j;
    for (i = 0; i < MAX_NOEUD; i++) {
        for (j = 0; j < MAX_NOEUD; j++) {
            printf("%d", grph->adj[i][j]);
            printf(j < MAX_NOEUD - 1 ? "\t" : "\n");
        }
    }
}

/* Ajoute une arête d'un sommet i vers un sommet j (avec poids) */
void add_edge_weight(graphe *grph, int i, int j, int weight) {
    grph->adj[i][j] += weight;
}

/* Ajoute une arête d'un sommet i vers un sommet j (sans poids) */
void add_edge(graphe *grph, int i, int j) { grph->adj[i][j] += 1; }

/* Supprime une arête (avec ou sans poids) de i vers j */
void remove_edge(graphe *grph, int i, int j) {
    if (grph->adj[i][j] == 0) {
        printf("Il n'y a pas d'arête à supprimer. ");
    } else {
        grph->adj[i][j] = 0;
        printf("Arête de %d vers %d supprimée. \n", i, j);
    }
}

Propriété (matrice adjacence)

Si G est un graphe (non) orienté de matrice d’adjacence A, le nombre de chemins de longueur n d’un sommet i vers un sommet j est égal au coefficient (i, j) de la matrice A^{n}

Ceci fournit un autre algo de parcours/plus court chemin…

• On calcule toutes les puissances successives A^{k} (k \geq 1) de A par exponentiation rapide, et on arrête si on trouve un entier n tel que \begin{cases} A^{n}(i, j) \neq 0 \\\\ A^{n}(i, j) = 0 \quad \forall \ k < n \end{cases}

Listes d’adjacences

Un graphe à n sommets peut aussi être représenté par un tableau de n listes contenant chacune les successeurs en question.

En C, on va représenter ces listes par des listes chaînées

Sachant qu’on veut aussi accéder au poids des arêtes, on va encoder un noeud d’une liste d’adjacence par :

typedef struct nodeAdjList {
    int target;
    int weight;
    struct nodeAdjList *next;
} nodeAdjList;

typedef struct AdjList {
    struct nodeAdjList *head;
} AdjList;

On peut ensuite représenter un graphe comme suit :

typedef struct graphe {
    int vertices;
    struct AdjList *array;
} graphe;

\Rightarrow Encodant le nombre de sommets et un tableau de listes d’adjacences

/* Fonction qui crée un graphe vide (sans arêtes) à n sommets. */
graphe *newgraph(int n) {
    graphe *grph = malloc(sizeof(*grph));
    grph->vertices = n;
    grph->array = (AdjList *)malloc(n * sizeof(struct AdjList));
    for (int i = 0; i < n; ++i)
        grph->array[i].head = NULL;
    return grph;
}

/* Ajoute une arête avec un poids */
void add_edge(graphe *grph, int src, int target, int weight) {
    if (weight == 0)
        return;
    nodeAdjList *Node = new_nodeAdjList(target, weight);
    Node->next = grph->array[src].head;
    grph->array[src].head = Node;
}

/* Fonction qui affiche une liste d'adjacence */
void print_adjlist(struct graphe *grph) {
    int v;
    for (v = 0; v < grph->vertices; v++) {
        nodeAdjList *temp = grph->array[v].head;
        printf("\n Liste d'adjacence de %d : \n head ", v);
        while (temp != NULL) {
            printf("-> (%d, %d)", temp->target, temp->weight);
            temp = temp->next;
        }
        printf("\n");
    }
}

/* Génération d'un graphe aléatoire, en stockant les poids des arêtes qu'on
 * ajoute dans un tableau n*n */
graphe *remplirgraphe(int n) {
    graphe *grph = newgraph(n);
    int i, j, w, num, max;
    float v, taux;
    max = n * n;
    taux = 25.0;
    num = n / 10;
    while (num > 1) {
        num /= 5;
        taux /= 3.0;
    }
    taux /= 100.0;
    srand(time(NULL));
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            v = (float)rand() / (float)RAND_MAX;
            add_edge(grph, i, j, v < taux ? (int)(v * 100.) : 0);
        }
    }
    return grph;
}

Remarques post-TP

La définition de graphe avec une matrice d’adjacence de taille MAX_NOEUD * MAX_NOEUD n’est pas optimale.

• soit on définit MAX_NOEUD très grand dès le départ
  \Rightarrow beaucoup de coefficients non utilisés
• sinon on change la valeur de la variable globale

Une manière meilleure

typedef struct graph {
    int vertices; // nb sommets
    int **adj;
} graphe;

Dans new_graph, il faut allouer la taille qu’il faut pour la matrice d’adjacence :

grph->vertices = m;
grph->adj = malloc(n * sizeof(int *));
for (int i = 0; i < n - 1; i++) {
    grph->adj[i] = malloc(n * sizeof(int));
}

Il faut écrire une fonction en plus pour libérer la mémoire.

Parcours en largeur, dijkstra, correction TP

void accessibles(graphe *grph, int src) {
    int *vus = malloc(grph->vertices * sizeof(int));
    int k;
    for (k = 0; k < grph->vertices; k++)
        vus[k] = 0;
    fifo *aVisiter = new_fifo();
    vus[src] = 1;
    push(aVisiter, src);
    while (aVisiter->taille != 0) {
        int i = take_first(aVisiter);
        for (int j = 0; j < grph->vertices; j++) {
            if (grph->adj[i][j] != 0 && vus[j] == 0) {
                vus[j] = 1;
                push(aVisiter, j);
            }
        }
        defiler(aVisiter);
    }
    print_acc(vus, grph->vertices, src);
    free(aVisiter);
    free(vus);
}

void dijkstra(graphe *grph, int src) {
    int n = grph->vertices;
    int *dist = malloc(n * sizeof(int));
    int *access = malloc(n * sizeof(int));
    int i, j, count;
    for (i = 0; i < n; i++) {
        dist[i] = INF;
        access[i] = 0;
    }
    dist[src] = 0;
    for (int k = 0; k < n - 1; k++) {
        int u = minDistance(grph, dist, access);
        access[u] = 1;
        for (j = 0; j < n; j++) {
            if (access[j] == 0 && grph->adj[u][j] != 0 &&
                dist[u] + grph->adj[u][j] < dist[j]) {
                dist[j] = dist[u] + grph->adj[u][j];
            }
        }
    }
    print_dist(dist, n, src);
    free(dist);
    free(access);
}

Le coefficient grph->adj[u][j] représente le poids d’une arête qui va de u vers j dans grph. On peut donc adopter aisément cet algorithme pour d’autres implémentations de graphes pour peu que l’on sache testéer s’il y a une arête de i vers j dans un graphe et en récupérer son poids.

int is_edge_in_adjlist(graphe *grph, int i, int j) {
    int test = 0;
    noeudListeAdj *n = grph->array[i].head;
    while (n != NULL && test == 0) {
        if (n->but == j)
            test = n->poids;
        n = n->suivant;
    }
    return test;
}

Ainsi, dans les algos précédents, il suffit de remplacer grph->adj[u][j] par is_edge_in_adjlist(grph, u, j) pour définir Dijkstra sans file de priorité.

Représentation par triplet

Supposons que l’on ait un graphe G à 15 sommets et une seule arête 0\ \underrightarrow{10}\ 1
Si on utilise une matrice d’adjacence pour représenter G, on va stocker 15 \times 15 + 225 coefficients dont… 224 zéros !
Or, il suffirait de connaître :

• 15 (nombre de sommets)
• (0, 1, 10) la seule arête de G

On peut éviter de stocker tous les zéros de la matrice d’adjacence en stockant de cette manière toutes les arêtes dans un vecteur contenant des triplets de la forme
(i, j, w) \leftrightarrow arête de i vers j de poids w dans G.

typedef struct triplet {
    int i;
    int j;
    int poids;
} triplet;

typedef struct graphe {
    int nbs;         /* nombre de sommets */
    int nba;         /* nombre d aretes */
    triplet *aretes; /* vecteur d aretes*/
} graphe;

Exemple

Nombre de sommets : S
Vecteur d’arêtes: (0, 4, 3), (0, 2, 18), (1, 0, 8), (2, 1, 4), (3, 1, 1), (4, 1, 10), (4, 3, 2)

Remarque

Pour déterminer s’il y a une arête de i vers j dans G, il suffit de parcourir le vecteur d’arêtes. C’est une opération en \Theta(a) où a est le nombre d’arêtes de G.

Représentation par brins

C’est une manière d’encoder un graphe introduite par Cori en 1973 ; très peu de références dans la littérature scientifique mais JJ aime bien alors voilà ¯\_(ツ)_/¯

Principe

On considère un graphe, dont on va numéroter les arêtes (si le graphe est pondéré, on peut garder les poids mais il faut des poids distincts)

Exemple

Une arête numérotée n va être séparée en deux parties :

• un brin -n vers le sommet d’où part l’arête
• un brin +n vers le sommet où arrive l’arête

On va ensuite associer à chaque sommet un brin (le premier brin), indiqué par le brin arrivant/sortant ou/du sommet avec la plus petite étiquette, et gardant son signe

Exemple

Ensuite, chaque brin est associé à un brin suivant en fonction du sommet qui lui est associé, ce brin suivant étant le premier que l’on rencontre en tournant autour du sommet dans le sens \circlearrowleft.

On aurait pu choisir l’autre convention, mais il faut être cohérent et garder le même.

Exemple

Question : Comment reconstruire un graphe de manière unique à partir de cette donnée ?
Exemple

On va construire un graphe à 3 sommets et 4 arêtes.

• le fait que le brin -4 soit associé au sommet 2 va indiquer que l’arête étiquetée 4 va partir du sommet 2
• le fait que le sommet 0 admette dans la ligne brin suivant le +4 indique que ce brin va arriver vers 0. On a donc une arête 2\ \underrightarrow{4}\ 0 et on peut ainsi reconstruire le graphe :
  

typedef struct strand {
    short int made;
    short next;
} strand;
typedef struct strandgraph {
    short int nbs;
    short int nba;
    short *made; // brim
    strand *nxt; // sommet et brim suivant
} strandgraphe;

Autres algos plus court chemin

Algo puissances de matrices d’adjacence (cf. Cours3)

Le nombre de chemin de longueur n d’un sommet i vers un sommet j est le coefficient (i, j) de la matrice M^{n}

(O -> 3)
k = 1
tant que M^{k}[0][3] == 0
    k+=1

Algo de Floyd-Warshall

Distance d’un plus court chemin \delta(u, v) entre deux sommets u et v pour toutes les paires (u, v)
G = (S, A) = S = \{s_{1}, \dots, s_{n}\}
On utilise une matrice M := M[i][j] = \begin{cases} 0\ p_{i} := J \\\\ w(s_{i}, s_{J})\ s_{i} j_{i}\ \overrightarrow{EA}\ s_{j} \\\\ \infty \text{ sinon} \end{cases}
Et on veut construire une matrice S(i, j) telle que \delta(S_{i}, J_{j})

Remarque

On peut avoir des poids négatifs

Exemple

Idée de l’algo :
P : v_{0} \underbrace{\rightarrow v_{1} \rightarrow v_{2} \dots \rightarrow v_{k-1}}\_\text{Intérieur de P} \rightarrow v_{k}
Un chemin d’intérieur vide est un chemin de la forme v_{k} ou v_{k} \rightarrow v_{k+1}
\delta(s_{i}, s_{j}) = un chemin dont l’intérieur est potentiellement contenu dans tout S
L’idée est que l’on va déchirer des chemins avec des intérieurs petits, et les autoriser à être de plus en plus grands

Soit I \leq S, soit \delta^{I}(u, v) la distance d’un plus court chemin d’intérieur inclus dans I.

Exemple

Propriété

\delta^{Iu\{x\}}(u, v) = \text{min}(\underbrace{\delta^{I}(u, v)}_\text{passer par x augmente la longueur du chemin}, \underbrace{\delta^{I}(u, x) + \delta^{I}(x, v)}_\text{passer par x améliore le ???})

void floyd_warshall(graphe *g) {
    int n = g->vertices;
    int dist[n][n];

    // Ici faut construire la matrice initiale

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // C'est du O(n³) donc ça pue un peu la merde
}

Algo de Belmann-Ford

C’est un algorithme de plus court chemin qui autorise d’avoir des arêtes avec des poids négatifs ; mais pas de cycles de poids négatifs

Exemple

\Rightarrow Le cycle 1\rightarrow 2\rightarrow 3\rightarrow 4 amène un chemin de longueur -2 de 1 vers lui-même. Ça n’a donc pas de sens de parler de plus court chemin de 0 vers 1.

Une partie importante de l’algo consiste à vérifier qu’il n’y a pas de cycle négatif, on s’en passera ici car on garde notre hypothèse de poids positifs !

Idée

On va calculer les longeurs des chemins les plus courts de longueur k, pour k++.

Observation

Les chemins les plus courts auront au plus n-1 arêtes ! (où n = nombre de sommets)

En effet

S’il y a plus de n arêtes, on passe par un sommet au moins 2 fois donc il y a forcément un cycle. Si ce cycle est de poids \geq 0, il est mauvais pour le plus court chemin donc on l’oublie. Il ne peut pas être de poids \leq 0.
De plus, un chemin de longueur du plus court chemin de src= u vers v avec au plus k arêtes.

On a alors :
\text{dist}^{k}[v] = \text{min}(\text{dist}^{k-1}[v], \text{dist}^{k-1}[w] + \text{poids}(w\rightarrow v))\ \text{pour tout voisin de }w\text{ et }v
Formule de réccurence !

Initialisation

\text{dist°}[u] = 0 \text{dist°}[w] = \text{INF} pour tout autre sommet

Exemple

Pour la représentation triplets :

void bellmanford(graphe *grph, int src) {
    int n = grph->nbs;
    int a = grph->nba;
    int u, v, poids;
    int *dist = malloc(n * sizeof(int));

    for (int k = 0; k < n; k++) {
        dist[k] = INF;
    }

    dist[src] = 0;

    for (int k = 0; k < n; k++) {
        for (int l = 0; l < a; l++) {
            u = grph->aretes[l].i;
            v = grph->aretes[l].j;
            poids = grph->aretes[l].poids;

            if (poids != 0 && dist[u] + poids < dist[v]) {
                dist[v] = dist[u] + poids;
            }
        }
    }

    print_dist(dist, n, src);
    free(dist);
}

Complexités

Les raisons

• Perception, théorisé par Grassman avec ses lois qui part du principe que si on voit pas la différence entre 2 couleurs c’est que c’est la même couleur
  ANB \Rightarrow A N > B
  CDE
  \forall A \quad \exists c,d,e \quad AN +C+D+E
  ANB \Rightarrow A+CNB+C
  Tout ça à donné le RGB, normalisé par une organisation, le CIE (Commission internationale de l’éclairage), en 1930
  Niveaux de bleus perçus par l’humain d’après les papis de l’époque :
  | Nb de Niveaux | Couleurs |
  | ———–– | –––– |
  | 60 | Bleu |
  | 100 | Rouge |
  | 200 | Vert |
  | 200 | Gris |

Avec une sensibilité de 72ppp (points par pouce)

Avec ce modèle de couleur (Trichomie), on ne sais pas créer de Jaune, de Cyan ou de Magenta, ce qui veux dire que les lois du dessous sont fausse :)

Ca c’est les chiffres sur lesquels les lois précédentes se sont basés (on remet pas en question parce que yavait des français au CIE hihi ^^)

Compression sans perte

• Shannon-Fano
• Huffman
• LZW
• RLE (Run length encoding) qui ne fonctionne que quand il y a plusieurs répétitions dans l’image.

Les taux de compressions de ces algos sont d’environs 30% (1Mo \rightarrow 700Ko)

Compression avec perte

Réduction de la fonction

On peut prendre une certaine surface de l’image et prendre la couleur dominante.

Sauf que c’est moche, ducoup on lisse l’image en stockant 2 couleurs

Pour le lissage / moyenne, 4 est un exemple, on peut prendre la valeur que l’on veut. Plus le paquet est grand plus la compression est grande, donc plus il y a de pertes.

On peut améliorer la compression en conservant non pas 1 couleur mais plusieurs, exemple de répartition :

Table d’indirection de couleurs

1 l \Rightarrow 128ko pour une image de 1Mo de pixel, mais là c’est du noir et blanc

nombres d’entrées \Rightarrow log_{2}n chiffres binaires.

Le prof raconte qu’il a connu ce genre de PC en parlant de la taille d’indirection de couleurs des cartes graphiques de l’époque.

Principe de base d’une table d’indirection de couleur (lookup table - CLUT) :

• considérer la CLUT comme un “nuage de points”, c’est à dire RGB ou HSV ou \dots
  \hookrightarrow Jusqu’à compactage à peu de couleurs
• simplification/détermination, “choisir” n couleurs | les “n milieu” à chaque étape
  \rightarrow en parcourant l’image faut faire le choix le plus justifié possible, ce qui est le plus compliqué et le moins systématisé. Le choix est très important pour éviter de n’utiliser que très peu de couleur dans la palette de couleurs choisis (par exemple n’utiliser que 10 couleurs sur 64 disponibles)
  

Thèse d’Anaïs Atencia

• Lien vers la BU
• Deuxième diaporama sur la synthèse d’Image from the Université de Gustave Eiffeil

Algorithmes par les Jeux

Résolution de jeux à un joueur

Le Sudoku

On a une manière brutale et naïve de résoudre un sudoku

Exemple

C’est un algorithme de type “backtracking” (retour en arrière)

On parcourt ainsi toutes les possibilités de remplir la grille \rightarrow c’est en fait un parcours en profondeur d’un arbre, dans lequel on cherche la branche qui mène à une solution

• Dans un sudoku moyen : ~50 cases vides, et en moyenne 3 possibilités par case : 3^{50} grilles à explorer, c’est beaucoup !
• Dans un sudoku difficile : peut prendre jusqu’à quelques minutes

Light up

Light up est un puzzle consistant à illuminer une grille formée de carrés noirs et blancs en ajoutant des ampules selon les règles suivantes :

• les ampoules peuvent être placés uniquement dans les carrés blancs, elles allument alors toute leur ligne et colonne jusqu’à un éventuel carré noir
• les carrés noirs peuvent être étiquetés d’un nombre correspondant au nombre d’ampoules qui devraient entourer le carré noir (en 4-connexité, cf. image)
  
  Ce nombre d’ampoules doit être exact, pas intérieur ni supérieur. Si un carré noir n’est pas numéroté le nombre d’ampoules l’entourant peut être quelconque.
• Il ne doit pas y avoir d’ampoule sur un carré blanc déjà éclairé par une autre ampoule.

Exemple

Implémentation d’un algorithme de résolution par backtracking

• On va utiliser une structure de board qui comprendra le nombre de lignes, le nombre de colonnes et un tableau de caractères
• On va utiliser une structure d’état pour stocker dans un tableau les positions des lampes dans le board.

typedef struct state {
   int nb_light;
   int light_pos;
}

• On devra écrire des fonctions :
  • print_board(board b) \rightarrow affichage du jeu
  • add_light \rightarrow ajoute une lumière supplémentaire dans le jeu et le vecteur détats
  • fill_board(board b, state s) \rightarrow éclaire le tableau en fonction des lampes présentes
  • check(board b, state s) \rightarrow vérifie si l’état actuel des lampes respecte les contraintes du jeu (0 si non, 1 si oui)
  • is_solved(board b, state s) \rightarrow détermine si le jeu est résolu (les contraintes sont respectés + tout est éclairé)
  • solve(board b) \rightarrow résout le jeu par backtracking naïf

  while (is_solved(b, s) == 0) {
      if (check(b, s) == 0) {
          return 0;
      }
      for(int k = 0; k < size; k++) {
          if (b.game[k] == ' ') {
              b <- add_light(b, s, k);
              b <- fill_board(b, s);
              if (solve(b) == 0) {
                  s.nb_light--;
                  b = fill_board(b, s);
                  solve(b);
              }
          }
          print_board(b);
      }
  }
  

Plus d’infos sur le TP ici et les fichiers ici.

\Rightarrow Sur un niveau difficile, la résolution par backtracking peut être couteuse

Comment améliorer cet algorithme ?

1. Placer les lumières que lumières que l’on peut placer à coup sûr

   Exemple

   
   N_{b} = nombre de carrés noirs
   i \in \\\{1, ..., N_{b}\\\}, avec :

   • Need_{i} = nombre dans le carré (dont on a besoin)
   • Space_{i} = nombre de carrés blanc pouvant accueillir une ampoule autour de ?
   • Have_i = nombre d’ampoules que l’on a autour
     Spl_i = { carrés blanc admissibles autour }

   Si Space_i + Have_i = Need_i \rightarrow on met une ampoule dans tous les éléments de Spl_i

2. Éliminer les cases qui ne pourront pas accueillir d’ampoule

Exemple

Si Have_i = Need_i \rightarrow toutes les positions restantes de Spl_i peuvent être marquées d’une croix

Exemple : Si on applique ce pattern 1 - 2 deux foix :

Le jeu est presque résolu en 2 étapes !
3. S’il y a une case non allumée isolée, on peut y placer une ampoule
N_w = nombre de carrés blancs
J \in \\\{1, ..., N_w\\\}
Si Source_J = 1, on peut placer une ampoule dans la seule position valable; Source_J correspond au nombre de carrés non éclairés autour de J_i incluent J

Exemple

Il y a d’autres patterns possibles d’améliorations…

Chiu - Chou - Yang - Yen ont publié en 2010 un article “A simple and rapid Lights-Up solver” dans lequel ils présentent un algorithme efficace du puzzle. Ils utilisent notamment 1, 2 et 3 ainsi que d’autres patterns ; ainsi qu’une méthode de parcours arborescente pour résoudre les zones blanches non encore éclairées.

Le fichier lightup.c contient une implémentation de cet algorithme \rightarrow vous pouvez ainsi tester et comparer l’efficacité de votre algorithme de backtracking par rapport à celui-ci.

Remarque

En fait, la résolution rapide de gros puzzles de Light Up est un problème qui intéresse encore des chercheurs à l’heure actuelle.
\rightarrow jeu qui apparaît comme un problème aux “Computer Olympiads” en 2010

Jeux à deux joueurs et IA

On étudie un jeu à deux joueurs à somme nulle (somme des gains et pertes égale à 0) où :

• chaque joueur joue dans l’objectif de gagner
• les joueurs jouent chacun leur tour

Exemple TicTacToe, Dames, Jeu de Go, Échecs, Puissance 4…

• On veut programmer une IA capable de jouer à un de ces jeux (contre une autre IA ou un joueur humain)

Difficultés :

• Il faut une IA capable de s’adapter à une position de jeu changeante
• Il faut une IA capable de jouer en fonction de la stratégie de son adversaire

Idée (naïve) : Construire l’arborescence des coups réalisables

Exemple avec un TicTacToe

• Évaluer à chaque position en fin de branche
  \rightarrow fonction qui nous permet d’évaluer et de mesurer quel joueur à l’avantage à une position de jeu donnée. Il faut donc un moyen de définir une fonction

Exemple : Pour les Échecs,

\begin{aligned}F(p) = &200(N_{k} - N_{k'}) + 9(N_{Q} - N_{Q'}) + S(N_{R} - N_{R'}) \\\ &+ 3(N_{B} + N_{N} - N_{B'} - N_{N'}) + N_{p}- N_{p'} \\\ &-(D-D'+S-S'+I-I')\end{aligned}
où N\cdot désigne le nombre de \cdot chez le joueur blanc (respectivement N\cdot' chez le joueur noir) et K King, Q Queen, R Rook (Tour), B Bishop (Fou), N kNight (Cavalier) et P Pawn (Pion).

D = nombre de pions doublés (cf. image)

S = nombre de pions bloqués
I = nombre de pions isolés
M = mobilité du joueur

Cette fonction renvoie un nombre flottant : plus il est grand (positif), plus le joueur blanc a l’avantage; plus il est petit (négatif); plus le joueur noir a l’avantage

Exemple

\begin{aligned}f(p) = &200(1-1)+9(1-1)+5(0-1)+3(2+0-1-0) \\\ &+3-3-\frac{0-2+0-1+1-1}{2}+\frac{37-46}{10}\\\ &\simeq-1.4\end{aligned}
On peut donc supposer qu’à cette position, le joueur noir a légèrement l’avantage. Cependant, si blanc bouge son fou en H7 (pour mettre en échec le roi), il prend l’avantage en capturant la dame au coup suivant…

Ceci est appelé un effet d’horizon.

• Choisir le chemin permettant d’atteindre la meilleure position finale, et jouer les coups menant à la position souhaitée.

Problème majeur : Complexité spatiale beaucoup trop grande aka arbre de jeu immense

Exemples

• TicTacToe : <3^{9} \approx 20 000
• Échecs : \approx (30\times 30)^{40} \approx 10^{120} \leftarrow ce nombre est appelé nombre de Shannon
• Jeu de Go : \approx 10^{600} \rightarrow impossible à gérer sans amélioration !
• Puissance 4 : Au max 3^{42} \approx 10^{20} parties possible puisque chaque case peut recevoir 3 états : Rouge / Jaune / Vide. Meilleur estimation : 1.3\times 10^{13}, calculée par ordinateur en retirant les configurations impossibles du type : \begin{cases} \text{Jaune} \\\\ \text{Vide} \\\\ \text{Jaune} \end{cases} et en éliminant toutes les cellules vides au dessus d’un cas gagnant.

Pour éviter cette explosion combinatoire, on peut se limiter à parcourir l’arbre jusqu’à une certaine profondeur

Exemple : TicTacToe avec profondeur 2

Principe de résolution :

• on va étudier l’arbre de jeu, et trouver la suite de coups optimale de la position initiale à un état final \rightarrow sélection d’une branche de l’arbre de jeu
• Estimation d’une position p : Soit \mathcal{P} l’ensemble des positions et \mathcal{P}^{\*} l’ensemble des positions légales terminales.
  Idéalement : fonction h^{*} : \mathcal{P} \rightarrow \\\{-\infty, 0, +\infty\\\} (avec -\infty : le joueur 2 gagne, 0 match nul et +\infty le joueur 1 gagne) qui détermine quel joueur gagne.

Pour obtenir une telle fonction, on utilise une estimation h : \mathcal{P} \rightarrow \R fonction d’évaluation
Cette fonction devra être d’autant plus fiable que p est proche d’une position terminale
Mais h est seulement une heuristique, et on ne peut pas prévoir les effets d’horizon.
\Rightarrow Il faut donc trouver un bon compromis entre la profondeur de jeu choisie et la fonction d’évaluation

Plus la profondeur est élevée, plus la fonction d’évaluation a des chances d’être efficace en s’approchant des positions terminales; mais plus la taille en mémoire sera importante.

Algorithme Minimax

Hypothèses :

• Les deux adversaires utilisent la même fonction d’évaluation et jouent pour gagner.
• Le joueur 1 cherche à maximiser son évaluation
• Le joueur 2 cherche à minimiser son évaluation

Joueur 1 = MAX
Joueur 2 = MIN

minimax (profondeur n, position p, joueur J)
    - si p est terminale
        return h*(p)
    - si n = 0 # On a atteint la profondeur maximale
        return h(p)
    - sinon, soit p1, ..., pm les m positions accessibles depuis p
        - si J = MAX
            return max minimax(n - 1, pi, MIN) # 1 <= i <= m
        - si J = MIN
            return min minimax(n - 1, pi, MAX) # 1 <= 1 <= m

Inconvénients

1. Complexité élevée \RA \O(c^{n}) avec c coups légaux en moyenne par chaque position et profondeur n.
2. Plus problématique : effets d’horizon; pour minimax(n, p, J) il se peut que p_{n+1} soit perdante alors que p_{n} est favorable

Amélioration

Première idée : on va éviter de parcourir les positions superflus de l’arbre de jeu \Rightarrow Élagage de l’arbre de recherche

Cet algorithme s’appelle alpha-beta (\alpha-\beta) puisque selon le joueur, on va réaliser deux types d’élagage dans l’arbre

Remarque

Cela n’enlève pas l’effet d’horizon, mais permet d’augmenter la profondeur en réduisant le nombre de positions à explorer.

On donne maintenant deux exemples d’élage de positions superflues : \begin{cases} \text{une coupure } \alpha \\\\ \text{une coupure } \beta \end{cases}

(1) MAX va choisir la valeur maximale renvoyée par l’évaluation de tous les coups possibles de MIN, donc 12
(2) MIN va choisir la valeur minimale renvoyée par l’évaluation de tous les coups possibles de MAX, donc 12

• En remontant ainsi jusqu’à la position initiale, on obtient 12, qui est l’évaluation du deuxième coup (dernier étage) \RA pour arriver à cette position, MAX devra donc jouer le premier coup et suivre le chemin en rouge.

Exemple :

• Une fois déterminée que h(p_{0}) = 14, on sait que MAX va choisir max(14,h(p_{1})) \geq 14, donc la valeur de son parent sera \geq 14 !
  MIN va donc ensuite choisir la valeur minimale entre 12 et \geq 14 \ra ce sera 12 !
  … peu importe ce que donne h(p_{1}) : on a donc pas besoin d’explorer la position p_{1} et on peut couper la tranchée qui relie p_{1} à son parent \RA c’est une coupe \beta
• Selon le même principe, une fois déterminées h(p_{2}) et h(p_{3}), MAX va choisir le coup qui mène à p_{3} (donc 6), puis MIN choisira nécesseraiment une valeur de parent \leq 6
  Ainsi, MAX préfèrera le coup qui mène à 12 plutôt que une position \leq 6 : c’est une coupe \alpha

Alpha-Beta (\alpha-\beta)

On considère comme précédemment une fonction d’évaluation h : \mathcal{P} \rightarrow \R et deux joueurs : MIN et MAX.
Pour évaluer p à une profondeur n, pour le joueur J, on conserve :

• \alpha = meilleur évaluation trouvée pour le joueur MAX dans les branches déjà vues
• \beta = meilleur évaluation trouvée pour le joueur MIN dans les branches déjà vues
• au départ, \alpha = -\infty et \beta = +\infty.

[Knuth ‘7s]: Lorsque l’algorithme minimax trouve un coup en parcourant n noeuds, alpha-beta trouve ce même coup en parcourant \approx 1+2\sqrt{n} coups si les coups sont bien ordonnées
\RA L’ordre des coups est important car en fonction de l’ordre, on ne réalise pas le même élagage.

Exemple:

alphabeta (profondeur n, position p, joueur J, alpha, beta)
    - si p est terminale, alpha = -INF ; beta = +INF
        return h*(p)
    - si n = 0
        return h(p)
    - sinon
        - soient p1, ..., pm les m positions accessibles depuis p
        - si J = MIN
            - e <- alphabeta(n-1, p1, MAX, alpha, beta)
            - si e <= alpha
                return alpha
            - sinon beta <- min(beta, e)
                recalculer e pour les autres positions p2, ..., pm
        - si J = MAX
            - e <- alphabeta(n-1, p1, MIN, alpha, beta)
            - si e >= beta
                return beta
            - sinon alpha <- max(alpha, e)
                recalculer e pour les autres positions p2, ..., pm

Schéma résumé :

Remarque

Il existe une variante de l’algorithme minimax, appelée negamax, plus utilisée actuellement. Plutôt que de tester si on est à une profondeur paire ou impaire pour savoir si on cherche à maximiser ou minimiser, on peut inverser le signe des évaluations et toujours chercher à maximiser.
On peut donc toujours procéder à un élagage alpha-beta à partir d’un negamax

Améliorations de l’algorithme alpha-beta

1. Autoriser des coupures plus longues : jusqu’à présent, on a réalisé des coupures alpha ou beta en comparant la valeur d’un noeud avec les valeurs des frères de son parent. On peut aussi regarder les parents des parents, exemple :
   
   Le 20 entouré en rouge ne peut a priori pas donner lieu à un élagage classique.
   Mais on peut constater que le frère du parent de son parent a pour valeur 10, et que valeur \geq 20 ne sera jamais choisie :

   • soit le minimum sera obtenue par le frère du 20 à profondeur 2, auquel cas le 20 n’est pas selectionné.
   • soit le 20 remonte jusqu’à 1, mais dans ce cas c’est le 10 qui sera choisi
     \ra le 20 ne sera donc jamais choisi, et donc son frère non plus (soit il est \leq 20 et ne remonte pas, soit il est \geq 20 et il sera encore moins choisi pour la même raison) : on peut donc réaliser une coupure “grande-\betaeta / \beta+”

2. Alpha-beta itératif incrémental
   L’idée est de commencer par réaliser une recherche à profondeur 1, puis recommencer avec une recherche complète à profondeur 2, puis profondeur 3, etc, jusqu’à ce qu’une solution soit trouvée
   Avantage : On trouve toujours la solution la plus courte, puisqu’un noeud n’est jamais engendré tant que tous les noeuds à profondeur inférieur n’ont pas été explorés.
   
   Complexité: \O(d) si l’algo se termine à profondeur d
   A priori, on perd beaucoup de temps dans les itérations précédent la solution. Mais ce travail supplémentaire est en général beaucoup plus petit que la dernière itération
   Exemple : Si n coups en moyenne par position, à profondeur d, on a n^{d} noeuds.
   Le nombre de noeuds à profondeur d-1 est de n^{d-1} mais chaque noeud est engendré 2 fois (une fois par le lancement à profondeur d-1 et une fois pour le lancement à profondeur d)
   Au final : nombre de noeuds engendrés : n^{d} + 2n^{d-1} + 3n^{d-2} + \dots + dn = \O(n^{d})
   Si n est grand, le premier terme est dominant, et c’est la dernière itération qui prend le plus de temps.
   De plus : alpha-beta incrémental permet de :

   • développer des heuristiques de parcours, en reprenant le parcours de l’arbre à partir de la position qui était jugée la meilleur au lancement à profondeur précédente
   • optimiser l’élagage en implémentant un tri rapide pour placer les meilleurs coups dans l’ordre

3. Approfondissement sélectif quiescence

   • Pour pallier aux inconveniants des effets d’horizon, Deap Blue a utilisé une meta fonction d’évaluation qui n’évalue pas la position mais plutôt le type de la position
     \ra elle évalue si une position est stable (essentiellement, si il reste des pièces en prise) qui donneront grosso-modo la même évaluation à profondeur d ou d+1.
     Une position stable a donc une évaluation en laquelle on peut avoir confiance alors qu’une instable non.
     Deepblue utilise un mécanisme de quiescence pour continuer de développer les positions basses de l’ordre jusqu’à des positions stables. Aux échecs, la quiescence est couramment utilisée pour des coups de capture ou des coups de promotion (sauf quand le roi est en échec)
     Chaque étape de l’algorithme est constituée de 4 phases :
     1. Sélection : Depuis la racine de l’arbre, on sélectionne successivement des enfants jusqu’à atteindre une feuille.
     2. Expansion : Si cette feuille n’est pas une position terminante, créer un enfant (ou plusieurs) en appliquant un mouvement suivant les règles du jeu, puis ajouté cet enfant marqué (0/0)
     3. Simulation (“Playout” ou “Roll-out” en anglais) : Simuler une exécution d’une partie au hasard depuis cet enfant, jusqu’à atteindre une position de jeu terminale
     4. Back propagation : Utiliser le résultat de la partie au hasard et mettre à jour les informations sur la branche en partant de la feuille vers la racine
        Exemple :

4. Approfondissement sélectif
   Si un coup semble intéressant, on continue à cherche à une profondeur plus grande que la profondeur habituelle.
   Si un coup semble mauvais, on arrête de chercher à une profondeur plus petite que la profondeur habituelle.
   Exemple : Chinook, IA pour les dames

   • S’il analyse un coup qui perd 3 pions, plutôt que d’analyser à profondeur 10, il va réduire à seulement 5 coups à l’avance, en considérant que le coup a de bonnes chances d’être mauvais
   • S’il analyse un coup qui paraît très bon, il augmentera la profondeur à 12 coups à l’avance

Monte-Carlo Tree Search (MCTS)

L’algorithme MCTS est un autre algorithme d’IA pour les jeux basé sur une recherche arborescente

MCTS conserve en mémoire un arbre qui correspond aux noeuds déjà explorés de l’arbre de jeu.
\ra une feuille de cet arbre est soit une position terminale du jeu, soit un noeud dont aucun enfant n’a encore été exploré.

Dans chaque noeud, on stocke deux nombres : le nombre de simulations gagnantes et le nombre totale de simuations.

Si la partie est perdante pour J1 : on incrémente le nombre de simulation total uniquement pour les noeuds J1 et on incrémente à la fois le nombre de simulations totales et gagnantes pour J2… et inversement si la partie est gagnante pour J1.

• Pour la phase de sélection, il faut choisir un bon compromis entre l’exploitation des choix qui ont l’air prometteurs et l’exploration des noeuds à partir desquels peu de simulations ont été réalisées
  \ra formule UCT (Upper Confidence Bound) introduite par Kocsis et Szepesvári donne un bon compromis
  On choisit en chaque noeud de l’arbre le successeur i qui maximise l’expression \frac{w_{i}}{m_{i}} + c \sqrt{\frac{\ln{N_{i}}}{n_{i}}} où :

  • w_{i} = nombre de parties gagnées marquées dans i
  • n_{i} = nombre de fois où i à été visité
  • N_{i} = nombre de fois où le noeud de base, père de i, a été visité
  • c = constante appelée paramètre d’exploration, en générale égale à \sqrt{2}

• La partie \frac{w}{n} correspond à l’exploitation : la fraction est grande pour les successeurs qui ont eu beaucoup de succès jusque là

• La partie \sqrt{\frac{\ln{N_{i}}}{n_{i}}} correspond à l’exploration : elle est grande pour des successeurs impliquées dans peu de simulations

Avantages :

• Pas besoin de fonction d’évaluation en cours de partie, uniquement de savoir jouer aléatoirement selon les règles du jeu et d’évaluer une partie terminée avec une fonction score
• Algorithme dit “anytime” : il est interruptible à tout instant en retournant son meilleur résultat courant. L’interruption peut se faire en nombre d’itérations ou en temps, ou réalisée par la découverte d’une solution.

selection (pos p)
    Si p est terminale
        return p
    N = nombre de visites du père p (fonction getN)
    Si N == 0
        return p
    M <- { Mouvements possibles depuis p }
    { max, best } <- { -1, ∅ }
    pour chaque m ∈ M faire
        ni = nombre de fois où p à été visité
        Si ni == 0
            return p
        new_eval <- UCT(p, m)
        Si new_eval > max
            { max, best } <- { new_eval, m }
    p' <- apply_move(p, best)
    return selection(p')

expansion (pos p)
    Si p est terminale
        return p
    N <- getN(p)
    Si N == 0
        make_moves(s)
    M <- { Mouvements possibles depuis p }
    pour chaque m ∈ M
        Ni <- getNi(p, m)
        Si Ni == 0
            p' = apply_move(p, m)
            return p'

playout (pos p)
    while not(p position termionale)
        M <- next_moves(p)
        m <- random(M)
        p <- apply_move(p, m)
    return score(p)

back_propagate (pos p, score)
    if parent(p) == ∅
        return
    add_score(p, score)
    return back_propagate(parent(p), score)

Fonction d’évaluation Puissance 4 :

1. Grille de jeu pondérée
   
   score(J1) = somme des poids des cases sur lesquelles J1 a un jeton

2. Compter le nombre d’alignements
   Pour chaque joueur, on évalue son score de la façon suivante :

   • +1 par jeton
   • +5 par 2 jetons alignés
   • +50 par 3 jetons alignés
   • +1000 par 4 jetons alignés

   f(p) = score(J1) - score(J2)

   Inconvénient : Cette évaluation tient en compte des alignements “bloqués”, par exemple :
   donnera un score positif pour J1 avec 2 alignements de 3, alors qu’un seul alignement de 4 n’est encore possible.
   Mieux : Ne compter dans ce calcul que les alignements encore envisageables