Q&A
一番上にある関数ctotalCostが意図しない動作をしてしまい、やけに大きい値が出てきます。
巡回セールスマン問題で、山登り法をプログラムしようとしたのですが、totalCostの値が変で行き詰まってしまいました。
おかしな点があれば指摘お願いします。
c
1#include<stdio.h> 2#include<stdlib.h> 3#include<math.h> 4#include<time.h> 5#include "MT.c" 6#include "quicksort.c" 7 8//totalCost 9int totalCost(int *route,int DIM,int cost[DIM][DIM]){ 10 int i,total=0; 11 12 for(i=0;i<DIM;i++){ 13 total += cost[route[i]][route[(i+1)%DIM]]; 14 } 15 return total; 16} 17 18//randomswap 19swap(int *array,int index1,int index2){ 20 int tmp; 21 22 tmp=array[index1]; 23 array[index1]=array[index2]; 24 array[index2]=tmp; 25} 26 27//hillclimb 28void hillclimb(int DIM,int *route,int cost[DIM][DIM],int *x,int *y,FILE *fp){ 29 int currentIterations,randIndex1,randIndex2; 30 float currentTotalCost,newTotalCost; 31 char filename[30]; 32 int j,Iteration,Interval; 33 34 printf("Iteration:"); 35 scanf("%d",&Iteration); 36 printf("Interval:"); 37 scanf("%d",&Interval); 38 for(currentIterations=0;currentIterations<Iteration;currentIterations++){ 39 randIndex1=rand()%DIM; 40 randIndex2=rand()%DIM; 41 42 currentTotalCost = totalCost(route,DIM,cost); 43 swap(route,randIndex1,randIndex2); 44 45 newTotalCost = totalCost(route,DIM,cost); 46 47 if(newTotalCost>currentTotalCost){ 48 swap(route,randIndex1,randIndex2); 49 } 50 51 //ファイルへ出力 52 if( (currentIterations+1)%Interval==0){ 53 sprintf(filename,"hillclimb-%d.dat",currentIterations+1); 54 if( (fp = fopen(filename,"w"))==NULL ){ 55 printf("File Open Error: %s\n ",filename); 56 exit(1); 57 }else{ 58 for(j=0;j<DIM+1;j++){ 59 fprintf(fp,"%d %d\n",x[route[j%DIM]],y[route[j%DIM]]); 60 } 61 } 62 } 63 } 64} 65 66 67//RandomRoute生成 68int *randRoute(int DIM,int *route,int *x,int *y){ 69 int j,k; 70 double *rand; 71 72 rand = (double *)malloc(sizeof(double) * DIM); 73 74 for(k=0;k<DIM;k++){ 75 rand[k]=genrand(); 76 } 77 quicksort(route,rand,0,DIM-1); 78 79 return route; 80} 81 82//iteration&output 83void output(int DIM,int *x,int *y,int *ans){ 84 int i,j; 85 FILE *fp; 86 char filename[30]; 87 int iteration,interval; 88 printf("iteration:"); 89 scanf("%d",&iteration); 90 printf("interval:"); 91 scanf("%d",&interval); 92 93 for(i=0;i<iteration;i++){ 94 if( (i+1)%interval==0){ 95 sprintf(filename,"random-%d.dat",i+1); 96 if( (fp = fopen(filename,"w"))==NULL ){ 97 printf("File Open Error: %s\n ",filename); 98 exit(1); 99 }else{ 100 for(j=0;j<DIM;j++){ 101 fprintf(fp,"%d %d\n",x[ans[j]],y[ans[j]]); 102 } 103 104 } 105 } 106 } 107} 108 109int main(int argc,char *argv[]){ 110 int i,j,k,DIM; 111 FILE *fp; 112 char temp[100],n[100],c[100],t[100],e[100]; 113 114 if(argc !=2){ 115 printf("Usage: sample <input_filename>\n"); //引数が足りない時のエラー表示 116 exit(1); 117 } 118 119 if((fp=fopen(argv[1],"r"))==NULL){//引数で指定されたファイル読み込み 120 printf("file open error!\n"); 121 exit(1); 122 } 123 124 do{ 125 fscanf(fp,"%s",temp); 126 if(strcmp("NAME",temp)==0){//NAMEの項目を読み込むまで空読み 127 fscanf(fp,"%s",temp); 128 break; 129 } 130 if(strcmp("NAME:",temp)==0)break;//NAMEの後に：が入っている場合の対処 131 }while(1); 132 133 fscanf(fp,"%s",&n);//NAMEの読み込み 134 printf("%s\n",n); 135 136 do{ 137 fscanf(fp,"%s",temp); 138 if(strcmp("COMMENT",temp)==0){//COMMENTの項目を読み込むまで空読み 139 fscanf(fp,"%s",temp); 140 break; 141 } 142 if(strcmp("COMMENT:",temp)==0)break; 143 //COMMENTの後に：が入っている場合の対処 144 }while(1); 145 146 fscanf(fp,"%s %s %s",&c);//COMMENTの読み込み 147 printf("%s\n",c); 148 149 do{ 150 fscanf(fp,"%s",temp); 151 if(strcmp("TYPE",temp)==0){//TYPEの項目を読み込むまで空読み 152 fscanf(fp,"%s",temp); 153 break; 154 } 155 if(strcmp("TYPE:",temp)==0)break; 156 //TYPEの後に：が入っている場合の対処 157 }while(1); 158 159 fscanf(fp,"%s",&t);//TYPEの読み込み 160 printf("%s\n",t); 161 162 do{ 163 fscanf(fp,"%s",temp); 164 if(strcmp("DIMENSION",temp)==0){//DIMENSIONの項目を読み込むまで空読み 165 fscanf(fp,"%s",temp); 166 break; 167 } 168 if(strcmp("DIMENSION:",temp)==0)break; 169 //DIMENSIONの後に：が入っている場合の対処 170 }while(1); 171 172 fscanf(fp,"%d",&DIM);//次元（都市数）の読み込み 173 printf("%d\n",DIM); 174 175 do{ 176 fscanf(fp,"%s",temp); 177 if(strcmp("EDGE_WEIGHT_TYPE",temp)==0){//EDGE_WEIGHT_TYPEの項目を読み込むまで空読み 178 fscanf(fp,"%s",temp); 179 break; 180 } 181 if(strcmp("EDGE_WEIGHT_TYPE:",temp)==0)break; 182 //EDGE_WEIGHT_TYPEの後に：が入っている場合の対処 183 }while(1); 184 185 fscanf(fp,"%s",&e);//EDGE_WEIGHT_TYPEの読み込み 186 printf("%s\n",e); 187 188 do{ 189 fscanf(fp,"%s",temp); 190 if(strcmp("NODE_COORD_SECTION",temp)==0)//NODE_COORD_SECTIONの項目を読込むまで空読み 191 break; 192 }while(1); 193 194 int *route,*x,*y; 195 route = (int *)malloc(sizeof(int)*DIM); 196 x = (int *)malloc(sizeof(int)*DIM); 197 y = (int *)malloc(sizeof(int)*DIM); 198 199 for(i=0;i<DIM;i++){ 200 fscanf(fp,"%d %d %d",&route[i],&x[i],&y[i]); 201 //NODE_COORD_SECTIONの読み込み 202 } 203 for(i=0;i<DIM;i++){ 204 printf("%2d %2d %2d\n",route[i],x[i],y[i]); 205 } 206 207 //各都市間コスト計算 208 int cost[DIM][DIM]; 209 double a; 210 for(i=0;i<DIM;i++){ 211 for(j=0;j<DIM;j++){ 212 a=sqrt(((x[i]-x[j])*(x[i]-x[j]) 213 +(y[i]-y[j])*(y[i]-y[j]))); 214 cost[i][j]=round(a); 215 } 216 } 217for(i=0;i<DIM;i++){ 218 for(j=0;j<DIM;j++){ 219 // printf("%3d ",cost[i][j]); 220 } 221 //printf("\n"); 222 } 223 224 //ランダムなシード値獲得 225 srand((unsigned)time(NULL)); 226 227 printf("Simple route Total cost:%d\n",totalCost(route,DIM,cost)); 228 229 int *randroute; 230 randroute = (int *)malloc(sizeof(int)*DIM); 231 232 randroute = randRoute(DIM,route,x,y); 233 234 hillclimb(DIM,randroute,cost,x,y,fp); 235 236 printf("Hillclimb Total cost:%d\n",totalCost(route,DIM,cost)); 237 238 fclose(fp); 239} 240 241
quicksortは以下の通りです
c
1void quicksort(int list1[],double list2[], int left, int right) 2{ 3 int i, last; 4 double temp; 5 6 if (left >= right) 7 return; 8 9 last = left; 10 for (i=left+1; i <= right; i++){ 11 if (list2[i] < list2[left] ){ 12 last++; 13 temp=list2[last]; 14 list2[last]=list2[i]; 15 list2[i]=temp; 16 temp=list1[last]; 17 list1[last]=list1[i]; 18 list1[i]=temp; 19 } 20 } 21 22 temp=list2[left]; 23 list2[left]=list2[last]; 24 list2[last]=temp; 25 temp=list1[left]; 26 list1[left]=list1[last]; 27 list1[last]=temp; 28 29 quicksort(list1,list2,left, last-1); 30 quicksort(list1,list2,last+1, right); 31} 32
自己解決
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。