A_star演算法題目求解- 藍色小舖 BlueShop

台灣最大程式設計社群網站

∣免費加入會員∣登入 ∣回首頁∣ 您好

線上人數
722

會員總數：244988
討論主題：188956

登入

登出

歡迎您免費加入會員

討論區選單

開發工具

行動裝置開發

資料庫

多媒體 / 網管

綜合

文章區

討論區列表 >> C/C++ >> A_star演算法題目求解

[]

[我要回覆]

A_star演算法題目求解
價值 : 100 QP 點閱數:138 回應數:1

樓主

cyatmirror

0	5
58	9

發送站內信

我正在解一題zerojudge上關於a star 演算法的題目
https://zerojudge.tw/ShowProblem?problemid=d747
不知道是哪裡寫錯了
還煩請版上大大協助

我的想法是去計算每個點的 g(x)(從起點到該點的距離)/h(x)(該點到終點的曼哈頓距離)/f(X)=g(x)+h(X)
然後丟進minheap裡面
若遇到f值相同則先pop出後進的元素(用order這個變數去計算進去heap的順序)
只是跑出來的結果
1.若沒把order納入考量，那結果會跟bfs幾乎一樣
2.若納入order，我的程式跑出來就會炸裂
ps我原本是用priority queue去做但還是炸裂QQ

希望有大大能幫我找到錯誤
這個問題我想了一個多禮拜了QAQ
感激不盡><

#include<bits/stdc++.h> 
struct record{
	int f=0,h=0,g=0,x,y,px,py;
	int order=0;//g:current h:heuristic 
};

record heap[1000000]; 
int n,gx,gy,order;//gx:goal x / gy:goal y
char maze[1000][1000];
bool closelist[1000][1000];
record mazedata[1000][1000];
int heapsize=0;
void heapify(int x){
	int left=2*x,right=2*x+1,min=x;
	if(left<heapsize&&(heap[left].f<heap[min].f||(heap[left].f==heap[min].f&&heap[left].order>heap[min].order)))min=left;
	if(right<heapsize&&(heap[right].f<heap[min].f||(heap[right].f==heap[min].f&&heap[right].order>heap[min].order)))min=right;
	if(min!=x){
		std::swap(heap[x],heap[min]);
		heapify(min);
	}
}
void push(record tmp){
	int x=++heapsize;
	heap[heapsize]=tmp;
	while(x>1&&(heap[x].f<heap[x/2].f||(heap[x].f==heap[x/2].f&&heap[x].order>heap[x/2].order))){
		std::swap(heap[x],heap[x/2]);
		x/=2;
	}
}
void pop(){
	if(heapsize==0)return;
	std::swap(heap[heapsize],heap[1]);
	heapsize--;
	heapify(1);
}
record front(){
	return heap[1];
}
void reset(){
	heapsize=0;
	order=0;
	for(int i=0;i<1000;i++){
		for(int j=0;j<1000;j++){
			closelist[i][j]=false;
			mazedata[i][j].f=0;mazedata[i][j].x=i;mazedata[i][j].y=j;
		}
	}
}
void astar_algorithm(int x,int y){
	int g,dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
	while(heapsize>0){
		g=mazedata[x][y].g;
		if(x==gx&&y==gy){
			closelist[x][y]=true;
			break;
		}
		for(int i=0;i<4;i++){
			if(x+dx[i]<n&&x+dx[i]>=0&&y+dy[i]<n&&y+dy[i]>=0&&closelist[x+dx[i]][y+dy[i]]==false&&maze[x+dx[i]][y+dy[i]]=='.'){
				if(mazedata[x+dx[i]][y+dy[i]].f!=0){
					if(g+1+mazedata[x+dx[i]][y+dy[i]].h<mazedata[x+dx[i]][y+dy[i]].f){
						mazedata[x+dx[i]][y+dy[i]].px=x;
						mazedata[x+dx[i]][y+dy[i]].py=y;
						mazedata[x+dx[i]][y+dy[i]].f=g+1+mazedata[x+dx[i]][y+dy[i]].h;	
						mazedata[x+dx[i]][y+dy[i]].g=g+1;
						mazedata[x+dx[i]][y+dy[i]].order=++order;
						push(mazedata[x+dx[i]][y+dy[i]]);					
					}
				}else{
					mazedata[x+dx[i]][y+dy[i]].h=abs(x+dx[i]-gx)+abs(y+dy[i]-gy);
					mazedata[x+dx[i]][y+dy[i]].g=g+1;
					mazedata[x+dx[i]][y+dy[i]].f=mazedata[x+dx[i]][y+dy[i]].h+mazedata[x+dx[i]][y+dy[i]].g;
					mazedata[x+dx[i]][y+dy[i]].px=x;
					mazedata[x+dx[i]][y+dy[i]].py=y;
					mazedata[x+dx[i]][y+dy[i]].order=++order;
					push(mazedata[x+dx[i]][y+dy[i]]);	
				}

}
		}
		closelist[x][y]=true;
		maze[x][y]='@';
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				std::cout<<maze[i][j];
			}
		}
		pop();
		x=front().x;
		y=front().y;

}
}
int main(){
	std::ios::sync_with_stdio(false);
	int m,a,b,x,y;
	std::cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int k=0;k<n;k++){
			std::cin>>maze[i][k];
		}
	}
	while(m--){
		reset();
		std::cin>>a>>b>>x>>y;
		if(maze[a][b]=='X'||maze[x][y]=='X'){
			std::cout<<"ERROR\n";
			continue;
		}else{
			gx=x;
			gy=y;
			mazedata[a][b].g=0;
			mazedata[a][b].order=0;
			push(mazedata[a][b]);
			astar_algorithm(a,b);
			if(closelist[x][y]==false)std::cout<<"-1\n";
			else {
				std::cout<<mazedata[x][y].g<<std::endl;	
			}
		}
	}
}

搜尋相關Tags的文章： [ a start algorithm ] , [ c++ ] ,
本篇文章發表於2019-07-19 16:20


別忘捐VP感謝幫助你的人	新手會員瞧一瞧

1樓

作者回應

cyatmirror

下面是我的ac code
但是有一行是參酌網路資料
-->(cnt[x+dx[i]][y+dy[i]]==0||cnt[x+dx[i]][y+dy[i]]>cnt[x][y]+1)
如果把這行省掉就會只拿到85%的分數
請問為甚麼不能寫成(cnt[x+dx[i]][y+dy[i]]==0||cnt[x+dx[i]][y+dy[i]]>cnt[x][y])

#include<bits/stdc++.h>
#define N 1000
#define NN 1000000
#define rep(k,n) for(int k=0;k<n;++k)
using namespace std;
struct grid{
	int x,y,f;
	grid(){;}
	grid(int _x,int _y,int _f){x=_x;y=_y;f=_f;}
};
struct cmp{
	bool operator() (const grid&a,const grid&b){
		return a.f>b.f;
	}
};
char maze[N][N];
bool visit[N][N];
int gx,gy,sx,sy;
int cnt[N][N]={0};
void init(int n){
	rep(i,n)
		rep(j,n)
			visit[i][j]=false,cnt[i][j]=0;
}
int cross(int x,int y){
	int p1x=sx-x,p1y=sy-y;
	int p2x=gx-x,p2y=gy-y;
	return abs(p1x*p2y-p1y*p2x);
}
int astar(int n,int x,int y){
	priority_queue<grid,vector<grid>,cmp>pq;
	int h,f;
	const int dx[]={-1,0,0,1},dy[]={0,-1,1,0};
	h=(abs(gx-x)+abs(gy-y))*NN+cross(x,y);
	f=h;
	grid tmp(x,y,f);
	pq.emplace(tmp);
	while(!pq.empty()){	
		x=pq.top().x;y=pq.top().y;f=pq.top().f;
		pq.pop();
		visit[x][y]=true;
		if(x==gx&&y==gy)break;
		rep(i,4){
			if(x+dx[i]>0&&x+dx[i]<n&&y+dy[i]>0&&y+dy[i]<n&&visit[x+dx[i]][y+dy[i]]==false&&(cnt[x+dx[i]][y+dy[i]]==0||cnt[x+dx[i]][y+dy[i]]>cnt[x][y]+1)&&maze[x+dx[i]][y+dy[i]]=='.'){
				cnt[x+dx[i]][y+dy[i]]=cnt[x][y]+1;
				h=(abs(gx-(x+dx[i]))+abs(gy-(y+dy[i])))*NN+cross(x+dx[i],y+dy[i]);
				f=cnt[x+dx[i]][y+dy[i]]*NN+h;
				tmp.x=x+dx[i];tmp.y=y+dy[i];tmp.f=f;
				pq.emplace(tmp);
			}
		}
	}
	while(!pq.empty())pq.pop();
	if(visit[gx][gy]==false)return -1;
	else return cnt[x][y];
}
int main(){
	int n,m,step;
	scanf("%d%d",&n,&m);
	getchar();
	rep(i,n){
		rep(j,n){
			scanf("%c",&maze[i][j]);//cin>>maze[i][j];
		}
		getchar();
	}
	while(m--){
		init(n);
		scanf("%d%d%d%d",&sx,&sy,&gx,&gy);
		if(maze[sx][sy]=='X'||maze[gx][gy]=='X'){
			printf("ERROR\n");
			continue;
		}
		step=astar(n,sx,sy);
		printf("%d\n",step );
	}
}

本篇文章回覆於2019-07-28 16:39

== 簽名檔 ==
--未登入的會員無法查看對方簽名檔--

回覆

如要回應,請先登入.