Contoh Implementasi Algoritma Exhaustive Search - Skripsi Teknik Informatika

Melakukan perhitungan pada kasus Travelling Salesperson Problem  (TSP)

• Persoalan: Diberikan n buah kota serta diketahui jarak antara setiap kota satu sama lain. Temukan perjalanan (tour) terpendek yang melalui setiap kota lainnya hanya sekali dan kembali lagi ke kota asal keberangkatan. 
• Persoalan TSP tidak lain adalah menemukan sirkuit Hamilton dengan bobot minimum. 

Langkah mengimplementasikan algoritma exhaustive search untuk persoalan TSP:

1. Enumerasikan (list) semua sirkuit Hamilton dari graf lengkap dengan n buah simpul.
2. Hitung (evaluasi) bobot setiap sirkuit Hamilton yang ditemukan pada langkah 1.
3. Pilih sirkuit Hamilton yang mempunyai bobot terkecil.

Baca juga Jasa Bimbingan Skripsi Teknik Informatika

 TSP dengan n = 4, simpul awal = a

Rute perjalananan terpendek adalah  :

a → c → b → d → a 

a → d → b → c → a 

dengan bobot 32.

Untuk n buah simpul semua rute perjalanan yang mungkin dibangkitkan dengan permutasi dari n – 1 buah simpul.

Permutasi dari n – 1 buah simpul adalah

(n – 1)! 

Pada contoh di atas, untuk n = 6 akan terdapat 

(4 – 1)! = 3! = 6

buah rute perjalanan. 

Jika diselesaikan dengan metode exhaustive search, maka kita harus mengenumerasi sebanyak (n – 1)! buah sirkuit Hamilton, menghitung setiap bobotnya, dan memilih sirkuit Hamilton dengan bobot terkecil. 

Kompleksitas waktu algoritma exhaustive search untuk persoalan TSP sebanding dengan (n – 1)! dikali dengan waktu untuk menghitung bobot setiap sirkuit Hamilton. 

Menghitung bobot setiap sirkuit Hamilton membutuhkan waktu O(n), sehingga kompleksitas waktu algoritma exhaustive search untuk persoalan TSP adalah O(n . n!). 

Exhaustive Search dalam Bidang Kriptografi

Di dalam bidang kriptografi, exhaustive search merupakan teknik yang digunakan penyerang untuk menemukan kunci enkripsi dengan cara mencoba semua kemungkinan kunci. Serangan semacam ini dikenal dengan nama exhaustive key search attack atau brute force attack.

Contoh: Panjang kunci enkripsi pada algoritma DES (Data Encryption Standard) = 64 bit. Dari 64 bit tersebut, hanya 56 bit yang digunakan (8 bit paritas lainnya tidak dipakai). Jumlah kombinasi kunci yang harus dievaluasi oleh pihak lawan adalah sebanyak :

(2)(2)(2)(2)(2) … (2)(2) = 2⁵⁶ = 7.205.759.403.7927.936

Jika untuk percobaan dengan satu kunci memerlukan waktu 1 detik, maka untuk jumlah kunci sebanyak itu diperlukan waktu komputasi kurang lebih selama 228.4931.317 tahun, waktu yang lama apa sebentar menurut anda? hehe

Baca juga Jasa Bimbingan Skripsi Teknik Informatika

Meskipun algoritma exhaustive search tidak berhasil, namun –sebagaimana ciri algoritma brute force pada umumnya– nilai plusnya terletak pada keberhasilannya yang selalu menemukan solusi tentunya jika diberikan waktu yang cukup untuk melakukan pemprosesan. 

Kata Kunci : Implementasi Algoritma Exhaustive Search, Contoh Skripsi Teknik Informatika, Contoh Skripsi, Skripsi, Skripsi Teknik Informatika