ALGORITMIEN SUUNNITTELU JA ANALYYSI 

Kevät-2007

 

Harjoitus 6. 

 

1.  Kirjoita hajoita ja hallitse menetelmään perustuva algoritmi, joka visualisoi puun tasoon.  Algoritmi siis valitsee puun solmuille paikat siten, että solmut eivät ole toistensa päällä eivätkä puukaaret risteä.  Solmun koko (ympyrän säde) on s (siis vakio) ja solmujen keski­pisteiden etäisyyden täytyy olla vähintään  d (myös vakio, 2s < d).

 


2.  Selvitä askeleittain, miten Kruskalin algoritmi löytää alla olevan verkon minimaalisen virittävän puun.  Algoritmin käyttämää union-find-rakennetta ei tarvitse näyttää.

 

 


3.  Ratkaise opetusmonisteen kohdassa 5.3.1 (Kauppamatkustajan ongelma) esitetyllä branch-and-bound-algoritmilla kauppamatkustajan ongelma alla olevassa verkossa.

 

4.  Maantiekarttaa voidaan kuvata verkkona, jonka solmut ovat kaupunkeja ja kaaret niiden välisiä teitä.  Kaaren paino on tien pituus kilometreissä.  Lisäksi kaupungeista tiedetään koordinaatit, joten voi­daan laskea linnuntie-etäisyyksiä kaupunkien välillä.

 

     Tee algoritmi, joka etsii maantiekarttaa kuvaavasta verkosta lyhimmän reitin kahden annetun kaupungin välille käyttäen apuna kaupunkien välisiä linnuntie-etäisyyksiä.   Vihje: Hyvä tapa mitata puolivalmiin reitin hyvyyttä on laskea yhteen tähän mennessä muodostetun reitin pituus ja linnuntie-etäisyys reitin päätepisteestä kohdekaupunkiin.

 

 

 

5.  Lyhimmän reitin pituutta kahden solmun välillä nimitetään solmujen väliseksi etäisyydeksi.  Verkon keskus on solmu, josta on mahdollisimman lyhyt etäisyys kauimpana sijaitsevaan solmuun.  Tee algoritmi, joka etsii annetun verkon keskuksen.  Kaarten painojen lisäksi ei tunneta solmujen koordinaatteja.

 

6.  Opetusmonisteen sivulla 96 (kohta Approksimointialgoritmeista) kuvattu laatikoiden pakkaus­ongel­man first-fitiä parempi ratkaisutapakaan ei ole optimaalinen.  Keksi esimerkki, jossa se ei anna optimaalista ratkaisua.  Paljonko sen antama ratkaisu eroaa esimerkissäsi optimista?