Metode Algoritma Pencarian

METODE SEARCHING (Sequential Search & Binary Search) dalam C++

METODE SEARCHING (Sequential Search & Binary Search)

Searching adalah metode pencarian informasi dalam suatu aplikasi, dengan suatu kunci( key ). Pencarian diperlukan untuk mencari informasi khusus dari table pada saat lokasi yang pasti dari informasi tersebut sebelumnya tidak diketahui. Pencarian selalu dinyatakan dengan referensi pada adanya sekelompok data yang tersimpan secara terorganisasi, kelompok data tersebut kita sebut table.

Pada metode searching (pencarian) ada 2 teknik yang digunakan yaitu : Pencarian sekuensial (sequential search) dan Pencarian biner (Binary search).

1. Pencarian sekuensial (sequential search)

Pencarian sekuensial (sequential search) atau sering disebut pencarian linier menggunakan prinsip sebagai berikut : data yang ada di bandingkan satu persatu secara berurutan dengan yang dicari.

Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah data. Pada setiap perulangan , di bandingkan data ke-i dengan yang dicari. Apabila sama , berarti data telah ditemukan . Sebaliknya apabila sampai akhir pengulangan , tidak ada yang sama berarti data tidak ada.

a. Sekuensial versi berdampingan dengan sintak C:

Contoh listing fungsi dalam bahasa C++ :

Int SequensialSearch(List_type list, Key_type target)

{ int location; // penempatan data

for (location=0;location

if (EQ(list.entry[location].key,target))

return location;

return –1

b. Sekuensial versi berangkai dengan sintak C:

Node_type* SequentialSearch (List_type list, Key_type target)

{ Node_type* location;

for (location=list.head;location!=NULL;locatioan->next)

if(EQ(location->info.key,target))

return location;

return NULL

}

Pengimplementasian sintak sekuensial search pada bahasa C :

#include

#include

void main()

{

clrscr();

int data[8] = {3,9,7,-3,11,5,2,18};

int cari,index;

int ketemu=0;

cout<<"Inputkan data yang ingin di cari = ";

cin>>cari;

for(int i=0;i<8;i++)

{

if(data[i] == cari)

{

ketemu=1;

index=1;

break;

}

}

if(ketemu == 1)

{

cout<<"Data tersedia!"<

cout<<"Data Terletak di index ke - "<

}

else cout<<"Data tidak tersedia!"<

getch();

}

2. Pencarian Biner (Binary Search)

Salah satu syarat pencarian biner (binary search) dapat dilakukan adalah data sudah dalam keadaan terurut. Dengan kata lain, apabila data belum dalam keadaan terurut , pencarian biner tidak dapat dilakukan . Dalam kehidupan sehari-hari, sebenarnya kita juga serig menggunakan pencarian biner. Misalnya saat kita ingin mencari suatu kata dalam kamus.

Langkah dalam pencarian biner adalah :

1. Mula-mula diambil dari posisi awal=1 dan posisi akhir = n

2. Kemudian kita cari posisi data tengah dengan rumus posisi tengah = (posisi awal + posisi akhir ) div 2

3. Kemudian data yang di cari dibandingkan dengan data tengah

a. Jika sama, data ditemukan, Proses selesai

b. Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah -1,

c. Jika lebih besar , proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah +1.

4. Ulangi langkah kedua hingga data ditemukan , atau tidak ditemukan.

5. Pencarian biner ini akan berakhir jika data ditemukan posisi awal lebih besar dari pada posisi akhir. Jika posisi awal sudah lebih besar dari posisis akhir berarti data tidak diketemukan.

Contoh sintak Binary search pada bahasa C:

#include

#include

int data[10] = {1,4,6,8,18,23,35,49,60,75};

int binary_search(int cari)

{

int l,r,m;

int n = 10;

l = 0;

r = n-1;

int ketemu = 0;

while(l<=r && ketemu==0)

{

m = (l+r)/2;

if ( data[m] == cari )

ketemu = 1;

else

if (cari <>

r = m-1;

else l = m+1;

}

if(ketemu == 1) return 1; else return 0;

}

void main()

{

clrscr();

int cari,hasil;

cout<<"Masukan data yang ingin dicari = ";

cin>>cari;

hasil = binary_search(cari);

if(hasil == 1)

{

cout<<"Data tersedia!"<

}

else

if(hasil == 0)cout<<"Data tidak tersedia!"<ETODE SEARCHING (Sequential Search & Binary Search) dalam C++

METODE SEARCHING (Sequential Search & Binary Search)

Searching adalah metode pencarian informasi dalam suatu aplikasi, dengan suatu kunci( key ). Pencarian diperlukan untuk mencari informasi khusus dari table pada saat lokasi yang pasti dari informasi tersebut sebelumnya tidak diketahui. Pencarian selalu dinyatakan dengan referensi pada adanya sekelompok data yang tersimpan secara terorganisasi, kelompok data tersebut kita sebut table.

Pada metode searching (pencarian) ada 2 teknik yang digunakan yaitu : Pencarian sekuensial (sequential search) dan Pencarian biner (Binary search).

1. Pencarian sekuensial (sequential search)

Pencarian sekuensial (sequential search) atau sering disebut pencarian linier menggunakan prinsip sebagai berikut : data yang ada di bandingkan satu persatu secara berurutan dengan yang dicari.

Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah data. Pada setiap perulangan , di bandingkan data ke-i dengan yang dicari. Apabila sama , berarti data telah ditemukan . Sebaliknya apabila sampai akhir pengulangan , tidak ada yang sama berarti data tidak ada.

a. Sekuensial versi berdampingan dengan sintak C:

Contoh listing fungsi dalam bahasa C++ :

Int SequensialSearch(List_type list, Key_type target)

{ int location; // penempatan data

for (location=0;location

if (EQ(list.entry[location].key,target))

return location;

return –1

b. Sekuensial versi berangkai dengan sintak C:

Node_type* SequentialSearch (List_type list, Key_type target)

{ Node_type* location;

for (location=list.head;location!=NULL;locatioan->next)

if(EQ(location->info.key,target))

return location;

return NULL

}

Pengimplementasian sintak sekuensial search pada bahasa C :

#include

#include

void main()

{

clrscr();

int data[8] = {3,9,7,-3,11,5,2,18};

int cari,index;

int ketemu=0;

cout<<"Inputkan data yang ingin di cari = ";

cin>>cari;

for(int i=0;i<8;i++)

{

if(data[i] == cari)

{

ketemu=1;

index=1;

break;

}

}

if(ketemu == 1)

{

cout<<"Data tersedia!"<

cout<<"Data Terletak di index ke - "<

}

else cout<<"Data tidak tersedia!"<

getch();

}

2. Pencarian Biner (Binary Search)

Salah satu syarat pencarian biner (binary search) dapat dilakukan adalah data sudah dalam keadaan terurut. Dengan kata lain, apabila data belum dalam keadaan terurut , pencarian biner tidak dapat dilakukan . Dalam kehidupan sehari-hari, sebenarnya kita juga serig menggunakan pencarian biner. Misalnya saat kita ingin mencari suatu kata dalam kamus.

Langkah dalam pencarian biner adalah :

1. Mula-mula diambil dari posisi awal=1 dan posisi akhir = n

2. Kemudian kita cari posisi data tengah dengan rumus posisi tengah = (posisi awal + posisi akhir ) div 2

3. Kemudian data yang di cari dibandingkan dengan data tengah

a. Jika sama, data ditemukan, Proses selesai

b. Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah -1,

c. Jika lebih besar , proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah +1.

4. Ulangi langkah kedua hingga data ditemukan , atau tidak ditemukan.

5. Pencarian biner ini akan berakhir jika data ditemukan posisi awal lebih besar dari pada posisi akhir. Jika posisi awal sudah lebih besar dari posisis akhir berarti data tidak diketemukan.

Contoh sintak Binary search pada bahasa C:

#include

#include

int data[10] = {1,4,6,8,18,23,35,49,60,75};

int binary_search(int cari)

{

int l,r,m;

int n = 10;

l = 0;

r = n-1;

int ketemu = 0;

while(l<=r && ketemu==0)

{

m = (l+r)/2;

if ( data[m] == cari )

ketemu = 1;

else

if (cari <>

r = m-1;

else l = m+1;

}

if(ketemu == 1) return 1; else return 0;

}

void main()

{

clrscr();

int cari,hasil;

cout<<"Masukan data yang ingin dicari = ";

cin>>cari;

hasil = binary_search(cari);

if(hasil == 1)

{

cout<<"Data tersedia!"<

}

else

if(hasil == 0)

cout<<"Data tidak tersedia!"<

getch();

}

· Pencarian Sekuensial :

a. Kelebihannya :

- Relatif lebih cepat dan efisien untuk data yang terbatas

- Algoritma sederhana

b. Kekuranganya :

- Kurang cepat untuk data dalam jumlah besar

- Beban komputasi cenderung lebih besar

· Pencarian Biner :

a. Kelebihannya :

- Untuk data dalam jumlah besar, waktu searching lebih cepat

- Beban komputasi lebih kecil

b. Kekuranganya :

- Data harus sudah di-sorting lebih dulu ( dalam keadaan terurut ) - See more at: http://edyuty.blogspot.com/2013/05/metode-searching-sequential-search.html#sthash.9kJZxAzl.dpuf

getch();

}

· Pencarian Sekuensial :

a. Kelebihannya :

- Relatif lebih cepat dan efisien untuk data yang terbatas

- Algoritma sederhana

b. Kekuranganya :

- Kurang cepat untuk data dalam jumlah besar

- Beban komputasi cenderung lebih besar

· Pencarian Biner :

a. Kelebihannya :

- Untuk data dalam jumlah besar, waktu searching lebih cepat

- Beban komputasi lebih kecil

b. Kekuranganya :

- Data harus sudah di-sorting lebih dulu ( dalam keadaan terurut ) - See more at: http://edyuty.blogspot.com/2013/05/metode-searching-sequential-search.html#sthash.9kJZxAzl.dpuf

BRANCH AND BOUND

•          Metode Branch and Bound adalah sebuah teknik algoritma yang secara khusus mempelajari bagaimana caranya memperkecil Search Tree menjadi sekecil mungkin.

•          Sesuai dengan namanya, metode ini terdiri dari 2 langkah yaitu :

–        Branch yang artinya membangun semua cabang tree yang mungkin menuju solusi.

–        Bound yang artinya menghitung node mana yang merupakan active node (E-node) dan node mana yang merupakan dead node (D-node) dengan menggunakan syarat batas constraint (kendala).

TEKNIK BRANCH AND BOUND

•          FIFO Branch and Bound

–        Adalah teknik Branch and Bound yang menggunakan bantuan queue untuk perhitungan Branch and Bound secara First In First Out.

•          LIFO Branch and Bound

–        Adalah teknik Branch and Bound yang menggunakan bantuan stack untuk perhitungan Branch and Bound secara Last In First Out.

•          Least Cost Branch and Bound

–        Teknik ini akan menghitung cost setiap node. Node yang memiliki cost paling kecil dikatakan memiliki kemungkinan paling besar menuju solusi.

MASALAH YANG DAPAT DIPECAHKAN

•          Branch and Bound dapat digunakan untuk memecahkan berbagai masalah yang menggunakan Search Tree

–        Traveling Salesman Problem

–        N-Queen Problem

–        15 Puzzle Problem

–        0/1 Knapsack Problem

                                -Shortest Path

 

Algoritma Brute Force

Algoritma  Brute Force adalah sebuah  pendekatan

yang lempang (straightforward) untuk memecahkan

suatu masalah, biasanya didasarkan pada pernyataan

masalah (problem statement) dan definisi konsep

yang dilibatkan.[7]

Prinsip –  prinsip algoritma brute force untuk

menyelesaikan persoalan Integer Knapsack ialah:

1)  Mengenumerasikan semua himpunan  bagian

dari solusi.

2)  Mengevaluasi total keuntungan  dari  setiap

himpunan bagian dari langkah pertama

3)  Pilih himpunan bagian yang mempunyai total

keuntungan terbesar

Algoritma Greedy

Secara harfiah,  greedy  berarti rakus atau tamak.

Algoritma  Greedy  merupakan  algoritma sedarhana

dan lempang yang paling populer untuk pemecahan

persoalan  optimasi (maksimum atau  minimum).

Prinsip  greedy   adalah: “take what you  can  get

now!”, yang digunakan dalam konteks positif.[7]

Ada tiga pendekatan dalam  menyelesaikan

persoalan  Integer Knapsack dengan algoritma

Greedy:

1)  Greedy by profit. 

Pada setiap langkah,  knapsack diisi dengan objek

yang mempunyai keuntungan terbesar. Strategi ini

mencoba memaksimumkan keuntungan dengan

memilih objek yang paling menguntungkan terlebih

dahulu.

2)  Greedy by weight.

Pada setiap langkah,  knapsack diisi dengan objek

yang mempunyai berat paling  ringan. Strategi ini

mencoba memaksimumkan keuntungan dengan

memasukkan sebanyak mungkin objek ke dalam

knapsack.

3)  Greedy by density. 

Pada setiap langkah,  knapsack diisi dengan objek

yang mempunyai densitas,  pi  /wi  terbesar.   Strategi

ini mencoba  memaksimumkan keuntungan  dengan

memilih objek yang mempunyai keuntungan per unit

berat terbesar.

Algoritma Dynamic Programming

Program Dinamis (dynamic programming): metode

pemecahan masalah dengan cara menguraikan solusi

menjadi  sekumpulan langkah (step) atau tahapan

(stage) sedemikian  sehingga solusi dari  persoalan

dapat dipandang  dari serangkaian keputusan  yang

saling berkaitan.[7] 

Pada penyelesaian persoalan dengan metode ini:

(1)  terdapat sejumlah berhingga pilihan  yang

mungkin,

(2)  solusi pada setiap tahap dibangun  dari hasil

solusi tahap sebelumnya,

(3)  kita menggunakan  persyaratan  optimasi dan

kendala untuk membatasi sejumlah pilihan yang

harus dipertimbangkan pada suatu tahap.

Dua  pendekatan yang digunakan  dalam  Dynamic

Progamming  adalah maju (forward atau  up-down)

dan mundur (backward atau bottom-up). 

Misalkan x1, x2, …, xn menyatakan peubah (variable)

keputusan  yang harus dibuat masing-masing untuk

tahap 1, 2, …, n. Maka,

a.  Program dinamis  maju: Program dinamis

bergerak mulai dari tahap 1, terus maju ke tahap 2, 3, dan seterusnya sampai  tahap n. Runtunan

peubah keputusan adalah x1, x2, …, xn.

b.  Program dinamis  mundur: Program dinamis

bergerak mulai dari tahap  n, terus mundur ke

tahap n – 1, n – 2, dan seterusnya sampai tahap

1.  Runtunan peubah keputusan  adalah  xn,  xn-1,

…, x1.

Secara  umum, ada empat langkah yang  dilakukan

dalam  mengembangkana algoritma program

dinamis:

1.  Karakteristikkan struktur solusi optimal.

2.  Definisikan secara rekursif nilai solusi

optimal.

3.  Hitung nilai solusi optimal secara maju atau

mundur.

4.  Konstruksi solusi optimal.

Algoritma Divide and Conquer

Algoritma  divide and conquer sudah lama diperkenalkan sebagai sumber dari

pengendalian proses paralel, karena masalah-masalah yang terjadi dapat diatasi

secara independen. Banyak arsitektur dan bahasa pemrograman paralel mendesain

implementasinya (aplikasi) dengan struktur dasar dari algoritma divide and conquer.

Untuk menyelesaikan masalah-masalah yang besar, dan dibagi (dipecah) menjadi

bagian yang lebih kecil dan menggunakan sebuah solusi untuk menyelesaikan

problem awal adalah prinsip dasar dari pemrograman/strategi divide and conquer.

Terima Kasih

Nama                                                    : M.Ropianto, M.Kom

NIDN:                                                  : 102867804

Status                                                  : Dosen Tetap YAPISTA / STT Ibnu Sina

Pengampuh Matakuliah                   : Algoritma & Pemrograman 3