PENGERTIAN ALGORITMA ITERATIF, REKURSIF, DAN EKSPLORASI
A. ITERATIF
1.Pengertian iteratif
Perulangan
iteratif merupakan perulangan yang melakukan proses perulangan terhadap
sekelompok instruksi di mana perulangan tersebut akan berhenti jika batasan
syarat sudah tidak terpenuhi.
Algoritma iteratif
- Teknik Iteratif merupakan suatu teknik pembuatan algoritma
dengan pemanggilan procedure beberapa
kali atau hingga suatu kondisi tertentu terpenuhi.
- Tidak ada variabel lokal baru
- Program tidak sederhana
- Menggunakan perulangan for dan while
Perulangan iteratif merupakan perulangan yang melakukan
proses perulangan terhadap sekelompok intruksi. Perulangan dilakukan dalam
batasan syarat tertentu. Ketika syarat tersebut tidak terpenuhi lagi maka
perulangan aka terhenti.
Kelebihan perulangan iteratif:
• Mudah dipahami dan mudah melakukan debugging ketika ada
perulangan yang salah.
• Dapat melakukan nested loop atau yang disebut dengan
looping bersarang.
• Proses lebih singkat karena perulangan terjadi pada
kondisi yang telah disesuaikan.
• Jarang terjadi overflow karena batasan dan syarat
perulangan yang jelas.
Kelemahan perulangan iteratif:
• Tidak dapat menggunakan batasan berupa fungsi.
• Perulangan dengan batasan yang luas akan menyulitkan dalam
pembuatan program perulangan itu sendiri.
program 1
Bentuk fungsi iteratif :
#include <cstdlib>
#include <iostream>
using namespace std;
int jumlah(int n) {
int hasil = 0;
for (int i=0; i<n; i=i+2)
hasil = hasil + i;
return hasil;
}
void cetak(int n) {
for (int i=0; i<n; i=i+2)
cout << i << ” “;
}
int main(int argc, char *argv[])
{
int n = 10;
cout << jumlah(n);
cetak(n);
system(“PAUSE”);
return EXIT_SUCCESS;
}
B.REKURSIF
1.Pengertian Rekursif
Rekursif dapat diartikan bahwa suatu proses yang bisa memanggil dirinya sendiri. sedikit
menyimpang dari pengertian ada sedikit pendapat tentang Rekursif salah satunya
adalah Menurut definisi dalam Microsoft Bookshelf, Rekursif adalah kemampuan
suatu rutin untuk memanggil dirinya sendiri. Dalam Rekursif sebenarnya
terkandung pengertian prosedur dan fungsi. Perbedaannya adalah bahwa rekursif
bisa memanggil ke dirinya sendiri, tetapi prosedur dan fungsi harus dipanggil
lewat pemanggil prosedur dan fungsi. Rekursif merupakan teknik pemrograman yang
penting dan beberapa bahasa pemrograman mendukung keberadaan proses rekursif
ini. Dalam prosedur dan fungsi, pemanggilan ke dirinya sendiri bisa berarti
proses berulang yang tidak bisa diketahui kapan akan berakhir.
Algoritma rekursif
- Teknik Rekursif merupakan salah satu cara pembuatan
algoritma dengan pemanggilan procedure atau function yang sama
- Ada variabel lokal baru
- Program menjadi lebih sederhana
- Menggunakan perulangan if else
Kelebihan perulangan rekursif:
• Sangat mudah untuk melakukan perulangan dengan batasan
yang luas dalam artian melakukan perulangan dalam skala yang besar.
• Dapat melakukan perulangan dengan batasan fungsi.
Perulangan rekursif merupakan salah satu metode didalam
pemrograman yang mana dalam sebuah fungsi terdapat intruksi yang memanggil
fungsi itu sendri, atau lebih sering disebut memanggil dirinya sendiri.
Kekurangan perulangan rekursif:
• Tidak bisa melakukan nested loop atau looping bersarang.
• Biasanya membuat fungsi sulit untuk dipahami, hanya cocok
untuk persoalan tertentu saja.
• Trace error sulit.
• Memerlukan stack yang lebih besar, sebab setiap kali
fungsi dipanggil, variabel lokal dan parameter formal akan ditempatkan ke stack
dan ada kalanya akan menyebabkan stack tak cukup lagi (Stack Overrun).
• Proses agak berbelit-belit karena terdapat pemangilan
fungsi yang berulang-ulang dan pemanggilan data yang ditumpuk.
jika pada program 1, diubah kedalam bentuk rekursif :
Dalam bentuk rekursif :
#include <cstdlib>
#include <iostream>
using namespace std;
int jumlah(int n) {
if(n==0) return (0);
else return (n-2 + jumlah(n-2));
}
void cetak(int n) {
if(n!=0){
cetak(n-2);
cout << n-2 << ” “;
}
}
int main(int argc, char *argv[])
{
int n = 10;
cout << jumlah(n);
cetak(n);
system(“PAUSE”);
return EXIT_SUCCESS;
}
C. EKSPLORASI
1. Strategi Pencarian Berbentuk yaitu meliputi :
A) Greddy Best First Search
Metode
pencarian ini melakukan ekspansi node yang memiliki jarak terdekat dengan goal.
Namun, ekspansi yang dilakukan pada metode ini menggunakan evaluasi node hanya
dengan melihat kepada fungsi heuristiknya. Dengan kata lain, yang dibandingkan
untuk penentuan ekspansi node adalah nilai estimasi/prediksinya saja.
f(n) = h(n)
B) A* Search
Bentuk
dari Best First Search yang paling dikenal adalah algoritma pencarian A*
(dibaca dengan “A-star”). Sedikit berbeda dengan Greedy yang hanya melihat
kepada nilai h(n), pencarian dengan A* melihat kepada kombinasi nilai dari
pathnya yaitu g(n) dengan nilai estimasi yaitu h(n).
f(n)
= g(n) + h(n)
C) Memory-Bounded Heuristic Search
2. Fungsi Heuristik
Heuristic
digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan
seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang
diinginkan.
3. Algoritma pencarian lokal dan masalah optimisasi yaitu
meliputi :
A) Hill Climbing Search
Metode ini
hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses
pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan
berikutnya tergantung pada feedback dari prosedur pengetesan. Tes yang berupa
fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang
diambil terhadap keadaan-keadaan lainnya yang mungkin.
B) Simulated Annealing Search
Simulated
Annealing adalah suatu algoritma optimasi yang mensimulasikan proses annealing
pada pembuatan materi yang terdiri dari butir kristal atau logam. Algoritma
untuk untuk optimisasi yang bersifat generik. Berbasiskan probabilitas dan
mekanika statistik, algoritma ini dapat digunakan untuk mencari pendekatan
terhadap solusi optimum global dari suatu permasalahan. Masalah yang
membutuhkan pendekatan SA adalah masalah-masalah optimisasi kombinatorial, di
mana ruang pencarian solusi yang ada terlalu besar, sehingga hampir tidak
mungkin ditemukan solusi eksak terhadap permasalahan itu
Berikut ini adalah pemetaan dari
Physical Annealing ke Simulated Annealing :
Fisika (termodinamika)
Simulated Annealing
Keadaan sistem
Solusi yang mungkin
Energi
Biaya
Perubahan keadaan
Solusi tetangga
Temperatur
Parameter kontrol
Keadaan beku
Solusi heuristik
Annealing adalah satu teknik yang dikenal dalam bidang
metalurgi, digunakan dalam mempelajari proses pembentukan kristal dalam suatu
materi. Agar dapat terbentuk susunan kristal yang sempurna, diperlukan
pemanasan sampai suatu tingkat tertentu, kemudian dilanjutkan dengan
pendinginan yang perlahan-lahan dan terkendali dari materi tersebut. Pemanasan
materi di awal proses annealing, memberikan kesempatan pada atom-atom dalam
materi itu untuk bergerak secara bebas, mengingat tingkat energi dalam kondisi
panas ini cukup tinggi. Proses pendinginan yang perlahan-lahan memungkinkan
atom-atom yang tadinya bergerak bebas itu, pada akhirnya menemukan tempat yang
optimum, di mana energi internal yang dibutuhkan atom itu untuk mempertahankan
posisinya adalah minimum.
Secara umum ada 3 hal pokok pada simulated annealing, yaitu:
a. Nilai awal untuk
temperatur (T0).
Nilai T0 biasanya ditetapkan cukup besar (tidak mendekati
nol), karena jika T mendekati 0 maka gerakan simulated annealing akan sama
dengan hill climbing. Biasanya temperatur awal ini ditetapkan sebesar 2 kali
panjang suatu jalur yang dipilih secara acak.
b. Kriteria yang
digunakan untuk memutuskan apakah temperatur sistem seharusnya dikurangi.
c. Berapa besarnya
pengurangan temperatur dalam setiap waktu.
Contoh Simulated Annealing
C) Local Beam Search
Beam Search adalah
algoritma pencarian heuristik yangmerupakan optimasi dari pencarian best-first
search yang mengurangikebutuhan memorinya. Dalam Beam Search, hanya jumlah
solusiparsial terbaik yang telah ditetapkan yang disimpan sebagai kandidat.
Beam Search membutuhkan tiga komponen sebagai inputnya,
yaitu :
a. Masalah yang akan di selesaikan
Biasanya di tampilkan dalam bentuk grafik dan berisi
kumpulan node yang tiap satu atau lebih node mengarah ke goal/hasil.
b. Kumpulan aturan-aturan heuristik untuk
pemangkasan
Adalah aturan-aturan spesifik yang mengarah ke ruang masalah
dan memangkas node yang tidak menguntungkan dari memori yang berhubungan dengan
ruang masalah.
c. Memori dengan kapasitas yang terbatas
Adalah memori
tempat menyimpan beam, dimana ketika memori dalam keadaan penuh dan node akan
di tambahkan ke beam, maka node yang nilainya paling besar yang dihapus,
jadi tidak akan melebihi memori yang tersedia.
Beam Search memiliki keuntungan yang berpotensi mengurangi
perhitungan dan waktu pencarian. Selain itu, pemakaian memori daripencarian ini
jauh lebih sedikit daripada metode yang mendasari mtode pencarian ini. Kelemahan utama Beam Search adalah metode
pencarian ini mungkin tidak dapat
mencapai tujuan/hasil yang optimaldan bahkan mungkin tidak mencapai tujuan sama
sekali. Padakenyataannya, algoritma beam search berakhir untuk dua kasus: nodetujuan yang diperlukan tercapai, atau
node tujuan tidak tercapai dantidak ada node tersisa untuk dieksplorasi.
Beam A*
Algoritma ini memberikan sedikit variasi pada A*, yaitu
dengan membatasi simpul yang bisa disimpan di dalam OPEN. Ketika jumlah simpul
di OPEN sudah melebihi batas tertentu, maka simpul dengan nilai f terbesar akan
dihapus. Sedangkan jumlah simpul yang di dalamCLOSED tetap dibiarkan tanpa
batasan karena simpul yang di dalamCLOSED memang tidak mungkin dihapus. Dengan
membatasi jumlah simpul di OPEN, maka pencarian menjadi lebih terfokus seperti
sinar (beam). Sehingga variasi ini dinamakan Beam A*.
Implementasi algoritma BA* sama dengan A* tetapi ada sedikit
fungsi tambahan untuk pengecekan dan penghapusan simpul terburuk di OPEN.
Algoritma Beam A* menggunakan dua senarai : OPEN danCLOSED.
OPEN adalah adalah senarai (list) yang digunakan untuk menyimpan simpul-simpul
yang pernah dibangkitkan dan nilai heuristiknya telah dihitung tetapi belum
terpilih sebagai simpul terbaik (best node). Dengan kata lain, OPEN berisi
simpul-simpul yang masih memiliki peluang (peluangnya masih terbuka) untuk
terpilih sebagai simpul terbaik. Sedangkan CLOSED adalah senarai untuk
menyimpan simpul-simpul yang sudah pernah dibangkitkan dan sudah pernah
terpilih sebagai simpul terbaik. Artinya, CLOSED berisi simpul-simpul yang
tidak mungkin terpilih sebagai simpul terbaik (peluang untuk terpilih sudah
tertutup).
Terdapat tiga kondisi bagi setiap sukseror yang
dibangkitkan, yaitu : sudah berada di OPEN, sudah berada di CLOSED, dan tidak
berada di OPEN maupun CLOSED. Pada ketiga kondisi tersebut diberikan penanganan
yang berbeda-beda.
Jika suksesor sudah pernah berada di OPEN, maka dilakukan
pengecekan apakah perlu pengubahan parent atau tidak tergantung pada nilai
g-nya melalui parent lama atau parent baru. Jika melaluiparent baru memberikan
nilai g yang lebih kecil, maka dilakukan pengubahan parent. Jika pengubahan
parent dilakukan, maka dilakukan pula perbaruan (update) nilai g dan f pada suksesor tersebut. Dengan perbaruan ini,
suksesor tersebut memiliki kesempatan yang lebih besar untuk terpilih sebagai
simpul terbaik (best node).
Jika suksesor sudah pernah berada di CLOSED, maka dilakukan
pengecekan apakah perlu pengubahan parent atau tidak. Jika ya, maka dilakukan
perbaruan nilai g dan f pada suksesor
tersebut serta pada semua “anak cucunya” yang sudah pernah berada di OPEN. Dengan
perbaruan ini, maka semua anak cucunya tersebut memiliki kesempatan lebih besar
untuk terpilih sebagai simpul terbaik (best node).
Jika suksesor tidak berada di OPEN maupun CLOSED, maka
suksesor tersebut dimasukkan ke dalam OPEN. Tambahkan suksesor tersebut sebagai
suksesornya best node. Hitung biaya suksesor tersebut dengan rumus f = g + h.
0 Comments: