Chapitre 40 : algorithmes de recherche de chemins

Après ces chapitres sur l’utilisation de X11, nous allons revenir à la programmation de quelques algorithmes de recherche de chemins tels qu’ils sont présentés dans le livre déjà cité de Virginie MATHIVET aux éditions ENI.
Tous les sources de ce projet sont à télécharger depuis ce répertoire 

La transposition des programmes JAVA en assembleur ARM pose quelques petits problèmes de réflexion (Oui je sais pour les fanas de langage évolué, c’est du grand n’importe quoi !!) mais rien d’impossible. Nous allons donc manipuler des tables, et des listes chainées ce qui nous permet d’utiliser les registres comme pointeurs.

Pour pouvoir réutiliser ces algorithmes dans d’autres programmes, j’ai décidé de les écrire dans des petits programmes sources différents et d’utiliser l’utilitaire make pour compiler et linker l’ensemble du projet. Comme cela j’ai découvert les subtilités de ce programme !!  Vous trouverez ici le fichier des commandes pour ce projet et qu’il faudra lancer par make –f makefile.txt sur le raspberry.

Remarque : il manque dans ces commandes, la recompilation lorsque l’on a modifié uniquement un fichier d’include (modification d’une constante ou d’une structure par exemple).

Le programme maitre est le programme lancer.s qui va contenir la description des cartes, l’appel aux programmes de création des structures de données puis les appels à chaque algorithme de recherche : recherche en profondeur, en largeur, algorithme de Bellman-Ford, de Dijkstra et A* (pour la théorie, je vous renvoie au livre en question ou à des articles sur Internet).

Pour chaque algorithme, nous mesurerons le temps d’exécution avec les procédures décrites dans les chapitres précédents de ce blog.

Le programme le plus important est le programme carte.s qui va traduire la description de chaque carte en données exploitable par les algorithmes. Chaque case de la carte est enregistrée dans une table composée d’une structure Tuile. Ici, j’ai eu quelques difficultés pour associer les données d’un nœud (nécessaires aux algorithmes) avec les données internes à la tuile. J’ai donc crée une structure Tuile mais qui contient au début les données d’un Nœud. Ceci permet de généraliser les algorithmes à d’autres problèmes de recherche. Il suffira simplement de modifier (ou dédoubler) la structure pour adapter les données internes au problème concerné

La taille des cartes étant très variable, la place nécessaire sera réservée sur le tas. Pour cela une routine contenant l’appel système BREAK sera ajouté au fichier des routines. Voici son code :

allocPlace:

                push {r1,lr}    /* save des  2 registres */

                push {r2,r7}  /* save des registres */

                mov r2,r0

                mov r0,#0      /* recuperation de l'adresse du tas */

                mov r7, #0x2D                  /* code de l'appel systeme 'brk' */

                swi #0                      /* appel systeme */

                mov r1,r0       @ save du début

                add r0,r2                  @ reservation place demandé

                mov r7, #0x2D                  /* code de l'appel systeme 'brk' */

                swi #0                      /* appel systeme */

                cmp r0,#-1       @ erreur allocation

                beq 100f

                mov r0,r1    @ retour adresse début

100:

                pop {r2,r7}

                pop {r1,lr}   /* fin procedure */

                bx lr   

Dans le programme carte.s, nous décodons les lignes de la description de la carte et pour chaque case, nous créeons une tuile dans une table avec le type, sa place et son cout.

Puis à partir de cette table, nous créons une liste chainée de tous les nœuds et une liste chainée de tous les arcs, listes qui seront utilisées par les algorithmes.

Chaque algorithme est codé dans un programme spécifique suivant la description java du livre et en l’adaptant aux structures de données crées dans le programme carte. La mise au point est un peu délicate compte tenu du nombre de registres utilisés. A ce propos, le rôle de chaque registre dans un programme comme celui-ci n’est pas toujours facile à déterminer. Faut-il respecter par exemple les normes habituelles de passage des arguments aux sous-routines ? si oui, cela oblige à faire des mouvements de registres à registres si ceux-ci ne sont pas bien choisis. On s’aperçoit par exemple qu’il faudrait utiliser les registres à partir de r4 pour les indices supérieurs de boucle ou pour conserver les données principales du programme. Je n’ai pas encore trouvé la bonne méthode pour ces attributions, ce qui entraine quelques bizarreries dans mes programmes. Comme ici, une fonction qui n’utilise pas comme paramètre d’entrée le registre r0 mais seulement r1 (indice de ligne dans la table des tuiles) et r2 (indice de colonnes) ou alors le registre r10 qui sert dans plusieurs routines !!!

Après corrections de nombreuses anomalies, le programme donne les mêmes résultats pour les exemples du livre avec bien sûr des temps d’exécution bien différents. L’algorithme de Bellman-Ford a un temps d’exécution anormal par rapport aux autres. Il faut que j’analyse plus finement son comportement pour voir s’il n’y a pas une erreur de programmation ou un mauvais choix de la structure des données.

Exercices :  lire la description d’une carte à partir d’un fichier dont on passe le nom en paramètre.

                Le départ de plusieurs algorithmes est toujours la case 0,0. Modifier les algorithmes pour qu’ils commencent à la case départ donnée par la structure graphe.

Adapter les algorithmes à d’autres problèmes.