PRESENTASI TUGAS AKHIR KI IMPLEMENTASI ALGORITMA PENCARIAN K JALUR SEDERHANA TERPENDEK DALAM GRAF

PRESENTASI TUGAS AKHIR – KI091391 IMPLEMENTASI ALGORITMA PENCARIAN K JALUR SEDERHANA TERPENDEK DALAM GRAF (Kata kunci: Algoritma deviasi, algoritma Dijkstra, jalur sederhana, jalur terpendek)

P enyusun Tugas Ak hir : Anggakara Hendra Nandana (NRP: 5108.100.075) Dosen P em bim bing : Yudhi Purwananto, S.Kom., M.Kom. Rully Soelaiman, S.Kom., M.Kom. 10 Juli 2013

Tugas Akhir - KI091391

1

KERANGKA PRESENTASI

Pendahuluan

Ilustrasi Permasalahan

Latar Belakang

Rangkaian Proses Batasan Masalah

Uji Coba Tujuan

Kesimpulan 10 Juli 2013


2

ILUSTRASI PERMASALAHAN

Problem dari situs Sphere Online Judge (SPOJ) berjudul “Kth Shortest Path” (http://www.spoj.com/problems/MKTHPATH/)

10 Juli 2013


3

DESKRIPSI SOAL SPOJ “Kth Shortest Path”

1. Seseorang bernama Isaac merasa bosan karena setiap hari melalui jalur yang sama untuk melakukan perjalanan dari rumah menuju kantor. 2. Jalur yang diambil Isaac selalu merupakan jalur terpendek, yaitu jalur dengan biaya terkecil, dan selalu merupakan jalur sederhana. 3. Biaya pada sebuah jalur merupakan total waktu yang dibutuhkan untuk melewati jalan-jalan yang menghubungkan dua buah tempat yang menyusun jalur tersebut. 4. Waktu yang dibutuhkan untuk melewati sebuah jalan bisa bernilai sama atau berbeda dengan jalan-jalan yang lain. 5. Pada hari-hari berikutnya, Isaac ingin melewati jalur terpendek yang belum pernah dilewatinya. 6. Dengan kata lain, pada hari ke-k, Isaac ingin melewati jalur terpendek ke-k. 7. Permasalahan Isaac dapat dimodelkan menjadi graf dengan masing-masing verteks merepresentasikan tempat dan masing-masing edge merepresentasikan jalan. 10 Juli 2013


4

BATASAN SOAL SPOJ “Kth Shortest Path”

1. Jumlah verteks maksimum 50 buah, jumlah edge maksimum 2450 buah, dan banyak jalur yang dicari (k) maksimum 200 buah. 2. Jalur yang dicari harus merupakan jalur sederhana, yaitu jalur yang tidak memiliki pengulangan verteks penyusun. 3. Jika terdapat dua kandidat jalur terpendek dengan bobot yang sama, maka jalur yang dipilih adalah jalur yang lebih dahulu memiliki verteks penyusun dengan nomor yang lebih kecil. (Contoh: Jika memiliki bobot yang sama, maka jalur 1-2-3-4 muncul lebih dahulu daripada jalur 1-3-4.)

10 Juli 2013


5

FORMAT DATA MASUKAN

•

Data masukan merupakan sebuah berkas teks yang hanya berisi bilangan bulat

•

Masing-masing bilangan bulat merepresentasikan detail graf dengan format seperti pada Gambar 1

jumlah jalur jumlah edge verteks yang dicari detail edge-edge

n m k a b x1 y1 z1 x2 y2 z2 … xm ym zm

verteks tujuan sumber jalur

Gambar 1 10 Juli 2013


6

FORMAT DATA MASUKAN

•

Data masukan merupakan sebuah berkas teks yang hanya berisi bilangan bulat

•

Masing-masing bilangan bulat merepresentasikan detail graf dengan format seperti pada Gambar 1

verteksedge sumber bobot verteks tujuan

n m k a b x1 y1 z1 x2 y2 z2 … xm ym zm Gambar 1

10 Juli 2013


7

CONTOH DATA MASUKAN

Data Masukan

4 2 1 1 1 2 3

6 3 3 2 4 4 4

2 1 4 1 2 1 3 2 1

Gambar Graf

1

3

4

10 Juli 2013

1


2 2

2

1

1

3

8

FORMAT DATA KELUARAN

•

Data keluaran merupakan sebuah berkas teks yang hanya berisi bilangan bulat.

•

Masing-masing bilangan bulat merepresentasikan verteks-verteks penyusun jalur yang ditemukan

•

Urutan penulisan verteks-verteks penyusun jalur dimulai dari verteks sumber hingga verteks tujuan.

•

Pada tiap dua buah verteks dipisahkan sebuah tanda hubung (-).

a-v2-…-vl-1-b verteks sumber jalur

10 Juli 2013

verteks tujuan jalur


9

CONTOH DATA KELUARAN

Data Masukan

4 2 1 1 1 2 3

6 3 3 2 4 4 4

2 1 4 1 2 1 3 2 1

10 Juli 2013

Gambar Graf 1

1

Data Keluaran 2

2

2 3

1

4

1

1-2-4

3


10

ALGORITMA NAIF (1)

1

1

2 2

2 3

4

1

1

3

• Daftar kemungkinan jalur dari vertex 1 ke vertex 4: 1 : 1-2-3-4, bobot = 3 2 : 1-2-4, bobot = 3 3 : 1-3-4, bobot = 3 4 : 1-4, bobot = 3 • Pada k jalur terpendek pertama, masing-masing verteks dapat menjadi verteks penyusun jalur sebanyak maksimal k kali. • Vertex sumber dan verteks tujuan jalur selalu muncul pada setiap k jalur terpendek. • Pencarian jalur dapat dilakukan dengan mencari seluruh kemungkinan jalur yang menuju verteks tujuan, hingga ditemukan jalur yang berasal dari verteks sumber sebanyak k kali.

10 Juli 2013


11

ALGORITMA NAIF (2)

1

1

2 2

2 3

4

1

1

10 Juli 2013

3

Daftar urutan jalur yang menuju ke verteks 4 : 1: 4 (bobot = 0) 2: 3-4 (bobot = 1) 3: 2-3-4 (bobot = 2) 4: 2-4 (bobot = 2) 5: 1-2-3-4 (bobot = 3) 6: 1-2-4 (bobot = 3) 7: 1-3-4 (bobot = 3)


12

HASIL ALGORITMA NAIF

Hasil pengujian implementasi algoritma naif pada soal “Kth Shortest Path”

Kesimpulan: Algoritma naif kurang efisien untuk menyelesaikan permasalahan pencarian k jalur sederhana terpendek.

10 Juli 2013


13

LATAR BELAKANG

1. Problem berjudul “Kth Shortest Path” pada situs SPOJ merupakan contoh permasalahan yang dapat ditemukan dalam kehidupan sehari-hari, sehingga dibutuhkan sebuah algoritma untuk menyelesaikan permasalahan tersebut. 2. Algoritma naif kurang efisien dalam hal kecepatan dan memori yang dibutuhkan, sehingga dibutuhkan algoritma lain yang lebih cepat dan lebih hemat memori

10 Juli 2013


14

BATASAN MASALAH

1. Pustaka yang digunakan untuk membantu pengimplementasian algoritma merupakan C++ Standard Template Library (STL). Pustaka-pustaka tersebut antara lain: cstdio, iostream, algorithm, cstring, vector, queue, dan ctime. 2. Kebutuhan memori hasil implementasi mengacu pada hasil keluaran dari server situs SPOJ untuk problem “Kth Shortest Path”.

10 Juli 2013


15

TUJUAN MASALAH

1. Untuk melakukan studi dan mengimplementasi algoritma pencarian k jalur sederhana terpendek dalam graf yang lebih optimal dibandingkan dengan algoritma naif dengan bantuan pustaka dari C++ Standard Template Library. 2. Untuk menguji kebenaran hasil implementasi algoritma pencarian k jalur sederhana terpendek dalam graf. 3. Untuk menguji dan membandingkan kecepatan algoritma naif dengan algoritma baru yang dijelaskan pada tugas akhir ini.

10 Juli 2013


16

KERANGKA PRESENTASI

1

Pencarian kandidat jalur terpendek pertama

2

Pengambilan jalur terpendek dari himpunan kandidat jalur X

3

Penghapusan subjalur dan edge-edge dari graf

4

Pembentukan pohon jalur terpendek Tt

5

Pencarian kandidat-kandidat jalur terpendek berikutnya

6

Pengecekan jumlah jalur dan isi himpunan kandidat jalur

Pendahuluan

Rangkaian Proses

Uji Coba



17

RANGKAIAN PROSES: LANGKAH 1

1

Pencarian kandidat jalur terpendek pertama Pengambilan jalur terpendek dari himpunan kandidat jalur X

• Jalur terpendek pertama digunakan sebagai acuan untuk menentukan kandidat-kandidat jalur terpendek berikutnya. • Jalur terpendek pertama dicari menggunakan algoritma Dijkstra



1

1

2

2 Pencarian kandidat-kandidat jalur terpendek berikutnya Pengecekan jumlah jalur dan isi himpunan kandidat jalur

10 Juli 2013

2

3

4

1

1

3

Gambar 2 Tugas Akhir - KI091391

18


1


• Jalur terpendek dari verteks 1 menuju verteks 4 pada Gambar 2 adalah jalur 1-2-3-4


• Jalur terpendek yang didapat kemudian ditambahkan ke himpunan kandidat jalur X



• Inisialisasi verteks sumber sebagai verteks deviasi jalur

1

1

2

2 Pencarian kandidat-kandidat jalur terpendek berikutnya Pengecekan jumlah jalur dan isi himpunan kandidat jalur

10 Juli 2013

2

3

4

1

1

3

Gambar 2 Tugas Akhir - KI091391

19

ALGORITMA DEVIASI

• Jalur-jalur terpendek yang didapat dari sebuah graf dapat membentuk pohon jalur terpendek seperti pada Gambar 3 • Sebuah jalur pk selalu memiliki rangkaian vertex yang sama dengan jalur p1, …, pk-1 dari verteks sumber sampai verteks tertentu.

• Verteks tersebut merupakan letak jalur pk menyimpang dari himpunan jalur {p1, …, pk-1} dan disebut verteks deviasi. Verteks deviasi pada jalur p dinotasikan sebagai d(p) 1

2

5

p1

4

3

3

5

5

p3

Gambar 3 10 Juli 2013

p2


• d(p1) = 1 • d(p2) = 1 • d(p3) = 2 20



2

Pengambilan jalur terpendek dari himpunan kandidat jalur X Penghapusan subjalur dan edge-edge dari graf


Pencarian kandidat-kandidat jalur terpendek berikutnya Pengecekan jumlah jalur dan isi himpunan kandidat jalur

10 Juli 2013

• Himpunan kandidat jalur X berisi kandidat-kandidat jalur terpendek • Jalur yang diambil adalah jalur dengan bobot minimum dari semua anggota X, dan dinotasikan sebagai jalur p.

• Panjang jalur p dinotasikan sebagai l, dan urutan verteks penyusunnya dinotasikan sebagai v1, v2, …, vl.

• Banyaknya jalur yang telah diambil dari X menunjukkan banyaknya jalur yang telah ditemukan

v1

1

1

v2

2

1

v3

3

1

vl /v4

4

(bobot = 3)

Contoh jalur terpendek dari X Tugas Akhir - KI091391

21



2


• Agar proses pemilihan jalur terpendek dapat lebih efisien, maka diperlukan struktur data yang tepat. • Pada program, implementasi himpunan kandidat jalur menggunakan struktur data priority_queue yang mengaplikasikan struktur heap biner.




10 Juli 2013

v1

1

1

v2

2

1

v3

3

1

vl /v4

4

(bobot = 3)

Contoh jalur terpendek dari X Tugas Akhir - KI091391

22



3



• Bertujuan agar jalur yang sudah ditemukan tidak dapat menjadi kandidat jalur terpendek berikutnya. • Subjalur yang dihapus dimulai dari verteks sumber hingga verteks ke-(l -1) pada jalur p dan dinotasikan dengan subp(s, vl -1 ) • Hapus semua edge yang berasal dari verteks deviasi jalur-jalur yang ditemukan sebelum jalur p. 1

1


10 Juli 2013

3

4

2

3

4

jalur p

2

2 Pencarian kandidat-kandidat jalur terpendek berikutnya

1

2

1

1

3


23



• Pohon jalur terpendek Tt adalah struktur pohon dari graf yang berakar pada verteks t, yaitu verteks tujuan jalur. • Jarak antara sebuah verteks dengan verteks akar pada pohon merupakan jarak minimum kedua verteks pada graf.


1

1 4


2 2

2 3


4

1

1

3


10 Juli 2013


24



• Pada proses algoritma, pohon jalur terpendek dibentuk dari graf setelah dilakukan penghapusan verteks dan edge pada graf

Pengambilan jalur terpendek dari himpunan kandidat jalur X Penghapusan subjalur dan edge-edge dari graf

4


4


10 Juli 2013


25


Pencarian kandidat jalur terpendek pertama 5.1

Pengambilan jalur terpendek dari himpunan kandidat jalur X 5.2

Penghapusan subjalur dan edge-edge dari graf 5.3



10 Juli 2013

Penghitungan jarak antara vi dengan t Penambahan kandidat jalur ke dalam X

diulang untuk setiap vi ∈ {vl -1, …, d(p) }

5.4

5

Pengembalian verteks vi ke dalam graf

5.5

Pengembalian edge (vi, vi+1) pada graf

Perbaikan struktur pohon Tt


26

RANGKAIAN PROSES: LANGKAH 5.1

5

Pencarian kandidat-kandidat jalur terpendek berikutnya 5.1

vi

1

2

3

4

Pengembalian verteks vi ke dalam graf Penghitungan jarak antara vi dengan t Penambahan kandidat jalur ke dalam X Pengembalian edge (vi, vi+1) pada graf


10 Juli 2013

1

1 2

2 2

3

4


1

1

3

27


5

Pencarian kandidat-kandidat jalur terpendek berikutnya Pengembalian verteks vi ke dalam graf 5.2

vi

1

2

3

Dilakukan penghitungan kembali jarak antara vi dengan t, yaitu dengan memperbaiki struktur pohon

Tt

Penghitungan jarak antara vi dengan t

2

Penambahan kandidat jalur ke dalam X Pengembalian edge (vi, vi+1) pada graf


10 Juli 2013

4

2

4


1

3

28


5

Pencarian kandidat-kandidat jalur terpendek berikutnya Pengembalian verteks vi ke dalam graf Penghitungan jarak antara vi dengan t 5.3

Penambahan kandidat jalur ke dalam X Pengembalian edge (vi, vi+1) pada graf

vi

1

2

3

subp(s, vi)

• Jika jalur dari verteks vi ke verteks t dapat ditetapkan, maka dilakukan penambahan kandidat jalur baru. • Kandidat jalur merupakan gabungan dari subp(s, vi) dengan jalur dari vi menuju t pada struktur pohon

Tt.

• Kandidat jalur terpendek yang dapat terbentuk adalah jalur 1-2-4 2


10 Juli 2013

4

4 Tugas Akhir - KI091391

1

2

3 29


5


vi

1

vi+1

2

3

4

Pengembalian verteks vi ke dalam graf Penghitungan jarak antara vi dengan t Penambahan kandidat jalur ke dalam X 5.4

Pengembalian edge (vi, vi+1) pada graf


10 Juli 2013

1

1 2

2 2

3

4


1

1

3

30


5


vi

1

2

3

4

Pengembalian verteks vi ke dalam graf Penghitungan jarak antara vi dengan t Penambahan kandidat jalur ke dalam X Pengembalian edge (vi, vi+1) pada graf

2 2

4

2 1

Tt sebelum diperbaiki

5.5


10 Juli 2013

2


3

4

1 1

3

Tt setelah diperbaiki

31


Pencarian kandidat jalur terpendek pertama Pengambilan jalur terpendek dari himpunan kandidat jalur X Penghapusan subjalur dan edge-edge dari graf

• Rangkaian proses algoritma berhenti jika salah satu dari dua kondisi berikut tercapai: 1. jumlah jalur yang diambil dari X sudah sama dengan k 2. Himpunan jalur X merupakan himpunan kosong



6


10 Juli 2013


32

KERANGKA PRESENTASI

Pendahuluan

Rangkaian Proses Uji Kebenaran

Uji Coba

Uji Kecepatan

Uji Perbandingan Algoritma



33

UJI KEBENARAN

Data Masukan 5 1 1 1 2 3 2 4 3

8 2 4 3 4 4 5 5 5

4 1 5 1 3 1 2 2 3 1 2

1

1-3-4-5

2

2 1 3

1

14

4 2

3 k=4

3 2

2

1

10 Juli 2013

1

Data Keluaran Program

1

1

3

3

5

2

2

5

5

p3

p1

2

4 1

5

5

p2

p4


34

UJI KECEPATAN (1)

• • •

Waktu minimal = 2,73 detik Waktu maksimal = 2,83 detik Rata-rata waktu yang dibutuhkan adalah 2,76 detik dengan standar deviasi sebesar 0,3

10 Juli 2013


35

UJI KECEPATAN (2)

Judul Graf Graf A Graf B Graf C Graf D

Jumlah Verteks

Jumlah Edge

51 50 730 6.551

1.183 2.450 5.762 47.322

k

100

500

1000

5000

Judul Graf

Waktu (detik)

A B C D A B C D A B C D A B C D

0.024 0.035 0.588 94.856 0.115 0.161 3.030 448.342 0.227 0.328 6.165 888.671 1.114 1.562 32.113 4486.230

Kompleksitas algoritma: Ο (kn (m + n log (n)) 10 Juli 2013


36

UJI PERBANDINGAN ALGORITMA

k 100 500 1000 5000

Judul Graf Graf A Graf B Graf C Graf D

10 Juli 2013


Judul Graf

Algoritma Algoritma Naif TA 0.296 0.561 1.294 3.104 2.62 6.24 14.461 30.576

0.016 0.035 0.093 0.161 0.187 0.328 0.974 1.562

A B A B A B A B

Jumlah Verteks

Jumlah Edge

51 50 730 6.551

1.183 2.450 5.762 47.322

37

KERANGKA PRESENTASI

Pendahuluan

Rangkaian Proses

Uji Coba Kesimpulan

Penutup 10 Juli 2013

Saran


38

Kesimpulan

1. Hasil implementasi algoritma pencarian jalur sederhana terpendek yang dijelaskan pada tugas akhir ini dapat menghasilkan keluaran yang benar. 2. Kompleksitas waktu eksekusi program adalah Ο (kn (m + n log (n)) pada n buah edge, m buah verteks, dan k jalur yang dicari pada graf. 3. Algoritma pada tugas akhir ini lebih efisien daripada algoritma naif yang telah ditemukan sebelumnya.

10 Juli 2013


39

Saran

Pengembangan dengan melakukan studi mengenai struktur heap Fibonacci beserta implementasinya pada program untuk mempercepat pemrosesan kandidat jalur.

10 Juli 2013


40

10 Juli 2013


41

KERANGKA PRESENTASI

Pendahuluan

Metode

Uji Coba

Struktur Pohon Jalur Terpendek

Struktur Percabangan Jalur

Struktur Pohon Tt

Rangkaian Proses



42

POHON JALUR TERPENDEK

2 0 Struktur Pohon Jalur Terpendek

3

1 Struktur Percabangan Jalur

0

2 0

3 0

1

5 2

4 Struktur Pohon Tt

Rangkaian Proses

10 Juli 2013

Daftar tiga jalur terpendek dari verteks 1 ke verteks 5: P1: 1-2-5 P2: 1-4-3-5 P3: 1-2-3-5


43

POHON JALUR TERPENDEK

2 0 Struktur Pohon Jalur Terpendek

3

1 Struktur Percabangan Jalur

0

2 0

3 0

1

5 2 1

4 Struktur Pohon Tt

Rangkaian Proses

10 Juli 2013

2

P1: 1-2-5 P2: 1-4-3-5 P3: 1-2-3-5

5

4

3

3

5

5

P3

P2

P1


44

PERCABANGAN JALUR

Jalur ke-p : Struktur Pohon Jalur Terpendek


s

t

a

Kandidat jalur-jalur ke-q (q > p):

s

…

a

t

s

a

…

t

Struktur Pohon Tt

Rangkaian Proses

10 Juli 2013


45

STRUKTUR POHON Tt


2 0


3

1 Struktur Pohon Tt

0

2 0

3 0

1

5 2

4 Rangkaian Proses

Struktur Pohon Tt

10 Juli 2013


46

STRUKTUR POHON Tt


2 2

Struktur Percabangan Jalur 3

1 Struktur Pohon Tt

0

3 0

1

5 2

4 Rangkaian Proses

Struktur Pohon Tt setelah dilakukan penghapusan edge-edge pada jalur 1-2-5 10 Juli 2013


47

PSEUDOCODE (1)

10 Juli 2013


48

PSEUDOCODE (2)

10 Juli 2013


49

KODE SUMBER (1)

10 Juli 2013


50

KODE SUMBER (2)

10 Juli 2013


51

PRESENTASI TUGAS AKHIR KI IMPLEMENTASI ALGORITMA PENCARIAN K JALUR SEDERHANA TERPENDEK DALAM GRAF

Recommend Documents