DESAIN DAN ANALISIS STRUKTUR DATA NON LINIER ROOTED TREE DINAMIS (Kata kunci: Graf, Struktur data, tree, LCA, pemrograman dinamis)

PRESENTASI TUGAS AKHIR – KI091391 DESAIN DAN ANALISIS STRUKTUR DATA NON LINIER ROOTED TREE DINAMIS (Kata kunci: Graf, Struktur data, tree, LCA, pemrograman dinamis)

Penyusun Tugas Akhir : Nur Ahmad Wahid (NRP: 5110.100.702) Dosen Pembimbing : Arya Yudhi Wijaya, S.Kom., M.Kom. Rully Soelaiman, S.Kom., M.Kom. 18/07/2014

Tugas Akhir - KI091391

1

Kerangka Presentasi Pendahuluan

Latar Belakang

Rangkaian Proses

Ilustrasi Permasalahan

Uji Coba dan Analisis

Batasan Masalah

Kesimpulan

Tujuan

18/07/2014


2

Latar Belakang  Rooted tree yang merupakan graf berarah memiliki tepat 1 vertex sebagai root dan semua edge yang terhubung pada tree diarahkan berlawanan dari root  Banyak permasalahan-permasalahan yang dapat ditemukan dalam pengimplementasian struktur data rooted tree.  Pada setiap vertex yang terhubung pada tree memiliki bobot masing-masing. Bagaimana menarik informasi jumlah bobot dari vertex-vertex yang terhubung pada suatu subtree secara tepat dan efisien dengan root yang dapat berubah-ubah.

18/07/2014


3


18/07/2014


4


18/07/2014


5

Ilustrasi Permasalahan  http://www.spoj.com/problems/DRTREE  Diberikan masukan struktur rooted tree dengan banyak vertex 𝑁 (𝑁 ≤ 105 )  Inisialiasi root awal pada vertex 1  Bobot sebuah vertex 𝑖 𝑤[𝑖] (1 ≤ 𝑤[𝑖] ≤ 109 )  Terdapat 𝑄 operasi (Q ≤ 105 ) :  Ri : menjadikan vertex i sebagai root  Si : mengembalikan nilai berupa jumlah bobot semua vertex yang terdapat pada subtree dengan i sebagai rootnya

18/07/2014


6

Batasan Masalah  Input dan output program menyesuaikan dengan Soal SPOJ Klasik 14943 beserta batasan-batasan lainnya  Bahasa pemrograman yang digunakan adalah C++

18/07/2014


7

Tujuan  Menganalisis dan merancang algoritma yang efisien untuk menyelesaikan masalah penarikan informasi dari struktur data rooted tree dinamis.  Mengimplementasikan struktur data dan algoritma yang telah terancang untuk menyelesaikan masalah penarikan informasi dari struktur data rooted tree dinamis secara efisien.  Menganalisis kompleksitas waktu dan ruang (space) algoritma yang diterapkan pada struktur data yang telah dirancang.

18/07/2014


8

Kerangka Presentasi Pendahuluan Rangkaian Proses

Permasalahan LCA Kasus LCA pada rooted tree Penyelesaian LCA

Uji Coba dan Analisis Kesimpulan

18/07/2014


9

Permasalahan LCA  Lowest Common Ancestor (LCA) adalah sebuah konsep dalam teori graf dan ilmu komputer.  Misalkan 𝑇 adalah rooted tree dengan 𝑛 vertex. Lowest Common Ancestor antara dua vertex 𝑣 dan 𝑤 didefinisikan sebagai vertex terendah di 𝑇 yang memiliki baik 𝑣 dan 𝑤 sebagai keturunan.  Dengan memanfaatkan konsep ini, maka rooted tree pada real memory tidak perlu berubah struktur dengan dilakukannya proses inisialiasi jumlah bobot vertex pada setiap subtree

18/07/2014


10

Kasus LCA pada rooted tree 1

LCA(2, 14)

Subtree dengan root vertex 2

2

Root dari rooted tree saat ini adalah r, dan vertex yang ditanyakan jumlahan subtree-nya adalah u maka …

3 4

6

5

7

8 9

10

 LCA(u, r) ≠ u, jawabannya adalah sum[u].

13 11

12

14

15

current root 16

18/07/2014


11

Kasus LCA pada rooted tree 1 LCA(3, 14)

2

Subtree dengan root vertex 3

3 4

6

5

7

8 9 13

11

12

14

15

10

Root dari rooted tree saat ini adalah r, dan vertex yang ditanyakan jumlahan subtree-nya adalah u maka …  LCA(u, r) adalah u, maka cara hitungnya adalah sum[1] dikurangi sum[v], yang mana v adalah salah satu child dari u yang mengarah ke r.  Pengecualian jika u = r, maka jawabannya adalah sum[1]

current root 16

18/07/2014


12

Kerangka Presentasi Permasalahan LCA Rangkaian Proses

Kasus LCA pada rooted tree Penyelesaian LCA

18/07/2014


13

Kerangka Presentasi Algoritma Path Doubling Reduksi LCA ke RMQ Penyelesaian LCA Algoritma Sparse Table Algoritma Khusus Permasalahan RMQ Terbatas

18/07/2014


14

Algoritma Path Doubling  Mengkondisikan pointer vertex x sejajar (level sama) dengan vertex y

1 2

 Kedua pointer pada kedua vertex bergerak menuju root secara paralel hingga mencapai vertex yang sama

3 10

11

4 5

 Kompleksitas 𝑂(𝑁)

Vertex y

6 Vertex x

18/07/2014

7


15

Algoritma Path Doubling 23

1

 Menggunakan teknik Meta-Binary Search

2 3

 Kompleksitas : • Preprocessing 𝑂(𝑁 log 𝑁) • Query 𝑂(log 𝑁)

4 ancestor yang dituju

22

5 6

𝑑𝑝 𝑖 [𝑗] =

𝑝𝑎𝑟𝑒𝑛𝑡[𝑖], &𝑑𝑝 𝑑𝑝 𝑖 [𝑗 − 1] [𝑗 − 1],

7

21 𝑗& = 0 0 &𝑗 > 80 2

Vertex permulaan 18/07/2014

9


16

Reduksi LCA ke RMQ  Diberikan suatu larik 𝐴 sepanjang 𝑁 yang berisi bilangan. Indeks i dan j berada diantara 1 dan 𝑁, maka query 𝑅𝑀𝑄𝐴 (𝑖, 𝑗) mengembalikan indeks dari larik 𝐴 yang menyimpan nilai terkecil pada sublarik 𝐴[𝑖& … &𝑗] RMQA (2, 7) = 4 A[0]

A[1]

A[2]

A[3]

A[4]

A[5]

A[6]

A[7]

A[8]

A[9]

4

2

3

6

1

7

8

9

7

1

18/07/2014


17

Reduksi LCA ke RMQ

0

1 1

 Inisialisasi indeks BFS

2 2 4

6

5

5

 Mengubah representasi rooted tree menjadi Euler Tour Representation (ETS)

3

4

3

7

11

7 10

13

11

9

12

6

13 15 18/07/2014

8

8

14

9

10

 Larik Euler, 𝐸[1, … , 2𝑛 − 1]&  Larik Level, 𝐿[1, … , 2𝑛 − 1]  Larik Representatif,𝑅[1, … , 𝑛]&

12 14

15

16


18

Kerangka Presentasi Pendahuluan

Uji Coba SPOJ

Rangkaian Proses

Uji Coba Kebenaran Kasus Kecil

Uji Coba dan Analisis

Uji Coba Kinerja

Kesimpulan

Analisis Kompleksitas

18/07/2014


19

Uji Coba SPOJ

18/07/2014


20

Uji Coba SPOJ

Algoritma

Waktu eksekusi rata-rata

memori

Path Doubling

0.52 detik

17 Megabyte

Sparse Table

0.50 detik

30 Megabyte

< 𝑂 𝑁 , 𝑂 1 > untuk permasalahan RMQ terbatas

0.25 detik

15 Megabyte

18/07/2014


21

Uji Coba Kebenaran Kasus Kecil  Menguji kebenaran keluaran program  Menguji 3 kasus LCA (Jika root dari rooted tree saat ini adalah r, dan vertex yang ditanyakan jumlahan subtree-nya adalah u) : 1. Jika u sama dengan r, maka cara hitungnya adalah sum[1] (sama dengan total bobot semua vertex). 2. LCA(u, r) adalah u, maka cara hitungnya adalah sum[1] dikurangi sum[v], yang mana v adalah salah satu child dari u yang mengarah ke r. 3. LCA(u, r) bukan u, jawabannya adalah sum[u].

18/07/2014


22

Uji Coba Kebenaran Kasus Kecil  Masukan rooted tree 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 1 1 2 2 2 3 3 3 6 6 8 13 13 14

18/07/2014


23

Uji Coba Kebenaran Kasus Kecil 136 8 S S S R S S S S

1 3 16 14 14 3 13 1

 Masukan query

2

88

3 4

5

11

 Keluaran program

6

7

7

58

11

12

66

9

8

9

10

13

12

30 16

18/07/2014

4

5 29

Kasus 1 : 𝑠𝑢𝑚 1 = 136

S 1 136

43

u=r

1


14

16

15

15

(S 1, R 1) 24

10


1 3 16 14 14 3 13 1

 Masukan query

5

11


2

6

7

7

58

11

12

u

3

4

66

9

8

9

10

13

12

30 16

18/07/2014

88

LCA(u, r) ≠ u

4

5 29

Kasus 3 : 𝑠𝑢𝑚 3 = 88

S 3 88

43

r

1


14

16

15

15

(S 3, R 1) 25

10


1 3 16 14 14 3 13 1

 Masukan query

2

88

LCA(u, r) ≠ u

3 4

5

11


6

7

66

7

58

11

12

9

8

9

10

13

12

30 16

18/07/2014

4

5 29

Kasus 3 : 𝑠𝑢𝑚 16 = 16

S 16 16

43

r

1


15

14

16

u

15

(S 16, R 1) 26

10


1 3 16 14 14 3 13 1

 Masukan query

Kasus 1 : 𝑠𝑢𝑚 1 = 136

S 14 136

11


5

11 18/07/2014

78 88 70

2

12

12

29

6

11

7 7 48 1

6

43

11

5

2

5 29

1 106

43

5

136


9

10

9 10

13

9 9

4

4

1216

16 15 15 4

10

58

30

13

3 8

3 66 8

14

14

7

12 16

15

15

7u = r (S 14, R 14) 27

16

4

10


1 3 16 14 14 3 13 1

 Masukan query

 Keluaran program 5

88 78 70

7 7 48 1

6

2

43

11

5

11 18/07/2014

2

5 29

Kasus 2 : 𝑠𝑢𝑚 1 − 𝑠𝑢𝑚 8 = 11 136 − 66 = 70

S 3 70

106

43

5

12

12

29

6

11

136

1


1216

9

10

9 10

13

9 9

4

4

16 12

15 415 4

10

58

30

LCA(u, r) = u 16 16 u

13

3 8

3 66 8

14

15

14

7

15

7r (S 3, R 14) 28

10

Uji Coba Kebenaran Kasus Kecil 136

136 8 S S S R S S S S

1 3 16 14 14 3 13 1

 Masukan query

43

5

S 13 106

70


11

5

5

11 18/07/2014

2

43

12 29

11

30

12 16


1216

9 9u

13

9

10

14

7

15

16

10

10

LCA(u, r) = u

4

4

12

6

10

58

16 15 415 4

9

8

14

13

83

3 66

7 48 7 1

6

106

78 88

5 29

Kasus 2 : 𝑠𝑢𝑚 1 − 𝑠𝑢𝑚 14 = 11 136 − 30 = 106

2

1

15

7r (S 13, R 14) 29


1 3 16 14 14 3 13 1

 Masukan query

106

43

5

2

7888 70

5 29

7 48

6

u

1

7

3 66

8

S 1 48


11

5

12 5

11 18/07/2014

2

43

29

11

6

4

4

30

14

7

1216 12 16


13

16 15

9

8

10 58

12

14 LCA(u, r) = u

3

1

Kasus 2 : 𝑠𝑢𝑚 1 − 𝑠𝑢𝑚 3 = 11 136 − 88 = 48

136

9

4

15

10

10

13

9 9 15

15

7r (S 1, R 14) 30

16

4

10

Uji Coba Kinerja Waktu (milidetik)

Percobaan

Jumlah vertex

< 𝑶 𝑵 , (𝟏) >

Sparse Table

Path Doubling

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

10000 15000 20000 25000 30000 35000 40000 45000 50000 55000 60000 65000 70000 75000 80000 85000 90000 95000

2 4 4 5 6 9 13 11 13 18 18 20 23 27 34 29 34 36

4 8 10 14 18 24 27 33 45 48 49 53 54 59 66 73 74 80

2 3 6 6 10 11 11 13 15 18 19 24 24 27 27 31 32 35

19

100000

37

97

35

18/07/2014


31

Uji Coba Kinerja Waktu (milidetik)

Percobaan

Jumlah vertex

< 𝑶 𝑵 , (𝟏) >

Sparse Table

Path Doubling

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

10000 15000 20000 25000 30000 35000 40000 45000 50000 55000 60000 65000 70000 75000 80000 85000 90000 95000

78 71 77 76 80 87 89 84 83 90 88 87 88 90 106 88 94 93

67 71 78 78 75 75 78 77 92 80 82 80 79 78 84 84 82 82

72 76 90 86 95 89 90 91 91 91 94 93 95 89 94 100 91 94

19

100000

90

102

93

18/07/2014


32

Analisis Kompleksitas Kompleksitas Program dengan algoritma

Waktu

Ruang

Path Doubling

< 𝑂 𝑁𝑙𝑜𝑔𝑁 , 𝑂(𝑙𝑜𝑔𝑁) >

𝑂(𝑁𝑙𝑜𝑔𝑁)

Sparse Table

< 𝑂 𝑁𝑙𝑜𝑔𝑁 , 𝑂(1) >

𝑂(𝑁𝑙𝑜𝑔𝑁)

Khusus pada Permasalahan RMQ Terbatas

< 𝑂 𝑁 , 𝑂(1) >

𝑂(𝑁)

18/07/2014


33

Kesimpulan  Dengan menggunakan tiga macam pendekatan dapat menyelesaikan masalah penarikan data pada struktur data rooted tree dinamis.  Algoritma Path Doubling membutuhkan memori lebih sedikit dari yang dibutuhkan oleh algoritma Sparse Table, sebaliknya waktu eksekusinya lebih lambat (sesuai uji coba situs penilaian daring SPOJ walaupun pada uji coba kinerja, preprocessing Sparse Table lebih lambat).  Pendekatan algoritma dengan kompleksitas < 𝑂 𝑁 , 𝑂(1) > pada permasalahan RMQ terbatas lebih unggul dari keduanya baik dari aspek kebutuhan memori maupun aspek kecepatan eksekusi namun implementasinya lebih kompleks.

18/07/2014


34

Kesimpulan  Lama waktu eksekusi preprocessing ketiga pendekatan dipengaruhi oleh banyaknya vertex secara linier baik yang memiliki kompleksitas 𝑂(𝑁) maupun 𝑂(𝑁𝑙𝑜𝑔(𝑁)) (sesuai dengan uji coba kinerja dengan masukan banyak vertex sampai batas permasalahan).  Lama waktu eksekusi operasi (query dan changeRoot) ketiga pendekatan tidak dipengaruhi oleh banyaknya vertex (konstan) baik yang memiliki kompleksitas 𝑂(1) maupun 𝑂(𝑙𝑜𝑔(𝑁)) (sesuai dengan uji coba kinerja dengan masukan banyak vertex sampai batas permasalahan).  Program dengan menggunakan algoritma khusus pada permasalahan RMQ terbatas unggul di kedua aspek, baik kompleksitas waktu maupun ruang

18/07/2014


35

Saran  Dibuat lebih dinamis lagi dengan ditambahnya berbagai macam operasi seperti penambahan nilai bobot dengan mempertahankan kompleksitas waktu.

18/07/2014


36

TERIMA KASIH

18/07/2014


37

Algoritma Sparse Table A[0]

A[1]

A[2]

A[3]

A[4]

A[5]

A[6]

A[7]

A[8]

A[9]

4

2

3

6

1

7

8

9

7

1

M[0][0] = 0 M[0][1] = 1

Kompleksitas preprocessing : 𝑂(𝑁&𝑙𝑜𝑔𝑁)

M[0][2] = 1 M[0][3] = 4

𝑀 𝑖 [𝑗] =

18/07/2014

𝑀 𝑖 [𝑗 − 1], 𝑀[𝑖 + 2𝑗−1 ][𝑗 − 1],

𝐴 & 𝑀 𝑖 𝑗 − 1 < 𝐴[𝑀[𝑖 + 2𝑗−1 ][𝑗 − 1]] &𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒


38

Algoritma Sparse Table i A[0]

j 2k elements 2k

elements

A[N]

𝑘& = & (𝑖𝑛𝑡)&𝑙𝑜𝑔(𝑗& − &𝑖& + &1), 𝑀 𝑖 [𝑘], 𝑀 𝑖 [𝑗] = 𝑀[𝑗 − 2𝑘 + 1][𝑘],

& 𝑀 𝑖 𝑘 < 𝐴[𝑀[𝑗 − 2𝑘 + 1][𝑘]] 𝐴 &𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

Kompleksitas query : 𝑂(1)

18/07/2014


39

Algoritma Sparse Table Euler Tour Representation 0

1

4

1

5

10

5

11

5

1

6

0

..

..

v LCA(u, r) sekaligus u

Root dari rooted tree saat ini adalah r, dan vertex yang ditanyakan jumlahan subtree-nya adalah u maka …  LCA(u, r) adalah u, maka cara hitungnya adalah sum[1] dikurangi sum[v], yang mana v adalah salah satu child dari u yang mengarah ke r.

18/07/2014


40

Algoritma Khusus Permasalahan RMQ Terbatas

 Ide dasar sama seperti Sparse Table yang menggunakan teknik table-lookup dengan melakukan preprocessing menghasilkan sublarik kecil.  Menghilangkan faktor 𝑙𝑜𝑔 pada algoritma Sparse Table

 Memanfaatkan properti khusus yang dimiliki larik hasil reduksi dari LCA, yaitu ±1 terbatas

18/07/2014


41


 Membagi larik menjadi blok-blok sebanyak log&(𝑛) 2

2𝑛 log&(𝑛)

yang berukuran

 Menyimpan elemen minimum di setiap blok  Preprocessing dengan algoritma Sparse Table, 2𝑛 2𝑛 2𝑛 Kompleksitas : ∗ log =𝑂 ∗ log 𝑛 𝑙𝑜𝑔(𝑛)

log 𝑛

log 𝑛

= 𝑂(𝑛)

L 2𝑛 log&(𝑛)

minB[0] blocks

18/07/2014

… log(𝑛) 2

2𝑛

minB[log&(𝑛) ]

minB[i]


…

42


log(𝑛) 2

j

i 3

1 2

 Cara menghitung RMQ :

1. Menghitung minimum elemen dari 𝑖 sampai akhir dari bloknya. 2. Menghitung minimum elemen yang terdapat pada blok antara blok yang terdapat 𝑖 di dalamnya dan blok yang terdapat 𝑗 di dalamnya. 3. Menghitung minimum elemen dari elemen awal sampai 𝑗 pada bloknya.

 Hasil dari ketiga proses hitung tadi, diambil yang minimum 18/07/2014


43


 Preprocessing semua blok dengan algoritma sparse table

 Setiap blok :  Semua blok

log 𝑛 log&(𝑛) log =𝑂 2 2 2𝑛 ( ) : 𝑂(𝑛 ∗ log&(log log&(𝑛)

log 𝑛 log log 𝑛 𝑛 ))

 Dengan memanfaatkan larik level (𝐿[1, … , 2𝑛 − 1]) yang memiliki properti ±1, semua blok dinormalisasi

18/07/2014


44


 Dengan memanfaatkan larik level (𝐿[1, … , 2𝑛 − 1]) yang memiliki properti ±1, semua blok dinormalisasi n X

4

5

6

7

6

5

4

5

6

5

Y

0

1

2

3

2

1

0

1

2

1

+1

+1

+1

-1

-1

-1

+1

+1

-1

1 ∙log 2

2

18/07/2014

𝑛 −1

= 𝑂( 𝑛).


45


 Dengan memanfaatkan larik level (𝐿[1, … , 2𝑛 − 1]) yang memiliki properti ±1, semua blok dinormalisasi Blok ke -

1

2

3

4

L=

0

1

2

1

2

3

2

3

2

1

2

1

0

…

B=

0

1

1

0

1

1

0

1

0

0

1

0

0

…

3

18/07/2014

3

2


2

46


 Dengan memanfaatkan larik level (𝐿[1, … , 2𝑛 − 1]) yang memiliki properti ±1, semua blok dinormalisasi  Membuat tabel dengan ukuran 𝑂( 𝑛)  Menggunakan algoritma trivial (𝑂(𝑛2 )) untuk menghitung RMQ  Ukuran blok :

18/07/2014

log&(𝑛) 2

,𝑂

𝑛 ∗ 𝑙𝑜𝑔2 𝑛

= 𝑂(𝑛)


47

DESAIN DAN ANALISIS STRUKTUR DATA NON LINIER ROOTED TREE DINAMIS (Kata kunci: Graf, Struktur data, tree, LCA, pemrograman dinamis)

Recommend Documents