Showing posts with label Branchbound. Show all posts
Showing posts with label Branchbound. Show all posts

Wednesday, May 16, 2012

Branch and Bound TSP java

Branch and Bound implementation TSP for Java
copy this code in the same folder or if take software like eclipse, netbeans ect. take in the same package.


Matrik.java
package branchandbound;/**
 *
 * @Rezaakhmadg
 */
public class Matrik {
int graph[][]=new int['H']['H'];
    Matrik(){
        graph['A']['A']=0;graph['A']['B']=75;graph['A']['C']=60;graph['A']['D']=50;graph['A']['E']=215;graph['A']['F']=130;graph['A']['G']=95;
        graph['B']['A']=60;graph['B']['B']=0;graph['B']['C']=60;graph['B']['D']=70;graph['B']['E']=85;graph['B']['F']=50;graph['B']['G']=135;

        graph['C']['A']=40;graph['C']['B']=55;graph['C']['C']=0;graph['C']['D']=130;graph['C']['E']=95;graph['C']['F']=100;graph['C']['G']=55;
        graph['D']['A']=40;graph['D']['B']=75;graph['D']['C']=140;graph['D']['D']=0;graph['D']['E']=45;graph['D']['F']=60;graph['D']['G']=135;
        graph['E']['A']=20;graph['E']['B']=85;graph['E']['C']=100;graph['E']['D']=40;graph['E']['E']=0;graph['E']['F']=90;graph['E']['G']=95;
        graph['F']['A']=120;graph['F']['B']=55;graph['F']['C']=110;graph['F']['D']=60;graph['F']['E']=95;graph['F']['F']=0;graph['F']['G']=65;
        graph['G']['A']=80;graph['G']['B']=135;graph['G']['C']=60;graph['G']['D']=130;graph['G']['E']=95;graph['G']['F']=60;graph['G']['G']=0;
    }

}


Matrikint.java
package branchandbound;
/**
 *
 * @Rezaakhmadg
 */
public class Matrikint {
int graphI[][]=new int[8][8];
    Matrikint(){
            graphI[1][1]=0;graphI[1][2]=75;graphI[1][3]=60;graphI[1][4]=50;graphI[1][5]=215;graphI[1][6]=130;graphI[1][7]=95;
            graphI[2][1]=60;graphI[2][2]=0;graphI[2][3]=60;graphI[2][4]=70;graphI[2][5]=85;graphI[2][6]=50;graphI[2][7]=135;
            graphI[3][1]=40;graphI[3][2]=55;graphI[3][3]=0;graphI[3][4]=130;graphI[3][5]=95;graphI[3][6]=100;graphI[3][7]=55;
            graphI[4][1]=40;graphI[4][2]=75;graphI[4][3]=140;graphI[4][4]=0;graphI[4][5]=45;graphI[4][6]=60;graphI[4][7]=135;
            graphI[5][1]=20;graphI[5][2]=85;graphI[5][3]=100;graphI[5][4]=40;graphI[5][5]=0;graphI[5][6]=90;graphI[5][7]=95;
            graphI[6][1]=120;graphI[6][2]=55;graphI[6][3]=110;graphI[6][4]=60;graphI[6][5]=95;graphI[6][6]=0;graphI[6][7]=65;
            graphI[7][1]=80;graphI[7][2]=135;graphI[7][3]=60;graphI[7][4]=130;graphI[7][5]=95;graphI[7][6]=60;graphI[7][7]=0;
    }

}


bb.java
package branchandbound;

/**
 *
 * @Rezaakhmadg
 */
public class bb {
        char hasil[];
        int idx;
}


branchbound.java
package branchandbound;
/**
 *
 * @Rezaakhmad
 */
public class branchbound {
    bb br[]= new bb[10];
    Matrik S=new Matrik();
    Matrikint Mat=new Matrikint();
    public float bound;
    public float cekbound;
    public char getMinNode(char n){
    char k='A';
    int l=999;
    for (char i='A';i<'H';i++) {
        if (S.graph[n][i]<l&&i!='A'&&S.graph[n][i]!=0){
            k=i;
            l=S.graph[n][i];
        }
    }
    return (k);
}
     public int isZero(){
        int x=1;
        for (char i='A';i<'H';i++){
            for (char j='A';j<'H';j++){
                if (S.graph[i][j]!=0) x=0;
            }
        }
        return x;
    }

     public void empty (char a,char b){
    if (a=='A'||b=='A'){
        S.graph[a][b]=0;
        S.graph[b][a]=0;
    }else{
    for (char i='A';i<'H';i++){
        if (a!='A'){
        S.graph[a][i]=0;
        S.graph[i][a]=0;
        }
        }

    }
    }

    public bb Solusi(){
    bb Brn=new bb();
    Brn.idx=0;
    Brn.hasil=new char[100];
    char p='A';
    char temp;
    Brn.hasil[Brn.idx]=p;
    Brn.idx++;
    int ketemu=0;
    while (ketemu==0){
        temp=getMinNode(p);
        Brn.hasil[Brn.idx]=temp;
        Brn.idx++;
        empty(p,temp);
        p=temp;
        if (isZero()==1){
            ketemu=1;
        }
    }
    Brn.hasil[Brn.idx]='A';
    Brn.idx++;
    return Brn;
}
    public int minDouble(char p,char c){
    int min1=999;
    int min2=999;
    int hasil=0;
    for (char i='A';i<'H';i++){
        if (i!=p&&i!=c){
            for (char j='A';j<'H';j++){
                if (S.graph[i][j]<min1&&S.graph[i][j]!=0) {
                    min2=min1;
                    min1=S.graph[i][j];
                }else if(S.graph[i][j]<min2&&S.graph[i][j]!=0){
                    min2=S.graph[i][j];
                }
            }
            if (min1==999) min1=0;
            if (min2==999) min2=0;
            hasil+=min1+min2;
            min1=999;min2=999;

        }
        }

    return hasil;
}
    public int minSingle(char p,char c){
    int min1=999;
    int min2=999;
    int hasil=S.graph[p][c]+S.graph[c][p];
        for (char i='A';i<'H';i++){
            if (S.graph[p][i]<min1&&S.graph[p][i]!=0&&i!=c) {
                min1=S.graph[p][i];
            }
            if (S.graph[c][i]<min2&&S.graph[c][i]!=0&&i!=p) {
                min2=S.graph[c][i];
            }
        }
    if (min1==999) min1=0;
    if (min2==999) min2=0;
    hasil+=min1+min2;
    return hasil;
}

    public float getBound(char p,char c){
      
    bound = ((minSingle(p,c))+(minDouble(p,c))/2);
    return bound;
}

    public void cetakSolusi(char c[],int n){
    int i=1,j=1;
    String d="A ";
    int h=0;
    int temp1=1;
    int temp2=0;
//    for (i=1;i<n;i++) {
//         System.out.print("Solusi Indeks : " +i+ "\n");
//         System.out.print("Solusi Kota   : " +c[i]+ " \n");
//       
//     }
//
// i=1;
        while (i<n){
            if (c[i]=='A' && i==n-1) break;
          
            d+=c[i]+ " ";
          
            switch (c[i]) {
            case 'A': temp2 = 1;
                     break;
            case 'B': temp2 = 2;
                     break;
            case 'C': temp2 = 3;
                     break;
            case 'D': temp2 = 4;
                     break;
            case 'E': temp2 = 5;
                     break;
            case 'F': temp2 = 6;
                     break;
            case 'G': temp2 = 7;
                     break;
            }
            System.out.print("isi  : " + temp1 + " " +temp2 + " " + c[i] + " \n");
            h+=Mat.graphI[temp1][temp2];
          
            switch (c[i]) {
            case 'A': temp1 = 1;
                     break;
            case 'B': temp1 = 2;
                     break;
            case 'C': temp1 = 3;
                     break;
            case 'D': temp1 = 4;
                     break;
            case 'E': temp1 = 5;
                     break;
            case 'F': temp1 = 6;
                     break;
            case 'G': temp1 = 7;
                     break;
            }
            i++;
          
          
              }
      
        System.out.print("Solusi : " + d + "total waktu yang dibutuhkan " + h + " \n");

    }
 
   public void branchNbound(){
    int idx=1;
    float cek=999;
    char p='A';
    char min;
    char c[];
   c=new char[20];
   float b[];
   b=new float[10];

    c[0]='A';
    while(isZero()==0){
        min='A';
        for(char i='A';i<'H';i++){
            if(i!='H'&&S.graph[p][i]!=0){
            b[i]=getBound(p,i);
            if (b[i]<cek){
                cek=b[i];
                min=i;
            }
            }
        }
        cek=999;
                c[idx]=min;
                idx++;

        empty(p,min);
        for(char i='A';i<'H';i++){
            b[i]=0;
        }
        p=min;
    }

    cetakSolusi(c,idx);
}
}



Main.java
package branchandbound;

/**
 *
 * @Rezaakhmadg
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Matrik BF =new Matrik();

        for (char x='A';x<'H';x++){
            for (char y='A';y<'H';y++){
                System.out.print(BF.graph[x][y]+" ");
            }
            System.out.println('\n');
        }

        branchbound b = new branchbound();
        bb keluaran = new bb();
//        b.branchNbound();
        keluaran = b.Solusi();
        System.out.print("Solusi studi kasus dengan algoritma Branch and Bound : \n");
        System.out.print("****************************************************** \n");
        b.cetakSolusi(keluaran.hasil, keluaran.idx);
      
    }

}