Algorytm Hoshena-Kopelmana

Hoshen-Kopelman algorytm jest podział algorytm ( klastry ) komórek w sieci, to znaczy, że umożliwia zliczanie ognisk typu obiektu w skończonego sieci. Służy do badania perkolacji .

Problem algorytmiczny

Algorytmiczne problem rozwiązany za pomocą algorytmu jest następujący: dana siatka, w której każda komórka jest zajętych lub zajęte, grupa zajmowana komórek na pakiety, tak, że wszystkie pakiety są utworzone z sąsiednich komórek, a która jest co najmniej o pakietach możliwe ( tj. dwa pakiety nie są ciągłe).

Opis

Algorytm jest aplikacją struktury danych znajdowania sumy .

Historia i zastosowania

Został on opracowany przez J. Hoshena i R. Kopelmana w 1976 roku w ramach określania przesiąkania sieci. Jest nadal używany w tym kontekście, podobnie jak algorytm Leatha-Alexandrowicza.

Uwagi i odniesienia

  1. Tobin Fricke, „  The Hoshen-Kopelman Algorithm  ”, na Uniwersytecie Kalifornijskim w Berkeley ,2000.
  2. (in) Perkolacja i dystrybucja klastrów. I. Technika wielokrotnego znakowania klastra i algorytm krytycznego stężenia, Fiz. Obrót silnika. B 14, 3438-3445 (1976) .
  3. „  Algorytmy w perkolacji  ” , na Uniwersytecie w Oldenburgu .
  4. PL Leath, „  Wielkość klastra i rozkład granic w pobliżu progu perkolacji  ”, Physical Review B , vol.  14 N O  11 1976, s.  5,046.
  5. Z. Alexandrowicz, „  Krytycznie rozgałęzione łańcuchy i klastry perkolacyjne  ”, Physics Letters A , vol.  80, n o  4, 1980, s.  284-286.

Linki zewnętrzne