PAPER Breadth-first search

PAPER Breadth-first search

By:

> Muhammad Zamroni Hamzah

   (100411100085)

> Moh. Zein Saedi

   (100411100034)

> Yusuf Machsar

   (100411100026)

> Moh. Aminur Rosyid

   (100411100021)

RANCANGAN ANALISIS ALGORITMA

Teknik Informatika

Fakultas Teknik

Universitas Trunojoyo Madura

2012
       Breadth-first search

PENGERTIAN ALGORITMA BFS

Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pad aras d+1.

Algoritma ini memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi. Simpulsimpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungu masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang te lah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu kali.

1.      CARA KERJA ALGORITMA BFS

Dalam algoritma BFS, simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian ini digunakan untuk mengacu simpul-simpul yang bertetangga dengannya yang akan dikunjungi kemudian sesuai urutan pengantrian.

Untuk memperjelas cara kerja algoritma BFS beserta antrian yang digunakannya, berikut langkah-langkah algoritma BFS:

Masukkan simpul ujung (akar) ke dalam antrian

Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi

Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.

Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian

Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan

Ulangi pencarian dari langkah kedua

Contohnya terlihat dibawah ini:

Maka penyelesaiannya adalah:

Gambar (a) BFS(1): 1, 2, 3, 4, 5, 6, 7, 1.

Gambar (b) BFS(1): 1, 2, 3, 4, 5, 6, 7, 1

Gambar (c) BFS(1): 1, 2, 3, 4, 5, 6, 7, 8, 9

2.      CONTOH PENCARIAN LINTASAN TERPENDEK DENGAN BFS

Adapun contoh untuk mencari lintasan terpendek dengan menggukan algoritma BFS adalah sebagai berkut:

Diketahui sebuah kota, dengan memiliki inisial seperti yang ditunjukkan dibawah ini. Jarak antar kota dibentuk dengan sebuah graph terlihat dibawah:

Pertanyaan: sebutkan rute yang akan ditempuh untuk mencapai kota no. 8. Titik awal perjalanan adalah kota no. 1. Gunakan algoritma BFS!

Maka dengan menggunakan algoritma BFS, rute tercepat yang didapat adalah sebagai berikut:

1 – 2 – 3 – 4 – 5 – 6 – 7 – 8

Rute tersebut didapat dari pencarian secara melebar. Hal; tersebut dapat dijabarkan sebagai berikut:

-          Pertama-tama, pointer menunujuk pada daun yang ada sebelah kanan, yaitu no.2 (1 – 2)

-          Setelah itu, proses dilanjutkan pada tetangga no.2 yaitu no.3 (1-2-3) dan selanjutnya mengarah pada tetangga terdekat, yakni no.4 (1-2-3-4).

-          Pointer mencari teteangga no.4, namun karna tidak ada, maka pointer kembali ke kota no.2 dan masuk ke daun berikutnya, yakni no.5.

-          Proses diulang hingga pointer menunjuk angka 8

Ilustrasi BFS

• Deskripsi keadaan

• Pointer ke parent

• Kedalaman simpul

• Operator yang membuka simpul ini

• Biaya total dari simpul awal sampai simpul ini

-Root node

-Leaf node

-Branching factor

-Ancestor / descendant

-Path

-Level

Ambil fringe sebagai list berisi keadaan awal

Loop

if fringe kosong return failure

Node ß remove-first (fringe)

if Node is a goal

then return jalur dari keadaan awal sampai Node

else buka semua suksesor Node, dan

(satukan Nodes baru ke dalam fringe)

tambahkan Nodes baru ke akhir fringe

End Loop

Algoritma BFS merupakan mekanisme pencarian sebuah simpul pada graf dengan cara memulai pencarian pada sebuah simpul dan kemudian mengunjungi semua

simpul yang bertetangga dengan simpul awal dan baru kemudian semua simpul yang belum dikunjungi yang bertetanggaan dengan simpul-simpul yang tadi dikunjungi.

Algoritma BFS memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi. Simpul-simpul yang telah dikunjungi suatu saat diperlukan sebagai acuan

untuk mengunjungi simpul-simpul yang bertetangga dengannya. Tiap simpul yang telah dikunjungi masuk ke dalam antrian hanya satu kali.[1] Algoritma BFS memerlukan tabel Boolean yang bernama Dikunjungi untuk menyimpan simpul yang telah dikunjungi agar tidak ada simpul yang dikunjungi lebih dari sekali. Deklarasi tabel tersebut di dalam kamus adalah [1] Deklarasi

Dikunjungi : array[1..n] of

boolean

Dalam implementasinya, algoritma BFS memerlukan matriks ketetanggaan A = [aij] yang berukuran n × n,

antrean q untuk menyimpan simpul yang telah dikunjungi dan tabel boolean dikunjungi. Pseudo-code dari algoritma BFS adalah sebagai berikut:

Algoritma: BuatAntrian(q) { buat antrian kosong } write(v) { cetak simpul awal yang dikunjungi } dikunjungi[v]true { simpul v telahdikunjungi, tandai dengan true} MasukAntrian(q,v) { masukkan simpulawal kunjungan ke dalam antrian} { kunjungi semua simpul graf selamaantrian belum kosong } while not AntrianKosong(q) do HapusAntrian(q,v) { simpul v telahdikunjungi, hapus dari antrian } for wl to n do if A[v,w] = 1 then { v dan w bertetangga } if not dikunjungi[w] then write(w) {cetak simpul yang dikunjungi} MasukAntrian(q,w) dikunjungi[w]true endif endif endfor endwhile { AntrianKosong(q) } {[1]}

Kompleksitas waktu algoritma BFS:

Asumsi: setiap simpul dapat membangkitkan b  buah simpul baru. Misalkan solusi ditemukan pada aras ke-d Jumlah maksimum seluruh simpul:

1 + b + b2 + b3 + ... + bd = (bd+1 – 1)/(b – 1) 

T(n) = O(bd). 

Kompleksitas ruang algoritma BFS = sama dengan kompleksitas waktunya, karena semua simpul daun dari pohon harus disimpan di dalam memori  selama proses pencarian.

Keuntungan BFS :

-Menemukan jalur solusi dengan jalur tersingkat, karena selalu mengambil lebar dari pohon pencarian.

-Membutuhkan memori yang relative kecil, karena hanya node-node pada lintasan yang aktif saja.

-Secara kebetulan, metode depth-first search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.

Reade more >>

PAPER RANCANGAN ANALISA ALGORITMA

PAPER

RANCANGAN ANALISA ALGORITMA

By:

Moh. Zein Saedi           (100411100034)

M. Aminur Rosyid        (100411100021)

M. Zamroni Hamzah   (100411100085)

Yusuf Machsar             (100411100026)

TEKNIK INFORMATIKA

FAKULTAS TEKNIK

UNIVERSITAS TRUNOJOYO MADURA

2012

ALGORITMA PRIM

Algoritma Prim adalah sebuah algoritma dalam teori graf untuk mencari rentang minimum untuk sebuah graf berbobot yang saling terhubung. Ini berarti bahwa sebuah himpunan bagian dari edge yang membentuk suatu pohon yang mengandung node, di mana bobot keseluruhan dari semua edge dalam pohon diminimalisasikan. Bila graf tersebut tidak terhubung, maka graf itu hanya memiliki satu pohon rentang minimum untuk satu dari komponen yang terhubung.

A.   Algoritma Prim ini, merupakan algoritma yang dapat dikategorikan sebagai Conquer Transformer. Karena, dalam metode penyelesaiannya memerlukan proses untuk menukar-kan posisi edge yang menjadi pertimbangan untuk perbandingan.

B.   Berikut ini penghitungan Tn, Cn, dan Cop:

A ← V[G]                                                                          1

 for each vertex u in Q                                                         N+1
     do key [u] ← ∞                                                               1
 key [r] ← 0                                                                      1
 π[r] ← NIL                                                                       1
 while array A is empty                                                         N+1
     /* do scan over A find the node u with smallest key, and remove it from

array A*/
     for each vertex v in Adj[u]                                                N+1
         if v is in A and w[u, v] < key[v]                                      N+1
           then  π[v] ← u                                                         1
                   key[v] ← w[u, v]                                               1

Tn = Cn * Cop

     = (1+N+1+1+1+1+N+1+N+1+N+1+1+1) * 10

     = (3N + 10) * 10

     = 30N + 100

C.   Berikut Inisialisasi Oh-nya

ALGORITMA HUFFMAN

Konsep dasar dari metode Huffman adalah dengan membangun sebuah skema atau tabel yang berisikan frekuensi kemunculan masing-masing simbol. Dari tabel tersebut kemudian dibangun suatu kode-kode unik untuk mengidentifikasikan masing-masing simbol. Proses kompresi dengan metode huffman adalah sebagai berikut:

·  Menyusun tabel frekuensi kemunculan masing-masing karakter, dan melakukan source reduction.

·  Langkah kedua dari algoritma ini adalah mengkodekan masing-masing source yang telah direduksi, dimulai dari reduksi terakhir kembali ke sumber awalnya.

·  Langkah berikutnya adalah mengkodekan data sumber berdasarkan table look-up yang ter-bentuk.

A.   Algoritma Huffman ini, merupakan algoritma yang dapat dikategorikan sebagai ConquerDecrease. Karena, dalam metode penyelesaiannya langsung membandingkan secara to the point pada membandingkan masing-masing vertex.

B.   Berikut ini penghitungan Tn, Cn, dan Cop:

algorithm:

   1- sort the message ensemble by decreasing probability.                  N+1                      

   2- N is the cardinal of the message ensemble (number of different              1

      messages).

   3- compute the integer n_0 such as 2<=n_0<=D and (N-n_0)/(D-1) is              1

      integer.

   4- select the n_0 least probable messages, and assign them each adigit   1

      code.

   5- substitute the selected messages by a composite message summing            N+1

      their probability, and re-order it.

   6- while there remains more than one message, do steps thru 8.                N+1

   7- select D least probable messages, and assign them each adigit code.   1

   8- substitute the selected messages by a composite message summing their N+1 

probability, and re-order it.

   9- the code of each message is given by the concatenation of the code          1

      digits of the aggregate they've been put in.

Tn = Cn * Cop

     = (N+1+1+1+1+N+1+N+1+1+N+1+1) * 9

     = (4N + 9) * 9

     = 36N + 81

C.   Berikut Inisialisasi Oh-nya

 

ALGORITMA KRUSKAL

Algoritma Kruskal adalah sebuah algoritma dalam teori graph yang menemukan pohon rentang minimum untuk terhubunggraf berbobot . Ini berarti menemukan subset dari tepi yang membentuk sebuah pohon yang mencakup setiap titik , di mana berat total semua tepi di pohon diminimalkan. Jika grafik tidak terhubung, maka ia menemukan hutan rentang minimum (minimal spanning pohon untuk setiap komponen terhubung ). Algoritma Kruskal adalah contoh dari algoritma rakus .

Algoritma Kruskal adalah algoritma dalam teori graph untuk mencari minimum spaning tree di dalam graph. Algoritma Kruskal adalah contoh dari salah satu strategi algoritma yaitu Greedy Algorithm.

A.   Algoritma Kruskal ini, merupakan algoritma yang dapat dikategorikan sebagai Conquer Transformer. Karena, dalam metode penyelesaiannya memerlukan proses untuk menukar-kan posisi edge yang menjadi pertimbangan untuk perbandingan.

B.   Berikut ini penghitungan Tn, Cn, dan Cop:

int kruskal(int n, int m, set_of_edges E,set_of_edges& F)

{

set_pointer p, q;                                                             1

edge e;                                                                       1

sort the m edges in E by weight;//mengurutkan berdasarkan bobot              N+1

initial(n);                                                                   1

while (# of edges in F < n1)                                                 N+1

{

e = next lowest weight edge;                                           1

i,j = e.indices();                                                     1

p = find(i);                                                           1

q = find(j);                                                           1

if (! equal(p,q)) {                                                    1

merge(p,q);                                                     1

add e to F;                                                     1

}

}

}

Tn = Cn * Cop

     = (1+1+N+1+1+N+1+1+1+1+1+1+1+1) * 12

     = (2N + 12) * 12

     = 24N + 144

C.   Berikut Inisialisasi Oh-nya

ALGORITMA GREEDY

Algoritma Greedy adalah salah satu algoritma yang dapat digunakan untuk mendapatkan solusi terbaik dan merupakan algoritma yang paling populer dalam hal ini.Secara Harfiah Greedy artinya rakus atau tamak, sifat yang berkonotasi negatif. Orang yang memiliki sifat ini akan mengambil sebanayak mungkin atau mengambil yang paling bagus atau yang paling mahal. Sesuai dengan arti tersebut, Prinsip Greedy adalah take what you can get now.

Dalam kehidupan sehari hari Greedy dapat digunakan dalam masalah seperti :

• Memilih beberapa jenis investasi

• Mencari jalur tersingkat

           

Ada juga yang dapat dilakukan algoritma ini dalam sesuatu yang biasa dilakukan mesyarakat modern, yaitu memilih spesifikasi komputer yang terbaik dengan budget maksimum tertentu seperti yang akan dibahas dalam makalah ini.

Algoritma Greedy membentuk solusi langkah per langkah (step by step). Terdapat banyak pilihan yang perlu di eksplorasi pada setiap langkah solusi, karenanya pada setiap langkah harus dibuat keputusann yang terbaik dalam menentukan pilihan.Keputusan yang telah
diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya. Sebagai contoh, jika kita manggunakan algoritma Greedy untuk menempatkan komponen diatas papan sirkuit, sekali komponen telah diletakkan dan dipasang maka tidak dapat dipindahkan lagi.
Pada setiap langkah diperoleh optimum lokal. Bila algoritma berakhir, kita berharap optimum lokal menjadi optimum global.

A.   Algoritma Greedy ini, merupakan algoritma yang dapat dikategorikan sebagai Conquer Decrease. Karena, dalam metode penyelesaiannya langsung membandingkan secara to the point pada membandingkan masing-masing vertex.

B.   Berikut ini penghitungan Tn, Cn, dan Cop:

S ← {}   // inisialisasi S dengan kosong                                          1

 while (not SOLUSI(S)) and (C ≠ {} ) do                                          N+1

       x ← SELEKSI(C)        // pilih sebuah kandidat dari C                      1

       C ← C - {x}           // elemen himpunan berkurang satu                    1

 if LAYAK(S ∪ {x}) then                                                           1

        S ← S ∪ {x}                                                               1

       endif                                                                      1

     endwhile                                                                     1

{SOLUSI(S) or C = {} }                                                            1

if SOLUSI(S) then                                                                 1

   return S                                                                       1

else                                                                              1

   write(’tidak ada solusi’)                                                      1

endif                                                                             1

Tn = Cn * Cop

     = (1+N+1+1+1+1+1+1+1+1+1+1+1+1+1) * 14

     = (N + 14) * 14

     = 14N + 196

C.   Berikut Inisialisasi Oh-nya

 

ALGORITMA DJIKSTRA

Algoritma Dijkstra adalah sebuah algoritma greedyyang dipakai dalam memecahkan permasalahan jarak terpendek untuk sebuah graf berarah dengan bobot-bobot sisi yang bernilai tak-negatif.Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi (edge weights) melambangkan jarak antara kota-kota tersebut, maka algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.

Input algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan sebuah sumber vertexs dalam G dan V adalah himpunan semua vertices dalam graph G.

Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertexu ke vertexv. Himpunan semua tepi disebut E.

A.   Algoritma Djikstra ini, merupakan algoritma yang dapat dikategorikan sebagai ConquerDecrease. Karena, dalam metode penyelesaiannya langsung membandingkan secara to the point pada membandingkan masing-masing vertex.

B.   Berikut ini penghitungan Tn, Cn, dan Cop:

function Dijkstra(G, w, s)                                                        1

for each vertex v in V[G]                    // Inisialisasi                     N+1

           d[v] := infinity                                                       1

           previous[v] := undefined                                              N+1

     d[s] := 0                                    // Jarak antar s          1

     S := empty set                                                               1

     Q := V[G]                                    // Mengisikan nilai vertex      1

while Q is not an empty set                  // Proses algoritma            N+1

           u := Extract_Min(Q)                                                    1

           S := S union {u}                                                       1

for each edge (u,v) outgoing from u                                         1

if d[u] + w(u,v) < d[v]         // Penyeleksian kondisi            1

                        d[v] := d[u] + w(u,v)                                     1

                        previous[v] := u                                    1

Tn = Cn + Cop

     = (1+N+1+1+N+1+1+1+1+N+1+1+1+1+1+1+1) * 14

     = (3N + 14) * 14

     = 42N + 196

C.   Berikut Inisialisasi Oh-nya

Reade more >>