急ぎなのですが、

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

急ぎなのですが、

#1

投稿記事 by おすぎ » 14年前

visualstudio c言語で今プログラムを書いています
まだ初心者に毛が生えた程度のレベルです

課題として、
「今いくつかの点があり、その中からスタートとゴールを決め、スタートから残りすべての点をまわり、ゴールに着く」
というものなのですが、今プログラムを書いて、ゴールを決めずにスタートから全探索するものは書けたのですが、
ゴールを固定するとなると、わからなくなりました。

コード: 

#include "stdafx.h"
#include <math.h>
//#define N 5   /* 点の個数 */
#define N 4   /* 点の個数 */

struct POINT{
	double x,y;  /* 座標用の変数 */
};

struct POINT data[N]={{0,0},{6,7},{3,5},{1,10},{10,6}}; /* 入力データ */
int root[N];
int root2[N];    /* 通った点を記憶 */
int flag[N];    /* 通ったか判定 */
double min = 1000000.0;  /* 初期の長さ */

/**************************** 探索用 serch関数 **********************************************************/
void search(double sum,int n,int k){
	//void search(int n,int k){
	int i,j;
	double x,y;
	double d[N][N];/* 距離配列 */
	double distance[N][N]; /* 距離記憶　*/
	double sum;
	++k;
	if(k > N-1){
		if(min > sum){
			min=sum;
			for(i=0;i<N;++i){
				root2[i]=root[i];
			}
		}
		return;
	}

	for(i=0;i<N;i++){
		for(j=1;j<N;j++){
			d[i][j]=sqrt(((data[j].x-data[i].x)*(data[j].x-data[i].x))+((data[j].y-data[i].y)*(data[j].y-data[i].y)));
		}
	}
	for(i=1;i<N;i++){
		if(flag[i]==0){
			sum=d[i][4];
			if(min > sum+d[n][i]){
				flag[i]=1;
				distance[n][i]=d[n][i]; /* 距離記憶 */
				root[k]=i;  /* 点記憶 */
				search(sum+d[n][i],i,k);
				flag[i]=0;
			}
		}
	}
}
/*************************** main関数 **********************************************/
int _tmain(int argc, _TCHAR* argv[])
{
	int i,j,a;
	flag[0] = 1;
	root[0] = 0;
	search(0.0,0,0);
	printf("経路  点\n");
	for(i=0;i<N;i++){

		a=root2[i];
		printf("%4d  %4d  (%7.2f,%7.2f) \n",i,a,data[a].x,data[a].y);

	}
	printf("\nmin=%lf\n",min);
	return 0;
}



/* 出力結果
経路  点
0  (   0.00,   0.00)
1  (   3.00,   5.00)
2  (   1.00,  10.00)
3  (   6.00,   7.00)
4  (  10.00,   6.00)

min=21.170174

.*/
これがそのプログラムです。
このプログラムをどう直せばよいでしょうか。。
ページトップ
box
記事: 2002
登録日時: 15年前

Re: 急ぎなのですが、

#2

投稿記事 by box » 14年前

おすぎ さんが書きました: 「今いくつかの点があり、その中からスタートとゴールを決め、スタートから残りすべての点をまわり、ゴールに着く」
「最短距離を求める」というような、他の条件は付いていないのでしょうか。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。
ページトップ
おすぎ

Re: 急ぎなのですが、

#3

投稿記事 by おすぎ » 14年前

すいません、プログラムを間違えました。

コード: 

#include "stdafx.h"
#include <math.h>
#define N 5   /* 点の個数 */
//#define N 4   /* 点の個数 */

struct POINT{
	double x,y;  /* 座標用の変数 */
};

struct POINT data[N]={{0,0},{6,7},{3,5},{10,6},{1,10}}; /* 入力データ */
int root[N];
int root2[N];    /* 通った点を記憶 */
int flag[N];    /* 通ったか判定 */
double min = 1000000.0;  /* 初期の長さ */

/**************************** 探索用 serch関数 **********************************************************/
void search(double sum,int n,int k){
	//void search(int n,int k){
	int i,j;
	double x,y;
	double d[N][N];/* 距離配列 */
	double distance[N][N]; /* 距離記憶　*/
	//double sum;
	++k;
	if(k > N-1){
		if(min > sum){
			min=sum;
			for(i=0;i<N;++i){
				root2[i]=root[i];
			}
		}
		return;
	}

	for(i=0;i<N;i++){
		for(j=1;j<N;j++){
			d[i][j]=sqrt(((data[j].x-data[i].x)*(data[j].x-data[i].x))+((data[j].y-data[i].y)*(data[j].y-data[i].y)));
		}
	}
	for(i=1;i<N;i++){
		if(flag[i]==0){
			if(min > sum+d[n][i]){
				flag[i]=1;
				distance[n][i]=d[n][i]; /* 距離記憶 */
				root[k]=i;  /* 点記憶 */
				search(sum+d[n][i],i,k);
				flag[i]=0;
			}
		}
	}
}
/*************************** main関数 **********************************************/
int _tmain(int argc, _TCHAR* argv[])
{
	int i,j,a;
	flag[0] = 1;
	root[0] = 0;
	search(0.0,0,0);
	printf("経路  点\n");
	for(i=0;i<N;i++){

		a=root2[i];
		printf("%4d  %4d  (%7.2f,%7.2f) \n",i,a,data[a].x,data[a].y);

	}
	printf("\nmin=%lf\n",min);
	return 0;
}



/* 出力結果
経路  点
0  (   0.00,   0.00)
1  (   3.00,   5.00)
2  (   1.00,  10.00)
3  (   6.00,   7.00)
4  (  10.00,   6.00)

min=21.170174

.*/



/***************** 出力結果(正解)***************************/
/*順番  点番号
0    0 (   0.00,   0.00)
1    2 (   3.00,   5.00)
2    4 (   1.00,  10.00)
3    1 (   6.00,   7.00)
4    3 (  10.00,   6.00)

21.170174
*/
ページトップ
おすぎ

Re: 急ぎなのですが、

#4

投稿記事 by おすぎ » 14年前

box さんが書きました:
おすぎ さんが書きました: 「今いくつかの点があり、その中からスタートとゴールを決め、スタートから残りすべての点をまわり、ゴールに着く」
「最短距離を求める」というような、他の条件は付いていないのでしょうか。
書き忘れました、すいません。
スタートから残りすべての点の、ゴールに着くときの最短経路を求める
というものです。
ページトップ
non
記事: 1097
登録日時: 15年前

Re: 急ぎなのですが、

#5

投稿記事 by non » 14年前

何度もこのような問題を見たような・・・デジャブか？
http://dixq.net/forum/viewtopic.php?f=3&t=9750

２つのプログラムを見たら、あまりにも似かよってるけど、でもちょっと違う。
どこまでが、自分で作ったんだろう。最初から全部自分で作ったわけではなさそうだ。
non
ページトップ
おすぎ

Re: 急ぎなのですが、

#6

投稿記事 by おすぎ » 14年前

non さんが書きました:何度もこのような問題を見たような・・・デジャブか？
http://dixq.net/forum/viewtopic.php?f=3&t=9750

２つのプログラムを見たら、あまりにも似かよってるけど、でもちょっと違う。
どこまでが、自分で作ったんだろう。最初から全部自分で作ったわけではなさそうだ。
すいません。
確かにわからなかったので、参考にさせてもらいました。
ページトップ
non
記事: 1097
登録日時: 15年前

Re: 急ぎなのですが、

#7

投稿記事 by non » 14年前

じゃあ、ゴールについては、一番最後にヒントを書いたけど。
non
ページトップ
おすぎ

Re: 急ぎなのですが、

#8

投稿記事 by おすぎ » 14年前

non さんが書きました:じゃあ、ゴールについては、一番最後にヒントを書いたけど。
なるほど。。
でも、なら、ゴール地点に2をいれるとはどういう意味ですか？
ページトップ
non
記事: 1097
登録日時: 15年前

Re: 急ぎなのですが、

#9

投稿記事 by non » 14年前

じゃ、スタートに1を入れたのはどういう意味ですか？
non
ページトップ
おすぎ

Re: 急ぎなのですが、

#10

投稿記事 by おすぎ » 14年前

non さんが書きました:じゃ、スタートに1を入れたのはどういう意味ですか？
そこはもう通ったということを、flag[]で判別するためです。
ページトップ
non
記事: 1097
登録日時: 15年前

Re: 急ぎなのですが、

#11

投稿記事 by non » 14年前

ゴールも通れないから、判別するためだよね。
０でなければ、１でも２でも同じでしょ。
non
ページトップ
おすぎ

Re: 急ぎなのですが、

#12

投稿記事 by おすぎ » 14年前

non さんが書きました:ゴールも通れないから、判別するためだよね。
０でなければ、１でも２でも同じでしょ。
なるほど。
では、再帰呼び出しの、 if(n > (N-1))のところでif(n > (N-2)とするところまでもわかりましたが、
この部分でゴールの一つ前の点とゴールまでの距離を出すにはどうすればよいのですか？
ページトップ
non
記事: 1097
登録日時: 15年前

Re: 急ぎなのですが、

#13

投稿記事 by non » 14年前

ゴールがわかっているのだから、1つ前の地点が決まれば求まるのでは？

それより、添付されたプログラムですが、35行～39行を再帰関数の中で計算させるのは無駄です。
グローバル変数にして、mainで計算させましょう。
non
ページトップ
おすぎ

Re: 急ぎなのですが、

#14

投稿記事 by おすぎ » 14年前

non さんが書きました:ゴールがわかっているのだから、1つ前の地点が決まれば求まるのでは？

それより、添付されたプログラムですが、35行～39行を再帰関数の中で計算させるのは無駄です。
グローバル変数にして、mainで計算させましょう。
35行～39行をグローバル変数にしました。
どこでひとつ前の点が決まるのですか？

コード: 

 ++k;
    if(k > N-2){
        if(min > sum){
            min=sum;
            for(i=0;i<N;++i){
                root2[i]=root[i];
            }
        }
        return;
    }
ページトップ
non
記事: 1097
登録日時: 15年前

Re: 急ぎなのですが、

#15

投稿記事 by non » 14年前

4行目で決まったからminに入れたんでしょ。

注意しておくけど、1個前の地点からゴールまでの距離を足してminに入れなきゃだめよ。
non
ページトップ
おすぎ

Re: 急ぎなのですが、

#16

投稿記事 by おすぎ » 14年前

non さんが書きました:4行目で決まったからminに入れたんでしょ。

注意しておくけど、1個前の地点からゴールまでの距離を足してminに入れなきゃだめよ。

コード: 

 
++k;
   if(k > N-2){
b=root[k-1];
		if(min > sum+d[b][4]){
			min=sum+d[b][4];
for(i=0;i<N;++i){
				root2[i]=root[i];
			}
		}
		return;
	}
こういうことでしょうか？
ページトップ
non
記事: 1097
登録日時: 15年前

Re: 急ぎなのですが、

#17

投稿記事 by non » 14年前

おすぎ さんが書きました:こういうことでしょうか？
って？自分で確認して。
理由：ゴールをどの地点にしているのか、私にはわからない。
non
ページトップ
閉鎖

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