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