Calcul Divers : SHA-256 (d'une string)

Principe

SHA-256 est un algorithme de hachage, dont le principe de fonctionnement est décrit ici et ici.

Complexité

Je dirai en <math>\(O(k \frac{l}{512})\)</math>, ou k est une constante, et l la longueur du message en bits (à vérifier).

C++

/*
 * SHA-256.h
 *
 *  Created on: 5 juin 2010
 *  Author: alexis
 *  References:
 *  http://en.wikipedia.org/wiki/SHA-2#SHA-256_.28a_SHA-2_variant.29_pseudocode
 *  http://docs.google.com/viewer?url=http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf
 */

#ifndef SHA256_H_
#define SHA256_H_

#include <sstream>
#include <stdint.h>
#include <string>
#include <vector>

std::string SHA256(std::string str);

#endif /* SHA256_H_ */

/*
 * SHA-256.cpp
 *
 *  Created on: 5 juin 2010
 *      Author: alexis
 */

#include "SHA-256.h"

//macro pour faire tourner les bits d'un entier vers la droite
#define ROTR(x, n) ((x >> n) | (x << (8 * sizeof(x) - n)))
#define SHR(x, n)  (x >> n)

using namespace std;

std::string SHA256(string str) {
    /* Cf. spec pour les valeurs suivantes */
    const uint32_t k[64] = { 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
                             0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
                             0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
                             0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
                             0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
                             0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
                             0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
                             0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
                             0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
                             0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
                             0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
                             0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
                             0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
                             0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
                             0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
                             0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2 };

    uint32_t H[8] = { 0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
                      0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19 };

    vector< uint8_t > msg;

    const uint8_t *str_ = reinterpret_cast< const uint8_t * >(str.c_str());

    for(unsigned int i = 0, m = str.size() * sizeof(char); i < m; ++i) {
    	msg.push_back(str_[i]);
    }

    const uint64_t msg_length = msg.size() * 8;

    msg.push_back(0x80); //0b10000000

    while((msg.size() * 8) % 512 != 448) {
        msg.push_back(0x0);
    }

    for(int i = 56; i >= 0; i -= 8) {
        //on stocke msg_length (64bits) sous la forme de 8 entiers de 8 bits
        msg.push_back(msg_length >> i);
    }

    //pour chaque bloc de 512 bits (donc inc cases du tableau)
    for(unsigned int inc = 512 / 8, i = 0, s = msg.size(); i < s; i += inc) {
        uint32_t w[64];

        for(unsigned int l = i, idx = 0; idx < 16; ++idx) {
            for(unsigned int m = 0; m < 4; ++m, ++l) {
                w[idx] <<= 8;
                w[idx] += msg[l];
            }
        }

        for(unsigned int idx = 16; idx < 64; ++idx) {
            uint32_t s0 = ROTR(w[idx - 15], 7) ^ ROTR(w[idx - 15], 18)
                            ^ SHR(w[idx - 15], 3),
                     s1 = ROTR(w[idx - 2], 17) ^ ROTR(w[idx - 2], 19)
                            ^ SHR(w[idx - 2], 10);
            w[idx] = w[idx - 16] + s0 + w[idx - 7] + s1;
        }

        uint32_t h[8];
        //h[0] = a, h[1] = b...

        for(unsigned int j = 0; j < 8; ++j) {
        	h[j] = H[j];
        }

        for(unsigned int m = 0; m < 64; ++m) {
            uint32_t s0 = ROTR(h[0], 2) ^ ROTR(h[0], 13) ^ ROTR(h[0], 22),
                     maj = (h[0] & h[1]) ^ (h[0] & h[2]) ^ (h[1] & h[2]),
                     t2 = s0 + maj,
                     s1 = ROTR(h[4], 6) ^ ROTR(h[4], 11) ^ ROTR(h[4], 25),
                     ch = (h[4] & h[5]) ^ ((~h[4]) & h[6]),
                     t1 = h[7] + s1 + ch + k[m] + w[m];

            for(unsigned int j = 7; j > 0; --j) {
            	h[j] = h[j - 1];
            }

            h[0] = t1 + t2;
            h[4] += t1;
        }

        for(unsigned int j = 0; j < 8; ++j) {
        	H[j] += h[j];
        }
    }

    string ans;

    for(unsigned int i = 0; i < 8; ++i) {
        ostringstream oss;
        oss << hex << H[i];

        //on rajoute les zéros au début du nombre
        //puisqu'ils sont nécessaire dans le hash final

        unsigned int numberOfLeadingZero = 8 - oss.str().size();
        for(unsigned int j = 0; j < numberOfLeadingZero; ++j) {
            ans += "0";
        }
        ans += oss.str();
    }

    return ans;
}
#undef ROTR
#undef SHR

Notes sur le code

• J'utilise deux tableaux "à la C" parceque je n'ai à aucun moment besoin de leur taille, ou de la modifier.
• Pour que SHA256 fonctionne il faut qu'un char occupe 8 bits.

C'est très piéton comme implémentation. Est-ce que tu pourrais faire quelque chose de factorisé pour les bouts de code comme celui-ci ?

H[0] = H[0] + a;
        H[1] = H[1] + b;
        H[2] = H[2] + c;
        H[3] = H[3] + d;
        H[4] = H[4] + e;
        H[5] = H[5] + f;
        H[6] = H[6] + g;
        H[7] = H[7] + h;

Sinon, pourquoi est-ce que tu limites la portabilité en faisant des suppositions sur char, alors que tu utilises déjà uint8 qui apporte la garantie dont tu as besoin ?

J'avais pas fait attention, mais en effet le bout de code que tu as copié/collé est pas très beau.

J'ai aussi édité mon post pour utiliser des uint8_t*, au lieu de string en entrée, le seul "problème" que je trouve, c'est la lourdeur de l'appel à SHA256 du coup :

SHA256(reinterpret_cast< const uint8_t * >
    ("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"));

Ou si on a une string str :

SHA256(reinterpret_cast< const uint8_t * >(str.c_str()));

Certes il y a toujours moyen de faire une fonction template (qui fera elle même le reinterpret_cast) mais ça reste lourd.

Et puis ça pose un autre problème, si je suppose que j'ai des char de 8 bits, je peux faire :

for(; *str; ++str) {
    msg.push_back(*str);
}

Alors que si j'ai des chars de 16 bits que l'on considère comme des uint8_t, je vais avoir un problème si j'ai un char qui vaut : 0b0000000010000000, la recopie s'arrêtera à 0b00000000 alors que ça ne sera pas le caractère '\0', cela implique qu'il faut que je prenne en second paramètre la longueur de la chaîne, ce qui complique encore un peu plus l'appel :</span>

Il suffit de garder une string en entrée et de faire le reinterpret_cast dans SHA256.

Je pense que le plus propre serait d'avoir une fonction de ton API qui propose le bon type de donnée, à savoir un flot de uint8 (donc vecteur, séquence, la structure de donnée itérable de ton choix), et éventuellement de rajouter une fonction différente qui prend une chaîne, en précisant ses limitations.

vector< uint8_t > msg;

const uint8_t *str_ = reinterpret_cast< const uint8_t * >(str.c_str());

for(unsigned int i = 0, m = str.size() * sizeof(char); i < m; ++i) {
    msg.push_back(str_[i]);
}

peut être simplifié en :

const uint8_t* str_ = reinterpret_cast < const uint8_t * >(str.c_str());
vector < uint8_t > msg(str_, str_ + str.size()*sizeof(char));

Sinon, on peut également envisager d'utiliser std::basic_string < uint8_t > pour le paramètre de SHA256 en spécifiant un char_traits pour uint8_t si nécessaire.

Calcul divers : intégration par la méthode des rectangles

Principe

On va intégrer une fonction entre a et b par la méthode des rectangles (sommes de Riemann).

Complexité

O(n) ou n est le nombre de sous intervalles.

[C] Implémentation

double rectangle(double a, double b, int n)
{
    double h = fabs(b-a)/n;
    double res = 0;
    for(; n>=0; n--)
        res += h*f(n*h +a);
    return res;
}

Calcul divers : intégration par la méthode de trapèzes

Principe

On va intégrer une fonction entre a et b par la méthode des trapèzes.

Complexité

O(n) ou n est le nombre de sous intervalles.

[C] Implémentation

double trapeze(double a, double b, int n)
{
    double h = fabs(b-a)/n;
    double res = 0;
    for(;n>=0;n--)
        res += h*(f((n-1)*h +a) + f( (n*h) +a));
    return res/2;
}

Calcul divers : intégration par la méthode de Simpson

Principe

On va intégrer une fonction entre a et b par la méthode de Simpson.

Complexité

O(n) ou n est le nombre de sous intervalles.

[C] Implémentation

double simpson(double a, double b, int n)
{
    double h = fabs(b-a)/n;
    double res = 0;
    for(;n>=0;n--)
        res += ( f((n-1)*h+a) + 4*f(((n*h+a) +((n-1)*h+a))/2) + f(n*h+a));
    return res*(h/6);
}

Voilà, ça ne ce voit pas mais j'ai un exa d'analyse numérique lundi, alors je me suis dit que ce serait une bonne idée de coder ça, pis tant qu'à faire, autant faire profiter.

J'ai essayé d'optimiser un peu le code, dites moi ce que vous en pensez.
Je verrai aussi s'il est possible (sans rajouter 120 lignes) de faire en sorte qu'on ait l'intégral exacte sur machine. Mais vu que ce n'est pas une méthode itérative, je vois pas trop comment faire...

Hedi

Calculs divers : PGCD

[Common-Lisp] Implémentation

Un langage qu'on voit peu sur ce topic, le Common-Lisp (CL) ou plus simplement appelé lisp.

(defun pgcd (a b)
  (if (zerop b) a
      (pgcd b (mod a b))))

;(pgcd 10 5) -> 5

Calculs divers : Factorielle

[Common-Lisp] Implémentation

Je propose une implémentation de la factorielle de manière tail-rec. L'originalité ici repose sur le fait qu'il n'est pas nécessaire d'appeler la fonction avec l'accumulateur, dans mon implémentation je définis un paramètre optionnel acc qui prend pour valeur 1 si rien n'est précisé.

(defun fac (n &optional (acc 1))
  (if (zerop n) acc
      (fac (- n 1) (* acc n))))

; (fac 4) -> 24

Calculs divers : PPCM

[Common-Lisp] Implémentation

Ma fonction reçoit en paramètre trois arguments : deux entiers a et b et une fonction f.

Cet exemple est surtout là pour montrer le passage d'une fonction en CL, on peut clairement faire autrement.

(defun pgcd (a b)
  (if (zerop b) a
      (pgcd b (mod a b))))

(defun ppcm (a b f)
  (/ (* a b) (funcall f a b)))

; (ppcm 10 5 #'pgcd) -> 10

L'autre méthode plus simple est de définir le paramètre optionnel f avec comme valeur la fonction PGCD.

(defun pgcd (a b)
  (if (zerop b) a
      (pgcd b (mod a b))))

(defun ppcm (a b &optional (f #'pgcd))
  (/ (* a b) (funcall f a b)))

; (ppcm 10 5) -> 10

Hm, bof, l'exemple n'est pas terrible, puisque si tu passes une autre fonction en paramètre pour f le résultat n'est plus bon. Du coup, la fonction globale ne calcule pas vraiment le ppcm.

Oui c'est vrai, mais dans ce cas il n'y pas vraiment d'autres moyens d'appeler PGCD dans PPCM, hormis l'astuce de &optional (ou alors je ne les connais pas).

Je ne comprends pas, pourquoi le code suivant ne convient-il pas ?

(defun ppcm (a b)
  (/ (* a b) (pgcd a b)))

Remarque : on peut définir le pgcd (et le ppcm) étendu à un ensemble de nombres, et pas seulement deux nombres : c'est le plus petit diviseur (et multiple) commun à tous ces nombres. Dans un langage qui met en avant les listes comme Lisp, il serait assez naturel que tes définitions soient étendues à ces situations.

Hum, j'aurais pas dû pasté tout d'un bloc dans mon toplevel, ce code ne passait pas :

(defun pgcd (a b)
  (if (zerop b) a
      (pgcd b (mod a b))))

(defun ppcm (a b)
  (/ (* a b) (funcall pgcd a b)))

Mais si on prend le temps de déclarer une fonction après une autre, il passe.

Calculs divers : Algorithmes d'Euclide

L'algorithmes d'Euclide a pour but de calculer le PGCD (le Plus Grand Diviseur Commun) de deux nombres.

Principe

Le principe de cette algorithmes est de faire des divisions successives pour calculer le PGCD de deux nombres. Mais mieux vos un schéma : (fait par mes soins )

Implémentation en Basic Casio

'On calcule le PGCD de A et de B
Do
Int (B/A)->Q
B-AQ-R
A->B:R->A
LpWhile R=!0
'B est le PGCD

Il y a sans doute une faute de frappe à la quatrième ligne : B-AQ-R ?

Qu'est-ce qui se passe, quand on exécute ce code ? Il va modifier les variables A et B, qu'il faut avant remplir à la main, et demander soi-même à afficher B ensuite ?


De même, le diagramme n'est pas très clair. Si on ne connaît pas déjà l'algorithme, je ne suis pas sûr qu'on puisse le comprendre en lisant ce diagramme. Son problème c'est qu'il décrit des modifications d'état de façon implicite : "On divise le diviseur par le reste", il faut comprendre que "le reste" et "le diviseur" sont définis par rapport à la dernière division qui a été effectuée, ce qui n'est pas forcément clair (d'autant plus qu'il y a deux divisions différentes dans le diagramme).

Une formulation plus complexe, mais plus précise, serait de dire :
« On remplace le plus grand des deux nombres par le reste de sa division euclidienne par le plus petit. »
« Le plus petit des deux nombres est-il nul ? »

Voilà une implémentation du PGCD en C :

int ___(int _,int __){return _%__?___(__,_%__):__;}

Les compilos acceptent ce genre de noms ?

Ouais. =D

Citation : Pouet_forever

Voilà une implémentation du PGCD en C :

int ___(int _,int __){return _%__?___(__,_%__):__;}

Qu'est ce que vous avez contre le PGCD (comité anti, toussa...) ?

hahaha, joli joli.
À moi maintenant (je vous laisse deviner ce que ça fait) :

int __(char *_) { return *_++?1+__(_):0; }

strlen

héhé, ce n'était pas très dur en même temps

Citation : Eusebus

Après avoir fait pas mal de calculs (une jolie somme en fait), j'en ai déduit que cet algorithme est en <math>\(O(n \cdot \psi(\sqrt{n}))\)</math> et je vous renvoie ici pour savoir ce que c'est que <math>\(\psi\)</math> : http://fr.wikipedia.org/wiki/Fonction_digamma

C'est <math>\(\Theta(n \log\log n)\)</math> et non <math>\(\Theta(n \log n)\)</math>
Démo vite faite :
<math>\(\Theta(\sum_{p<N} \frac{N}{p})=\Theta(N\sum_{p<N} {1/p})=\Theta(N\int_2^{\frac{N}{\log N}}\frac{dx}{x \cdot \log x})=\Theta(N \cdot \log\log N)\)</math>
Il peut s'améliorer en <math>\(\Theta(N)\)</math> et même en <math>\(\Theta(\frac{N}{\log N})\)</math>.

Citation

Notons que cet algorithme, même s'il a une complexité temps meilleure que le test de tous les diviseurs inférieur à la racine, a une complexité mémoire bien supérieure : on passe en effet de O(1) à O(n). Boire ou conduire, il faut choisir.

Heureusement, on peut facilement l'améliorer pour qu'il n'utilise que <math>\(\Theta(\sqrt N)\)</math> bits en mémoire.

int _(int *__){return __?__*_(__--):1};
Ça devrait marcher.

edit :
int _(int *__,int *___){return ___?___--;___--;_(__,___)*_(__,___)*___%2?__:1:1};
Je suis moins sûr de moi sur celui là.

Citation : Maxibolt

Ça devrait marcher.

Loupé.
Pareil pour le deuxième. =D

--__ , et pas de point-virgule après une définition de fonction (par contre, dans le corps de la fonction faut finir l'instruction). Ça fait longtemps que t'as pas fait de C, hein ?

5 ans

Pour en revenir a l'algorithme d'Euclide, voici une petite implementation en assembleur intel x86 (syntaxe AT & T, gcc sous linux) :

.text
.global  pgcd

pgcd:
        push    %ebp
        mov     %esp, %ebp

        mov     8(%ebp), %eax
        mov     12(%ebp), %ecx
        push    %edx

.loop:
        cmp     $0, %ecx
        je      .end
        xor     %edx, %edx
        div     %ecx
        mov     %ecx, %eax
        mov     %edx, %ecx
        jmp     .loop

.end:
        pop     %edx
        leave
        ret

Arbre binaire de recherche équilibré - AVL

Principe

Le principe d'un arbre équilibré est de garantir des opérations (recherche, suppression) en temps O(log n) dans un arbre binaire, en introduisant un système permettant à l'arbre de rester équilibré - c'est à dire que l'écart entre le nombre de fils de chaque noeud reste toujours optimal. C'est ce qui va permettre de rendre un arbre binaire de recherche réellement intéressant.

Le premier type d'arbre de ce genre inventé est l'arbre AVL, c'est aussi l'un des plus simple à mettre en oeuvre. Le principe est d'introduire un mécanisme de rotations des branches de l'arbre au cours de l'insertion et de la suppression pour garantir l'équilibre dudit arbre. se rapporter à la page Wikipédia pour plus d'informations.

Complexité

L'insertion et la suppression de clé se font en O(log n). Bien que ce soit moins bien qu'avec une Hashtable, les ABR équilibrés restent extrêmement utilisés, notament en raison d'une plus grande souplesse de gestion de mémoire O(n).

[C] Implémentation

La majorité des langages évolués fournissent ce genre d'outil. Ce type d'arbre existe certainement dans des bibliothèques C, mais ne fait pas partie de la lib standard. Voici une implémentation générique en C :

#include <stdlib.h>


/* structure de l'arbre binaire de recherche equilibre AVL */
typedef struct node
{
    void* key;          /* pointeur sur la cle */
    unsigned h;         /* hauteur du noeud */
    struct node* fd;    /* fils droit (superieur au noeud) */
    struct node* fg;    /* fils gauche (inferieur au noeud) */
}
tsearch_avl;

/* recherche recursive d'une cle */
void* search_key (tsearch_avl* abr, const void* key, int (*compar)(const void*, const void*))
{
    while (abr != NULL)
    {
        if (compar(key, abr->key) == 0)
            return abr->key;
        else if (compar(key, abr->key) > 0)
            abr = abr->fd;
        else
            abr = abr->fg;
    }
    return NULL;
}

#define _hauteur(a)     ( a == NULL ? 0 : a->h )
/* calcule la hauteur d'un noeud a partir de ses sous-noeuds */
static inline void calc_hauteur (tsearch_avl* abr)
{
    unsigned a, b;
    abr->h = 1 + ( (a = _hauteur(abr->fg)) > (b = _hauteur(abr->fd)) ? a : b );
}

/* rotations AVL */
static inline tsearch_avl* rotate_g (tsearch_avl* p)
{
    tsearch_avl *q, *v;
    q = p->fd;
    v = q->fg;
    q->fg = p;
    p->fd = v;
    calc_hauteur(p);
    calc_hauteur(q);
    return q;
}

static inline tsearch_avl* rotate_d (tsearch_avl* q)
{
    tsearch_avl *p, *v;
    p = q->fg;
    v = p->fd;
    p->fd = q;
    q->fg = v;
    calc_hauteur(q);
    calc_hauteur(p);
    return p;
}

/* equilibrage suivant le principe AVL */
static tsearch_avl* equilibrage (tsearch_avl* abr)
{
    unsigned hg = _hauteur(abr->fg), hd = _hauteur(abr->fd);
    if (hg-hd == 2)
    {
        if ( _hauteur(abr->fg->fg) < _hauteur(abr->fg->fd) )
            abr->fg = rotate_g (abr->fg);
        abr = rotate_d (abr);
    }
    else if (hd-hg == 2)
    {
        if ( _hauteur(abr->fd->fd) < _hauteur(abr->fd->fg) )
            abr->fd = rotate_d (abr->fd);
        abr = rotate_g (abr);
    }
    return abr;
}

/* fonction recursive de suppression d'une cle dans l'arbre binaire de recherche */
void delete_key (tsearch_avl** abr, const void* key, int (*compar)(const void*, const void*))
{
    tsearch_avl *tmp;
    if (*abr != NULL)
    {
        /* si la cle est trouvee, on effectue la suppression */
        if (compar(key, (*abr)->key) == 0)
        {
            if ((*abr)->fd == NULL && (*abr)->fg == NULL)
            {
                free(*abr);
                *abr = NULL;
            }
            else if ((*abr)->fg == NULL)
            {
                tmp = *abr;
                *abr = (*abr)->fd;
                free(tmp);
            }
            else if ((*abr)->fd == NULL)
            {
                tmp = *abr;
                *abr = (*abr)->fg;
                free(tmp);
            }
            else
            {
                tmp = (*abr)->fd;
                while (tmp->fg != NULL)
                    tmp = tmp->fg;
                (*abr)->key = tmp->key;
                delete_key (&(*abr)->fd, tmp->key, compar);
            }
        }
        else if (compar(key, (*abr)->key) > 0)
            delete_key (&(*abr)->fd, key, compar);
        else
            delete_key (&(*abr)->fg, key, compar);
        /* reequilibre et recalcule la hauteur
           le long de la remontee recursive */
        if (*abr != NULL)
        {
            *abr = equilibrage (*abr);
            calc_hauteur(*abr);
        }
    }
}

/* cree une nouvelle feuille allouee dynamiquement */
static tsearch_avl* new_leaf (const void* key)
{
    tsearch_avl* leaf = malloc(sizeof *leaf);
    if (leaf != NULL)
        leaf->key = (void*) key, leaf->fg = NULL, leaf->fd = NULL, leaf->h = 1;
    return leaf;
}

/* fonction recursive d'insertion d'une cle dans l'arbre */
void insert_key (tsearch_avl** abr, const void* key, int (*compar)(const void*, const void*))
{
    if (*abr == NULL)
        *abr = new_leaf(key);
    else
    {
        if (compar(key, (*abr)->key) > 0)
        {
            insert_key(&(*abr)->fd, key, compar);
        }
        else if (compar(key, (*abr)->key) < 0)
        {
            insert_key(&(*abr)->fg, key, compar);
        }
        /* reequilibre et recalcule la hauteur
           le long de la remontee recursive */
        *abr = equilibrage (*abr);
        calc_hauteur(*abr);
    }
}

/* fonction de suppression de l'arbre binaire de recherche - libere la memoire allouee */
void tsearch_delete (tsearch_avl** abr)
{
    if (*abr != NULL)
    {
        if ((*abr)->fg != NULL)
            tsearch_delete (&(*abr)->fg);
        if ((*abr)->fd != NULL)
            tsearch_delete (&(*abr)->fd);
        free(*abr), *abr = NULL;
    }
}

Recherche de chemin: A*

Principe

A* est un algorythme de recherche de chemin axé sur la performance, c'est-à-dire qui trouvera un chemin assez rapidement mais pas forcément le plus court (généralement assez proche quand même), par opposition à un algorythme qui recherche à tout prix la solution la plus courte mais nécéssitant plus de temps (algorythme de Dijkstra).
Vous trouverez plus de détails sur cet algorythme dans ce tutoriel.

Complexité

L'algorythme de Dijkstra étant en o((m+n)*ln(n)), on espère qu'A* est généralement meilleur pour un terrain pas trop accidenté. Il faut quand même noter qu'il met pas mal de temps avant de se rendre compte qu'un chemin est impossible sur de grand graphes, spécialement entre deux composantes connexes (typiquement, deux îles séparées par la mer sur une carte)

Java

Cette impémentation est indépendante des données manipulées. La seule restriction que vous avez est que chaque noeud doit implémenter l'interface Node et que la distance entre deux noeuds d'un même graphe soit cohérente.

L'interface Node que vous devez implémenter :

import java.util.*;
public interface Node {
public Iterable<? extends Node> getNeighbours (Object param) ;
public Iterable<? extends Node> getNeighbours () ;
public double getDistanceTo (Node node) ;
}

Puis l'algorythme proprement dit:

import java.util.*;

public class AStarPathFinder {
private class Item implements Comparable<Item> {
protected double cost1, cost2, totalCost;
protected Item parent;
protected Node node;
public Item () {}
public Item (double a, double b, double c, Item p, Node n) {
cost1=a;
cost2=b;
totalCost=c;
parent=p;
node=n;
}
public boolean equals (Object o) {
return ((Item)o).node.equals(node);
}
public int hashCode () { 
return node.hashCode();
}
public int compareTo (Item it) {
if (this.totalCost<=it.totalCost) return -1;
else return 1;
}}

private NavigableSet<Item> openList = new TreeSet<Item>();
private Set<Item> closedList = new HashSet<Item>();
private Deque<Node> path = null;
private Node start, end;
private Item tmp = new Item();
private Object param;
private boolean impossible = false;

public AStarPathFinder (Node s, Node e, Object p) {
start=s;
end=e;
param=p;
}
public AStarPathFinder (Node s, Node e) { this(s,e,null); }
public AStarPathFinder () { this(null,null,null); }

public void clear () {
openList.clear();
closedList.clear();
path = null;
impossible = false;
}
private void calculatePath () {
clear();
openList.add(new Item(0, 0, 0, null, start));
browseOpenList();
}
private void browseOpenList () {
Item e;
while ((e = openList.pollFirst())!=null) {
closedList.add(e);
if (e.node.equals(end)) break;
browseNeighbours(e);
}
if (e!=null && e.node.equals(end)) buildPath(e);
else impossible = true;
}
private void browseNeighbours (Item it) {
for (Node n : it.node.getNeighbours(param)) {

tmp.node = n;
if (closedList.contains(tmp)) continue;
double cost1 = it.cost1 + it.node.getDistanceTo(n);
double cost2 = end.getDistanceTo(n);
double totalCost = cost1 + cost2;
if (openList.contains(tmp)) {
Item e = openList.ceiling(tmp);
if (e.totalCost <= totalCost) continue;
else {
openList.remove(e);
openList.add(new Item(cost1, cost2, totalCost, it, n));
}}
else openList.add(new Item(cost1, cost2, totalCost, it, n));
}}
private void buildPath (Item it) {
path = new LinkedList<Node>();
while (!it.node.equals(start)) {
path.addFirst(it.node);
it = it.parent;
}}
public Queue<Node> getPath () {
if (path==null && !impossible) calculatePath();
return path;
}
public Queue<Node> getPath (Node start, Node end, Object param) {
this.start = start;
this.end = end;
this.param = param;
calculatePath();
return path;
}
public Queue<Node> getPath (Node start, Node end) { return getPath(start,end,null); }
}

Qu'on peut très facilement utiliser de cette manière :

Collection<Node> path = new AStarPathFinder(noeudDépart, noeudARrivée, paramètre).getPath();

L'objet paramètre est une donnée utilisateur qui sera passée à chaque appel de getDistanceTo. ON peut ainsi passer des critères de recherches spécifiques par exemple.

Améliorations possibles: encore plus profiter de la généricité.

Voilà, amusez-vous bien !

QuentinC 2>>l'indentation a pas du aimer le copier coller...

Citation

QuentinC 2>>l'indentation a pas du aimer le copier coller...

C'est pas grave. Il est plus que probable que celui qui en fera un copier-coller le fera dans un IDE qui le réindentera automatiquement.
La vraie raison c'est que je ne sais pas pourquoi...