分支定界问题的 C 代码

Question

所以我认为我在正确的轨道上使用分支定界法来解决我的启发式问题解决旅行问题，然而，我在我的“最小”函数中遇到了段错误，但我仍然很难理解算法。任何解决此问题的帮助将不胜感激。基本上该功能的要求(因为我的主要功能看起来很有趣)是该程序最多应占用 150 个城市，如果读取时间低于 60 秒，我将获得奖励积分(这意味着我不会失败)输入文件看起来喜欢(例如):121 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;
}

Answer 1

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

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