巡回セールスマン問題における貪欲法の作り方

Question

前提・実現したいこと

巡回セールスマン問題(地点間の最小距離を求める問題)において、貪欲法(地点間を結ぶ線の中で最小なものを選んでいき、すべての地点を結ぶようにつなぐ方法)のプログラムを作りたいです。
1つ以上地点に余りが出てしまい、与えられた地点数Nにたいして全てをつなぐような線を結ぶことができません。
どのようにすればよいでしょうか？分かる方いましたら、回答をお願いします。

発生している問題・エラーメッセージ

自分なりに作ってみたプログラムでは、ループが発生してしまいました。
途中に長いif文がありますが、一応それが閉回路(1つ以上地点に余りが出てしまう経路)を構成しない条件です。

該当のソースコード

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>

#define visit 1.0
#define N 5
#define M 5

typedef struct xy{
    double x;
    double y;
}VTEX;

int i,j,k,rmin;
VTEX pt[N];
double r[N][N];
double min,s;
clock_t start_clock, end_clock;

void ransuu(void){
    for(k=0;k<N;k++){
        pt[k].x=(double)rand()/RAND_MAX;
        pt[k].y=(double)rand()/RAND_MAX;
        //printf("pt[%d]=(%f %f)\n",k,pt[k]);
    }
}

void length(void){
    for(i=0;i<N-1;i++){
        for(j=1+i;j<N;j++){
            r[i][j]=sqrt((pt[i].x-pt[j].x)*(pt[i].x-pt[j].x)+(pt[i].y-pt[j].y)*(pt[i].y-pt[j].y));
            printf("r[%d][%d]=%f\n",i,j,r[i][j]);
        }
    }
}

void hantei(void){
    s=0, rmin=0;
    double b[N]={0};
    for(k=0;k<N;k++)
       r[k][k]=visit; 
    int c=-1, d=-1;
    min=r[c+1][d+1];
    while(!((b[0]==2)&&(b[1]==2)&&(b[2]==2)&&(b[3]==2)&&(b[4]==2))){
    //printf("%d\n",rmin);
    for(i=0;i<N-1;i++){
        for(j=1+i;j<N;j++){
            if(b[i]>=2.0) continue; //3つ以上線がついていたら
            if((min>r[i][j])&&!(r[i][j]==visit)&&(b[j]<2)){ c=i; d=j; min=r[c][d];printf("%d %d\n",c,d);} //最小値判定法
            //printf("%d %d\n",c,d);
        }
    }
    printf("%dから%dへの線 min:%f\n",c+1,d+1,r[c][d]);
    if((rmin!=0)&&(!((b[0]==2)&&(b[1]==2)&&(b[2]==2)&&(b[3]==2)&&(b[4]==2)))&&((b[0]==2)||(b[0]==0))&&((b[1]==2)||(b[1]==0))&&((b[2]==2)||(b[2]==0))&&((b[3]==2)||(b[3]==0))&&((b[4]==2)||(b[4]==0))){min=visit; r[c][d]=visit; continue;}
        if(c==0||d==0)b[0]+=visit;
        if(c==1||d==1)b[1]+=visit;
        if(c==2||d==2)b[2]+=visit;
        if(c==3||d==3)b[3]+=visit;
        if(c==4||d==4)b[4]+=visit;
    s+=min;
    min=visit; r[c][d]=visit; //線が触れた回数をカウント
    //printf("b[%d]:%f\n",c,b[c]);
    rmin++;
    }
    printf("最小経路長は%f\n",s);
}

int main(void){
    srand((unsigned int)time(NULL));
    double a[M],s;
    for(int n=0;n<M;n++){
        start_clock=0,end_clock=0;
        printf("%d回目\n",n+1);
        ransuu();
        length();
        start_clock=clock();
        hantei();
        end_clock=clock();
        a[n]=(double)(end_clock-start_clock)/CLOCKS_PER_SEC;
        s+=a[n];
        //printf("%f\n",a[n]);
    }
    double MAX=a[0];
    for(i=1;i<N;i++){
        if(MAX<a[i]) MAX=a[i];
    }
    printf("最大時間計算量:%f\n",MAX);
    printf("平均時間計算量:%f\n",s/M);
    return 0;
}

Comments

[ozwk]

素直に考えると
「現在地から、過去に行ったことのない都市の距離をすべて求め、距離が最小だった都市に行く。」
を繰り返すだけのように思えます。(巡回セールスマン問題と言ったら、普通全ての都市をちょうど1回ずつ回る最短経路を求める)

コードには
//3つ以上線がついていたら
とか
//線が触れた回数をカウント
と謎の概念が出てきます。
コードから意図を読み解こうにも変数名がaだのbだのcだの暗号になっているのでわかりません。

なにか条件があるのですか?

[katkey]

このプログラムは地点間の線の本数に注目しています。
ある地点から出ている線の本数が3本ならば、一筆書きができないのでプログラムを終了させます。
また、地点間の中で最小のものを求めるので、現在地は関係ありません。

[katkey]

その後、自己解決したのですが、質問の取り消し方が分からないです。
どうすればよいかわかりますか？

[ozwk]

問題文が存在して、可能であれば原文を引用してください
↑すれ違いました

Answer 1

int hantei(void){
    min=0,s=0,rmin=0;
    double a[M]={0};
    for(k=0;k<N;k++)
       r[k][k]=visit; 
    int c=-1, d=-1;
    min=r[c+1][d+1];
    while(rmin<N){
    ++rmin;
    //printf("%d\n",rmin);
    for(i=0;i<N-1;i++){
        for(j=1+i;j<N;j++){
            if(a[i]>=2.0) continue; 
            if((min>r[i][j])&&!(r[i][j]==visit)&&(a[j]<2)){ c=i; d=j; min=r[c][d];printf("%d %d\n",c,d);} 
            //printf("%d %d\n",c,d);
        }
    }
    printf("%dから%dへの線 min:%f\n",c+1,d+1,r[c][d]);
    for(k=0;k<N;k++){
        if((c==k)||(d==k))a[k]+=visit;
    }
    s+=min;
    min=visit; r[c][d]=visit; 
    //printf("b[%d]:%f\n",c,b[c]);
    }
    for(k=0;k<N;k++){
        if(!(a[k]==2.0)){
            rmin=0;
            printf("最短経路長を求めるのに失敗しました");
            return 1;
        }
    }
    printf("最短経路長は%f\n",s);
}

結局、地点数Nに対して一筆書きできる条件はN回の探索で終了できる場合なので、N回プログラムを実行したところで打ち切ってしまい、すべての地点に2回訪れていなければ、プログラム失敗とすればループが起こらなくて済むことが分かった。