Algoritma Searching
Pengertian Algoritma
Searching
Searching merupakan proses dasar dalam pengolahan data. Yaitu untuk
menemukan nilai tertentu dalam sekumpulan data yang bertipe sama.
Algoritma searching dijelaskan secara luas sebagai algoritma yang
menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi
untuk masalah tersebut. Algoritma searching menerima sebuah argument
kunci dan dengan langkah-langkah tertentu akan mencari rekaman dengan
kunci tersebut. Setelah melakukan proses pencarian, akan diperoleh salah
satu dari dua kemungkinan, yaitu data yang dicari ditemukan atau tidak
ditemukan.Macam-macam Algoritma Searching
1. Pencarian Beruntun (Sequential Search)
Konsep
a) Membandingkan setiap elemen larik satu per satu secara urut (beruntun), mulai dari elemen pertama sampai dengan elemen yang terakhir sampai data ditemukan atau tidak ditemukan.
b) Proses pencarian akan dihentikan jika data yang dicari sudah ditemukan.
c) Merupakan metode yang paling sederhana
d) Kelemahan pada kasus ini adalah, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula.
Algoritma
Algoritma pencarian beruntun dapat dituliskan sebagai berikut:
(1) i ← 0
(2) ketemu ← false
(3) selama (tidak ketemu) dan (i <= N) kerjakan baris 4
(4) jika (Data[i] = x) maka ketemu ← true, jika tidak i ← i + 1
(5) jika (ketemu) maka i adalah indeks dari data yang dicari, jika data tidak ditemukan.
Contoh
#include <stdio.h>
#include <conio.h>
void main()
{
int data[8] = {8,10,6,-2,11,7,1,100};
int cari;
int flag=0;
printf(“masukkan data yang ingin dicari = “);scanf(“%d”,&cari);
for(int i=0;i<8;i++)
{
if(data[i] == cari) flag=1;
}
if(flag==1) printf(“Data ada!\n”);
else printf(“Data tidak ada!\n”);
getch();
return 1;
}
Dari program di atas, terlihat bahwa dilakukan perulangan untuk mengakses semua elemen array data satu per satu berdasarkan indeksnya.
a) Program menggunakan sebuah variable flag yang berguna untuk menandai ada atau tidaknya data yang dicari dalam array data. Hanya bernilai 1 atau 0.
b) Flag pertama kali diinisialisasi dengan nilai 0.
c) Jika ditemukan, maka flag akan diset menjadi 1, jika tidak ada maka flag akan tetap bernilai 0.
d) Semua elemen array data akan dibandingkan satu per satu dengan data yang dicari dan diinputkan oleh user.
2. Pencarian Beruntun dengan sentinel
Konsep
a) Pencarian bertujuan untuk menambahkan elemen baru setelah elemen terakhir larik, maka terdapat sebuah varian dari metode pencarian berurutan. NIlai x yang akan dicari sengaja ditambahkan terlebih dahulu. Data yang ditambahkan setelah elemen larik ini disebut dengan sentinel.
b) Perhatikan array berikut ini:
0
|
1
|
2
|
3
|
4
|
5
|
6
|
indeks |
| 3 | 12 | 9 | -4 | 21 | 6 | ||
ffea
|
ffeb
|
ffec
|
ffed
|
ffef
|
fffa
|
fffb
|
alamat |
(2) Array pada indeks ke-6 berguna untuk menjaga agar indeks data berada pada indeks 0 s.d. 5 saja. Nila pencarian data sudah
mencapai array indeks yang ke-6 maka berarti data TIDAK ADA, sedangkan jika pencarian tidak mencapai indeks ke-6, maka data ADA.
Algoritma
Procedure SeqSearchWithSentinel(input L: LarikInt, input n: integer, input x: integer, output idx: integer)
DEKLARASI
I: integer
ALGORITMA
L[n+1] ← X {sentinel}
I ← 1
While (L[i] ≠ x) do
I ← i+1
Endwhile
If idx = n+1 then
idx ← -1
else
idx ← 1
endif
Contoh
#include <stdio.h>
#include <conio.h>
void main(){
int data[7] = {3,12,9,-4,21,6};
int cari,i;
printf(“masukkan data yang ingin dicari = “);scanf(“%d”,&cari);
data[6] = cari;
i=0;
while(data[i] != cari) i++;
if(i<6) printf(“Data ada!\n”); else printf(“Data tidak ada!\n”);
getch;
return 1;
}
3. Pencarian Bagi Dua (Binary Search)
Konsep
(a) Merupakan metode pencarian pada data terurut yang paling efisien.
(b) Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat.
(c) Prinsip pencarian dengan membagi data atas dua bagian mengilhami metode ini. data yang disimpan didalam larik harus sudah terurut.
Algoritma
Algoritma pencarian biner dapat dituliskan sebagai berikut:
(a) L ← 0
(b) R ← N – 1
(c) Ketemu ← false
(d) Selama (L <= R) dan (tidak ketemu) kerjakan baris 5 sampai dengan 8
(e) m ← (L + R) / 283
(f) jika (Data[m]) maka ketemu ← true
(g) jika (x < Data[m]) maka R ← m – 1
(h) jika (x > Data[m]) maka L ← m + 1
(i) jika (ketemu) maka m adalah indeks dari data yang dicari, jika tidak maka data tidak ditemukan.
Contoh
int binary_search(int cari)
{
int l,r,m;
l = 0;
r = n-1;
int ktm = 0;
while(l<=r && ktm==0)
{
m = (l+r)/2;
if(data[m] == cari) ktm=1;
else if (cari < data[m]) r=m-1;
else l=m+1;
{
if(ktm==1) return 1; else return 0;
}
}
}
JENIS ALGORITMA PENCARIAN
a. Pencarian Buta
Pencarian buta merupakan sekumpulan prosedur yang digunakan dalam melacak ruang keadaan. Pencarian berlangsung sampai solusi terakhir ditemukan. Idenya adalah menguji seluruh kemungkinan yang ada untuk menemukan solusi.
- Pencarian Melebar Pertama (Breadth-First Search)
Pada metode
Breadth-First Search, semua node pada level n akan dikunjungi terlebih
dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai
dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian
berpindah ke level berikutnya demikian pula dari kiri ke kanan sampai
ditemukannya solusi.
Algoritma :
– Buat sebuah antrian, inisialisasi node pertama dengan Root dari tree
– Bila node pertama, jika ≠ GOAL, diganti dengan anak-anaknya dan diletakkan di belakang per level
– Bila node pertama = GOAL, selesai
Keuntungan :
– Tidak akan menemui jalan buntu
– Jika ada satu solusi, maka breadth first search akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.
Kelemahan :
– Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon
– Kemungkinan ditemukan optimal local
- Pencarian Mendalam Pertama (Depth-First Search)
Pada Depth
First Search, proses pencarian akan dilaksanakan pada semua anaknya
sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai
dari node akar ke level yang lebih tinggi. Proses ini diulangi terus
hingga ditemukannya solusi.
Algoritma :
– Buat sebuah antrian, inisialisasi node pertama dengan Root dari tree
– Bila node pertama, jika ≠ GOAL, node dihapus diganti dengan anak-anaknya dengan urutan LChild
– Bila node pertama = GOAL, selesai
Keuntungan :
– Membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan
– Menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan
Kelemahan :
– Kemungkinan terjebak pada optimal lokal
– Hanya akan mendapatkan 1 solusi pada setiap pencarian
- Pencarian dengan Mendaki Bukit (Hill Climbing Search)
Algoritma :
– Buat sebuah antrian, inisialisasi node pertama dengan Root dari tree
– Bila node pertama, jika ≠ GOAL, node dihapus diganti dengan anak-anaknya dengan urutan yang paling kecil jaraknya
– Bila node pertama = GOAL, selesai
– Buat sebuah antrian, inisialisasi node pertama dengan Root dari tree
– Bila node pertama, jika ≠ GOAL, node dihapus diganti dengan anak-anaknya dengan urutan yang paling kecil jaraknya
– Bila node pertama = GOAL, selesai
Keuntungan :
– Membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan
– Metode hill climbing search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan
Kerugian :
– Algoritma akan berhenti kalau mencapai nilai optimum lokal
– Perlu menentukan aturan yang tepat
- Pencarian dengan Best-First Search
Algoritma :
– Bila sebuah antrian, inisialisasi node pertama dengan Root dari tree
– Bila node pertama, jika ≠ GOAL, node dhapus dan diganti dengan anak-anaknya. Selanjutnya keseluruhan node yang ada di Queu di-sort Ascending
– Bila node pertama = GOAL, selesai
Keuntungan :
– Membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan aktif saja yang dismpan
– Secara kebetulan, metode best first search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan
Kerugian :
– Algoritma akan berhenti kalau mencapai nilai optimum lokal
– Tidak diijinkan untuk melihat satupun langkah sebelumnya
b. Pencarian Heuristic
Kata heuristic berasal dari bahasa Yunani heuriskein dari kata dasar eureka atau heurika yang berarti mengungkap atau menemukan.
Dalam Artificial Intelligence, heuristic diperkenalkan sebagai suatu teknik yang meningkatkan efisiensi proses pencarian, yang dimungkinkan dengan mengorbankan kelengkapan.
Menggunakan heuristic kita berharap mendapatkan solusi yang baik dari masalah yang sulit.
– Arah search
Dapat dilakukan :
Maju, bermula dari keadaan awal (start state)
Mundur, di awali dari keadaan tujuan (goal stat)
Topologi proses search
Ada dua macam penggambaran problem, yatiu dalam bentuk :
1. Pohon (tree)
2. Graf (graph) : graf berarah dan graf tidak berarah
a. Pohon Pencarian
Untuk menghindari kemungkinan adanya proses pencarian suatu node secara berulang, maka digunakan struktur pohon.
Struktur pohon digunakan untuk meggambarkan keadaan secara hirarkis. Pohon juga terdiri dari beberapa node. Node yang terletak pada level-0 disebut juga “akar”. Node akar menunjukkan keadaan awal yang biasanya merupakan topik atau obyek. Node akar ini terletak pada level ke-0. Node akar mempunyai beberapa percabangan yang teridri atas beberapa node successor yang sering disebut dengan nama “anak” dan merupakan node-node perantara. Namun jika dilakukan pencarian mundur, maka dapat dikatakan bahwa node tersebut memiliki predececesor. Node-node yang tidak mempunyai anak sering disebut dengan nama node “daun” yang menunjukkan akhir dari suatu pencarian, dapat berupa tujuan yang diharapkan (goal) atau jalan buntu (dead end).
b. Graf Keadaan
Graf terdiri dari node-node yang menunjukkan keadaan, yaitu keadaan awal dan keadaan baru yang akan dicapai dengan menggunakan operator. Node-node dalam graf keadaan saling dihubungkan dengan menggunakan arc (busur) yang diberi panah untuk menunjukkan arah dari suatu kedaan ke keadaan berikutnya.
Metode pencarian akan berusaha menemukan kombinasi dari item-item yang dimulai dari start menuju ke goal.
Untuk memenuhi tugas Algoritma III
Dosen Pengampuh Matakuliah
Nama: M.Ropianto, M.Kom
NIDN : 102867804
Status : Dosen Tetap STT Ibnu
Sina
Pengampuh Matakuliah : Pemrograman 3
Kunjungi juga ya website http://sttibnusinabatam.ac.id
Sumber Referensi:
Modul / slide Definisi dan Masalah Artificial Intelligence – BSI, tahun pembuatan 2006.
Bab 4 Algoritma Pencarian (Searching Algorithm), oleh Entin – Gunadarma, tahun pembuatan 2007. (http://bsavitri.staff.gunadarma.ac.id).
Bab 4 Algoritma Pencarian (Searching Algorithm), oleh Entin – Gunadarma, tahun pembuatan 2007. (http://bsavitri.staff.gunadarma.ac.id).
Tidak ada komentar:
Posting Komentar