Klusteroindualgoritmu

Kui tunnustua murdehet Bubrihan murrehatlasas? Suurikogozen 220-sivuhizen kirjan syväindön voi sumbendua 186x206 taulukokse, kudaman elementat ozutetah tyhjäl libo yhtel libo monen kirjaimel, kudai ozuttau vastavusvaihtoehton täs paikas. Leskizen kirjan tiedoloil atlasua voi tävvendiä kuvvel paikal 192:h.

Wiik ečči murrehrajoi verduamal kartal vierekkäi sijaiččijoi paikkoi, kui suuri oli susiedoin väline ero. Nenga huahmoituttih murreherot. Paikkoi on 186 da paikkupuaroi 186x185/2. Verdailus on äijy ruaduo da varavo on edukädeh duumaija, kus murrehrajat ollah da löydiägi rajat, kus niilöi eččiy. Tiedokoneh on boikoimbi da objektiivizembi massiivizeh ečindäh.

Pädevy algoritmu murdehien luokitteluh löydyy vuottamattomas suunnas. Algoritmiloin teories virittäjän puun algoritmoil ečitäh optimualine taba yhtistiä ezim. kartan čökkehii optimualizesti. Čehieläine inženieru Otakar Boruvka keksi vuonnu 1926 algoritman, kui yhtistiä paikat optimualizesti sähköliinielöil. Tämän algoritman rinnakkaistettu versii yhtistäy enzimäi lähimät susiedat "klusteriloikse" da sit tazo tazol yhtistäy klusteriloi suuremmikse klusteriloikse, kuni kai puututah yhteh klusterih. Algoritmu löydyy sežo Sollinin algoritman nimel JaJa:n kirjas. Pseudo-ohjelmoindukielel algoritmua voi kuvata nenga:

  # luaji erotaulukko
  for all kartu k do
    for all paikku p do
      luve arvo[k,p]
  for all paikku p do
    for all paikku q do
      ero[p,q]=0
      for all kartu k do
        if arvo[k,p]<>arvo[k,q] then ero[p,q]=ero[p,q]+1
  # lövvä lähin susiedu
  for all paikku p do
    min=999 # "iäretöi"
    for all paikku q do
      if p<>q and ero[p,q]< min then 
        min=ero[p,q]; sus[p]=q
  # luaji klusterit
  klusterit=[]
  for all paikku p do
    piirrä nuoli p->sus[p]
  # on tarkah yksi puaru p->q, q->p
  for all paikku p do
    if p=sus[sus[p]] then 
      liziä p klusteriloih
      klusteri[p]=[]
      # p on klusterin juuri
  for all paikku q
    while q ei joukos klusterit do
      mene juureh p susiedunuolii myö 
      liziä q joukkoh klusteri[p] da piirrä viiva q-p 
  # klusterit lövvetty
  
  # voi jatkua rekuriivizesti
  # uuzi erotaulukko klusteroile (kudamii juuret edustetah)
  for all p in klusterit
    for all q in klusterit
      ero[p,q]=999
      for all m in klusteri[p]
        for all n in klusteri[q]
	  if ero[m,n]<ero[p,q] then ero[p,q]=ero[m,n]
  Jatka kui enzimäzel kierroksel
  Jatka kuni klusteroi jiäy vaiku yksi.

Ohjelmas on eri versielöi Python da Java ohjelmoindukielil. Python ohjelmoindukielel algoritmu syndyy 300 rivih. Interaktiivine verkos ajettavu Javascript ohjelmu syndyy 45 rivih.

Vihjavukset