![(SA GIA) 02 - Brute Force [PDF]](https://pdfs.asia/img/200x200/sa-gia-02-brute-force.jpg)
10 0 443 KB
CII2K3 STRATEGI ALGORITMA
PERTEMUAN 2 & 3: BRUTE FORCE
Outline
1. Pengertian, Kekuatan, dan Kelemahan 2. Algoritma Brute Force berdasarkan konsep yang terlibat 3. Algoritma Brute Force untuk permasalahan kombinatorial 4. Latihan Soal
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
2
Pengertian, Kekuatan, dan Kelemahan
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
3
Pengertian Brute Force ◦ Brute Force: Pendekatan yang lempeng (straightforward) untuk memecahkan suatu masalah ◦ Biasanya didasarkan pada: ▶ pernyataan masalah (problem statement) ▶ definisi konsep yang dilibatkan
◦ Algoritma brute force memecahkan masalah dengan ▶ sangat sederhana ▶ langsung ▶ cara yang jelas
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
4
Karakteristik Algoritma Brute Force (1) ◦ Umumnya tidak “cerdas” dan tidak mangkus ◦ Kata “force” mengindikasikan “tenaga” ketimbang “otak” ◦ Terkadang disebut algoritma naif (naive algorithm) ◦ Sederhana dan mudah diimplementasikan sehingga cocok digunakan untuk masalah yang berukuran kecil karena ◦ Sering digunakan sebagai basis pembanding pada algoritma yang lebih mangkus ◦ Hampir semua masalah dapat diselesaikan dengan algoritma brute force ◦ Ada masalah yang hanya dapat diselesaikan dengan algoritma brute force, e.g. mencari bilangan terbesar dalam suatu list
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
5
Kekuatan Algoritma Brute Force
◦ Dapat digunakan untuk memecahkan hampir sebagian besar masalah (wide applicability ) ◦ Sederhana dan mudah dipahami ◦ Menghasilkan algoritma yang layak untuk beberapa masalahan, e.g. pencarian, pencocokan string, perkalian matriks ◦ Menghasilkan algoritma yang baku untuk tugas-tugas komputasi, seperti penjumlahan/perkalian, menentukan elemen minimum/maksimum dari suatu list
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
6
Kelemahan Algoritma Brute Force
◦ Jarang menghasilkan algoritma yang mangkus ◦ Bebrapa algoritma brute force sangat lambat hingga tidak dapat diterima ◦ Tidak sekonstruktif atau sekreatif teknik pemecahan masalah lainnya
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
7
Algoritma Brute Force berdasarkan konsep yang terlibat
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
8
Contoh Brute Force: perkalian bilangan Menghitung an, dengan a > 0 dan n bilangan bulat tak-negatif
Solusi: { a × a × . . . × a (n kali) jika n > 0 a×n= 1 jika n = 0
Algoritma: kalikan 1 dengan a sebanyak n kali
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
9
Contoh Brute Force: perhitungan faktorial Menghitung n!, dengan n bilangan bulat tak-negatif
Solusi: { 1 × 2 × 3 × ... × n n! = 1
jika n > 0 jika n = 0
Algoritma: kalikan n buah bilangan bulat, yaitu 1, 2, 3, . . . , n, bersama-sama
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
10
Contoh Brute Force: perkalian matriks Mengalikan dua buah matriks yang berukuran n × n Solusi: Untuk matriks A, B. dan C = A × B dengan elemen matriks A, B, dan C pada baris ke-i dan kolom ke-j dinyatakan sebagai aij , bij , dan cij , cij = ai1 b1j + ai2 b2j + . . . + ain bnj =
n ∑
aik bkj
k=1
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
11
Contoh Brute Force: perkalian matriks Mengalikan dua buah matriks yang berukuran n × n Solusi: Untuk matriks A, B. dan C = A × B dengan elemen matriks A, B, dan C pada baris ke-i dan kolom ke-j dinyatakan sebagai aij , bij , dan cij , cij = ai1 b1j + ai2 b2j + . . . + ain bnj =
n ∑
aik bkj
k=1
Algoritma: hitung setiap elemen hasil perkalian satu per satu, dengan cara mengalikan dua vektor yang panjangnya n CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
11
procedure PerkalianMatriks (input A, B : Matriks, input n : integer, output C : Matriks) {Mengalikan matriks A dan B yang berukuran n × n, menghasilkan matriks C yang juga berukuran n × n. Masukan: matriks integer A dan B, ukuran matriks n Keluaran: matriks C } Deklarasi i, j, k : integer Algoritma for i←1 to n do for j←1 to n do C[i,j]←0 { inisialisasi penjumlahan } for k←1 to n do C[i,j]←C[i,j] + A[i,k]*B[k,j] endfor endfor endfor
Kompleksitas algoritma ini adalah CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
12
procedure PerkalianMatriks (input A, B : Matriks, input n : integer, output C : Matriks) {Mengalikan matriks A dan B yang berukuran n × n, menghasilkan matriks C yang juga berukuran n × n. Masukan: matriks integer A dan B, ukuran matriks n Keluaran: matriks C } Deklarasi i, j, k : integer Algoritma for i←1 to n do for j←1 to n do C[i,j]←0 { inisialisasi penjumlahan } for k←1 to n do C[i,j]←C[i,j] + A[i,k]*B[k,j] endfor endfor endfor
Kompleksitas algoritma ini adalah O(n3 ) CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
12
Contoh Brute Force: faktor bilangan Menemukan semua faktor dari bilangan bulat n selain dari 1 dan n itu sendiri Faktor: Bilangan bulat a adalah faktor dari bilangan bulat b jika a habis membagi b
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
13
Contoh Brute Force: faktor bilangan Menemukan semua faktor dari bilangan bulat n selain dari 1 dan n itu sendiri Faktor: Bilangan bulat a adalah faktor dari bilangan bulat b jika a habis membagi b Algoritma: cek satu per satu bilangan dari 2 hingga n − 1, apakah bilangan tersebut habis membagi n
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
13
procedure CariFaktor (input n : integer) {Mencari faktor dari bilangan bulat n selain 1 dan n itu sendiri Masukan: n Keluaran: dicetak setiap bilangan yang menjadi faktor n } Deklarasi k : integer Algoritma k←1 for k←2 to n-1 do if n mod k = 0 then write(k) endif endfor
Kompleksitas algoritma ini adalah
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
14
procedure CariFaktor (input n : integer) {Mencari faktor dari bilangan bulat n selain 1 dan n itu sendiri Masukan: n Keluaran: dicetak setiap bilangan yang menjadi faktor n } Deklarasi k : integer Algoritma k←1 for k←2 to n-1 do if n mod k = 0 then write(k) endif endfor
Kompleksitas algoritma ini adalah O(n)
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
14
Contoh Brute Force: mencari elemen terbesar
Diberikan sebuah himpunan yang beranggotakan n buah bilangan bukat. Bilangan-bilangan bulat tersebut dinyatakan sebagai a1 , a2 , . . . , an . Carilah elemen terbesar di dalam himpunan tersebut.
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
15
Contoh Brute Force: mencari elemen terbesar
Diberikan sebuah himpunan yang beranggotakan n buah bilangan bukat. Bilangan-bilangan bulat tersebut dinyatakan sebagai a1 , a2 , . . . , an . Carilah elemen terbesar di dalam himpunan tersebut.
Algoritma: cek satu per satu bilangan dari a1 hingga an dan selalu ingat bilangan terbesar yang pernah dicek
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
15
procedure CariElemenTerbesar (input a1 , a2 , . . . , an : integer output maks : integer) {Mencari elemen terbesar di antara elemen a1 , a2 , . . . , an . Elemen terbesar akan disimpan di dalam maks. Masukan: a1 , a2 , . . . , an Keluaran: maks } Deklarasi k : integer Algoritma maks← a1 for k←2 to n do if ak > maks then maks← ak endif endfor
Kompleksitas algoritma ini adalah
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
16
procedure CariElemenTerbesar (input a1 , a2 , . . . , an : integer output maks : integer) {Mencari elemen terbesar di antara elemen a1 , a2 , . . . , an . Elemen terbesar akan disimpan di dalam maks. Masukan: a1 , a2 , . . . , an Keluaran: maks } Deklarasi k : integer Algoritma maks← a1 for k←2 to n do if ak > maks then maks← ak endif endfor
Kompleksitas algoritma ini adalah O(n)
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
16
Contoh Brute Force: sequential search Diberikan n buah bilangan bulat yang dinyatakan sebagai a1 , a2 , . . . , an . Carilah apakah bilangan bulat x berada di dalam himpunan bilangan bulat tersebut. Jika x ditemukan, maka lokasi (indeks) elemen yang bernilai x disimpan di dalam peubah idx. Jika x tidak terdapat di dalam himpunan tersebut, maka idx diisi dengan nilai 0.
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
17
Contoh Brute Force: sequential search Diberikan n buah bilangan bulat yang dinyatakan sebagai a1 , a2 , . . . , an . Carilah apakah bilangan bulat x berada di dalam himpunan bilangan bulat tersebut. Jika x ditemukan, maka lokasi (indeks) elemen yang bernilai x disimpan di dalam peubah idx. Jika x tidak terdapat di dalam himpunan tersebut, maka idx diisi dengan nilai 0. Algoritma: cek satu per satu bilangan dari a1 hingga an . Jika ada yang bernilai sama dengan x, simpan indeksnya. Jika hingga an tidak ada yang bernilai sama dengan x, simpan angka 0.
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
17
procedure PencarianBeruntun (input a1 , . . . , an : integer, x : integer, output idx : integer) {Mencari x di dalam elemen a1 , a2 , . . . , an . Elemen terbesar akan disimpan di dalam maks. Lokasi (indeks elemen) tempat x ditemukan diisi ke dalam idx. Jika idx tidak ditemukan, idx diisi dengan 0. Masukan: a1 , a2 , . . . , an Keluaran: idx} Deklarasi k : integer Algoritma k←1 while k < n and (ak ̸= x) do k← k + 1 endwhile if ak = x then idx←k else idx←0 endif
{ k = n or ak = x } { x ditemukan } { x tidak ditemukan }
Kompleksitas algoritma ini adalah
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
18
procedure PencarianBeruntun (input a1 , . . . , an : integer, x : integer, output idx : integer) {Mencari x di dalam elemen a1 , a2 , . . . , an . Elemen terbesar akan disimpan di dalam maks. Lokasi (indeks elemen) tempat x ditemukan diisi ke dalam idx. Jika idx tidak ditemukan, idx diisi dengan 0. Masukan: a1 , a2 , . . . , an Keluaran: idx} Deklarasi k : integer Algoritma k←1 while k < n and (ak ̸= x) do k← k + 1 endwhile if ak = x then idx←k else idx←0 endif
{ k = n or ak = x } { x ditemukan } { x tidak ditemukan }
Kompleksitas algoritma ini adalah O(n).
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
18
Contoh Brute Force: bubble sort Diberikan sebuah tabel yang berisi n buah bilangan bulat. Urutkan isi dari tabel tersebut secara menaik dengan metode pengurutan bubble sort. Metode bubble sort: Merupakan salah satu bentuk pengurutan yang menerapkan pertukaran nilai pada prosesnya. Idenya adalah gelembung air yang akan“mengapung”: elemen bernilai kecil akan “diapungkan”, artinya diangkat ke atas melalui pertukaran.
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
19
Contoh Brute Force: bubble sort Diberikan sebuah tabel yang berisi n buah bilangan bulat. Urutkan isi dari tabel tersebut secara menaik dengan metode pengurutan bubble sort. Metode bubble sort: Merupakan salah satu bentuk pengurutan yang menerapkan pertukaran nilai pada prosesnya. Idenya adalah gelembung air yang akan“mengapung”: elemen bernilai kecil akan “diapungkan”, artinya diangkat ke atas melalui pertukaran. Algoritma: Untuk putaran pertama, cek bilangan satu per satu mulai dari elemen terakhir pada list dan tukar posisi sesuai kebutuhan sehingga kita mendapatkan bilangan terendah pada posisi pertama. Untuk putaran ke-2, ulangi langkah tersebut hingga kita mendapatkan bilangan terendah selanjutnya pada posisi ke-2, dan seterusnya hingga kita telah mengisi posisi terakhir dengan bilangan terbesar. CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
19
procedure BubbleSort (input/output L : TableInt, n : integer) {Mengurutkan tabel L[1,. . .,n] sehingga terurut menaik dengan metode pengurutan bubble sort. Masukan: Tabel L dengan panjang n yang terdefinisi nilai-nilainya Keluaran: Tabel L yang terurut menaik sehingga L[1]≤ . . . ≤L[N]} Deklarasi i : integer k : integer temp : integer
{ pencacah untuk jumlah langkah } { pencacah untuk pengapungan pada setiap langkah } { peubah bantu untuk pertukaran }
Algoritma for i←1 to n - 1 do for k←n downto i + 1 do if L[k] < L[k-1] then temp←L[k] L[k]←L[k-1] L[k-1]←temp endif endfor endfor
{pertukaran L[k] dengan L[k-1]}
Kompleksitas algoritma ini adalah
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
20
procedure BubbleSort (input/output L : TableInt, n : integer) {Mengurutkan tabel L[1,. . .,n] sehingga terurut menaik dengan metode pengurutan bubble sort. Masukan: Tabel L dengan panjang n yang terdefinisi nilai-nilainya Keluaran: Tabel L yang terurut menaik sehingga L[1]≤ . . . ≤L[N]} Deklarasi i : integer k : integer temp : integer
{ pencacah untuk jumlah langkah } { pencacah untuk pengapungan pada setiap langkah } { peubah bantu untuk pertukaran }
Algoritma for i←1 to n - 1 do for k←n downto i + 1 do if L[k] < L[k-1] then temp←L[k] L[k]←L[k-1] L[k-1]←temp endif endfor endfor
{pertukaran L[k] dengan L[k-1]}
Kompleksitas algoritma ini adalah O(n2 ).
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
20
Contoh Brute Force: uji keprimaan Diberikan sebuah bilangan bulat positif n. Ujilah apakah bilangan tersebut merupakan bilangan prima atau bukan. Bilangan prima: Bilangan yang lebih besar dari 1 dan hanya habis dibagi 1 dan dirinya sendiri.
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
21
Contoh Brute Force: uji keprimaan Diberikan sebuah bilangan bulat positif n. Ujilah apakah bilangan tersebut merupakan bilangan prima atau bukan. Bilangan prima: Bilangan yang lebih besar dari 1 dan hanya habis dibagi 1 dan dirinya sendiri. Algoritma: Jika n = 1 maka n bukan prima. Jika n = 2 maka n prima. Jika √ n ≥ 2, cek apakah ada bilangan bulat dari 2 hingga ⌈ n ⌉ yang habis membagi n. Jika ada maka n bukan prima; dan n prima jika sebaliknya.
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
21
function Prima(input x : integer)→boolean {Menguji apakan x bilangan prima atau bukan. Masukan: x Keluaran: true jika x prima, dan false jika x bukan prima} Deklarasi k, y : integer test : boolean Algoritma if x < 2 then { 1 bukan prima } return false else if x = 2 then { 2 adalah prima, kasus khusus } return true else √ y← ⌈ x ⌉ test←true while (test) and (y ≥ 2) do if x mod y = 0 then test←false else y←y - 1 endif endwhile { not test or y < 2 } return test endif endif
Kompleksitas algoritma ini adalah CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
22
function Prima(input x : integer)→boolean {Menguji apakan x bilangan prima atau bukan. Masukan: x Keluaran: true jika x prima, dan false jika x bukan prima} Deklarasi k, y : integer test : boolean Algoritma if x < 2 then { 1 bukan prima } return false else if x = 2 then { 2 adalah prima, kasus khusus } return true else √ y← ⌈ x ⌉ test←true while (test) and (y ≥ 2) do if x mod y = 0 then test←false else y←y - 1 endif endwhile { not test or y < 2 } return test endif endif
Kompleksitas algoritma ini adalah O(n) CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
22
Contoh Brute Force: menghitung nilai polinom
Hitung nilai polinom p(x) = an xn + an−1 xn−1 + . . . + a1 x + a0 pada titik x = x0 .
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
23
procedure polinom(input x0 : real)→real {Menghitung nilai p(x) pada x = x0. Koefisien-koefisien polinom sudah disimpan di dalam tabel a. Derajat polinom (n) juga sudah terdefinisi. Masukan: x0 Keluaran: nilai polinom pada x = x0} Deklarasi i, j : integer p, pangkat : real Algoritma p←0 for i←n downto 0 do pangkat←1 for j←1 to i do pangkat←pangkat * x0 endfor p←p + ai * pangkat endfor return p
{ hitung xi }
Kompleksitas algoritma ini adalah
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
24
procedure polinom(input x0 : real)→real {Menghitung nilai p(x) pada x = x0. Koefisien-koefisien polinom sudah disimpan di dalam tabel a. Derajat polinom (n) juga sudah terdefinisi. Masukan: x0 Keluaran: nilai polinom pada x = x0} Deklarasi i, j : integer p, pangkat : real Algoritma p←0 for i←n downto 0 do pangkat←1 for j←1 to i do pangkat←pangkat * x0 endfor p←p + ai * pangkat endfor return p
{ hitung xi }
Kompleksitas algoritma ini adalah O(n2 ).
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
24
Perbaikan (improvement) : procedure polinom2(input x0 : real)→real {Menghitung nilai p(x) pada x = x0. Koefisien-koefisien polinom sudah disimpan di dalam tabel a. Derajat polinom (n) juga sudah terdefinisi. Masukan: x0 Keluaran: nilai polinom pada x = x0} Deklarasi i, j : integer p, pangkat : real Algoritma p← a0 pangkat←1 for i←1 to n do pangkat←pangkat * x0 p←p + ai * pangkat endfor return p
Kompleksitas algoritma ini adalah
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
25
Perbaikan (improvement) : procedure polinom2(input x0 : real)→real {Menghitung nilai p(x) pada x = x0. Koefisien-koefisien polinom sudah disimpan di dalam tabel a. Derajat polinom (n) juga sudah terdefinisi. Masukan: x0 Keluaran: nilai polinom pada x = x0} Deklarasi i, j : integer p, pangkat : real Algoritma p← a0 pangkat←1 for i←1 to n do pangkat←pangkat * x0 p←p + ai * pangkat endfor return p
Kompleksitas algoritma ini adalah O(n).
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
25
Algoritma Brute Force untuk permasalahan kombinatorial
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
26
Exhaustive Search
◦ Teknik pencarian dengan solusi brute force untuk menyelesaikan masalah kombinatorik ◦ Biasanya digunakan di antara objek-objek kombinatorik, seperti permutasi, kombinasi, dan himpunan bagian dari suatu himpunan
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
27
Langkah-langkah Metode Exhaustive Search 1. Enumerasi (list) setiap solusi yang mungkin dengan cara yang sistematis 2. Evaluasi setiap kemungkinan solusi satu per satu, simpan solusi terbaik yang ditemukan sejauh ini 3. Bila setiap elemen telah dievaluaasi, umumkan solusi terbaik
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
28
Langkah-langkah Metode Exhaustive Search 1. Enumerasi (list) setiap solusi yang mungkin dengan cara yang sistematis 2. Evaluasi setiap kemungkinan solusi satu per satu, simpan solusi terbaik yang ditemukan sejauh ini 3. Bila setiap elemen telah dievaluaasi, umumkan solusi terbaik Meskipun exhaustive search secara teoritis pasti menghasilkan solusi, namun waktu dan sumber daya yang diperlukan dalam pencarian solusi tersebut sangatlah besar.
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
28
Contoh Exhaustive Search: TSP (1)
Permasalahan Travelling Salesperson Problem: Diberikan n buah kota beserta jarak antar kota. Temukan perjalanan (tour ) terpendek dari satu kota keberangkatan yang melalui setiap kota lainnya tepat satu kali dan kembali ke kota asal keberangkatan.
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
29
Contoh Exhaustive Search: TSP (1)
Permasalahan Travelling Salesperson Problem: Diberikan n buah kota beserta jarak antar kota. Temukan perjalanan (tour ) terpendek dari satu kota keberangkatan yang melalui setiap kota lainnya tepat satu kali dan kembali ke kota asal keberangkatan. Persoalan TSP dapat dipandang sebagai pencarian bobot minimum dari sirkuit Hamiltonian.
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
29
Contoh Exhaustive Search: TSP (2)
Langkah exhaustive search untuk TSP: 1. Representasikan data n kota dan jarak antar kota sebagai graf lengkap dengan n buah simpul 2. Enumerasi (list) semua sirkuit Hamilton dari graf lengkap tersebut 3. Hitung (evaluasi) bobot setiap sirkuit Hamilton yang ditemukan pada langkah 2 4. Pilih sirkuit Hamilton dengan bobot terkecil
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
30
Contoh Exhaustive Search: TSP (1) Contoh TSP dengan 4 simpul dan simpul a sebagai simpul awal:
5
10
d
No
12
a
9
15
Rute Perjalanan
Bobot
b 8
c
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
31
Contoh Exhaustive Search: TSP (1) Contoh TSP dengan 4 simpul dan simpul a sebagai simpul awal: 12
a 5
10
d
b 9
15
No 1
Rute Perjalanan a→b→c→d→a
Bobot 12 + 8 + 15 + 10 = 45
8
c
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
31
Contoh Exhaustive Search: TSP (1) Contoh TSP dengan 4 simpul dan simpul a sebagai simpul awal:
a
12
b 9
10
15
Rute Perjalanan a→b→c→d→a a→b→d→c→a
Bobot 12 + 8 + 15 + 10 = 45 12 + 5 + 9 + 15 = 41
8
5
d
No 1 2
c
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
31
Contoh Exhaustive Search: TSP (1) Contoh TSP dengan 4 simpul dan simpul a sebagai simpul awal: 12
a 5
10
d
b 9
15
8
No 1 2 3
Rute Perjalanan a→b→c→d→a a→b→d→c→a a→c→b→d→a
Bobot 12 + 8 + 15 + 10 = 45 12 + 5 + 9 + 15 = 41 10 + 5 + 9 + 8 = 32
c
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
31
Contoh Exhaustive Search: TSP (1) Contoh TSP dengan 4 simpul dan simpul a sebagai simpul awal: 12
a
b
5
10
8
9
d
15
c
No 1 2 3 4
Rute Perjalanan a→b→c→d→a a→b→d→c→a a→c→b→d→a a→c→d→b→a
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
Bobot 12 + 8 + 15 + 10 = 45 12 + 5 + 9 + 15 = 41 10 + 5 + 9 + 8 = 32 12 + 5 + 9 + 15 = 41
31
Contoh Exhaustive Search: TSP (1) Contoh TSP dengan 4 simpul dan simpul a sebagai simpul awal:
a 10
12
b 8
9 5
d
15
c
No 1 2 3 4 5
Rute Perjalanan a→b→c→d→a a→b→d→c→a a→c→b→d→a a→c→d→b→a a→d→b→c→a
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
Bobot 12 + 8 + 15 + 10 = 45 12 + 5 + 9 + 15 = 41 10 + 5 + 9 + 8 = 32 12 + 5 + 9 + 15 = 41 10 + 5 + 9 + 8 = 32
31
Contoh Exhaustive Search: TSP (1) Contoh TSP dengan 4 simpul dan simpul a sebagai simpul awal: 12
a 5
10
d
b 9
15
8
c
No 1 2 3 4 5 6
Rute Perjalanan a→b→c→d→a a→b→d→c→a a→c→b→d→a a→c→d→b→a a→d→b→c→a a→d→c→b→a
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
Bobot 12 + 8 + 15 + 10 = 45 12 + 5 + 9 + 15 = 41 10 + 5 + 9 + 8 = 32 12 + 5 + 9 + 15 = 41 10 + 5 + 9 + 8 = 32 10 + 12 + 8 + 15 = 45
31
Contoh Exhaustive Search: TSP (1) Contoh TSP dengan 4 simpul dan simpul a sebagai simpul awal: 12
a 5
10
d
b 9
15
8
c
No 1 2 3 4 5 6
Rute Perjalanan a→b→c→d→a a→b→d→c→a a→c→b→d→a a→c→d→b→a a→d→b→c→a a→d→c→b→a
Bobot 12 + 8 + 15 + 10 = 45 12 + 5 + 9 + 15 = 41 10 + 5 + 9 + 8 = 32 12 + 5 + 9 + 15 = 41 10 + 5 + 9 + 8 = 32 10 + 12 + 8 + 15 = 45
Rute perjalanan terpendek adalah
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
31
Contoh Exhaustive Search: TSP (1) Contoh TSP dengan 4 simpul dan simpul a sebagai simpul awal: 12
a 5
10
d
b 9
15
8
c
No 1 2 3 4 5 6
Rute Perjalanan a→b→c→d→a a→b→d→c→a a→c→b→d→a a→c→d→b→a a→d→b→c→a a→d→c→b→a
Bobot 12 + 8 + 15 + 10 = 45 12 + 5 + 9 + 15 = 41 10 + 5 + 9 + 8 = 32 12 + 5 + 9 + 15 = 41 10 + 5 + 9 + 8 = 32 10 + 12 + 8 + 15 = 45
Rute perjalanan terpendek adalah rute a → c → b → d → a dan a → d → b → c → a dengan bobot 32
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
31
Contoh Exhaustive Search: TSP (2) ◦ Untuk n buah simpul, semua rute perjalanan yang mungkin adalah
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
32
Contoh Exhaustive Search: TSP (2) ◦ Untuk n buah simpul, semua rute perjalanan yang mungkin adalah (n − 1)!
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
32
Contoh Exhaustive Search: TSP (2) ◦ Untuk n buah simpul, semua rute perjalanan yang mungkin adalah (n − 1)! ◦ (n − 1)! berasal dari permutasi n − 1 simpul (karena titik awal dan akhir telah ditentukan ◦ Pada contoh sebelumnya, terdapat 4 simpul sehingga banyak rute yang mungkin adalah (4 − 1)! = 3! = 6 rute perjalanan
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
32
Contoh Exhaustive Search: TSP (2) ◦ Untuk n buah simpul, semua rute perjalanan yang mungkin adalah (n − 1)! ◦ (n − 1)! berasal dari permutasi n − 1 simpul (karena titik awal dan akhir telah ditentukan ◦ Pada contoh sebelumnya, terdapat 4 simpul sehingga banyak rute yang mungkin adalah (4 − 1)! = 3! = 6 rute perjalanan ◦ Penyelesaian dengan metode exhaustive search berarti kita harus menghitung bobot dari (n − 1)! buah rute untuk kemudian memilih bobot terkecil ◦ Perhitungan bobot n sisi dapat dilakukan dalam
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
32
Contoh Exhaustive Search: TSP (2) ◦ Untuk n buah simpul, semua rute perjalanan yang mungkin adalah (n − 1)! ◦ (n − 1)! berasal dari permutasi n − 1 simpul (karena titik awal dan akhir telah ditentukan ◦ Pada contoh sebelumnya, terdapat 4 simpul sehingga banyak rute yang mungkin adalah (4 − 1)! = 3! = 6 rute perjalanan ◦ Penyelesaian dengan metode exhaustive search berarti kita harus menghitung bobot dari (n − 1)! buah rute untuk kemudian memilih bobot terkecil ◦ Perhitungan bobot n sisi dapat dilakukan dalam O(n), dan ini perlu dilakukan (n − 1)! kali ◦ Kompleksitas waktu metode exhaustive search seperti pada contoh adalah CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
32
Contoh Exhaustive Search: TSP (2) ◦ Untuk n buah simpul, semua rute perjalanan yang mungkin adalah (n − 1)! ◦ (n − 1)! berasal dari permutasi n − 1 simpul (karena titik awal dan akhir telah ditentukan ◦ Pada contoh sebelumnya, terdapat 4 simpul sehingga banyak rute yang mungkin adalah (4 − 1)! = 3! = 6 rute perjalanan ◦ Penyelesaian dengan metode exhaustive search berarti kita harus menghitung bobot dari (n − 1)! buah rute untuk kemudian memilih bobot terkecil ◦ Perhitungan bobot n sisi dapat dilakukan dalam O(n), dan ini perlu dilakukan (n − 1)! kali ◦ Kompleksitas waktu metode exhaustive search seperti pada contoh adalah O(n.n!) CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
32
Contoh Exhaustive Search: TSP (3) ◦ Metode yang digunakan pada contoh sebelumnya dapat diperbaiki karena setengah dari rute perjalanan mencerminkan rute lainnya ◦ Maka kita dapat menghilangkan setengah dari banyaknya permutasi ◦ Pada contoh sebelumnya, kita cukup mempertimbangkan tiga rute: a
12
10
5
8
d
15
c
12
a
b
d
15
a
b 9
c
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
b 5
10
d
9
8
c
33
Contoh Exhaustive Search: TSP (4) ◦ Dengan metode perbaikan ini, rute yang perlu kita hitung bobotnya pada graf dengan n simpul adalah (n − 1)!/2 rute ◦ Untuk ukuran graf yang besar, metode perbaikan tetap tidak mangkus ◦ Misalkan untuk persoalan TSP dengan n = 20 simpul, akan terdapat (n − 1)!/2 = 6.1016 rute perjalanan yang harus dievaluasi ◦ Sayangnya, untuk ketepatan solusi (akurasi), tidak ada algoritma lain yang lebih baik daripada exhaustive search
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
34
Contoh: 0/1 Knapsack Problem (1) Permasalahan: ◦ Diberikan n buah objek dan sebuah knapsack (tas punggung) dengan kapasitas bobot K ◦ Setiap objek i mempunyai properti bobot wi dan keuntungan (profit) pi ◦ Objek mana saja yang perlu dimasukkan ke dalam knapsack sehingga keuntungan yang didapat bernilai maksimum? ◦ Catatan: total bobot objek yang dimasukkan ke dalam knapsack tidak boleh melebihi kapasitas knapsack
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
35
Contoh: 0/1 Knapsack Problem (2) ◦ Persoalan 0/1 Knapsack ini dapat dipandang sebagai pencarian himpunan bagian dari keseluruhan objek yang dapat dimasukkan ke knapsack dengan keuntungan yang paling besar ◦ Solusi persoalan dapat dinyatakan sebagai: X = {x1 , . . . , xn } dimana untuk i = 1, . . . , n, { 1 , jika objek ke-i dipilih xi = 0 , jika objek ke-i tidak dipilih
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
36
Contoh: 0/1 Knapsack Problem (3) Formulasi secara matematis: Maksimasi F =
n ∑
p i xi
i=1
dengan kendala (constraint) n ∑
wi x i ≤ K
i=1
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
37
Contoh: 0/1 Knapsack Problem (4)
Langkah exhaustive search untuk 0/1 knapsack problem: 1. Enumerasi (list) semua himpunan bagian dari himpunan dengan n objek 2. Hitung (evaluasi) total keuntungan dari setiap himpunan bagian dari langkah 1 dengan mempertimbangkan kendala yang ada 3. Pilih himpunan bagian yang memberikan total keuntungan terbesar
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
38
Contoh: 0/1 Knapsack Problem (5)
Contoh: Terdapat n = 4 objek dan knapsack dengan kapasitas bobot K = 16. Adapun bobot (wi ) dan profit (pi ) untuk setiap objek tersebut adalah: ◦ w1 = 2; p1 = 20 ◦ w2 = 5; p2 = 30 ◦ w3 = 10; p3 = 50 ◦ w4 = 5; p4 = 10
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
39
Contoh: 0/1 Knapsack Problem (5) Himpunan Bagian
Total Bobot
Total Keuntungan
K = 16, w1 = 2, p1 = 20, w2 = 5, p2 = 30, w3 = 10, p3 = 50, w4 = 5, p4 = 10 CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
40
Contoh: 0/1 Knapsack Problem (5) Himpunan Bagian {} {1} {2} {3} {4} {1,2} {1,3} {1,4} {2,3} {2,4} {3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,2,3,4}
Total Bobot
Total Keuntungan
K = 16, w1 = 2, p1 = 20, w2 = 5, p2 = 30, w3 = 10, p3 = 50, w4 = 5, p4 = 10 CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
40
Contoh: 0/1 Knapsack Problem (5) Himpunan Bagian {} {1} {2} {3} {4} {1,2} {1,3} {1,4} {2,3} {2,4} {3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,2,3,4}
Total Bobot 0
Total Keuntungan 0
K = 16, w1 = 2, p1 = 20, w2 = 5, p2 = 30, w3 = 10, p3 = 50, w4 = 5, p4 = 10 CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
40
Contoh: 0/1 Knapsack Problem (5) Himpunan Bagian {} {1} {2} {3} {4} {1,2} {1,3} {1,4} {2,3} {2,4} {3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,2,3,4}
Total Bobot 0 2
Total Keuntungan 0 20
K = 16, w1 = 2, p1 = 20, w2 = 5, p2 = 30, w3 = 10, p3 = 50, w4 = 5, p4 = 10 CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
40
Contoh: 0/1 Knapsack Problem (5) Himpunan Bagian {} {1} {2} {3} {4} {1,2} {1,3} {1,4} {2,3} {2,4} {3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,2,3,4}
Total Bobot 0 2 5 10 10
Total Keuntungan 0 20 30 50 50
K = 16, w1 = 2, p1 = 20, w2 = 5, p2 = 30, w3 = 10, p3 = 50, w4 = 5, p4 = 10 CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
40
Contoh: 0/1 Knapsack Problem (5) Himpunan Bagian {} {1} {2} {3} {4} {1,2} {1,3} {1,4} {2,3} {2,4} {3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,2,3,4}
Total Bobot 0 2 5 10 10 7
Total Keuntungan 0 20 30 50 50 50
K = 16, w1 = 2, p1 = 20, w2 = 5, p2 = 30, w3 = 10, p3 = 50, w4 = 5, p4 = 10 CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
40
Contoh: 0/1 Knapsack Problem (5) Himpunan Bagian {} {1} {2} {3} {4} {1,2} {1,3} {1,4} {2,3} {2,4} {3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,2,3,4}
Total Bobot 0 2 5 10 10 7 12 7 15 10 15
Total Keuntungan 0 20 30 50 50 50 70 30 80 40 60
K = 16, w1 = 2, p1 = 20, w2 = 5, p2 = 30, w3 = 10, p3 = 50, w4 = 5, p4 = 10 CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
40
Contoh: 0/1 Knapsack Problem (5) Himpunan Bagian {} {1} {2} {3} {4} {1,2} {1,3} {1,4} {2,3} {2,4} {3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,2,3,4}
Total Bobot 0 2 5 10 10 7 12 7 15 10 15 17
Total Keuntungan 0 20 30 50 50 50 70 30 80 40 60 tidak layak
K = 16, w1 = 2, p1 = 20, w2 = 5, p2 = 30, w3 = 10, p3 = 50, w4 = 5, p4 = 10 CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
40
Contoh: 0/1 Knapsack Problem (5) Himpunan Bagian {} {1} {2} {3} {4} {1,2} {1,3} {1,4} {2,3} {2,4} {3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,2,3,4}
Total Bobot 0 2 5 10 10 7 12 7 15 10 15 17 12 17 20 22
Total Keuntungan 0 20 30 50 50 50 70 30 80 40 60 tidak layak 60 tidak layak tidak layak tidak layak
K = 16, w1 = 2, p1 = 20, w2 = 5, p2 = 30, w3 = 10, p3 = 50, w4 = 5, p4 = 10 CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
40
Contoh: 0/1 Knapsack Problem (5) Himpunan Bagian {} {1} {2} {3} {4} {1,2} {1,3} {1,4} {2,3} {2,4} {3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,2,3,4}
Total Bobot 0 2 5 10 10 7 12 7 15 10 15 17 12 17 20 22
Total Keuntungan 0 20 30 50 50 50 70 30 80 40 60 tidak layak 60 tidak layak tidak layak tidak layak
K = 16, w1 = 2, p1 = 20, w2 = 5, p2 = 30, w3 = 10, p3 = 50, w4 = 5, p4 = 10 CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
40
Contoh: 0/1 Knapsack Problem (5) Himpunan Bagian {} {1} {2} {3} {4} {1,2} {1,3} {1,4} {2,3} {2,4} {3,4} {1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,2,3,4}
Total Bobot 0 2 5 10 10 7 12 7 15 10 15 17 12 17 20 22
Total Keuntungan 0 20 30 50 50 50 70 30 80 40 60 tidak layak 60 tidak layak tidak layak tidak layak
Himpunan bagian yang memberikan keuntungan maksimum adalah {2, 3} dengan total keuntungan 80. Solusi: {0, 1, 1, 0}
K = 16, w1 = 2, p1 = 20, w2 = 5, p2 = 30, w3 = 10, p3 = 50, w4 = 5, p4 = 10 CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
40
Contoh: 0/1 Knapsack Problem (6)
◦ Untuk n buah objek, anyaknya himpunan bagian yang harus dievaluasi adalah
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
41
Contoh: 0/1 Knapsack Problem (6)
◦ Untuk n buah objek, anyaknya himpunan bagian yang harus dievaluasi adalah 2n ◦ Perhitungan total bobot setiap himpunan bagian dapat dikerjakan dalam
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
41
Contoh: 0/1 Knapsack Problem (6)
◦ Untuk n buah objek, anyaknya himpunan bagian yang harus dievaluasi adalah 2n ◦ Perhitungan total bobot setiap himpunan bagian dapat dikerjakan dalam O(n) ◦ Sehingga komplekitas algoritma exhaustive search untuk permasalahan 0/1 knapsack adalah O(n.2n )
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
41
TSP dan 0/1 Knapsack Problem
◦ TSP dan 0/1 knapsack problem adalah contoh persoalan eksponensial ◦ Keduanya digolongkan sebagai persoalan NP (nondeterministic polynomial) ◦ Belum ada algoritma deterministik polinomial yang dapat menyelesaikan kedua masalah tersebut
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
42
Contoh: dalam bidang kriptografi Di bidang kriptografi, exhaustive search merupakan teknik penyerangan untuk menemukan kunci enkripsi dengan cara mencoba semua kemungkinan kunci (exhaustive key search attack atau brute force attack). Contoh: ◦ Panjang kunci enkripsi pada algoritma DES (Data Encryption Standard) = 64 bit. Namun, hanya 56 bit yang digunakan. ◦ Banyaknya kombinasi kunci yang harus dievaluasi:
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
43
Contoh: dalam bidang kriptografi Di bidang kriptografi, exhaustive search merupakan teknik penyerangan untuk menemukan kunci enkripsi dengan cara mencoba semua kemungkinan kunci (exhaustive key search attack atau brute force attack). Contoh: ◦ Panjang kunci enkripsi pada algoritma DES (Data Encryption Standard) = 64 bit. Namun, hanya 56 bit yang digunakan. ◦ Banyaknya kombinasi kunci yang harus dievaluasi: 256 = 7.205.759.403.7927.936 ◦ Jika untuk 1 percobaan diperlukan waktu 1 detik, maka dalam kondisi terburuk diperlukan waktu kurang lebih selama 228.4931.317 tahun CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
43
Mempercepat Exhaustive Search ◦ Exhaustive search dapat diperbaiki kinerjanya sehingga tidak perlu melakukan pencarian terhadap semua kemungkinan solusi ◦ Salah satu cara untuk mempercepat pencarian solusi adalah dengan menggunakan teknik heuristik ◦ Teknik heuristik digunakan untuk mengeliminasi beberapa kemungkinan solusi tanpa harus mengeksplorasinya secara penuh ◦ Heuristik tidak menjamin selalu dapat memecahkan masalah, tetapi seringkali memecahkan masalah dengan cukup baik untuk kebanyakan masalah ◦ Heuristik yang bagus dapat secara dramatis mengurangi waktu yang dibutuhkan untuk memecahkan masalah CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
44
Contoh Heuristik: Permasalahan Anagram (1)
Anagram adalah penukaran huruf dalam sebuah kata atau kalimat sehingga kata atau kalimat yang baru memiliki arti yang lain. Contoh-contoh anagram (dalam Bahasa Inggris): ◦ lived → devil ◦ tea → eat ◦ charm → march
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
45
Contoh Heuristik: Permasalahan Anagram (2)
◦ Penyelesaian dengan exhaustive search:
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
46
Contoh Heuristik: Permasalahan Anagram (2)
◦ Penyelesaian dengan exhaustive search: Mencari semua permutasi huruf-huruf pembentuk kata atau kalimat, lalu memeriksa apakah kata atau kalimat yang terbentuk mengandung arti
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
46
Contoh Heuristik: Permasalahan Anagram (2)
◦ Penyelesaian dengan exhaustive search: Mencari semua permutasi huruf-huruf pembentuk kata atau kalimat, lalu memeriksa apakah kata atau kalimat yang terbentuk mengandung arti ◦ Teknik heuristik yang dapat digunakan:
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
46
Contoh Heuristik: Permasalahan Anagram (2)
◦ Penyelesaian dengan exhaustive search: Mencari semua permutasi huruf-huruf pembentuk kata atau kalimat, lalu memeriksa apakah kata atau kalimat yang terbentuk mengandung arti ◦ Teknik heuristik yang dapat digunakan: Membuat aturan bahwa dalam Bahasa Inggris, huruf “c” dan “h” selalu digunakan berdampingan sebagai “ch”
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
46
Latihan Soal
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
47
Latihan (1) 1. (Masalah Penugasan) Misalkan terdapat n orang dan n buah pekerjaan. Setiap orang akan di-assign dengan sebuah pekerjaan. Penugasan orang ke-i dengan pekerjaan ke-j membutuhkan biaya sebesar c(i, j). agaimana melakukan penugasan sehingga total biaya penugasan adalah seminimal mungkin? Misalkan instansiasi persoalan dinyatakan dengan matriks C sebagai berikut Orang a
C=
Orang b Orang c Orang d
Job 1
Job 2
Job 3
Job 4
9 6 5 7
2 4 8 6
7 3 1 9
8 7 4 4
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
48
Latihan (2) 2. (Masalah partisi). Diberikan n buah bilangan bulat positif. Bagilah menjadi dua himpunan bagian disjoint sehingga setiap bagian mempunyai jumlah nilai yang sama (catatan: masalah ini tidak selalu mempunyai solusi). Contoh: n = 6, yaitu 3, 8, 4, 6, 1, 2, dibagi dua menjadi {3, 8, 1} dan {4, 6, 2} yang masing-masing jumlahnya 12. Rancang algoritma exhaustive search untuk masalah ini. Cobalah mengurangi jumlah himpunan bagian yang perlu dibangkitkan.
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
49
Latihan (3) 3. (Bujursangkar ajaib). Bujursangkar ajaib (magic square) adalah pengaturan n buah bilangan dari 1 hingga n2 di dalam bujursangkar yang berukuran n × n sedemikian sehingga jumlah nilai setiap kolom, baris, dan diagonal sama. Contoh, untuk orde n = 3: 4 3 8
9 5 1
2 7 6
Rancanglah algoritma exhaustive search untuk membangkitkan bujursangkar ajaib dengan orde n. CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
50
Referensi 1. T. H. Cormen, C. E. Leiserson, R. L. Riverst, C. Stein. Introduction to Algorithms –3rd Edition, MIT Press, 2009. 2. ] A. Levitin. Introduction to The Design and Analysis of Algorithms –3rd Edition, Pearson, 2011. 3. R. Neapolitan, K. Naimipour. Foundations of Algorithms –5th Edition, Jones and Bartlett Learning, 2014. 4. Ir. Rinaldi Munir, M.T. Diktat Strategi Algoritmik IF2251. Departemen Teknik Informatika, Institut Teknologi Bandung 5. Ian Parberry. Lecture notes on Algorithm Analysis. Department of Computer Sciences, University of North Texas, 2001
CII2K3-Strategi Algoritma / PRODI S1 INFORMATIKA
51
THANK YOU
