1

所以我认为我在正确的轨道上使用分支定界方法来解决我对旅行问题的启发式解决方案，但是，我的“最小”功能出现分段错误，但我仍然很难理解围绕算法。任何解决此问题的帮助将不胜感激。基本上该功能的要求（因为我的主要功能看起来很有趣）是程序应该占用多达 150 个城市，如果它在 60 秒内读取，我会得到奖励积分（这意味着我不会失败）输入文件会看起来like（例如）： c 1 c 2 a 1 2 300 其中“c”表示“创建城市”，“a”表示“添加边界”。这就是为什么我的程序是这样设置的。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int cost=0;
int main(){
int numcity ,a[151][151],visited[151],worthless,city1,city2,distance;
char citystring[2];
  a[1][1]=0;
  while(scanf("%s",citystring) != EOF){
  if(strcmp(citystring, "c") == 0){
    scanf("%d", &worthless);
    numcity++;
    }
  else if(strcmp(citystring, "a") == 0){
    scanf("%d %d %d",&city1,&city2,&distance);
    a[city1][city2] = distance;
    a[city2][city1] = distance;
    }
  }
  mincost(1,numcity,a,visited);
  printf("The minimum cost tour is %d",cost);

  return 0;
}

int mincost(int city,int n,int a[151][151],int visited[151]){
int i,ncity;
  visited[city]=1;
  printf("%d->",city);
  ncity=least(city,n,a,visited);
  if(ncity==999999){
    ncity=1;
    printf("%d",ncity);
    cost+=a[city][ncity];
  }
  mincost(ncity,n,a,visited);
}

int least(int c,int n,int a[151][151],int visited[10]){
int i,nc=999999,min=999999,kmin;
  for(i=1;i<=n;i++){
    if((a[c][i]!=0)&&(visited[i]==0)){
      if(a[c][i]<min){
        min=a[i][1]+a[c][i];
        kmin=a[c][i];
        nc=i;
      }
    }
  }
  if(min!=999999)
    cost+=kmin;
    return nc;
}
4

2 回答 2

0

您的程序核心转储到 mincost() 的最后一行，这是对 mincost() 的递归调用。

崩溃的原因是你正在吹（溢出）堆栈。

你有一个无限循环的递归等价物。

mincost应该什么时候返回？

于 2013-04-05T23:26:44.813 回答
0

C 数组是 0 索引的，但是您的索引从 1..n 而不是 0..(n-1) 开始......这就是为什么您将它们声明为 151 而不是 150？

但是您的崩溃可能是由于 mincost 无条件地调用自己。您说您认为自己走在正确的轨道上，但是在围绕算法思考时遇到了麻烦……我认为这些陈述是不一致的。在尝试编码之前，您应该确保您了解该算法。

于 2013-04-05T23:27:07.927 回答