Perles de Dijkstra

Les perles de Dijkstra sont un problème de retour sur trace en programmation énoncé par Edsger Dijkstra dans les Communications of the ACM au début des années 1970^{[réf. nécessaire]}.

L'intérêt du problème vient du fait qu'il est difficile de le programmer sans instruction goto, mais que si on le programme avec une telle instruction, on a de fortes chances aussi de se tromper, et de rendre le programme très dur à corriger.

Il a donné lieu aussi à des développements mathématiques simples.

Le problème

Soit un fil sur lequel on désire enfiler des perles de trois couleurs. Dijkstra propose bleu, blanc et rouge, couleurs du drapeau néerlandais, mais on peut dans une formulation plus neutre les nommer 0, 1 et 2.

Une seule contrainte existe : il ne doit pas y avoir sur le fil deux séquences adjacentes identiques.

Questions :

• Combien de perles peut-on ainsi enfiler ?
• Écrire l'algorithme qui réalise la plus longue séquence possible, ou le cas échéant celui qui pourra continuer indéfiniment.

L'analyse

Plausibilité

Elle commence tout d'abord avec un peu de réflexion préalable : chaque choix de perle est un choix parmi trois. Le degré de liberté dans la construction est de l'ordre de 3^N. La contrainte, elle, semble diminuer plutôt en N^3/2, ce qui conduit à se dire que passé un certain cap, on a assez de marge de manœuvre pour continuer indéfiniment. Mais impression n'est pas démonstration.

Familiarisation simple

Elle contient ensuite avec un peu de simulation à la main :

• 0 est correct
• 00 serait incorrect
• 01 est correct
• 010 est correct
• 0100 et 0101 seraient incorrects
• 0102 est correct
• ...
• 0102010 est correct

Nous avons ensuite un souci pour placer une perle supplémentaire :

• 01020100 ne convient pas (répétition du 0)
• 01020101 ne convient pas (répétition du 01)
• 01020102 ne convient pas davantage (répétition du 0102)

Est-ce la chaîne la plus longue cherchée ? Non. Nous pouvons toujours remettre en cause un de nos choix (arbitraires) antérieurs pour voir si cela ne débloque pas la situation. Et de fait :

0102012 débloque les choses et permet de continuer. Cette procédure se nomme le backtracking.

Il n'y a plus qu'à programmer.

Programmation

Mais attention aux programmeurs négligents : si leur programme ne prévoit pas qu'il puisse y avoir de nombreux backtrackings successifs depuis la même position, ils sont partis pour rencontrer de sérieux ennuis. Ennuis qui deviennent vite inextricables si de surcroît ils ont fait usage de l'instruction GO TO, qui interdit toute prédiction facile sur les invariants valides en chaque point du programme.

Méthode mathématique

On peut construire une telle chaîne arbitrairement longue. Soit $\ f$ le morphisme (vérifiant $\ f(ab)=f(a)f(b)$) sur l'alphabet $\ \{0,1\}$, défini par $\ f(0)=01$ et $\ f(1)=10$. Notons $\ u_{n}=f^{n}(0)$. On a alors: $\ u_{1}=01$; $\ u_{2}=0110$; $\ u_{3}=01101001$; $\ u_{4}=0110100110010110$; $\ u_{5}=01101001100101101001011001101001$. Ainsi l'on définit le mot de Thue et Morse, en prenant la limite de cette suite (car chaque élément de la suite est préfixe des autres). Ce mot possède plusieurs particularités mais ici celle qui nous intéresse est la suivante : on peut prouver que le mot ne comporte pas de facteur 000 ou 111. Ceci permet de décomposer le mot en produit de facteurs de la forme $\ 0.1^{*}$. Si l'on remplace ensuite chacun de ces facteurs par le nombre de 1 qu'il contient (toujours inférieur a 2), on obtient le mot $\ v=210201210120210201202.....$

On peut montrer que ce mot est un mot sans facteur carré.

Implémentation

JavaScript

Fonction de vérification de validité de la chaine

Décomposée en trois fonctions

La première, renvoie un booléen, indiquant si les deux séquences passées en argument sont identiques.

function verifier_sequence(sequence_a, sequence_b)
{
	var maxI = sequence_a.length;
	for (var i = 0; i < maxI; i++)
	{
		if (sequence_a[i] != sequence_b[i])
			return true;
	}
	return false;
}

La seconde teste toutes les sous-chaines qui partent du premier caractère qu'on lui envoie.

function verifier_a_partir_de(morceau)
{
	var maxJ = morceau.length;
	for ( var j = 2; j <= maxJ; j += 2 )
	{
		var sequence_a = morceau.substring(0, j / 2);
		var sequence_b = morceau.substring(j / 2, j);
		if ( !verifier_sequence(sequence_a, sequence_b) )
			return false;
	}
	return true;
}

La troisième exécute la seconde sur chacun des caractères de la chaine.

function verifier(fil) {
	var maxI = fil.length;
	for ( var i = 0; i < maxI; i++ ) {
		if ( !verifier_a_partir_de(fil.substring(i, fil.length)) )
			return false;
	}
	return true;
}

Optimisation

Cette implémentation naïve, peut être fortement optimisée si on prend en compte qu'à chaque étape on ne fait que concaténer un élément à une chaine déjà valide :

function verifier_sequence(sequence_a, sequence_b)
{
	var maxI = sequence_a.length;
	for (var i = 0; i < maxI; i++)
	{
		if (sequence_a[i] != sequence_b[i])
			return true;
	}
	return false;
}

function verifier(fil) {
	var maxJ = fil.length;
	for ( var j = 2; j <= maxJ; j += 2)
	{
		var sequence_a = fil.substring(maxJ - j, maxJ - j / 2);
		var sequence_b = fil.substring(maxJ - j / 2, maxJ);
		if ( !verifier_sequence(sequence_a, sequence_b) )
			return false;
	}
	return true;
}

Récursivité

La fonction récursive va tester chacune des trois couleurs et vérifier si la chaine produite est valide. La première condition de la fonction utilise une variable globale "iterations" initialisée au début du programme pour éviter le dépassement de pile, et le Do While fait appel a la fonction de Backtracking décrite dans la section suivante, quand on constate qu'on ne peut plus ajouter de perle, et ce tant que la chaine obtenue n'est pas valide.

function ajouter_perle(fil) {
	if (iterations-- < 0)
		return (fil);

	if (verifier(fil + "0")) {
		return ajouter_perle(fil + "0");
	}
	else if (verifier(fil + "1")) {
		return ajouter_perle(fil + "1");
	}
	else if (verifier(fil + "2")) {
		return ajouter_perle(fil + "2");
	}

	do {
		fil = time_machine(fil);
	} while (!verifier(fil))

	return ajouter_perle(fil);
}

Backtracking

La première condition tente d’incrémenter la valeur de la dernière perle, et si elle a atteint son maximum (2), elle retire la dernière perle.

function time_machine(fil)
{
	if ( fil[fil.length - 1] == "0" )
	{
		fil = fil.substring(0, fil.length - 1) + "1";
	}
	else if ( fil[fil.length - 1] == "1" )
		fil = fil.substring(0, fil.length - 1) + "2";
	else
		fil = time_machine(fil.substr(0, fil.length - 1));
	return fil;
}

C

La solution en Javascript est rapide à concevoir et écrire, mais ses performances sont très faibles. Il est donc conseillé de réécrire le programme en C afin d'obtenir des résultats bien plus rapides.

À titre indicatif, cette solution s’exécute environ 100 fois plus rapidement que celle en JS. (Pour 10000 itérations, le JS prends 17,5s, contre 0,18s en C)

#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

int iterations = 30000;

// 1 = sequence valide | 0 = sequence invalide
char verifier_sequence(char *str, int deb, int mi)
{
	int max = mi - deb;

	for (int i = 0; i < max; i++)
	{
		if (str[deb + i] != str[mi + i])
			return (1);
	}
	return (0);
}

// 1 = sequence valide | 0 = sequence invalide
char verifier(char *fil)
{
	int max = strlen(fil);

	if (max <= 1)
		return (1);
	for (int i = 2; i <= max; i += 2)
		if (!verifier_sequence(fil, max - i, max - (i / 2)))
			return (0);
	return (1);
}

char *time_machine(char *fil)
{
	if (fil[strlen(fil) - 1] != '2')
		fil[strlen(fil) - 1]++;
	else
	{
		fil[strlen(fil) - 1] = '\0';
		fil = time_machine(fil);
	}
	return (fil);
}

char *ajouter_perle(char *fil)
{
	if (iterations-- < 0)
		return (fil);

	strcat(fil, "0");
	if (verifier(fil))
		return ajouter_perle(fil);
	fil[strlen(fil) - 1] = '\0';

	strcat(fil, "1");
	if (verifier(fil))
		return ajouter_perle(fil);
	fil[strlen(fil) - 1] = '\0';

	strcat(fil, "2");
	if (verifier(fil))
		return ajouter_perle(fil);
	fil[strlen(fil) - 1] = '\0';

	do {
		fil = time_machine(fil);
	} while (!verifier(fil));

	return ajouter_perle(fil);
}

int 	main(int argc, char **argv)
{
	char *str;

	if (argc == 2)
		iterations = atoi(argv[1]);
	str = malloc(iterations);
        str[0] = '\0';
	ajouter_perle(str);
	printf("%s\nLength : %d\n", str, strlen(str));
}

Voir aussi

• backtracking ou retour sur trace
• branch and bound ou séparation et évaluation
• programmation structurée
• recherche opérationnelle
• théorie des graphes