IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
logo
Sommaire > Algorithmes
        2.1. Tris (6)
                Tri à bulles
                Tri par insertion
                Tri rapide
                Tri par selection
                Tri de Shell
                Tri par paniers
        A*
        Distance de Levenshtein

rechercher
precedent    sommaire    suivant    telechargermiroir


Auteur : khayyam
Version : 13/08/2008
Page de l'auteur
Téléchargez le zip
A*
Voici un exemple d'implémentation de l'algorithme A* réalisé par khayyam dans son article Recherche de chemin par l'algorithme A*


Auteur : Davidbrcz
Version : 13/08/2008
Distance de Levenshtein
Voici une implémentation de la distance de Levenshtein pour calculer la similarité entre 2 chaînes. Ce code utilise cette classe crée par r0d pour simuler des tableaux 2D.

template <class T> int distanceLevenshtein(const T& s1,const T& s2)
{
    const int N1= s1.size();
    const int N2= s2.size();

    if(N1==0)
      return N2;

    if(N2==0)
      return N1;
    
    int cout;
    DynMatrix::Dyn2DMatrix<int> mat(N1+1,N2+1);

    for(int i=0;i<=N1;++i)
      mat(i,0)=i;

    for(int i=0;i<=N2;++i)
      mat(0,i)=i;

     for(int i=1;i<=N1;++i)
     {
       for(int j=1;j<=N2;++j)
       {
          cout= s1[i-1]==s2[j-1] ? 0 : 1;

           mat(i,j)=std::min(std::min(mat(i-1,j)+1,mat(i,j-1)+1),mat(i-1,j-1)+cout);
       }
     }

    return mat(N1,N2);
}

rechercher
precedent    sommaire    suivant    telechargermiroir

Consultez les autres pages sources


Valid XHTML 1.1!Valid CSS!

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2004 Developpez Developpez LLC. Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents et images sans l'autorisation expresse de Developpez LLC. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.