antstrip.txt

多年前俺帮朋友编的一个蚂蚁算法。里面有不少冗余的地方

import java.io.*;

public class AntsTrip {
    
    public static void main(String[] args) {        
       boolean r0,r1,r2;
       int m = 0 ,n = 0;//m个城市,n个蚂蚁
       int city_map[][];//城市距离取1到21之间的数
       float  tl[][];//信息素初始值为城市路线个数的倒数
       int ants_trip[][];//所有蚂蚁行走路线
       int min_count;//当前最短路径长
       int ant_count[];//记录当前路径长
       int min_trip[];//当前最短路径的路线
       int walk_num;//记录当前步数
       float proba[];//用于暂时存放概率
       float probb[];//用于计算概率使用
       float count_proba ;//用于计算概率使用
       float prob;//用于产生随机概率
       int now_city ;//蚂蚁当前所在城市    
       int next_city;//暂时记录下一个城市
       
       r0=true;    
       while(r0){
           r0=false;
           try{
               BufferedReader in = new BufferedReader(
                   new InputStreamReader(System.in));
               System.out.print("请输入城市的个数(整数):");
                String num_m =  in.readLine();
                System.out.print("请输入蚂蚁个数(整数):");
               String num_n =     in.readLine();                  
               m = Integer.parseInt( num_m );
              n = Integer.parseInt( num_n );                  
              if(m <= 0 && n <= 0){
                  System.out.print("输入错误请从新输入!\n");
                  r0 = true;
              }
           }catch(NumberFormatException e1){
               System.out.print("输入错误请从新输入!\n");
               r0 = true;
           }catch(IOException e2){
               System.out.print("输入错误请从新输入!\n");
               r0 = true; 
            }
       }//结束while(r0)得到城市的个数n 和蚂蚁的个数m
       
        // TODO Auto-generated method stub        
        city_map = new int[m][m];
        tl = new float[m][m];
        min_trip = new int[m];
        ants_trip = new int[m][n];
        min_count=21*m;//因为城市之间有m个路段,每段最大取21
        proba = new float[m];
        probb = new float[m];
        ant_count = new int[n];
        
        System.out.print("产生的随机地图为:\n");
        for(int i=0; i<city_map.length; i++){
            for(int j=0; j<city_map.length; j++){
                if(i!=j){
                    city_map[j] = (int)(Math.random()*20)+1;//初始化城市
                    tl[j] = (float)1.0/m*(m-1);//初始化信息素
                    System.out.print("  c_map[" + i + "][" + j + "]" +"="+ city_map[j]);                    
                }
            }
            System.out.print("\n");
        }
        walk_num = 0;
        int marks0 = 0;//标记总循环次数
        boolean marks1;//标记是否都走同一路径
        r2=true;
        while(r2){//总循环－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－步骤３
            marks0++;
            marks1 = true;
            for(int i=0; i<ants_trip.length; i++){//清空ants_trip
                for(int j=0; j<ants_trip[0].length; j++){
                    ants_trip[j] = 0;
                }
            }
            
            for(int j=0; j<ants_trip[0].length; j++){//把n只蚂蚁(行)放入m个城市(列)中
                int k;
                k = (int)(Math.random()*m);
                ants_trip[k][j]=1;
            }
            
            for(int j=0; j<ants_trip[0].length;j++){//蚂蚁循环 -----------------------------步骤1
                int k1=0;
                now_city = 0;
                ant_count[j] = 0;
                for(int i=0; i<ants_trip.length; i++){//找到蚂蚁的出发城市
                    if(ants_trip[j] == 1){
                        k1 = i;
                        now_city = i;
                        walk_num = 1;
                        break;
                    }                    
                }
                r1 = true;
                while( r1 ){//用于处理单只蚂蚁j
                    r1 = false;
                    count_proba = 0;
                    prob = 0;                    
                    for(int i=0; i<proba.length; i++){
                        proba=0;//将概率暂存表清空
                        probb=0;
                    }
                    
                    for(int i=0; i<ants_trip.length; i++){//计算由now_city到其他城市的概率
                        if(ants_trip[j]==0){
                            proba=(float)(tl[now_city]*(1.0/city_map[now_city]))*100000;
                        }
                    }
                                       
                    for(int i=0,k=0; i<proba.length; i++){//将概率处理为线段
                        if(proba != 0){
                            count_proba += proba;
                            probb[k] = count_proba;                                 
                            k++;                            
                        }
                    }
                    next_city = 0;
                    prob = (float)Math.random()*count_proba;//产生随机概率                    
                    
                    for(int i=0,l=0; i<probb.length; i++){//判断落入区间
                        if(prob < probb){
                            
                            for(int k=0; k<proba.length; k++)
                            {
                                if(proba[k]!=0){
                                    l++;
                                }
                                if(l==i+1){
                                    next_city = k;//得到了下一个城市
                                    break;
                                }
                            }
                            break;
                        }
                    }//结束了对落入范围的判断，获得了下一个城市
                    ant_count[j] +=city_map[now_city][next_city];                        
                    now_city = next_city;                
                    walk_num++;
                    ants_trip[now_city][j] = walk_num;
                    
                    int k3,k4;//                    判断蚂蚁j是否走完所有城市
                    k3 = 0; k4 = 0;
                    for(int i=0; i<ants_trip.length; i++){
                        if(ants_trip[j]==0){
                            k3++;k4=i;
                        }
                    }
                    if(k3>1){
                        r1=true;
                    }else{
                        ants_trip[k4][j]=m;
                        ant_count[j] += city_map[now_city][k4];
                        ant_count[j] += city_map[k4][k1];//由最后一个城市回到出发城市
                        now_city = k4;
                        System.out.print("\n  蚂蚁" + j + "走完全程,总路程为" + ant_count[j]);
                    }                                       
               }//结束了while语句，即一只蚂蚁j已经走完所有城市    
                
                /*int k6 = 1;
               while(k6 <= m){
                   for(int i=0; i<ants_trip.length; i++){
                       if(ants_trip[j]==k6){
                           System.out.print("  "+i);
                       }
                   }
                   k6++;
               }*/
               if(ant_count[j] < min_count){
                for(int i=0; i<ants_trip.length; i++){
                    min_trip=ants_trip[j];                            
                }
                min_count = ant_count[j];
               }
               System.out.print("\n  当前最短路程长为"+ min_count);                        
            } ////////////////////////所有蚂蚁都走过了            
            System.out.print("\n所有蚂蚁都走完所有城市!");
            
            for(int i=0; i<tl.length; i++){//－－－－－－－－－－－－－－－－步骤２
                for(int j=0; j<tl[0].length; j++){
                    tl[j] /=4;
                }
            }
            for(int j=0; j<ants_trip[0].length; j++){
                for(int i=0; i<tl.length; i++){
                    for(int k=0; k<ants_trip.length; k++){
                        if((ants_trip[j]-1)==ants_trip[k][j]%m){
                            tl[k] +=(float) 3.0/(8*ant_count[j]);
                               if((min_trip-1)==min_trip[k]%m){
                                         tl[k] +=(float) 3.0/(8*min_count);                          
                                       }                          
                        
                        }
                    }
                }
            }
            for(int j=0,k=0; j<ants_trip[0].length; j++){//判断所有蚂蚁是否都走同一路线
                for(int i=0; i<ants_trip.length; i++){                    
                    k=ants_trip[0][j]-min_trip[0];
                    if((ants_trip[j]-k-1+m)%m != (min_trip-1)){
                        marks1 = false;
                        j = ants_trip[0].length;
                        break;
                    }
                }
            }
            if(marks1 || marks0 > 100){//循环次数最高为100次
                if(marks1){
                    System.out.print("\n\n\n成功查寻到最短路!!");
                }
                else{
                    System.out.print("\n\n\n循环到次数了!");
                }
                r2=false;
                }
        }//结束总while        
        System.out.print("\n当前路线为：");
        int k5 = 1;
        while(k5 <= m){
           for(int i=0; i<min_trip.length; i++){
               if(min_trip==k5){
                   System.out.print(i+"  ");
               }
           }
           k5++;
       }
            
        System.out.print("\n总路程为：" + min_count);    
        System.exit(0);
    }//结束main
}