Algoritma Pencarian


Algoritma pencarian

 

Dalam ilmu komputer, sebuah algoritma pencarian dijelaskan secara luas yaitu sebuah algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, algoritma biasanya di dapat dari evaluasi beberapa kemungkinan solusi. Sebagian besar algoritma yang dipelajari oleh ilmuwan komputer adalah algoritma pencarian. Himpunan semua kemungkinan solusi dari sebuah masalah disebut ruang pencarian. Algortima pencarian brute-force atau pencarian uninformed menggunakan metode yang sederhana dan sangat intuitif pada ruang pencarian, sedangkan algoritma pencarian informed menggunakan heuristik untuk menerapkan pengetahuan tentang struktur dari ruang pencarian untuk berusaha mengurangi banyaknya waktu yang dipakai dalam pencarian.

 

Adapun macam-macam algoritma dapat dijelaskan sebagai berikut:

  1. 1.      Algoritma Pencarian Pohon A*

A* adalah algoritma best-first search yang menggabungkan Uniform Cost Search dan Greedy Best-First Search. Biaya yang diperhitungkan didapat dari biaya sebenarnya ditambah dengan biaya perkiraan. Dalam notasi matematika dituliskan sebagai f(n)= g(n) + h(n). Dengan perhitungan biaya seperti ini, algoritma A* adalah complete dan optimal.

Algoritma pencarian pohon adalah jantung dari teknik-teknik pencarian. Algoritma ini mencari node dari pohon, terlepas apakah pohon tersebut eksplisit atau implisit (dibangkitkan saat pengerjaan). Prinsip dasarnya adalah sebuah node diambil dari sebuah struktur data, suksesornya algoritma ini diperiksa dan ditambahkan pada struktur data. Dengan memanipulasi struktur data, pohon dieksplorasi dalam urutan yang berbeda-beda, dieksplore dari satu tingkat ke tingkat. Contoh dari pencarian pohon antara lain adalahg pencarian iterative deepening depth dan Pencarian uninformed.

Pencarian uninformed adalah algoritma yang tidak mempertimbangkan sifat alami dari permasalahan. Oleh karena itu algoritma tersebut dapat diimplementasikan secara umum, sehingga dengan implementasi yang sama dapat digunakan pada lingkup permasalahan yang luas, hal ini berkat abstraksi. Kekurangannya adalah sebagian besar ruang pencarian adalah sangat besar, dan sebuah pencarian uninformed (khususnya untuk pohon) membutuhkan banyak waktu walaupun hanya untuk contoh yang kecil. Sehingga untuk mempercepat proses, kadang-kadang hanya pencarian informed yang dapat melakukannya.

 

 

  1. 2.      Algoritma Semut

Algoritma Semut diadopsi dari perilakukoloni semut yang dikenal sebagai sistem semut Secara alamiah koloni semutmampu menemukan rute terpendek dalam perjalanandari sarang ke tempat-tempat sumber makanan.

Intensitas jejak semut antar kota danperubahannya:

 

 

 

  1. 3.      Algoritma Dept-Firs Search

Algoritm depth-first search (DFS) melakukan pencarian secara preorder. Algoritma ini mengunjungi anak suatu simpul sebelum simpul tetangganya. Berikut gambar yang mengiilustrasikan urutan simpul yang dikunjungi pada algoritma DFS:

 

 

Ilustrasi urutan kunjungan simpul pada algoritma DFS

 

Dari gambar, dapat dilihat bahwa dengan algoritma DFS, setiap anak simpul pertama yang bertetangga dengan simpul akar dikunjungi sampai tingkat terdalamnya lebih dahulu, lalu seluruh simpul pada subpohon tersebut, sebelum simpul lain yang juga bertetangga dengan simpul akar.

 

Berikut ini adalah algoritma Depth-First Search :

Deklarasi

w : integer

 

Algoritma:

write(v)

   dikunjungi[v]true

   for tiap simpul w yang bertetangga dengan simpul v do

      if not dikunjungi[w] then

          DFS(w)

      Endif

Endfor

 

  • Keuntungan Dari Algoritma Depth-First Search

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

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

 

  • Kelemajan Dari Algoritma Depth-First Search

v  Memungkinkan tidak ditemukannya tujuan yang diharapkan.

v  Hanya akan menemukan satu solusi pada setiap pencarian.

 

 

  1. 4.      Algoritma Breadth-First Search

Algoritma 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 simpul-simpul yang tadi dikunjungi, demikian seterusnya. algoritma BFS menggunakan graf sebagai media representasi persoalan, tidak sulit untuk mengaplikasikan algoritma ini dalam persoalan-persoalan teori graf.

 

 

 

Cara Kerja Algoritma BFS

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

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

  1. Masukkan simpul ujung (akar) ke dalam antrian.
  2. Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi.
  3. Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.
  4. Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian.
  5. Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan.
  6. Ulangi pencarian dari langkah kedua.

 

  1. 5.      Algoritma Best-first Search

Algoritma best-firs search pertama kali, dibangkitkan node A. Kemudian semua suksesor A dibangkitan, dan dicari harga paling minimal. Pada langkah 2, node D terpilih karena harganya paling rendah, yakni 1. Langkah 3, semua suksesor D dibangkitkan, kemudian harganya akan dibandingkan dengan harga node B dan C. Ternyata harga node B paling kecil dibandingkan harga node C, E, dan F. Sehingga B terpilih dan selanjutnya akan dibangkitkan semua suksesor B. Demikian seterusnya sampai ditemukan node tujuan. Ilustrasi algoritma best-first search dapat dilihat pada gambar 3.4 dibawah ini.

 

langkah-langkah yang dilakukan algoritma best-first search

 

  1. 6.      Algoritma ID3

ID3 singkatan dari Iterative Dichotomiser Three. Ada juga yang menyebut Induction of Decision Tree. ID3 adalah suatu algooritma matematika yang digunakan untuk menghasilkan suatu pohon keputusan yang mampu mengklasifikasi suatu obyek. ID3 merepresentasi konsep-konsep dalam bentuk pohon keputusan. Aturan-aturan yang dihasilkan oleh ID3 mempunyai relasi yang hirarkis seperti suatu pohon (mempunyai akar, titik, cabang, dan daun). Beberapa peneliti menyebut struktur model yang dihasilkan ID3 sebagai pohon keputusan (decision tree) sementara peneliti yang lain menyebutnya pohon aturan (rule tree).

Contoh Flowchart:

 

 

Keuntungan dan kekurangan

 

Keuntungan :

  • Dapat membuat aturan prediksi yang mudah dimengerti.
  • Membangun pohon keputusan dengan cepat.
  • Membangun pohon keputusan yang pendek.
  • Hanya membutuhkan beberapa tes atribut hingga semua data diklasifikasikan.

 

Kerugian :

  • Jika contoh yang diteliti terlalu kecil / sederhana mungkin membuat data over-classified.
  • Hanya satu atribut yang dapat dites dalam satu waktu untuk membuat keputusan.
  • Mengelompokkan data yang berkelanjutan mungkin terhitung mahal, sebanyak pohon yang harus dibuat untuk melihat dimana menghentikan proses kelanjutannya.

 

  1. 7.      Algoritma C4.5

Algoritma C4.5 merupakan algoritma yang digunakan untuk membentuk pohon keputusan. Sedang pohon keputusan dapat diartikan suatu cara untuk memprediksi atau mengklarifikasi yang sangat kuat. Pohon keputusan dapat membagi kumpulan data yang besar menjadi himpunan-himpunan record yang lebih kecil dengan menerapkan serangkaian aturan keputusan.

Dalam algoritma C4.5 untuk membangun pohon keputusan hal pertama yang dilakukan yaitu memilih atribut sebagai akar. Kemudian dibuat cabang untuk tiap-tiap nilai didalam akar tersebut. Langkah berikutnya yaitu membagi kasus dalam cabang. Kemudian ulangi proses untuk setiap cabang sampai semua kasus pada cabang memiliki kelas yang sama.

Untuk memilih atribut dengan akar, didasarkan pada nilai gain tertinggi dari atribut-tribut yang ada. Untuk menghitung gain digunakan  rumus sebagai berikut:

 

 

  1. 8.      Algoritma J48

J48 merupakan implementasi C4.5 di WEKA.

 

Gambar algoritma J48

 

  1. 9.      Algoritma Bellman-Ford

Algoritma Bellman-Ford menyelesaikan masalah garis terpendek single-source untuk grafik dengan dua simpul (node) positive dan negative. Jika hanya membutuhkan untuk menyelesaikan masalah jalur terpendek untuk node positive, Algoritma Dijkstra memberikan alternatif yang lebih efisien.

Ada dua pilihan utama untuk memperoleh output dari fungsi Bellman. Jika user memberikan jarak peta melalui parameter distance_map() kemudian jarak yang paling pendek dari node utama untuk setiap root di grafik akan direkam dip peta jarak (diberikan jika fungsi bernilai true). Pilihan kedua adalah merekam jalur pohon terpendek di predecessor_map(). Untuk setiap root u di V, p[u] akan menjadi predesesor dari u di jarak terpendek pohon (kalau tidak p[u] = u, pada kasus u adalah root utama).Pada dua pilihan tersebut, user dapat memberikan pengunjung buatan sendiri yang dapat mengambil aksi pada setiap poin dari kebanyakan algoritma.

 

  1. 10.  Metode Pencarian Jalur Terpendek (Dijkstra Algorithm)

Algoritma ini bertujuan untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titik lainnya. Misalkan titik mengambarkan gedung dan garis menggambarkan jalan, maka algoritma Dijkstra melakukan kalkulasi terhadap semua kemungkinan bobot terkecil dari setiap titik.

 

 

Contoh keterhubungan antar titik  dalam algoritma Dijkstra

 

Dibawah ini penjelasan langkah per langkah pencarian jalur terpendek secara rinci dimulai dari node awal sampai node tujuan dengan nilai jarak terkecil.

  1. Node awal 1, Node tujuan 5. Setiap edge yang terhubung antar node telah diberi nilai

 

Contoh kasus Djikstra – Langkah 1

 

  1. Dijkstra melakukan kalkulasi terhadap node tetangga yang terhubung langsung dengan node keberangkatan (node 1), dan hasil yang didapat adalah node 2 karena bobot nilai node 2 paling kecil dibandingkan nilai pada node lain, nilai = 7 (0+7).

 

Contoh kasus Djikstra – Langkah 2

 

  1. Node 2 diset menjadi node keberangkatan dan ditandai sebagi node yang telah terjamah. Dijkstra melakukan kalkulasi kembali terhadap node-node tetangga yang terhubung langsung dengan node yang telah terjamah. Dan kalkulasi dijkstra menunjukan bahwa node 3 yang menjadi node keberangkatan selanjutnya karena bobotnya yang paling kecil dari hasil kalkulasi terakhir, nilai 9 (0+9).

 

Contoh kasus Djikstra – Langkah 3

 

 

  1. Perhitungan berlanjut dengan node 3 ditandai menjadi node yang telah terjamah. Dari semua node tetangga belum terjamah yang terhubung langsung dengan node terjamah, node selanjutnya yang ditandai menjadi node terjamah adalah node 6 karena nilai bobot yang terkecil, nilai 11 (9+2).

 

Contoh kasus Djikstra – Langkah 4

 

  1. Node 6 menjadi node terjamah, dijkstra melakukan kalkulasi kembali, dan menemukan bahwa node 5 (node tujuan ) telah tercapai lewat node 6. Jalur terpendeknya adalah 1-3-6-5, dan niilai bobot yang didapat adalah 20 (11+9). Bila node tujuan telah tercapai maka kalkulasi dijkstra dinyatakan selesai.

 

Contoh kasus Djikstra – Langkah 5

 

  1. 11.  Algoritma Kruskal

Algoritma Kruskal Adalah salah satu algoritma yang digunakan untuk mendapatkan minimum spanning tree dengan weight terkecil.

 

  1. 12.  Algoritma Floyd-Warshall

 

Algoritma floyd-warshall adalah satu varian dari pemrograman dinamis,yaitu dengan memandang solusi yang akan diperoleh sebagai suatu keputusan yang saling terkait. Sehingga solusi tersebut terbentuk dari solusi yang berasal dari tahap seblumnya. Algoritma warshall ini berbeda dengan algoritma greedy.karena algoritma greedy tidak diperhatikan konsekuensi yang akan terjadi seandainya kita memilih suatu keputusan pada suatu tahap. Algoritma warshall disebut juga algoritma dinamis.

 

Karakteristik dari algoritma dinamis ialah :

  1. persoalannya dibagi atas beberapa tahap,yang setiap tahapnya diambil satu keputusan.
  2. Masing-masing tahap terdiri dari sejumlah status yang saling berhubungan.
  3. Hasil keputusan akan di transformasikan.
  4. Ongkos tergantung dari ongkos tahapan yang telah berjalan dan ongkos pada tahap itu sendiri.
  5. Keputusan terbaik pada tahap bersifat independen.
  6. Terdapat hubungan rekursif yang menyatakan bahwa keputusan terbaik dalam setiap status pada tahap -k.

 

Pada algoritma ini dilakukan pendekatan ,yaitu pendekatan maju dan pendekatan mundur.

Analisisnya :

Melakukan perbandingan terlebih dahulu,yaitu pada tiap tahap antara 2 simpul hingga perkiraan tersebut diketahui sebagai nilai optimal. Ada 2 kemungkinan yang terjadi jika kita mencari jalur terpendek (shortest path) dari setiap i ke simpul j dan perantara simpul 1 s.d ke k+1,

 

  1. Jalur terpendek hanya berasal dari simpul yang berada antara 1 hingga k.
  2. Ada sebagian jalur yang berasal dari simpul 1 s/d k+1 dan juga dari k+1 hingga i.

Maka dari itu rumus fungsi shortest path dengan algoritma ini ;

basis -0

shortest path(i,j,0)=edgecost(i,j);

rekurens

shortest path (i,j,k) = min(shortestpath (i,,j,k-1),shortestpath(i,k,k-1)+shortestpath(k,j,k-1);

 

  1. 13.  Algoritma Prim

Algoritma Prim adalah sebuah algoritma dalam teori graf untuk mencari pohon 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.

Langkah-langkahnya adalah sebagai berikut:

Buat sebuah pohon yang terdiri dari satu node, dipilih secara acak dari graf.

Buat sebuah himpunan yang berisi semua cabang di graf.

Loop sampai semua cabang di dalam himpunan menghubungkan dua node di pohon.

ü  Hapus dari himpunan satu cabang dengan bobot terkecil yang menghubungkan satu node di pohon dengan satu node di luar pohon.

ü  Hubungkan cabang tersebut ke pohon.

Dengan struktur data binary heap sederhana, algoritma Prim dapat ditunjukkan berjalan dalam waktu O(Elog V), di mana E adalah jumlah cabang dan V adalah jumlah node. Dengan Fibonacci heap, hal ini dapat ditekan menjadi O(E + Vlog V), yang jauh lebih cepat bila grafnya cukup padat sehingga E adalah  (Vlog V).

Contoh:

Ini adalah graf berbobot awal. Graf ini bukan pohon karena ada circuit. Nama yang lebih tepat untuk diagram ini adalah graf atau jaringan. Angka-angka dekat garis penghubung adalah bobotnya. Belum ada garis yang ditandai, dan node D dipilih secara sembarang sebagai titik awal.
Node kedua yang dipilih adalah yang terdekat ke D: A jauhnya 5, B 9, E 15, dan F 6. Dari keempatnya, 5 adalah yang terkecil, jadi kita tandai node A dan cabang DA.
Node berikutnya yang dipilih adalah yang terdekat dari D atau A. B jauhnya 9 dari D dan 7 dari A, E jauhnya 15, dan F 6. 6 adalah yang terkecil, jadi kita tandai node F dan cabang DF.

 

Algoritma ini berlanjut seperti di atas. Node B, yang jauhnya 7 dari A, ditandai. Di sini, cabang DB ditandai merah, karena baik node B dan node D telah ditandai hijau, sehingga DB tidak dapat digunakan.

 

Dalam hal ini, kita dapat memilih antara C, E, dan G. C jauhnya 8 dari B, E 7 dari B, dan G 11 dari F. E yang terdekat, jadi kita tandai node E dan cabang EB. Dua cabang lain ditandai merah, karena kedua node yang terhubung telah digunakan.

 

Di sini, node yang tersedia adalah C dan G. C jauhnya 5 dari E, dan G 9 dari E. C dipilih, jadi ditandai bersama dengan cabang EC. Cabang BC juga ditandai merah.

 

Node G adalah satu-satunya yang tersisa. Jauhnya 11 dari F, dan 9 dari E. E lebih dekat, jadi kita tandai cabang EG. Sekarang semua node telah terhubung, dan pohon rentang minimum ditunjukkan dengan warna hijau, bobotnya 39.

 

 

 

  1. 14.  Algoritma Bayesian Learning

Algoritma Bayesian learning digunakan untuk menghitung probabilitas dari setiap hipotesis.

 

 

 

 

  1. 15.  Algoritma Boruvka

 

Algoritma ini digunakan untuk mencari pohon merentang minimum dari suatu graf. Untuk menentukan pohon merentang minimum dari sebuah graf dengan menggunakan Algoritma Boruvka maka diperlukan langkah-langkah sebagai berikut:

Mencari pohon merentang minimum pada graf G, maka

Langkah 1 : Salin titik dari G ke graf baru L yang kosong.

Langkah 2 : Sedangkan L tidak terhubung (artinya hutan lebih dari satu pohon)

Untuk setiap pohon di L, hubungkan sebuah titik ke titik yang lain pada pohon yang lain di L dengan menambahkan sisi yang berbobot minimum.

 

 

  1. 16.  Edmonds–Karp algorithm

 

Dalam ilmu komputer dan teori graf, algoritma Edmonds-Karp merupakan implementasi dari metode Ford-Fulkerson untuk menghitung aliran maksimum dalam jaringan aliran dalam waktu. Hal ini asimtotik lebih lambat dari algoritma mengubah sebutan-ke-depan, yang berjalan di O (V3) waktu, tetapi sering lebih cepat dalam praktek sedangkan untuk grafik jarang.

 

Pseudocode

Algorithm EdmondsKarp

 

input:

        C[1..n, 1..n] (Capacity matrix)

        E[1..n, 1..?] (Neighbour lists)

        s             (Source)

        t             (Sink)

    output:

        f             (Value of maximum flow)

        F             (A matrix giving a legal flow with the maximum value)

    f := 0 (Initial flow is zero)

    F := array(1..n, 1..n) (Residual capacity from u to v is C[u,v] – F[u,v])

    forever

        m, P := BreadthFirstSearch(C, E, s, t, F)

        if m = 0

            break

        f := f + m

        (Backtrack search, and write flow)

        v := t

        while v ≠ s

            u := P[v]

            F[u,v] := F[u,v] + m

            F[v,u] := F[v,u] – m

            v := u

    return (f, F)

 

algorithm BreadthFirstSearch

    input:

        C, E, s, t, F

    output:

        M[t]          (Capacity of path found)

        P             (Parent table)

    P := array(1..n)

    for u in 1..n

        P[u] := -1

    P[s] := -2 (make sure source is not rediscovered)

    M := array(1..n) (Capacity of found path to node)

    M[s] := ∞

    Q := queue()

    Q.push(s)

    while Q.size() > 0

        u := Q.pop()

        for v in E[u]

            (If there is available capacity, and v is not seen before in search)

            if C[u,v] – F[u,v] > 0 and P[v] = -1

                P[v] := u

                M[v] := min(M[u], C[u,v] – F[u,v])

                if v ≠ t

                    Q.push(v)

                else

                    return M[t], P

    return 0, P

 

Capacity Path

Resulting network

 

 

 

 

 

 

 

 

 

  1. 17.  Simulated annealing

Simulated annealing (SA) adalah salah satu 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.

 

 

 

 

Keterangan Pseudo Code

Evaluasi : Fungsi evaluasi (cost function). Contoh dalam Traveling Salesman Problem (TSP) fungsi ini adalah jarak yang harus ditempuh oleh si penjaja keliling.

 

Modifikasi : Mekanisme sederhana untuk mengubah solusi yang sudah ada, untuk menghasilkan solusi baru yang berbeda tidak terlalu jauh dengan solusi yg sudah ada. Biasanya disebut neighbour solution. Contoh dalam TSP bila solusi sementara dari TSP dengan 3 kota adalah : A B C. Hasil fungsi modifikasi adalah solusi baru dengan urutan A C B.

exp(-Delta/T) : Probabilitas bahwa langkah/solusi baru yang tidak lebih baik, akan diterima sebagai solusi sementara. Perhatikan tanda minus dalam kurung. Delta bernilai positif, yang berarti solusi baru pada tahap ini lebih buruk daripada solusi sementara yang sudah ada. Expresi ini menyatakan bahwa semakin buruk solusi baru, kemungkinan diterima sebagai solusi sementara semakin kecil. Tetapi pada awal proses Annealing, karena faktor T sebagai pembagi masih bernilai besar, probabilitas ini akan tetap cukup besar. Tidak demikian halnya setelah T menurun, dalam proses pendinginan.

T = 0.9*T : hanya merupakan salah satu contoh jadwal penurunan temperatur. Sebenarnya tidak selalu harus seperti ini. Biasanya juga dalam implementasi SA, diadakan perulangan proses modifikasi dan update solusi sementara untuk suhu tertentu. (Jadi mestinya ada loop lagi di dalam while ini, untuk mengulang simulasi pada suhu yang sama).

 

  1. 18.  Algoritma SVM (Support Vector Machine)

Algoritma SVM terutama teknik SMO (Sequential Minimal Optimization) juga merupakan algoritma paling popular dalam teknik klasifikasi maupun regresi.

Support Vector Machine (SVM) adalah sistem pembelajaran yang pengklasifikasiannya menggunakan ruang hipotesis berupa fungsi-fungsi linear dalam sebuah ruang fitur (feature space) berdimensi tinggi, dilatih dengan algoritma pembelajaran yang didasarkan pada teori optimasi dengan mengimplementasikan learning bias yang berasal dari teori pembelajaran statistic.

 

  1. 19.  Algoritma Genetik

Algoritma genetik adalah teknik pencarian yang di dalam ilmu komputer untuk menemukan penyelesaian perkiraan untuk optimisasi dan masalah pencarian. Algoritma genetik adalah kelas khusus dari algoritma evolusioner dengan menggunakan teknik yang terinspirasi oleh biologi evolusioner seperti warisan, mutasi, seleksi alam dan rekombinasi (atau crossover).

Algoritma Genetik khususnya diterapkan sebagai simulasi komputer dimana sebuah populasi representasi abstrak (disebut kromosom) dari solusi-solusi calon (disebut individual) pada sebuah masalah optimisasi akan berkembang menjadi solusi-solusi yang lebih baik. Secara tradisional, solusi-solusi dilambangkan dalam biner sebagai string ‘0’ dan ‘1’, walaupun dimungkinkan juga penggunaan penyandian (encoding) yang berbeda. Evolusi dimulai dari sebuah populasi individual acak yang lengkap dan terjadi dalam generasi-generasi. Dalam tiap generasi, kemampuan keseluruhan populasi dievaluasi, kemudian multiple individuals dipilih dari populasi sekarang (current) tersebut secara stochastic (berdasarkan kemampuan mereka), lalu dimodifikasi (melalui mutasi atau rekombinasi) menjadi bentuk populasi baru yang menjadi populasi sekarang (current) pada iterasi berikutnya dari algoritma.

 

  1. 20.  Algoritma Reverse-Delete

Algoritma reverse-delete adalah suatu algoritma dalam teori graf yang digunakan untuk mendapatkan pohon rentang minimum dari graf terhubung yang diberikan, ujung-ditimbang. Jika grafik terputus, algoritma ini akan menemukan pohon rentang minimum untuk setiap bagian terputus dari grafik. Himpunan pohon-pohon rentang minimum disebut hutan rentang minimum, yang berisi setiap titik dalam grafik.

 

Algoritma ini merupakan algoritma serakah, memilih pilihan terbaik yang diberikan setiap situasi. Ini adalah kebalikan dari algoritma Kruskal, yang merupakan algoritma greedy untuk menemukan pohon rentang minimum. Algoritma Kruskal dimulai dengan grafik kosong dan menambahkan tepi sementara algoritma Reverse-Delete dimulai dengan grafik asli dan tepi menghapus dari itu. Algoritma ini bekerja sebagai berikut:

 

Mulailah dengan graph G, yang berisi daftar tepi E.

Pergi melalui E dalam urutan penurunan bobot edge.

Untuk setiap tepi, memeriksa apakah menghapus tepi lanjut akan melepas grafik.

Lakukan penghapusan yang tidak mengarah pada pemutusan tambahan.

 

Pseudocode

 

function ReverseDelete(edges[] E)

    sort E in decreasing order

    Define an index i ← 0

    while i < size(E)

       Define edge temp ← E[i]

         delete E[i]

         if temp.v1 is not connected to temp.v2

             E[i] ← temp

         i ← i + 1

   return edges[] E

 

 

  1. 21.  Algoritma Hungaria

 

Algoritma ini memodifikasi baris dan kolom dalam matriks efektifitas sampai muncul sebuah komponen nol tunggal dalam setiap baris atau kolom sehingga komponen tersebut dapat dipilih sebagai alokasi penugasan baris dan kolom yang sesuai dengan komponen tersebut. Semua alokasi penugasan yang dibuat adalah alokasi yang optimal, dan saat diterapkan pada matriks efektifitas awal, maka akan memberikan hasil biaya alokasi penugasan yang paling minimum. Penggambaran masalah penugasan dalam bentuk jaringan ditunjukan pada gambar berikut :

 

Langkah-langkah algoritma Hungaria

Algoritma Hungaria akan mencari alokasi pasangan untuk setiap node sumber (A) masing-masing tepat ke satu node tujuan (T) dengan biaya (C) seminimal mungkin. Langkah langkah algoritma Hungaria adalah sebagai berikut :

  1. Mulai
  2. Tentukan penyelesaian fisibel awal berupa matriks C (n x n)
  3. Dalam setiap baris, tentukan sel yang memiliki nilai terkecil. Kurangkan seluruh sel pada baris tersebut dengan sel  yang memiliki nilai terkecil.
  4. Dalam setiap kolom, tentukan sel yang memiliki nilai terkecil. Kurangkan seluruh sel pada kolom tersebut dengan sel yang memiliki nilai terkecil.
  5. Periksa setiap baris yang hanya memiliki 1 buah nol yang belum ditandai. Jika ada, maka tandai sel ini dengan simbol (∆) dan tandai sel nol lainnya yang terletak pada kolom yang sama dengan simbol (×). Ulangi sampai setiap baris tidak punya nol yang belum ditandai atau paling sedikit 2 buah nol yang belum ditandai.
  6. Periksa setiap kolom yang hanya memiliki 1 buah nol yang belum ditandai. Jika ada maka tandai sel ini dengan simbol (∆) dan tandai sel nol lainnya yang terletak pada baris yang sama dengan simbol (×). Ulangi sampai setiap kolom tidak punya nol yang belum ditandai atau paling sedikit 2 buah nol yang belum ditandai.
  7. Ulangi langkah 5 dan 6 sampai salah satu kemungkinan berikut terjadi : a. Semua baris sudah mempunyai alokasi penugasan (∆), b. Ada paling sedikit 2 buah nol yang belum ditandai pada setiap baris atau kolom, c. Tidak ada nol yang belum ditandai dan alokasi penugasan yang lengkap belum tercapai.
  8. Jika (a) maka alokasi penugasan lengkap sudah tercapai lanjutkan ke langkah 14, Jika (b) maka pilih salah satu sel nol yang belum ditandai dan berikan tanda (∆) sebagai alokasi penugasan, dan tandai semua sel nol lain pada baris dan kolom yang bersesuaian lalu kembali ke langkah 5. Jika (c) maka Lanjutkan ke langkah 9.
  9. Lakukan langkah berikut : 1. Tandai baris (check) yang belum punya alokasi penugasan, 2. Tandai kolom (check) yang belum ditandai yang mempunyai nol di baris yang sudah ditandai, 3. Tandai baris (check) yang belum ditandai yang punya penugasan di kolom yang sudah ditandai. Lakukan langkah 2 dan 3 sampai terbentuk perulangan tertutup.
  10. Gambar garis melewati semua baris yang belum diberi tanda (check) dan gambar garis melewati semua kolom yang sudah diberi tanda (check). Garis-garis ini akan menutupi semua elemen nol dalam matriks penugasan.
  11. Dari sel-sel yang tidak tertutup garis, tentukan sel yang memiliki nilai terkecil. Bobotnya adalah k.
  12. Kurangkan setiap sel yang tidak tertutup garis dengan k.
  13. Tambahkan setiap sel yang tertutup 2 garis dengan k. Kembali ke langkah 5.
  14. Selesai.

 

  1. 22.  Algoritma Pencarian Biner atau Binary Seach

Binary seach adalah algoritma yang memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya. Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan). Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.

Contoh program:

#include

#include

int data[10] = {1,3,4,7,12,25,40,65,78,90}; //variabel global

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 < data[m])

r = m-1;

else l = m+1;

}

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

}

void main()

{

clrscr();

int cari,hasil;

cout<<”masukkan data yang ingin dicari = “;

cin>>cari;

hasil = binary_search(cari);

if(hasil == 1)

{

cout<<”Data ada!”<}

else

if(hasil == 0)

cout<<”Data Tidak ada!”<getch();

}

 

 

 

REFERENSI

 

http://zeromin0.blogspot.com/2011/07/analisa-algoritma-depth-first

 

http://www.churdhulz.byethost22.com/blogs/pengertian-breadth-first-search-bfs

 

http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm

 

http://rubhie-hendri.blogspot.com/2011/01/algoritma-pencarian.html

 

http://id.wikipedia.org/wiki/Algoritma_pencarian

 

http://zeromin0.blogspot.com/2011/07/analisa-algoritma-depth-first-search.html#axzz29XbbOzZ6

 

http://id.wikipedia.org/wiki/Algoritma_Prim

 

http://www.google.co.id/url?sa=t&rct=j&q=pengertian+algoritma+boruvka&source=web&cd=1&cad=rja&ved=0CCAQFjAA&url=http%3A%2F%2Flib.uin-malang.ac.id%2Fthesis%2Ffullchapter%2F06510037-mufidatul-khoiroh.ps&ei=yF9-UOCHOYflrAeawoDIDg&usg=AFQjCNH2DUTlFM8gmAxHV8B03n0e3FN4Pw

 

http://www.ifors.ms.unimelb.edu.au/tutorial/hungarian/welcome_frame.html

 

http://edwardgr.wordpress.com/2009/02/03/algoritma-hungaria/

 

http://www.generation5.org

 

http://www.scribd.com/doc/38867855/Algoritma-Semut-Dan-Algoritma-Genetika

 

http://www.google.co.id/url?sa=t&rct=j&q=pengertian+algoritma+dijkstra&source=web&cd=1&cad=rja&ved=0CCAQFjAA&url=http%3A%2F%2Fasyadeeq.files.wordpress.com%2F2009%2F11%2Fdijkstra-pencarian-jalur-terpendek.doc&ei=BGZ-UNuFD4yurAfjnYD4CQ&usg=AFQjCNHSM1LRQJsAJzYdZ6X9ZamcotXh3w

 

http://sakurachan89.blogspot.com/2009/04/algoritma-warshall-dan-bellman-1.html

 

http://www.scribd.com/doc/21742228/Prim-and-Kruskal-algorithm

 

http://fiqihsofiana.blogspot.com/2012/01/algoritma-c45.html

 

http://codemath.wordpress.com/2011/06/20/perbedaan-algoritma-id3-c4-5-dan-j48/

 

http://gunadarma.ac.id/library/articles/graduate/computer-science/2008/Artikel_11104835.pdf

4 pemikiran pada “Algoritma Pencarian

  1. mas, itu algoritma dijkstra kalau misalkan untuk studi kasus pencarian rute terpendek skala besar biar ndak looping-forever gmna ? terimakasih

  2. Ping balik: Algoritma Semut | Sistem Berbasis Pengetahuan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s