Analisis Algoritma: Anany Levitin, Introduction to Design and Analysis of Algorithm, 3 rd Edition, Pearson Education, Inc

11/5/2015

Bab 3: Brute Force and Exhaustive Search

Analisis Algoritma:

Agenda. • • • • • •

Anany Levitin, Introduction to Design and Analysis of Algorithm, 3rd Edition, Pearson Education, Inc., Addison-Wesley

Definition Selection Sort and Bubble Sort Sequential Search and Brute-Force Search Closest-Pair and Convex-Hull Problems Exhaustive Search Depth-First Search and Breath-First Search

Fakultas Teknologi dan Desain 1-1 Informatika Program Studi Teknik

Analisis Algoritma |

Definition • Brute force: “straightforward approach to solving a problem, usually directly based on the problem statement and definitions of the concepts involved.” • Force = just do it! • Konsep brute-force merupakan strategi yang paling mudah untuk diterapkan.

2

Selection Sort and Bubble Sort Selection Sort. • Metode pengurutan (sorting) dengan cara membandingkan setiap elemen yang terdapat dalam sebuah deret untuk dapat menentukan elemen yang tepat untuk diletakkan pada posisi yang telah ditentukan. • Operasi selection sort: 1. membandingkan elemen yang diamati dengan elemen berikutnya hingga elemen terakhir; 2. jika ditemukan, catat posisinya kemudian ditukar.


3


4

1

11/5/2015

Selection Sort and Bubble Sort • Contoh kasus: Selection sort. 89 12 57 16 25

Selection Sort and Bubble Sort Problem 2: Berdasarkan deret elemen pada contoh kasus di atas, jika urutan elemen deret diubah menjadi 25 57 12 89 16, berapakah banyaknya iterasi sortir yang dihasilkan?

Problem: Tentukan prosedur pengurutan deret secara ascending menggunakan metode sorting selection sort?

Problem 3: Kemudian, jika urutan elemen deret diubah kembali menjadi 16 25 57 12 89, berapakah banyaknya iterasi sortir yang dihasilkan?

Latihan 1. Kasus: Selection sort.

Problem 4: Berdasarkan problem 1, 2, dan 3, tentukanlah persamaan untuk menentukan banyaknya iterasi proses sortir selection sort ketiga deret tersebut, jika 𝑛 merupakan banyaknya elemen deret!

Problem 1: Berdasarkan deret elemen pada contoh kasus di atas, tentukanlah banyaknya iterasi sortir yang dihasilkan!


5


Selection Sort and Bubble Sort

6

Selection Sort and Bubble Sort 2. jika ditemukan, kemudian tukarkan posisinya;

Bubble Sort.

• Contoh kasus: Bubble sort. 89 12 57 16 25

• Merupakan sebuah metode pengurutan (sorting) dengan cara membandingkan pasangan elemen-elemen yang saling berdampingan dalam sebuah deret dan saling bertukar posisi ke urutan depan/atas (bubbling up)

Problem: Tentukan prosedur pengurutan deret secara ascending menggunakan metode sorting bubble sort?

Latihan 2.

• Operasi bubble sort:

Kasus: Bubble sort. Problem 1: Berdasarkan deret elemen pada contoh kasus di atas, tentukanlah banyaknya iterasi sortir yang dihasilkan

1. membandingkan pasangan-pasangan elemen yang diamati dengan elemen berikutnya hingga elemen terakhir; Analisis Algoritma |

7


8

2

11/5/2015

Selection Sort and Bubble Sort Problem 2: Berdasarkan deret elemen pada contoh kasus di atas, jika urutan elemen deret diubah menjadi 25 57 12 89 16, berapakah banyaknya iterasi sortir yang dihasilkan?

Selection Sort and Bubble Sort Problem 5: Berdasarkan problem 5, tentukanlah persamaan untuk menentukan banyaknya operasi sortir bubble sort deret tersebut, jika 𝑛 merupakan banyaknya elemen deret!

Problem 3: Kemudian, jika urutan elemen deret diubah kembali menjadi 16 25 57 12 89, berapakah banyaknya iterasi sortir yang dihasilkan? Problem 4: Berdasarkan problem 1, 2, dan 3, tentukanlah persamaan untuk menentukan banyaknya iterasi proses sortir bubble sort ketiga deret tersebut, jika 𝑛 merupakan banyaknya elemen deret! Analisis Algoritma |

9

Sequential Search and Brute-Force String Matching


Sequential Search and Brute-Force String Matching

Sequential Search.

Brute-Force String Matching.

• Melakukan pengulangan algoritma dengan membandingkan elemen satu dengan lainnya secara terus menerus menggunakan teknik tertentu hingga mendapatakan hasil yang diinginkan (successful search).

• Membandingkan string yang diamati dengan string pembanding untuk menentukan kebenaran string. Latihan 3. Kasus: Brute-Force String Matching. Problem 1: Tentukanlah prosedur untuk menentukan kebenaran sebuah string!

• Sebuah algoritma pencarian dikatakan tidak berhasil (unsuccessful search) jika lagortima tidak mencapai hasil yang diinginkan. Analisis Algoritma |

10

11


12

3

11/5/2015

Closest-Pair and Convex-Hull Problems

Sequential Search and Brute-Force String Matching Problem 2: Berdasarkan prosedur yang telah dibuat, tentukanlah pseudocode untuk menguji kebenaran penulisan string kata “belajr” dari string pembanding “belajar”!

Closest-Pair Problem. • Closest-pair problem digunakan untuk menemukan 2 poin terdekat dari sekumpulan 𝑛 nilai. • Contoh kasus: Closest-pair problem Problem: Perhatikan gambar berikut kemudian tentukan pasangan lokasi terdekat lokasi pengumpulan paket, jika kurir berada pada posisi X dan jarak X ke setiap agen paket secara berturut adalah: (X,A,4), (X,B,7), (X,C,9), (X,D,5),


13


(X,E,8), (X,F,6)



Latihan 4.

Convex-Hull Problem.

Problem 1: Berdasarkan contoh problem diatas, tentukan prosedur untuk menentukan kedua pasangan poin tersebut!

• Convex set, adalah himpunan poin-poin dimana untuk setiap 2 poin, baik 𝑝 maupun 𝑞 dalam himpunan tersebut merupakan bagian dari sebuah segmen yang dikelilingi oleh garis. • Contoh convex set:


15

14


16

4

11/5/2015


Closest-Pair and Convex-Hull Problems • Contoh kasus: Convex-hull problem

Convex-Hull Problem.

Problem: Perhatikan struktur poinpoin pada gambar di samping berikut, kemudian tentukan himpunan poin-poin yang merupakan convex-set dan convex-hull!

• Convex hull, adalah himpunan dari sejumlah 𝑆 poin yang merupakan bagian terkecil dari convex set. • Contoh convex hull:


17


18

Exhaustive Search • Exhaustive search merupakan sebuah pendekatan brute-force untuk menyelesaikan permasalahan kombinatorial.

Latihan 5. Problem 1: Diketahui sebuah deret memiliki elemen dari 1 s.d. 15, jika poin-poin pembentuk convex-set adalah himpunan deret elemen bilangan ganjil dan convex-hull himpunan deret elemen bilangan genap, tentukanlah prosedur untuk menentukan himpunan-himpunan pembentuk convex-set dan convex-hull tersebut!

• Kombinatorial digunakan untuk menentukan jumlah cara pengaturan objek-objek penyusun yang ada, dimana objek tersebut merupakan objek diskrit. • Kombinatorial didasarkan pada hasil yang diperoleh dari suatu percobaan yang dilakukan dalam bentuk eksperimen.

Problem 2: Tentukanlah pseudocode untuk menampilkan himpunan poinpoin convex-set dan convex-hull berdasarkan problem 1!



19


20

5

11/5/2015

Exhaustive Search

Exhaustive Search • Contoh kasus: Traveling Saleman Problem

Traveling Salesman Problem (TSP).

Problem: Tentukan rute terpendek pengiriman paket dari kota A ke setiap kota dan kembali ke kota A, dimana setiap kota hanya diperbolehkan disinggahi tepat 1 kali! Jarak antar kota diperlihatkan dalam graph di samping ini.

• Merupakan sebuah permasalahan dalam exhaustive search yang menarik bagi banyak peneliti. • Permasalahan TSP adalah untuk menentukan rute terpendek dari kumpulan 𝒏 kota yang diberikan, dimana setiap kota hanya diperbolehkan untuk disinggahi tepat satu kali sebelum kembali ke kota asal. • Permasalahan ini dapat disajikan dalam bentuk weighted graph. Analisis Algoritma |

21

Exhaustive Search Latihan 6. Problem 1: Lakukan hal yang sama seperti pada problem sebelumnya jika letak kota ditunjukkan seperti 2 gambar graph di bawah ini.

1

8


22

Exhaustive Search Problem 3: Perhatikan jumlah jalur terpendek dari setiap graph yang ada. Apakah setiap graph memiliki jalur terpendek yang sama banyak? Jika ya, tentukan formula untuk menentukan banyaknya jalur terpendek untuk sembarang julah node yang saling terhubung dalam sebuah graph! Problem 4: Jika tidak, tentukan formula setiap graph untuk dapat menentukan banyaknya jalur terpendek!

3


23


24

6

11/5/2015

Exhaustive Search

Exhaustive Search • Contoh kasus: Knapsack problem.

Knapsack Problem.

Problem: Tentukan total hasil curian tertinggi dari beberapa lokasi berikut!

• Sebuah permasalahan lain yang menggunaan exhaustive search yang digunakan untuk menentukan subset yang paling berharga (memiliki weight (beban) tinggi) yang dapat dimuati ke dalam ransel (knapsack). • Memiliki 𝒏 buah elemen yang masing-masing memiliki weight (𝒘: 𝒘𝟏, 𝒘𝟐, 𝒘𝟑, … ) dan value (𝒗: 𝒗𝟏, 𝒗𝟐, 𝒗𝟑, … ) dan sebuah kapasitas knapsack (𝑾)


25


Exhaustive Search

26

Exhaustive Search • Contoh kasus: Assignment problem.

Assignment Problem.

Problem: Tentukan total nilai efisiensi biaya yang dapat dilakukan untuk menugaskan seorang personil untuk mengerjakan 2 tugas/job/task yang memiliki biayanya masing-masing seperti tertuang dalam tabel di bawah ini!

• Contoh permasalahan jenis exhaustive search yang digunakan untuk menentukan nilai paling efisien sebuah kasus. • Memiliki 𝒊 buah elemen yang masing-masing memiliki kaitan terhadap 𝒋 buah nilai dan sebuah 𝑪 nilai efisien yang disajikan dalam bentuk matriks 2D 𝑪[𝒊, 𝒋].


27


28

7

11/5/2015

Exhaustive Search

Depth-First Search and Breadth-First Search

Latihan 7.

Depth-First Search (DFS).

Problem 1: lakukan hal yang sama seperti problem di sebelumnya jika setiap tugas/job/task yang memiliki biayanya masing-masing seperti tertuang dalam tabel di bawah ini!

• Merupakan algoritma pencarian dengan melakukan kunjungan (visit) ke setiap node dan menandai node jika telah dikunjungi (visited). • Node satu dengan node lainnya yang dapat saling terhubung maupun saling lepas. • Dua buah node dikatakan saling terhubung, apabila node tersebut dihubungkan dengan sebuah garis/line/vertex.


29

Depth-First Search and Breadth-First Search • Kunjungan dapat berujung pada node yang tidak terhubung dengan node lainnya (buntu) . • Jika kunjungan berujung pada kondisi buntu, maka penelusuran akan kembali satu node diatasnya, kemudian dicatat urutan. • Dengan demikian setiap node akan memiliki 2 buah nilai urutan kunjungan; (1) nilai urutan kunjungan (x), dan (2) nilai urutan sebuah node ketika kunjungan berujung pada kondisi buntu (y). • Dapat dinotasikan dengan < 𝒏𝒐𝒅𝒆 > 𝒙, 𝒚



30

Depth-First Search and Breadth-First Search • Contoh kasus: Depth-First Search (DFS). Problem: Tentukan urutan kunjungan (𝑥) ke setiap node dan urutan kunjungan ke setiap node jika kunjungan berujung pada kondisi buntu 𝑦 sebagai hasil penelusuran DFS graph di samping ini!

31


32

8

11/5/2015



Latihan 8. Problem 1: Perhatikan labirin di samping ini, kemudian: 1. gambarkan tree hubungan setiap node!, 2. tentukan nilai x dan y setiap node jika dilakukan penelusuran menggunakan konsep DFS!, 3. berdasarkan konsep DFS, jika dimisalkan sebuah robot diletakkan di node A dan harus mencari jalan keluar menuju node akhir dalam labirin tersbut, maka tentukan jalur lintasan robot tersebut!, 4. bagaimanakah cara menentukan jalur lintasan robot tersebut? Analisis Algoritma |

33


34


Analisis Algoritma:

Breadth-First Search (BFS).

Anany Levitin, Introduction to Design and Analysis of Algorithm, 3rd Edition, Pearson Education, Inc., Addison-Wesley

• Merupakan algoritma pencarian dengan melakukan kunjungan (visit) ke semua node yang berada pada level teratas, kemudian kunjungan dilakukan ke semua node dibawahnya level per level dan menandai urutan node yang dikunjungi pada setiap levelnya. • Contoh kasus: Breadth-First Search (BFS). Problem: Berdasarkan problem 1 pada latihan 8 sebelumnya, jelaskan bagaimana bagaimanakah cara menentukan jalur lintasan robot tersebut berdasarkan konsep BSF? Analisis Algoritma |

35

1-36

9

Analisis Algoritma: Anany Levitin, Introduction to Design and Analysis of Algorithm, 3 rd Edition, Pearson Education, Inc

Recommend Documents