Lalgorithme de Hoshen-Kopelman est un algorithme de partitionnement () des cases d'un réseau, autrement dit, il permet de dénombrer les amas d'un type d'objet dans un réseau fini. Il est utilisé pour étudier la percolation.
Problème algorithmique Le problème algorithmique résolu par l'algorithme est le suivant : étant donné une grille dont chaque case est soit occupée, soit inoccupée, regrouper les cases occupées en paquets tels que tous les paquets sont formés de cellules contiguës et qu'il y ait le moins de paquets possible (c'est-à-dire que deux paquets ne soient pas contigus)..
Description L'algorithme est une application de la structure de données union-find.
Histoire et utilisations Il a été développé par J. Hoshen et R. Kopelman en 1976 Percolation and cluster distribution. I. Cluster multiple labeling technique and critical concentration algorithm, Phys. Rev. B 14, 3438 - 3445 (1976). dans le cadre de la détermination de la percolation d'un réseau. Il est toujours utilisé dans ce cadre, de même que l'algorithme de Leath-Alexandrowicz....
Notes et références
Liens externes
Catégorie:Physique statistique Catégorie:Algorithme numérique