Résoudre un problème algorithmique

> Ébauches

Ébauche en cours de rédaction par ''Hazurl''

Cet article vous donnera les bases afin de réaliser tous types de problème algorithmique. Il s'adresse avant tout aux débutants qui ne savent pas comment commencer, mais pas seulement. La première partie explicitera les différentes méthodes de résolution, c'est-à-dire la théorie. Puis je prendrais pour exemple l'algorithme des cases accessibles afin de concrétiser ces méthodes. J'ai fait le choix de cet algorithme car c'est l'un des algorithmes les plus utiles, et parce que la page traitant de celui-ci n'est pas adapté pour les débutants; elle est plus dans une optique d'optimisation. Puisque j'en parle, l'optimisation ne fera pas partie de cet article, il en existe déjà à ce sujet.

Théoriquement

De façon générale, on appelle un problème algorithmique, une question qui peut être résoluble par un ordinateur. On en distingue deux :

Problème de décision : la réponse est binaire, oui ou non, on peut citer par exemple canUseWeapon ou isObstacle, on peut remarquer que ces fonctions ont souvent "is" ou "can" au début de leur nom, cela permet à la lecture, de tout de suite savoir que le réponse de la fonction sera un booléen, je vous encourage vivement à faire de même pour vos fonctions.
Problème d'évaluation : consiste en la création d'un objet énoncé par le problème, par exemple getCellsToUseWeapon qui renvoie une structure : un tableau

Ce n'est pas vraiment à retenir mais plus pour votre connaissance générale.

Comprendre l'énoncé

Rien de plus évidement mais pourtant une étape que beaucoup de personne oublie. Et pas que les débutants. Il faut bien comprendre le sujet et ne pas hésiter à le relire pour ne pas que ce soit flou. Imaginez expliquer le sujet à quelqu'un qui ne l'ait jamais lu. Il faut savoir le reformuler de tête, sans faire de généralisation ou de spécification sous peine de débuter sur de mauvaises bases. Ne commencer pas à réfléchir à la résolution du programme. Il faut expliciter les données en entrée et en sortie, de quelle manière celle-ci sont construite, etc... Si le problème ne possède pas de contrainte sur la sortie, imaginer comment elle va être manipuler afin de simplifier son utilisation. il faut savoir répondre (parfaitement !) à ces deux question :

Qu'est-ce que j'ai en entrée ?
Qu'est-ce que je dois obtenir ?

Résoudre des exemples

Le meilleur moyen pour trouver une implémentation de l'algorithme est de le résoudre par soi-même. Les exemples à résoudre ne sont pas à trouver purement aléatoirement. Il faut prendre des cas différents et limites. Il faut chercher à quel moment la résolution est compliqué, et ensuite créer les exemples à l'extrême. Il faut ensuite préparer un support pour tester l'algorithme. Un simple test d'égalité sur la bonne sortie peut faire le boulot, sinon vous pouvez en faire un affichage simple pour le vérifier à la main.

Recherche de l'algorithme

Voici l'étape la plus concrète. Vous devez transformer votre problème en solution. Le mieux est de procéder par étape de plus en plus précise en commençant avec votre problème initiale, d'ailleurs on peut voir que ce procédé est un algorithme en soit 😉. Il faut diviser le problème en sous-problèmes tout en faisant apparaître les structure de contrôle : boucles, structures conditionnelles... Chercher à redéfinir à chaque étape tous vos problèmes. Rien de mieux qu'un exemple pour illustrer ce concept : Trier un tableau. On a un tableau en entrée et en retour un tableau trié (disons par ordre croissant). Comment trier un tableau ? il faut le modifier évidement, mais ce n'est pas suffisant, il faut le modifier jusqu'à ce qu'il soit trier. Oh ! Mais... ne serait-ce pas une boucle ? Notre première division a donc fait apparaître une boucle ainsi que son corps et sa condition. Mais modifier le tableau n'est pas très précis... Il faut aussi prendre en compte que boucle égale potentiellement boucle infini. Faire très attention à ce que la condition soit évaluée différemment à un moment pour sortir de la boucle. Donc, modifier le tableau doit le rendre plus trié avant qu'après la boucle de façon à ce que le tableau soit trié à un moment et que la boucle se termine. Il y a énormément de façon de trier un tableau, une des plus simple consiste à inverser l'élément le plus petit avec le premier élément, puis faire de même avec le second élément, c’est-à-dire plus généralement, pour chaque élément du tableau à la position i l'inverser avec le plus petit élément à sa gauche. Voici une représentation de là où nous en sommes :

Fonction trier_tableau (tab) // tab étant la variable du tableau à trier Tant que est_pas_trie(tab) Pour i allant de 0 à n - 1 // n est la taille du tableau pos_elem_min = pos_elem_min_droite(tab, i) // position du plus petit élément du tableau à droite de i inverser(tab, i, pos_elem_min) // On inverse les deux éléments Fin Pour Fin Tant que retourner tab Fin Fonction

Il faut encore définir si un tableau est trié ou non (la condition) ainsi que la position du petit élément à droite de i, et enfin inverser les deux éléments du tableau. Pour trouver l'élément à droite de i qui est le plus petit, il faut parcourir les éléments à partir de i jusqu'à la fin du tableau, et prendre le plus petit d'entre eux :

[Pas fini]

Tester son algorithme

Il est important de tester ses algorithmes, dans un premier temps avec les exemples résolus à la main précédemment puis avec des problèmes plus complexes. Il faut cependant avoir une méthode de vérification. Elle peut être vérifiée par le calcul ou en observant les données (grâce à mark ou debug). Si votre algorithme ne répond pas aux exigences du problème, il faut reprendre votre algorithme en ciblant la cause du problème, toujours avec l'aide des fonctions de debugs. Vous pouvez aussi créer votre bench pour tester votre algorithme mais celui-ci est souvent dans une optique d'optimisation. Pour en faire une rapide description, un bench est une fonction qui va tester, vérifier et compter le coût d’exécution de votre fonction sur de larges échantillons de données. Par exemple : function bench (fonctionATester, message, entrer, retourPrevu);.

Mise en pratique

Super, maintenant que vous savez tout il faut le mettre en oeuvre. Et pourquoi pas avec l'algorithme des cases accessibles... Je vais vous expliquer brièvement le problème en question, si vous voulez plus de détails ou des idées d'optimisation, une page est consacrée entièrement à cela.

Compréhension du problème

Qu'est-ce que j'ai au début ?

Vous vous rappelez des questions de base à savoir répondre ? Ceci en est une. Et elle n'est pas très compliquée. Je veux juste avant vous préciser une astuce. Ne rendez pas vos fonctions trop spécifiques, celles-ci ne doivent avoir besoin que d'informations passés en paramètre, les effets de bords sont à exclure (aller chercher une information à l'extérieur de la fonction). Vous ne devez en aucun cas faire quelque chose comme getNearestEnemy dans une fonction. Ceci est valable dans toutes vos fonctions. Evidemment, ce que je viens de dire n'est pas dans l'absolu vrai pour tout. En effet, si vous créez une fonction getDistanceFromNearestEnemy, l'appel à getNearestEnemy est justifié même si faire une fonction plus générique vous avantagerez : getDistanceFrom. Il faut faire un juste milieu. Bon reprenons à notre question... Il faut trouver l'ensemble des cellules accessibles à partir d'une case et d'un certain nombre de MP. Le choix des paramètres est important, si nous ne définissons pas de paramètre, et bien, impossible de savoir les cases accessibles par notre poireau et celles du poireau adverse. Il faut donc avoir au moins le choix du poireau dans nos paramètre mais un autre problème fait son apparition : et si nous voulions déterminer les cases accessibles après un déplacement pour prévoir ? Dans ce cas il faut utiliser une cellule dans nos paramètres, mais à ce moment plus moyen de savoir le nombre de MP, voici donc la signature de la fonction :

getReachableCells (cellFrom, MP)

C'est celle que nous allons utiliser dans cette page, libre à vous de faire autrement, notamment savoir la distance pour toutes les cases, comme ça pas besoin de recalculer après un boost de MP.

Qu'est-ce que je dois obtenir ?

Nous devons obtenir la liste des cases accessibles à partir d'une case et d'un certain nombre de PM. Une liste est représenté par un tableau. Ce qui nous arrangerai c'est d'avoir le tableau trié par distance de façon à, lors d'un parcours via un for, analyser les cases les plus proches pour économiser des MPs. On peut même faire mieux, en exploitant la propriété des tableaux (associatifs), on peut avoir un tableau avec les cellules en clées et le nombre de MP en valeur, c'est-à-dire : tab[cell] retourne le nombre de MP pour atteindre cell. On a donc déterminé que notre tableau sera de la forme :

[cellFrom: 0, cell1 : 1, ... , cellX : 2, ..., cellN : n] // soit plus simplement [cell : MP] trié par MP croissant pour un tableau qui part de cellFrom avec n MP. Grâce à cela, si l'on parcours notre tableau avec for (var cell : var mp in getReachableCells (cellLambda, MPLambda) ), les deux variables cell et mp vont prendre pour valeur cellLambda et 0 puis toutes les cellules à 1 de distance, puis à deux, etc jusqu'à MPLambda.

Réalisation

Nous allons maintenant diviser notre problème afin de pouvoir traduire plus simplement en LeekScript notre algorithme. Initialement, on a : "Trouver toutes les cellules accessibles à partir d'une cellule avec un certain nombre de MP" Comme nous voulons les avoir dans un ordre précis (ordre croissant de la distance), le mieux est de pouvoir créer le tableau directement dans l'ordre puisqu'un tri est relativement coûteux. Il faut donc ajouter les cases à 0 de distance, puis 1 puis 2 jusqu'à n MP. Nous avons notre première case, car celle-ci est donné en paramètre. Pour la suite, nous devons trouvé les cases à 1 de distance (sauf si la distance est de 0 MP), par quel moyen peut-on les obtenir ? getCellDistance ne prend pas en compte les obstacles, getPathLength est coûteux... trop coûteux, et je rappelle que cet algorithme est là pour éviter d'avoir à faire getPathLength à chaque fois. Réfléchissons plus globalement, lorsque nous trouverons les cellules accessibles à 1 de distance, il va falloir trouver les cellules accessibles à 2 de distance, etc. Donc si on résume lorsque l'on veut les cellules à x MP, on a :

La case d'origine : cellFrom La liste des cases à x - 1 MP

Le plus simple n'est pas de les trouver à partir de la cellule d'origine mais plutôt à partir de la liste des cellules précédentes. En effet, car il faut prendre en compte les obstacles et partir de cellFrom nous ferait tout recalculer de nouveau. Pour obtenir les cases à partir des précédentes, il faut trouver les "voisins" de ces cellules. Il faut ensuite les analyser pour ne pas ajouter un obstacle ou une cellule déjà définie.