Algorithme de Hoshen-Kopelman

L'algorithme de Hoshen-Kopelman est un algorithme de partitionnement (clustering) 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)[1].

Description

L'algorithme est une application de la structure de données union-find[1].

Histoire et utilisations

Il a été développé par J. Hoshen et R. Kopelman en 1976[2] 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[3],[4],[5].

Notes et références

  1. ↑ a et b Tobin Fricke, « The Hoshen-Kopelman Algorithm », sur Université de Californie à Berkeley, .
  2. ↑ (en) Percolation and cluster distribution. I. Cluster multiple labeling technique and critical concentration algorithm, Phys. Rev. B 14, 3438 - 3445 (1976).
  3. ↑ « Algorithms in percolation », sur Université d'Oldenbourg.
  4. ↑ P. L. Leath, « Cluster size and boundary distribution near percolation threshold », Physical Review B, vol. 14, no 11,‎ , p. 5 046.
  5. ↑ Z. Alexandrowicz, « Critically branched chains and percolation clusters », Physics Letters A, vol. 80, no 4,‎ , p. 284-286.

Liens externes