質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.76%

  • C

    3464questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

巡回セールスマン問題 距離の計算がおかしい

解決済

回答 1

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 96

ike-0315

score 4

一番上にある関数ctotalCostが意図しない動作をしてしまい、やけに大きい値が出てきます。
巡回セールスマン問題で、山登り法をプログラムしようとしたのですが、totalCostの値が変で行き詰まってしまいました。
おかしな点があれば指摘お願いします。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#include "MT.c"
#include "quicksort.c"

//totalCost
int totalCost(int *route,int DIM,int cost[DIM][DIM]){
  int i,total=0;

  for(i=0;i<DIM;i++){
    total += cost[route[i]][route[(i+1)%DIM]];
  }
  return total;
}

//randomswap
swap(int *array,int  index1,int index2){
  int tmp;

  tmp=array[index1];
  array[index1]=array[index2];
  array[index2]=tmp;
}

//hillclimb
void hillclimb(int DIM,int *route,int cost[DIM][DIM],int *x,int *y,FILE *fp){
  int currentIterations,randIndex1,randIndex2;
  float currentTotalCost,newTotalCost;
  char filename[30];
  int j,Iteration,Interval;

  printf("Iteration:");
  scanf("%d",&Iteration);
  printf("Interval:");
  scanf("%d",&Interval);
  for(currentIterations=0;currentIterations<Iteration;currentIterations++){
    randIndex1=rand()%DIM;
    randIndex2=rand()%DIM;

    currentTotalCost = totalCost(route,DIM,cost);
    swap(route,randIndex1,randIndex2);

    newTotalCost = totalCost(route,DIM,cost);

    if(newTotalCost>currentTotalCost){      
      swap(route,randIndex1,randIndex2);
    }

    //ファイルへ出力   
    if( (currentIterations+1)%Interval==0){
      sprintf(filename,"hillclimb-%d.dat",currentIterations+1);
      if( (fp = fopen(filename,"w"))==NULL ){
    printf("File Open Error: %s\n ",filename);
    exit(1);
      }else{
    for(j=0;j<DIM+1;j++){
      fprintf(fp,"%d %d\n",x[route[j%DIM]],y[route[j%DIM]]);    
    }
      }
    }
  }
}


//RandomRoute生成 
int *randRoute(int DIM,int *route,int *x,int *y){
  int j,k;
  double *rand;

  rand = (double *)malloc(sizeof(double) * DIM);

  for(k=0;k<DIM;k++){
    rand[k]=genrand();
  }
  quicksort(route,rand,0,DIM-1);

  return route;
}

//iteration&output
void output(int DIM,int *x,int *y,int *ans){
  int i,j;
  FILE *fp;
  char filename[30];
  int iteration,interval;
  printf("iteration:");  
  scanf("%d",&iteration);
  printf("interval:");
  scanf("%d",&interval);

  for(i=0;i<iteration;i++){
    if( (i+1)%interval==0){
      sprintf(filename,"random-%d.dat",i+1);
      if( (fp = fopen(filename,"w"))==NULL ){
    printf("File Open Error: %s\n ",filename);
    exit(1);
      }else{
    for(j=0;j<DIM;j++){
      fprintf(fp,"%d %d\n",x[ans[j]],y[ans[j]]);
    }

      }
    }
  }
}

int main(int argc,char *argv[]){
  int i,j,k,DIM;
  FILE *fp;
  char temp[100],n[100],c[100],t[100],e[100];

  if(argc !=2){
    printf("Usage: sample <input_filename>\n"); //引数が足りない時のエラー表示
    exit(1);
  }

  if((fp=fopen(argv[1],"r"))==NULL){//引数で指定されたファイル読み込み
    printf("file open error!\n");
    exit(1);
  }

  do{
    fscanf(fp,"%s",temp);
    if(strcmp("NAME",temp)==0){//NAMEの項目を読み込むまで空読み
      fscanf(fp,"%s",temp);
      break;
    }
    if(strcmp("NAME:",temp)==0)break;//NAMEの後に:が入っている場合の対処      
  }while(1);

  fscanf(fp,"%s",&n);//NAMEの読み込み
  printf("%s\n",n);

  do{
    fscanf(fp,"%s",temp);
    if(strcmp("COMMENT",temp)==0){//COMMENTの項目を読み込むまで空読み
      fscanf(fp,"%s",temp);
      break;
    }
    if(strcmp("COMMENT:",temp)==0)break;
    //COMMENTの後に:が入っている場合の対処      
  }while(1);

  fscanf(fp,"%s %s %s",&c);//COMMENTの読み込み
  printf("%s\n",c);

  do{
    fscanf(fp,"%s",temp);
    if(strcmp("TYPE",temp)==0){//TYPEの項目を読み込むまで空読み
      fscanf(fp,"%s",temp);
      break;
    }
    if(strcmp("TYPE:",temp)==0)break;
    //TYPEの後に:が入っている場合の対処      
  }while(1);

  fscanf(fp,"%s",&t);//TYPEの読み込み
  printf("%s\n",t);

  do{
    fscanf(fp,"%s",temp);
    if(strcmp("DIMENSION",temp)==0){//DIMENSIONの項目を読み込むまで空読み
      fscanf(fp,"%s",temp);
      break;
    }
    if(strcmp("DIMENSION:",temp)==0)break;
    //DIMENSIONの後に:が入っている場合の対処      
  }while(1);

  fscanf(fp,"%d",&DIM);//次元(都市数)の読み込み
  printf("%d\n",DIM);

  do{
    fscanf(fp,"%s",temp);
    if(strcmp("EDGE_WEIGHT_TYPE",temp)==0){//EDGE_WEIGHT_TYPEの項目を読み込むまで空読み
      fscanf(fp,"%s",temp);
      break;
    }
    if(strcmp("EDGE_WEIGHT_TYPE:",temp)==0)break;
    //EDGE_WEIGHT_TYPEの後に:が入っている場合の対処      
  }while(1);

  fscanf(fp,"%s",&e);//EDGE_WEIGHT_TYPEの読み込み
  printf("%s\n",e);

  do{
    fscanf(fp,"%s",temp);
    if(strcmp("NODE_COORD_SECTION",temp)==0)//NODE_COORD_SECTIONの項目を読込むまで空読み
      break;
  }while(1);

  int *route,*x,*y;
  route = (int *)malloc(sizeof(int)*DIM);
  x = (int *)malloc(sizeof(int)*DIM);
  y = (int *)malloc(sizeof(int)*DIM);

  for(i=0;i<DIM;i++){
    fscanf(fp,"%d %d %d",&route[i],&x[i],&y[i]);
    //NODE_COORD_SECTIONの読み込み
  }      
  for(i=0;i<DIM;i++){
    printf("%2d %2d %2d\n",route[i],x[i],y[i]);
  }

  //各都市間コスト計算
  int cost[DIM][DIM];
  double a;
  for(i=0;i<DIM;i++){
    for(j=0;j<DIM;j++){
      a=sqrt(((x[i]-x[j])*(x[i]-x[j])
          +(y[i]-y[j])*(y[i]-y[j])));
      cost[i][j]=round(a);     
    }
  }
for(i=0;i<DIM;i++){
    for(j=0;j<DIM;j++){
      // printf("%3d ",cost[i][j]);
    }
    //printf("\n");
  }

  //ランダムなシード値獲得
  srand((unsigned)time(NULL));

  printf("Simple route Total cost:%d\n",totalCost(route,DIM,cost)); 

  int *randroute;
  randroute = (int *)malloc(sizeof(int)*DIM);

  randroute = randRoute(DIM,route,x,y);

  hillclimb(DIM,randroute,cost,x,y,fp);

  printf("Hillclimb Total cost:%d\n",totalCost(route,DIM,cost));

  fclose(fp);
}


quicksortは以下の通りです

void quicksort(int list1[],double list2[], int left, int right)
{
  int i, last;
  double temp;

  if (left >= right)
    return;

  last = left;
  for (i=left+1; i <= right; i++){
    if (list2[i] < list2[left] ){
      last++;
      temp=list2[last];
      list2[last]=list2[i];
      list2[i]=temp;
      temp=list1[last];
      list1[last]=list1[i];
      list1[i]=temp;         
    }
  }

  temp=list2[left];
  list2[left]=list2[last];
  list2[last]=temp;
  temp=list1[left];
  list1[left]=list1[last];
  list1[last]=temp;

  quicksort(list1,list2,left, last-1);
  quicksort(list1,list2,last+1, right);
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

check解決した方法

0

コスト行列の都市の番号と、配列routeの都市番号に1だけの差異がありました。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.76%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • C

    3464questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。