Hill Climbing Search

    Hill Climbing termasuk dalam metode Uninformed Search, ia menggunakan metode mencari nilai yang lebih baik dari sebelumnya, cara ini biasanya diterapkan pada tree.

Silahkan di lihat gambarnya.

     Dari gambar di atas dapat kita simpulkan cara kerjanya, pertama kita tentukan dulu aturan(list) mana yang terbaik dan terburuknya. Gambar ini menentukan M-D-B-N-L-O sebagai prioritasnya.
     Selanjutnya ketika kita memulai pencarian(dari root = S(start)), kita akan menentukan langkah selanjutnya dengan patokan aturan tersebut, hingga kita menemukan G(goal)nya.
     Solusi ini jelas tidak akan optimal untuk mencari suatu solusi, tapi kita dapat "mengakali" nya dengan cara memperbanyak climbernya(startnya dari beberapa tempat), dengan memperbanyak climber kita dapat meningkatkan kemungkinan mendapatkan solusi terbaik.

Read More...

Depth First Search

Termasuk dalam metode Uninformed Search, berlawanan cara dengan metode Breadth First Search yang saya bahas sebelumnya.

Ini gambar animasinya.

Metode ini akan mencari dulu di satu sisi, hingga kedalaman yang paling jauh, lalu akan melakukan backtrack.

Keuntungan :

1. Tidak menghabiskan banyak memory, karena tidak perlu menyimpan apapun.

Kerugian :

1. Kalau data banyak, data yang di cari dekat dengan root, dan tidak 1 arah dengan perjalanan pertama ke kedalaman paling jauh. Jelas akan menghabiskan banyak waktu.

Read More...

Breadth First Search

    Metode pencarian ini merpakan metode Uninformed Search, metode ini mencari nilai terbaik dengan cara melihat per baris.

Silahkan melihat gambar berikut agar lebih jelas.

Dapat di lihat bahwa setiap akan turun, akan memeriksa anaknya, lalu di simpan.

Cara penyimpanan :
a
bc     (node anak dari root)
cde   (node c + node anak dari b)
defg  (node anak dari b + node anak dari c)
dfgh  (dst....*hingga ketemu goalnya.)

Keuntungan :

1. Tidak akan menemui jalan buntu
2. Jika terdapat banyak solusi, metode ini dapat menemukan dan membandingkan untuk mendapatkan hasil yang terbaik

Kerugian :

1. Memory yang di butuhkan sangat banyak, karena metode ini akan mengingat semua node anak nya.

Read More...

Segmented Sieve of Eratosthenes

    Segmented Sieve of Eratosthenes adalah pengembangan dari Sieve of Eratosthenes, bila bilangan prima yang di cari tidak di mulai dari angka 0.
    Contohnya "Tuliskan bilangan Prima dari 999900000 sampai 1000000000" coba bayangkan kompleksitas nya kalau harus mulai dari 0. XD.


Ini source code upgrade an Sieve of Eratosthenes" saya :D

#include <iostream>
#include <math.h>

typedef long long LL;

using namespace std;

LL N,M;
bool Prima[1000000000];

int main()
{
    cout<<"Masukan angka minimal bilangan prima = ";cin>>N;
    cout<<"Masukan angka maximal bilangan prima = ";cin>>M;
    for(LL i=N;i<M;i++)
        Prima[i] = true;
    cout<<"Bilangan Prima dari "<<N<<" - "<<M<<" adalah : ";
    Prima[0] = false;
    Prima[1] = false;

    for(LL i=2;i<sqrt(M);i++)
        for(LL j=N;j<M;j++)
            if(Prima[j] && ((j/i)*i == j))
            {
                j += i;
                while(j < M)
                {
                    if(Prima[j])
                        Prima[j] = false;
                    j += i;
                }
            }
    for(int i=N;i<M;i++)
        if(Prima[i])
            cout<<i<<endl;
    return 0;
}

Read More...