ALGORITMIEN SUUNNITTELU JA ANALYYSI 

Kevät-2007

 

Harjoitus 5. 

 

 

1.  Etsi sivulla 55 olevan leikkauspisteet-algoritmin avulla alla esitetyssä kuvassa olevien janojen leikkauspisteet.  Käy algoritmia läpi vaihe vaiheelta.  Ilmoita kunkin pysähdyspisteen kohdalla rakenteisiin lisättävät ja poistettavat alkiot.  Käytettyjä rakenteita ei tarvitse kuvata.

 

 

     6

 

     5

 

     4

 

     3

 

     2

 

     1

    

 

 

                   1       2        3        4        5        6       7        8        9        10      11

 

 

2.  Säännöllisen 6-kulmion kunkin sivun pituus on 1.  Etsi kuvion optimaalinen kolmiointi opetusmonisteen kohdan 3.4.1 kuvaamalla menetelmällä.  Kolmiointi on optimaalinen, jos kolmioiden sivujen yhteispituus on mahdollisimman pieni.  Koska ratkaisu on työläs, on seuraavassa esitetty alkuosa tehtävän ratkaisusta:

 


     Numeroidaan monikulmion kärkipisteet nollasta viiteen. Merkitään myös monikulmion erilaisten sisäsivujen pituuksiksi a ja b; yhtä hyvin nämä voisi laskea jo nyt, mutta laskut näyttävät siistimmiltä, jos niitä merkitsee vielä symboleilla.

     Lasketaan arvoja T[i,j] seuraavanlaiseen taulukkoon:

5

 

 

 

 

 

x

4

 

 

 

 

x

x

3

 

 

 

x

x

x

2

 

 

x

x

x

x

1

 

x

x

x

x

y

i = 0

x

x

x

x

(x)

 

 

j = 0

1

2

3

4

5

 

 

 

 

 

 

 

 

 

     Tässä y:llä merkitty alkio (T[1,5] eli T[1, n], n = 5) kertoo halutun optimaalisen kolmioinnin hinnan, mutta sen laskemiseksi pitää ensin laskea kaikki x:llä merkityt alkiot.

 

     Aloitetaan vasemmanpuoleisesta vinorivistä T[0, 0], T[1, 1], T[2, 2], T[3, 3], T[4, 4], T[5, 5]. Kaik­ki nämä alkiot ovat nollia, koska ne ovat muotoa T[i,j] ,i = j.

 

     Lasketaan seuraavaa vinoriviä.  Nyt käytetään jo T:n määritelmän minimin sisältävää osaa, mutta minimin sisällä on vain yksi vaihtoehto.

 

          T[0,1]  =  min{T[0,0] + T[1,1] + w(-1,0,1)}      =   min{0 + 0 + (1 + 1 + a)}  =  a + 2

 

     Tässä w(-1,0,1) = w(5,0,1) = 1 + 1 + a = a + 2.  w(x,y,z) on siis kärkipisteiden (x,y,z) määräämän kolmion sivujen pituuksien summa. Kärkipiste -1 on sama kuin kärkipiste 5, joten sivut ovat 5 → 0, 0 → 1 ja 1 → 5.  Näiden pituudet ovat 1, 1 ja a (ks. kuvaa).

     Seuraavassa vinorivissä minimiä pitääkin jo laskea.  Kaikki laskua varten tarvittavat T:n arvot on jo laskettu.

 

          T[0,2]         = min { T[0,0] + T[1,2] + w(-1,0,2),   T[0,1] + T[2,2] + w(-1,1,2) }

                             = min { 0 + (a + 2) + (1 + a + b),   (a + 2) + 0 + (a + 1 + b) }

                             = min { 2a + b + 3,   2a + b + 3 }     =     2a + b + 3

 

 

3.  Erään union-find-rakenteen taulukkoesityksen p sisältö on:

    

i

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

p(i)

1

5

4

1

1

7

7

5

10

10

11

9

2

10

2

9

5

     Rakenteeseen kohdistetaan operaatio  union(find(15), find(9)).   Union tehdään puun koon mukaan ja  find-operaatiossa polku tiivistetään (opetusmon: kohdan 4.2.1 alakohdat 2 ja 4).

 

          a)       Piirrä taulukon sisältämä metsä ennen operaatioiden suorittamista.

          b)      Piirrä metsä find-operaatioiden jälkeen.

          c)       Piirrä find- ja union-operaatioiden jälkeinen lopullinen metsä.

          d)      Esitä lopullinen metsä taulukkona.

 

 


4.  Selvitä askeleittain, miten Primin algoritmi löytää alla olevan verkon minimaalisen virittävän puun lähtien solmusta b.  Algoritmin käyttämää kekoa ei tarvitse näyttää.