セールスマン問題について

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら
閉鎖
qwerty

セールスマン問題について

#1

投稿記事 by qwerty » 11年前

セールスマン問題について質問です！
後半部分(k,i,next,min,tdisを表示するあたり)がよくわからないので質問しました。
アドバイスがほしいです。

問題はランダムに100都市の場所を作成します。
そして、ある都市から出発し、ほかの都市を一回ずつすべて訪問して最初の訪問都市にもどってくるまでの総移動距離が最小となる最短巡回経路と総移動距離を最近隣法を用いて求める。といった感じです。

よろしくお願いします。
ちなみにコードは

コード: 

#include<stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define distance(xi,xj,yi,yj) sqrt(pow((xi)-(xj),2.0)+pow((yi)-(yj),2.0))
#define MaxN 100

FILE *fp1;
FILE *fp2;
FILE *fp3;

struct CityInfo
{
	int citynumber;
	double x;
	double y;
};

int main(void){
int N;
int n;
int city_number;
double a, b;
	double ux;
	double uy;

	struct CityInfo cityinfo[MaxN]{{ 0, 0.0, 0.0 }};


	printf("訪問都市の位置座標x座標とy座標の範囲(下限a,上限b)の設定について\n");
	printf("範囲の下限aを指定して下さい____> "); scanf_s("%lf", &a);
	printf("範囲の上限bを指定して下さい____> "); scanf_s("%lf", &b);
	printf("訪問都市数Nを指定して下さい____>"); scanf_s("%d", &N);

	errno_t err, err_r;
	err = fopen_s(&fp1, "citydata_info.csv", "w");
	if (err == 1)
	{
		printf("The file 'citydata_info.csv'was not opened\n\n");
	}

	srand((unsigned int)time(NULL));

	printf("\n都市番号\tx座標\t\t\ty座標\n");

	for (n = 1; n <= N; n++) {
		
		city_number = n;

		ux = (double)rand() / (double)RAND_MAX;
		cityinfo[n].x = a + (b - a) * ux;
		uy = (double)rand() / (double)RAND_MAX;
		cityinfo[n].y = a + (b - a) * uy;
		
		
		printf("%d\t\t%lf\t\t%lf\n", n, cityinfo[n].x, cityinfo[n].y);
		fprintf(fp1, "%d\t%lf\t%lf\n", n, cityinfo[n].x, cityinfo[n].y);

	}

	if (fp1)
	{
		err = fclose(fp1);
		if (err == 1)
		{
			printf("The file 'citydata_info.csv'was not closed\n\n");
		}
	}


	struct CityInfo *cityinfodata;

	cityinfodata = (struct CityInfo *)malloc((N + 1) *sizeof(struct CityInfo ));
	if (cityinfodata == NULL){
		printf(" メモリが確保できません。\n"); exit(1);
	}

	for (n = 0; n <= N; n++){
		cityinfo[n].citynumber = 0;
		cityinfo[n].x = 0.0;
		cityinfo[n].y = 0.0;
	}
	if (err == 1){
		printf("The file 'citydata_info.txt' was not opened as read mode.\n\n");
	}
	err_r = fopen_s(&fp2, "citydata_info.csv", "w");

	if (err_r == 1){
		printf("The file 'citydata_info.csv' was not opened as read mode.\n\n");
	}

	n = 0;

	while ((fscanf_s(fp1, "%d,%lf,%lf", &cityinfo[n].citynumber, &cityinfo[n].x, &cityinfo[n].y)) == 3){

		fprintf_s(fp2, "%d,%lf,%lf\n", cityinfo[n].citynumber, cityinfo[n].x, cityinfo[n].y);

		n++;

	}
	

	if (fp1){
		err = fclose(fp1);
		if (err == 1){ printf("The file 'citydata_info.txt' was not closed.\n\n"); }
	}
	if (fp2){
		err_r = fclose(fp2);
		if (err_r == 1){ printf("The file 'citydata_info.csv' was not closed.\n\n"); }
	}

	err_r = fopen_s(&fp2, "citydata_info.csv", "r");

	if (err_r == 1){
		printf("The file 'citydata_info.csv' was not opened as read mode.\n\n");
	}

	errno_t err3;
	err3 = fopen_s(&fp3, "qwerty.csv", "w");
	if (err3 == 1)
	{
		printf("The file qwerty.csv' was not opened as read mode.\n\n");
	}
	fprintf_s(fp3, "都市番号,x座標,y座標\n");

	while ((fscanf_s(fp3, "%d,%lf,%lf", &cityinfo[n].citynumber, &cityinfo[n].x, &cityinfo[n].y)) == 3){

		n++;

	}

	int *z;
	z = (int *)malloc((N + 1) *sizeof(int));
	if (z == NULL){
		printf("一次元配列 z のメモリを確保できません。\n"); exit(1);
	}

	for (n = 0; n <= N; n++){
		z[n] = 0;
	}

	int *zz;
	zz = (int *)malloc((N + 1) *sizeof(int));
	if (zz == NULL){
		printf("一次元配列 zz のメモリを確保できません。\n"); exit(1);
	}

	for (n = 0; n <= N; n++){
		zz[n] = 0;
	}
	
	clock_t start_time, end_time;
	int start;
	int i;
	int j;
	int k;
	int next;
	double min;
	double disij;
	double tdis=0.0;
	
	start = 0;
	printf("\n最初の出発都市startを都市番号1～%dより指定してください。-->", N); scanf_s("%d", &start);

	start_time = clock();
	i = start;

	printf("k\ti\tnext\tmin\ttdis\n");
	
	k = 1;

	
	z[i] = k;
	zz[k] = i;

	for (k = 2; k <= N; k++) {
		min = 10000.0;
		for (j = 1; j <= N ; j++) {
			if (z[j] == 0) {
				disij = distance(cityinfo[i].x, cityinfo[j].x, cityinfo[i].y, cityinfo[j].y);

				if (disij<min) {
					next = j;
					min = disij;
				}
			}
		}
		
		z[next] = k;
		zz[k] = next;
		tdis = tdis + disij;
		i = next;
		
		printf("%d\t%d\t%d\t%lf\t%lf\n", k, i, next, min, tdis);
		fprintf(fp3, "%d,%d,%d,%lf,%lf\n", k, i, next, min, tdis);

	}

	end_time = clock();

	double ldis= 0.0;
	ldis = sqrt(pow(cityinfo[start].x - cityinfo[next].x, 2.0) + pow(cityinfo[start].y - cityinfo[next].y, 2.0));
	tdis = tdis+ldis;
	
	printf("\t%d\t%d\t%lf\t%lf\n", next, start, ldis, tdis);
	fprintf(fp3, ",%d,%d,%lf,%lf\n", next, start, ldis, tdis);

	double searching_time;
	searching_time = (double)(end_time - start_time) / (double)CLOCKS_PER_SEC;

	printf("\n最近隣法による最短巡回経路の総移動距離は%lfです。\n", tdis);
	fprintf_s(fp3, "\n最近隣法による最短巡回経路の総移動距離は%lfです。\n", tdis);

	printf("探索処理時間%lf秒\n", searching_time);
	fprintf_s(fp3, "探索処理時間%lf秒\n", searching_time);

	free(cityinfo);
	free(z);
	free(zz);

	return 0;
}
ページトップ
box
記事: 2002
登録日時: 14年前

Re: セールスマン問題について

#2

投稿記事 by box » 11年前

qwerty さんが書きました: 後半部分(k,i,next,min,tdisを表示するあたり)がよくわからないので質問しました。
printf()のところですか？
何がどのようにわからないのか、もっと詳しく教えてください。

ところで、本題とは無関係ですが、
qwerty さんが書きました:

コード: 

	err = fopen_s(&fp1, "citydata_info.csv", "w");
	if (err == 1)
	{
		printf("The file 'citydata_info.csv'was not opened\n\n");
	}
書き込み用のファイルが正しくオープンできないときでも
そのまま処理を続けているのはいかがなものか、と思います。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
ページトップ
qwerty

Re: セールスマン問題について

#3

投稿記事 by qwerty » 11年前

[quote="box" id=3,15233,121294][quote="qwerty" id=3,15233,121288]
後半部分(k,i,next,min,tdis)というのは
計算結果がminやtdisに表れるはずなのに0.00000となってしまうところ
iとnextが同じ数字になってしまうところの二点です。
例えばi=2,next=2というような感じです。

あと、もしよければ他にも間違っている部分があれば教えてほしいです。

プログラミングを始めたばかりなのでわからないことが多いのでよろしくお願いします。
ページトップ
box
記事: 2002
登録日時: 14年前

Re: セールスマン問題について

#4

投稿記事 by box » 11年前

とりあえず、くだんのコードの192行目で
qwerty さんが書きました:

コード: 

		i = next;
このように書いているのですから、その直後の
qwerty さんが書きました:

コード: 

		printf("%d\t%d\t%d\t%lf\t%lf\n", k, i, next, min, tdis);
		fprintf(fp3, "%d,%d,%d,%lf,%lf\n", k, i, next, min, tdis);
でiとnextが同じ値になるのは必然かと思います。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
ページトップ
qwerty

Re: セールスマン問題について

#5

投稿記事 by qwerty » 11年前

気づきませんでした。
そこが原因だったのですね。
あとminとtdisについてが謎なのでよろしくお願いします。
ページトップ
box
記事: 2002
登録日時: 14年前

Re: セールスマン問題について

#6

投稿記事 by box » 11年前

なんか、ファイルのオープン／クローズが頻発していて、
今、どのファイルを読み込み／書き込みのどちらのモードで
オープンしているかがひじょうにわかりづらいです。

一度整理してみる方がいいのではないでしょうか。

なお、くだんのコードの180行目のすぐ下で

cityinfo.x, cityinfo[j].x, cityinfo.y, cityinfo[j].y

の4個のデータをprintfしてみたところ、すべてゼロでした。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
ページトップ
qwerty

Re: セールスマン問題について

#7

投稿記事 by qwerty » 11年前

cityinfo.x, cityinfo[j].x, cityinfo.y, cityinfo[j].y
の4個のデータが0になってしまう原因がわからないので、少しアドバイスいただけますか？
ページトップ
box
記事: 2002
登録日時: 14年前

Re: セールスマン問題について

#8

投稿記事 by box » 11年前

126行～130行のwhile文は何をしていますか？
書き込み用にオープンしているはずの
fp3
から
fscanf_s（つまり読み込み）
している理由がわかりません。


また、
92行目で初期化し、
98行目と128行目でインクリメントしている
n
の値を使わないまま、
138行目のfor文でゼロに初期化しています。
インクリメントしている意味がなくなってしまっています。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
ページトップ
qwerty

Re: セールスマン問題について

#9

投稿記事 by qwerty » 11年前

でしたら126行～130行のwhile文のところのfp3をfp2にしたらいいのでしょうか？

あと
92行目で初期化し、
98行目と128行目でインクリメントしている
n
の値を使わないまま、
138行目のfor文でゼロに初期化しています。
インクリメントしている意味がなくなってしまっています。
こちらの対処法がちょっとわからないので具体的にお願いできますか？
ページトップ
box
記事: 2002
登録日時: 14年前

Re: セールスマン問題について

#10

投稿記事 by box » 11年前

qwerty さんが書きました:でしたら126行～130行のwhile文のところのfp3をfp2にしたらいいのでしょうか？
それは、fp2やfp3が何のために存在しているかがわかっている（はずの）質問者さんが判断することです。
もし存在理由がわからないのであれば、どのファイルが何のために存在していて
どういうタイミングで読み書きしなければならないのか、整理する必要があります。
qwerty さんが書きました: こちらの対処法がちょっとわからないので具体的にお願いできますか？
変数nが何のために存在しているかを整理してみましょう。
インクリメントしているということは、その値を後の局面で使いたいからですよね？
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
ページトップ
qwer

Re: セールスマン問題について

#11

投稿記事 by qwer » 11年前

いろいろと直してみたところ
_Crtisvalidheappointerのエラーが出てしまい先に進めません。
どうすればいいのでしょうか？
ページトップ
閉鎖

“C言語何でも質問掲示板” へ戻る