Fringe Search for pathfinding 边缘搜索算法路径搜索

gistfile1.cpp

#include <hash_map>
#include <iostream>
#include <list>
#include <vector>
#include <algorithm>

using namespace std;
using namespace stdext;

int R,C;//地图行列
int srcr,srcc,destr,destc;//起点 终点
int map[100][100];//0是障碍1是可行

struct Node 
{
	int f,g,h;
	int r,c;
	int parent;
};

list<Node> nowList;
list<Node> laterList;
hash_map< int , Node > cacheList;
vector<Node> bestList;

int Hfun(int r,int c)
{
	return abs(destr-r)+abs(destc-c);
}

bool Reach(int r,int c)
{
	if (!map[r][c]||r<0||c<0||r>R||c>C)
		return false;
	return true;
}

int GetCost(int r,int c)
{
	return 1;
}

Node child;

bool check(Node value)
{
	if (value.r==child.r&&value.c==child.c)
	{
		return true;
	}
	return false;
}

bool checkhash(pair<int,Node> value)
{
	if (value.second.r==child.r&&value.second.c==child.c)
	{
		return true;
	}
	return false;
}

int HashKey(Node& node)
{
	return (node.r<<16|node.c);
}

void Generate(Node& node,int r,int c,list<Node>& curlist)
{
	child.r=r;
	child.c=c;
	child.g=GetCost(r,c)+node.g;
	child.h=Hfun(r,c);
	child.f=child.g+child.h;
	child.parent=node.r<<16|node.c;

	hash_map<int,Node>::iterator posPL=find_if(cacheList.begin(),cacheList.end(),checkhash);
	if (posPL!=cacheList.end())
	{
		if (child.g>=posPL->second.g)
		{
			return;
		}
	}
	list<Node>::iterator posCL=find_if(curlist.begin(),curlist.end(),check);
	if (posCL!=curlist.end())
	{
		curlist.erase(posCL);
	}
	curlist.push_front(child);

	cacheList[HashKey(child)]=child;
}

void Kuozhan(Node& node,list<Node>& curlist)
{
	if (Reach(node.r-1,node.c))// 上 
	{
		Generate(node,node.r-1,node.c,curlist);
	}
	if (Reach(node.r,node.c+1))//右
	{
		Generate(node,node.r,node.c+1,curlist);
	}
	if (Reach(node.r+1,node.c))// 下
	{
		Generate(node,node.r+1,node.c,curlist);
	}
	if (Reach(node.r,node.c-1))// 左 
	{
		Generate(node,node.r,node.c-1,curlist);
	}
}

void BestPath(Node &best)
{
	Node mudi=best;
	if (!bestList.empty())
	{
		bestList.clear();
	}
	for (;;)
	{
		bestList.push_back(mudi);
		if (mudi.parent==-1)
			return;
		mudi=cacheList[mudi.parent];
	}
}

void FindPath(int sr,int sc,int dr,int dc)
{
	Node start;
	start.g=0;
	start.h=Hfun(sr,sc);
	start.f=start.g+start.h;
	start.r=sr;
	start.c=sc;
	start.parent=-1;
	
	nowList.push_front(start);
	laterList.clear();
	cacheList[HashKey(start)]=start;

	int flimit=Hfun(sr,sc);
	bool found=false;

	list<Node>* curlist=&nowList;
	list<Node>* nextlist=&laterList;
	while (!found&&(!laterList.empty()||!nowList.empty()))
	{
		int fmin=0x7fffffff;

		while (!curlist->empty())
		{
			Node node=curlist->front();
			curlist->pop_front();
			if (node.f>flimit)
			{
				fmin=min(node.f,fmin);
				nextlist->push_back(node);
				continue;
			}
			if (node.r==dr&&node.c==dc)
			{
				found=true;
				BestPath(node);
				break;
			}
			Kuozhan(node,*curlist);
		}
		flimit=fmin;
		list<Node>* tmp=curlist;
		curlist=nextlist;
		nextlist=tmp;
	}

	if (found)
		cout<<"找到路径\n";
	else
		cout<<"没有出路\n";
}

void ShowPath()
{
	int i,j;
	for (i=bestList.size();i>0;i--)
	{
		map[bestList.back().r][bestList.back().c]=8;
		bestList.pop_back();
	}
	for (i=0;i<R;i++)
	{
		for (j=0;j<C;j++)
		{
			cout<<map[i][j]<<" ";
		}
		cout<<endl;
	}
}

gistfile2.cpp

//test
int main( int argc,char* argv[] )
{
	freopen("in.txt","r",stdin);
	int i,j;
	cin>>R>>C;
	for (i=0;i<R;i++)
	{
		for (j=0;j<C;j++)
		{
			cin>>map[i][j];
			if (map[i][j]==5)
			{
				srcr=i,srcc=j;
				map[i][j]=1;
			}
			if (map[i][j]==6)
			{
				destr=i,destc=j;
				map[i][j]=1;
			}
		}
	}

	FindPath(srcr,srcc,destr,destc);
	freopen("out.txt","w",stdout);

	cout<<bestList.front().f<<endl;
	ShowPath();
	
	return 0;
}

input data

10 10
1 1 1 1 1 0 0 0 0 0
1 5 0 0 1 1 1 1 1 0
1 1 1 0 1 0 0 0 1 1
0 0 1 0 1 1 1 0 1 1
1 1 1 0 0 0 0 1 1 1
1 1 0 0 1 1 1 1 1 1
1 1 1 0 1 1 1 0 0 0
0 0 1 0 0 0 6 0 1 1
1 1 1 1 1 0 0 0 1 1
1 1 1 1 1 1 1 1 1 1

output data

17
1 8 8 8 8 0 0 0 0 0 
1 8 0 0 8 8 8 8 8 0 
1 1 1 0 1 0 0 0 8 1 
0 0 1 0 1 1 1 0 8 1 
1 1 1 0 0 0 0 8 8 1 
1 1 0 0 1 1 8 8 1 1 
1 1 1 0 1 1 8 0 0 0 
0 0 1 0 0 0 8 0 1 1 
1 1 1 1 1 0 0 0 1 1 
1 1 1 1 1 1 1 1 1 1 

good !

look

good job

good

useful

我就随便看看