Javaa: ongelma Primin algoritmin kanssa

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Primin algoritmi löytää yhtenäisestä kaaripainoisesta verkosta pienimmän mahdollisen virittävän puun.

Tällä hetkellä Primille annetaan syötteenä verkko, jonka solmut ovat omia olioita. Solmuilla on singulaarinen linkitetty lista jossa datana (naapurin id = verkon solmutaulun indeksi, paino). Linkitetty lista kuvaa kaarta.

Aputietorakenteena käytetään binääristä minimikekoa, jossa tällä hetkellä on avain (kaaripaino) ja datana verkon solmu

Pseudokoodia:

for each v neighbours(u,v) do
if (v in_heap and weight(u,v) < key[v] then {
parent[v] <-- u;
heap.decreasekey(v, weight(u,v))
}

Ongelmani tulee kaaripainon = avaimen vertailussa. Solmussa on naapurit listattuna linkitettynä listana, jossa on solmun id. Tämän saa tietysti helposti ulos käsiteltäväksi. Keossa taas on solmut sekaisin, koska avaimena on kaaripaino. En siis pääse vertailemaan oikeita kahta solmua keskenään.

Karvalakkiratkaisuja, jotka eivät toimi, koska samalla menetetään algoritmin tehokkuus:
- "käy kaikki keon solmut läpi kunnes oikea id löytyy"
- "päivitä naapurilista kun swappaat keossa solmuja"

Kuten aina harjoitustyön ohjaajat ovat laiskoja lukemaan ja vastailemaan maileihin...

Ongelmaan löytyy varmasti jokin todella yksinkertainen ratkaisu, mutta en vain tunnu saavan sitä päähäni.

Kommentit (0)

Uusimmat

Suosituimmat