Informatics: TSP

Showing posts with label TSP. Show all posts

Sunday, May 20, 2012

how to use Java Applet in html

in this lesson i'd like to share about give an output from php to html..

in Swing, applet imlementation with Japplet, that inheritance from Applet class(Japplet) and has a Container , with method called getContentPane(), with a declaration
Container getContentPane()
next to add another components , we need method add(), with a declaration
void add(comp)

example:
Demo.java

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

public class DemoAppletSwing extends JApplet
implements ActionListener {

public JTextField textField;
public JButton button;

public void init() {

    // mendapatkan container
    Container cont = getContentPane();
    cont.setLayout(new FlowLayout());

    // menambahkan komponen JTextField
    textField = new JTextField(25);
    cont.add(textField, BorderLayout.CENTER);

    // menambahkan komponen JButton
    button = new JButton("Tombol Applet");
    button.addActionListener(this);
    cont.add(button, BorderLayout.CENTER);
}

// menangani event klik pada komponen JButton
public void actionPerformed(ActionEvent event) {
    if (event.getSource() == button) {
      textField.setText("Anda telah melakukan klik " +
        "pada tombol Applet");
    }
}
}

and with same directory
Test.html

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);

    }

}

Greedy TSP in Java

Greedy Implementation for TSP in java

Matrik.java

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

}

Greedy.java

package Greedy_TSP;

/**
*
* @Rezaakhmadg
*/
public class Greedy {
    Matrik M=new Matrik();
    int[][] hasil=new int[9][9];
    int[] solusi=new int[10];
//    char[] record=new char[100];

//    public char ruteKota() {
//
//}
    public Greedy(){

    }
    public void showHasil(){
    String temp="";
    int row=1;
    int col=1;
    int cc=0;
    int rr=0;
    int com=0;
    int cek=2;
    int jarak=0;
    int i=0;
    int j=0;
    int ce=0;
    solusi[1]=1;
    for (i=1;i<=8;i++) {
        for (j=1;j<=8;j++) {
            hasil[i][j]=1;
         }
    }

    while (cek<=8) {
        if (cek>7) break;
   com=1000;

         col=2;
         while (col<8) {
             if (col>7) break;
             ce=0;
             if (M.graph[row][col]<com && row!=col && hasil[row][col]==1) {
                        com=M.graph[row][col];
                        cc=col;
                        ce=1;

                }


             col++;


         }
//         System.out.print("Solusi hasil colom: " + cc + " com : " + com +" cek: "+ col + " row: " + row +" \n");
            jarak+=com;
             for (i=1;i<8;i++) {
                for (j=1;j<8;j++) {
                    if (j==cc) hasil[i][j]=0;
         }
    }

            solusi[cek]=cc;
            row=cc;
            cek++;

    }

           jarak+=M.graph[cc][1];
           solusi[cek]=1;


    for (i=1; i<cek; i++) {

             switch (solusi[i]) {
                    case 1: temp = temp+ "A ";
                             break;
                    case 2: temp = temp+ "B ";
                             break;
                    case 3: temp = temp+ "C ";
                             break;
                    case 4: temp = temp+ "D ";
                             break;
                    case 5: temp = temp+ "E ";
                             break;
                    case 6: temp = temp+ "F ";
                             break;
                    case 7: temp = temp+ "G ";
                             break;
                    }
                if (i==cek-1){
             System.out.print("Solusi : " + temp + "total waktu yang dibutuhkan " + jarak + " \n");
                }

    }


}


}

Main.java

package Greedy_TSP;

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

    /**
     * @param args the command line arguments
     */
        public static void main(String[] args) {
        // TODO code application logic here
//        Matrik baru =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');
//        }

        Greedy g = new Greedy();
//        bb keluaran = new bb();
//        keluaran = b.Solusi();
        System.out.print("Solusi studi kasus dengan algoritma Greedy : \n");
        System.out.print("****************************************************** \n");
        g.showHasil();

    }

}