経路探索のプログラム
Posted: 2011年12月12日(月) 16:39
何度もすいません。
今プログラムをc言語で作成しているのですが....
つくろうとしているものとしては、
・最初にスタート地点とゴールを決める
・いくつかの巡回する候補地を決める
・その結果、いくつかの候補地を回りながら、目的地にたどりつく
というもので、今はスタート地点を固定した全探索の形ならば作ることができました。
しかし、スタート地点とゴールをきめてから探索するとなるとできません
そのためには、どうすればよいでしょうか？
プログラムに関しては初心者で、Microsoft Visual C++専用C言語
で作成しています。
今プログラムをc言語で作成しているのですが....
つくろうとしているものとしては、
・最初にスタート地点とゴールを決める
・いくつかの巡回する候補地を決める
・その結果、いくつかの候補地を回りながら、目的地にたどりつく
というもので、今はスタート地点を固定した全探索の形ならば作ることができました。
しかし、スタート地点とゴールをきめてから探索するとなるとできません
そのためには、どうすればよいでしょうか？
プログラムに関しては初心者で、Microsoft Visual C++専用C言語
で作成しています。
#include "stdafx.h"
#include <stdlib.h>
#include <math.h>
#define N 5
struct POINT2
{
double x,y;
};
POINT2 point[N]={{0,0},{6,7},{3,5},{10,6},{1,18}};
int flag[N]; /* 通った点の記憶 */
int trace[N];
int trace2[N];
double distance;
void search(int n,int k,double sum) /* 探索 */
{
int i;
double x,y,d;
++n;
if(n > (N-1))
{
if(sum < distance)
{
distance = sum;
for(i=0;i<N;++i)
trace2[i]=trace[i];
}
return;
}
for(i=0;i<N;++i)
{
if(flag[i] == 0)
{
x=point[k].x-point[i].x;
y=point[k].y-point[i].y;
d=x*x + y*y;
d=sqrt(d);
if(distance > sum+d)
{
flag[i] = 1;
trace[n] = i;
search(n,i,sum+d);
flag[i] = 0;
}
}
}
}
int _tmain(int argc, _TCHAR* argv[]) /* main文 */
{
int i,k;
distance = 10000000.0; /* 初期の長さ */
flag[0] = 1; /* スタートする点 */
trace[0]= 0;
search(0,0,0.0);
printf("順番 点番号\n");
for(i=0;i<N;++i)
{
k=trace2[i];
printf("%4d %4d (%7.2lf,%7.2lf) \n",i,k+1,point[k].x,point[k].y);
}
printf("\n%lf\n",distance);
return 0;
}
ちなみに、これがその作成したプログラムです。
どこに何を加えればよいのか、なるべく詳しくお願いします。
補足