Kamis, 18 Oktober 2012

Binary Tree : Mencari kedalaman suatu binary tree


Pengertian kedalaman (depth) atau ketinggian (height) pada tree.
Tree bisa didefinisikan sebagai suatu kumpulan elemen yang salah satu elemennya disebut dengan akar (root), dan sisa elemen lainnya (yang disebut simpul) terpecah menjadi sejumlah himpunan yang paling tidak berhubungan satu sama lain, yang disebut dengan subpohon (subtree), atau disebut juga cabang. Jika kita melihat pada subpohon, maka subpohon inipun juga mempunyai akar dan sub-subpohonnya masing-masing.
Dalam kehidupan sehari-hari, tree dapat dilihat dari pohon silsilah keluarga. Tingkat yang tertinggi disebut juga sebagai root. Untuk lebih jelasnya lihat gambar di bawah ini  merupakan contoh dari sebuah tree.

Di dalam sebuah tree dikenal istilah Tingkat atau level. Tingkat (level) suatu simpul ditentukan dengan pertama kali menentukan akar sebagai bertingkat 0. jika suatu simpul dinyatakan sebagai tingkat N, maka simpul-simpul yang merupakan anaknya dikatakan berada dalam tingkat N+1. pada pohon dibawah merupakan tree dengan 4 level.
Tinggi (Height) atau Kedalaman (Depth) dari suatu pohon adalah tingkat(level) maksimum dari suatu pohon dikurangi dengan satu. Dengan demikian pohon diatas mempunyai tinggi atau kedalaman sama dengan 4.






Pohon Biner (Binary Tree)
Pohon biner bisa didefinisikan sebagai suatu kumpulan simpul yang mungkin kosong atau mempunyai akar dan dua subpohon yang saling terpisah yang disebut dengan subpohon kiri dan sub pohon kanan. Subpohon disebut juga sebagai cabang. Karakteristik dari pohon biner ialah bahwa setiap simpul paling banyak hanya mempunyai dua buah anak. Dengan kata lain derajat tertinggi dari sebuah pohon biner adalah dua.
Pengertian daun, root, level, tinggi dan derajad yang berlaku pada pohon juga berlaku pada binary tree. Penyajian binary tree pada komputer di gunakan double link list.
Deklarasi mencari kedalaman atau ketinggian dari suatu tree
int height(Tree *root)
{
 if (root == NULL) return -1;
 int u = height(root->left), v = height(root->right);
 if (u > v)
return u+1;
 else
return v+1;
}
Algoritma pada penghitungan kedalaman dimulai dari menghitung setelah root, yang dimulai dari subtree bagian kiri kemudian ke subtree bagian kanan.  Untuk masing-masing kedalaman kiri dan kanan akan dibandingkan, jika ternyata subtree kiri lebih dalam, maka yang dipakai adalah jumlah kedalaman subtree kiri, demikian sebaliknya.  Hal ini didasarkan pada prinsip binary tree, dimana tree-nya selalu memiliki maksimal 2 node anak.

contoh codingnya :





 

#include <iostream.h>
#include <conio.h>
#include <stdio.h>



struct tree_node     //deklarasi variabel
{                    //menggunakan double linked list
    int data;
    tree_node* left;
    tree_node* right;
};


tree_node* root;


bool isEmpty()
{return root==NULL;}


void insert(int d) //untuk memasukkan data
{
    tree_node* t = new tree_node;
    tree_node* parent;

    t->data = d; //data masukan
    t->left = NULL;//cabang kiri
    t->right = NULL;//cabang kanan

    parent = NULL;

    if(isEmpty())root = t; //jika belum ada data yg dimasukkan

   else  //jika sudah ada data yang masuk
        {
            tree_node* curr;
            curr = root;

            while(curr!=NULL)
                {
                    parent = curr;
               if(t->data == curr->data) { printf("DATA ALREADY EXIST !"); break;  }
                    else if(t->data > curr->data) {curr = curr->right;}
                    else if(t->data < curr->data) {curr = curr->left;}


            }
         //meletakkan posisi anak
            if(t->data < parent->data) parent->left = t;
         else if(t->data > parent->data) parent->right = t;
         else if(t->data == parent->data) parent->left = parent->right = NULL;
        }
}




void inorder(tree_node* p) //menampilkan data dengan kunjungan secara inorder
{
    if(p!=NULL)
        {
            if(p->left) inorder(p->left);

            cout<<" "<<p->data<<" ";

            if(p->right)inorder(p->right);
        }
    else return;
}





void print_inorder() //menampilkan inorder
{
    inorder(root);
}


void print(struct tree_node* p, int x, int y, int j)
{
if(p == NULL) return;
gotoxy(x,y);
printf("%d", p->data);
print(p -> left, x-j, y+2, j/2);
print(p -> right, x+j, y+2, j/2);
getch();
}


int height(tree_node* p) //fungsi height untuk menghitung kedalaman tree
{
    if(p==NULL)return -1;
    else {
               int l = height(p->left) ;
                int r = height(p->right);
                if (l > r) {return l+1;}
                else {return r+1;}
        }
getch();
}


void print_height() //menampilkan kedalaman dari tree
{
    height(root);
}





int main()
{
    root=NULL;
    int a,data;


    while(1)
        {
         clrscr();
            cout<<endl;

         cout<<"\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n";
         cout<<"===============================================================================\n";
         cout<<"\t\t\t\tPROGRAMMER BY :\n";
         printf("\t\t"); textcolor(17); cprintf("1. Ulva S. Nurmayani"); textcolor(7);
         printf("\t\t"); textcolor(26); cprintf("081012015"); textcolor(7);                                                                      
         printf("\n\t\t"); textcolor(37); cprintf("2. Etik Ulfianita");  textcolor(7);
         printf("\t\t"); textcolor(27);   cprintf("081012016"); textcolor(7);
            printf("\n\t\t"); textcolor(13); cprintf("3. Madya Vica A.");  textcolor(7);
         printf("\t\t"); textcolor(14);   cprintf("081012025"); textcolor(7);
            printf("\n\t\t"); textcolor(495); cprintf("4. Candra Arga M.");  textcolor(7);
         printf("\t\t"); textcolor(396);   cprintf("081012063"); textcolor(7);
         printf("\n\t\t"); textcolor(395); cprintf("5. Nuri Fashichah");  textcolor(7);
         printf("\t\t"); textcolor(300);   cprintf("081012066"); textcolor(7);

            cout<<"\n===============================================================================\n\n\n";
         cout<<"\n\t\t\a1----INSERT A NODE IN A BINARY TREE.";
            cout<<"\n\t\t\a2----IN-ORDER TRAVERSAL.";
            cout<<"\n\t\t\a3----HEIGHT OF TREE.";
            cout<<"\n\t\t\a4----EXIT.";
            cout<<"\n\n\t\t\aENTER CHOICE::";
            cin>>a;
         print(root, 40, 2, 20);
         cout<<endl;

         switch(a)
                {

                    case 1 : gotoxy(37,39);
               printf("\n\tENTER THE ELEMENT : ");
                    scanf("%d",&data);
                    insert(data);
               print(root, 40, 2, 20);
                    break;

               case 2 : gotoxy(37,39);
               cout<<endl;
               cout<<"\n\t****IN-ORDER TRAVERSAL OF A TREE****"<<endl;
                    cout<<"\t------------------------------------"<<endl;
                    print_inorder();
               getch();
                    break;

               case 3 : gotoxy(37,39);
               cout<<"\n\tHEIGHT OF A TREE"<<endl;
                    cout<<"\t-----------------"<<endl;
                    cout<<height(root);
               getch();
                    break;

                    case 4 : cout<<"\n\n\n\t\t\tTHANKS";
               return 0;
                    break;

               default: gotoxy(37,39);
               cout<<"INVALID INPUT"<<endl;
                    getch();
                    break;
                }
        }
}

Rabu, 17 Oktober 2012

HEURISTIC SEARCH TECHNIQUES : PROBLEM REDUCTION

Problem Reduction
Problem reduction atau yang biasa dikenal dengan constraint, intinya adalah berusaha mengurangi masalah dengan harapan masalah yang bersangkutan menjadi lebih mudah diselesaikan. Sekarang ini sudah diketahui teknik konsistensi ini sangat penting dalam penyelesaian constraint satisfactionproblem yang sangat berat sehingga semua aplikasi komersial penyelesaian constraint satisfactionproblem menggunakan teknik konsistensi ini sebagai langkah dasar. Sejarah konsistensi constraint dapat ditlusuri dari peningkatan efisiensi program pengenalan gambar oleh peneliti di intelejensi semu. Pegenalan gambar melibatkan pemberian label kepada semua garis pada gambar dengan cara yang konsisten. Jumlah kombinasi pemberian label pada garis yang memungkinkan dapat menjadi sangat besar, sementara hanya sedikit yang konsisten pada tahap awal. Dengan demikian memperpendek pencarian untuk pembeian nilai yang konsisten.Untuk mengilustrasikan teknik konsistensi ini akan diberikan sebuah contoh constraint satisfaction problem yang sangat sederhana.

Anggap A < B adalah constraint antara variabel A dengan domainDA = { 3..7} dan variabel B dengan domain DB = { 1..5}. dengan jelas tampak bahwa bahwa untuk sebagian nilai pada DA tidak ada nilai yang konsisten di DB yang memenuhi constraint A < B dan sebaliknya. Niai yang demikian dapat dibuang dari domain yang berkaitan tanpa kehilangan solusi apapun. Reduksi itu aman. Didapatkan domain yang tereduksi DA = {3,4} dan DB = {4,5}.
Perhatikan bahwa reduksi ini tidak membuang semua pasangan yang tidak konsisten. Sebagai contoh kumpulan label (<A, 4>, <B, 4>) masihh dapat dihasilkan dari domain, tetapi untuk setiap nilai A dari DA adalah mungkin untuk mencari nilai B yang konsisten dan sebaliknya.
Walaupun teknik konsistensi ini jarang digunakan sendirian untuk menghasilkan solusi, teknik konsistensi ini membantu menyelesaikan constraint satisfactionproblem dalam beberapa cara. Teknik konsistensi ini dapat dipakai sebelum pencarian maupun pada saat pencarian.
Constraint sering direpresentasikan dengan gambar graf (gambar 1) di mana setiap verteks mewakili variabel dan busur antar verteks mewakili constraint binari yang mengikat variabel-variabel yan dihubungkan dengan busur tersebut. Constraint unari diwakilkan dengan busur melingkar.

Kebanyakan solusi menggunakan pohonOR,dimana lintasan dari awal sampai tujuan tidak terletak pada satu cabang. Bila lintasan dari keadaan awal sampai tujuan dapat terletak pada satu cabang, maka kita akan dapat menemukan tujuan lebih cepat.

Graf AND-OR

Pada dasarnya sama dengan algoritma Best First Search, dengan mempertimbangkan adanya arc AND. Gambar berikut menunjukkan bahwa untuk mendapatkan TV orang bisa dengan cara singkat yaitu mencuri atau membeli asal mempunyai uang.Untuk mendeskripsikan algoritma, digunakan nilai F_UTILITY untuk biaya solusi.

 
Untuk mendeskripsikan algoritma Graph AND-OR kita menggunakan nilai F_UTILITY, yaitu biaya solusi.
Algoritma:
1.    Inisialisasi graph ke node awal.
2.    Kerjakan langkah-langkah di bawah ini hingga node awal SOLVED atau sampai biayanya lebih tinggi dari F_UTILITY:
(a.)      Telusuri graph, mualai dari node awal dan ikuti jalur terbaik. Akumulasikan kumpulan node yang ada pada lintasan tersebut dan belum pernah diekspansi atau diberi label SOLVED.
(b.)      Ambil satu node dan ekspansi node tersebut. Jika tidak ada successor, maka set F_UTILITY sebagai nilai dari node tersebut. Bila tidak demikian, tambahkan successor-successor dari node tersebut ke graph dan hitung nilai setiap f’ (hanya gunakan h’ dan abaikan g). Jika f’ = 0, tandai node tersebut dengan SOLVED.
(c.)      Ubah f’ harapan dari node baru yang diekspansi. Kirimkan perubahan ini secara backward sepanjang graph. Jika node berisi suatu arc suatu successor yang semua descendant-nya berlabel SOLVED maka tandai node itu dengan SOLVED.
Pada Gambar 2.33, pada langkah-1 semula hanya ada satu node yaitu A. Node A diekspansi hasilnya adalah node B, C, dan D.  Node D memiliki biaya yang lebih rendah (6) jika dibandingkan dengan B dan C (9). Pada langkah-2 node D terpilih untuk diekspansi, menjadi E dan F dengan biaya estimasi sebesar 10. Sehingga kita harus memperbaiki nilai f’ dari D menjadi 10. Kembali ke level sebelumnya, node B dan C memiliki biaya yang lebih rendah daripada D (9 < 10). Pada langkah-3, kita menelusuri arc dari node A, ke B dan C bersama-sama. Jika B dieksplore terlebih dahulu, maka akan menurunkan node G dan H. Kita perbaiki nilai f’ dari B menjadi 6 (nilai G=6 lebih baik daripada H=8), sehingga biaya AND-arc B-C menjadi 12 (6+4+2). Dengan demikian nilai node D kembali menjadi lebih baik (10 < 12). Sehingga ekspansi dilakukan kembali terhadap D. Demikian seterusnya.

 

Algoritma AO* menggunakan struktur Graph. Tiap-tiap node pada graph tersebut akan memiliki nilai h’ yang merupakan biaya estimasi jalur dari node itu sendiri sampai suatu solusi.
Algoritma
1.    Diketahui GRAPH yang hanya berisi  node awal (sebut saja node INIT). Hitung h’(INIT).
2.    Kerjakan langkah-langkah di bawah ini hingga INI bertanda SOLVED atau samoai nilai h’(INIT) menjadi lebih besar daripada FUTILITY:
(a)     Ekspand INIT dan ambil salah satu node yang belum pernah diekspand (sebut NODE).
(b)     Bangkitkan successor-successor NODE. Jika tida memiliki successor maka set FUTULITY dengan nilai h’(NODE). Jika ada successor, maka untuk setiap successor (sebut sebagai SUCC) yang bukan merupakan ancestor dari NODE, kerjakan:
                            i      Tambahkan SUCC ke graph.
                           ii      Jika SUCC adalah terminal node, tandai dengan SOLVED dan set nilai h’-nya sama dengan 0.
                          iii      Jika SUCC bukan terminal node, hitung nilai h’.
(c)     Kirimkan informasi baru tersebut ke graph, dengan cara: tetapkan S adalah node yang ditandai dengan SOLVED atau node yang nilai h’-nya baru saja diperbaiki, dan sampaikan nilai ini ke parent-nya. Inisialisasi S = NODE. Kerjakan langkah-langkah berikut ini hingga S kosong:
                            i      Jika mungkin, seleksi dari S suatu node yang tidak memiliki descendant dalam GRAPH yang terjadi pada S. Jika tidak ada, seleksi sebarang node dari S (sebut: CURRENT) dan hapus dari S.
                           ii      Hitung biaya tiap-tiap arc yang muncul dari CURRENT. Biaya tiap-tiap arc ini sama dengan jumlah h’ untuk tiap-tiap node pada akhir arc ditambah dengan biaya arc itu sendiri. Set h’(CURRENT) dengan biaya minimum yang baru saja dihitung dari stiap arc yang muncul tadi.
                          iii      Tandai jalur terbaik yang keluar dari CURRENT dengan menandai arc yang memiliki biaya minimum.
                         iv      Tandai CURRENT dengan SOLVED jika semua node yang dihubungkan dengannya hingga arc yang baru saja ditandai tadi telah ditandai dengan SOLVED.
                          v      Jika CURRENT telah ditandai dengan SOLVED atau jika biaya CURRENT telah berubah, maka status baru ini harus disampaikan ke GRAPH. Kemudian tambahkan semua ancestor dari CURRENT ke S.






Sebagai contoh, pada Gambar 2.34 Jelas bahwa jalur melalui C selalu lebih baik daripada melalui B. Tetapi jika biaya node E muncul, dan pengaruh perubahan yang diberikan ke node B tidak sebesar pengaruhnya terhadap node C, maka jalur melalui B bisa jadi lebih baik. Sebagai contoh, hasil expand node E, misalkan 10, maka biaya node C menjadi 11 (10+1), dengan demikian biaya node A apabila memilih jalur lewat C adalah 12 (11+1). Tentu saja akan lebih baik memilih jalur melalui node B (11). Tapi tidak demikian halnya apabila kemudian node D diekspan. Bisa jadi jalur dengan melalui node B akan lebih buruk lagi ketimbang jalur dengan melalui node C.


Sumber : 
Tsang, Edward.1993. Foundations of Constraint Satisfaction. Academic PressLimited. USA : Sandiego