A * 계발 식 알고리즘 시 뮬 레이 션 실현

A * 알고리즘 의 핵심 은 평가 함수 입 니 다. 평가 함 수 를 통 해 대 가 를 확정 하고 같은 점 을 거 쳤 을 때 대가 가 가장 적은 경로 만 유지 합 니 다.
예:
A  B  C 
E  F  G  여섯 시  우 리 는 A 에서 C 에 도착 해 야 한다. 그러나 어떤 경 로 는 A - B - C, A - E - F - B - C, A - E - B - C 등 이 몇 가지 경 로 를 모두 B 를 거 쳐 야 한다. 잠시 동안 인접 한 두 점 의 직접적인 대 가 를 모두 1 로 정 하고 대각선 을 2 로 정 하면 위의 세 경 로 는 B 를 거 친 대가 가 각각 1, 3, 3 이 므 로 우 리 는 작은 값 만 저장 하면 된다. 왜냐하면 이 대 가 는 의심 할 여지없이 가장 적 기 때문이다.우리 가 모든 노드 를 경 로 했 을 때 이 대가 가 현재 가장 작은 것 인지, 가장 작은 것 인지, 아니면 그것 을 상관 하지 않 는 것 이 바로 A * 알고리즘 의 정수 입 니 다!  다음은 코드 시 뮬 레이 션 실현 입 니 다. 설명 하지 않 겠 습 니 다.

//        A*    
//////////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <assert.h>

using namespace std;

const int nMapWidth = 8;
const int nMapHeight = 8;

struct Node
{
	int nEnable;
	int nNodeMark;
	int nValue;
	int x;
	int y;
	Node():nEnable(0),nNodeMark(0),nValue(0),x(0),y(0){};
};

std::map<int ,int > m_OpenList;
std::map<int ,int > m_CloseList;
std::vector<int>    m_KeyList;
Node m_MapNode[nMapWidth][nMapHeight];

//  openlist          
void ComputerRound(int curx,int cury);
//          OPenList 
void AddNodeToOpenList(Node* pNode,int nNum);
//    
void Print(Node pNode[][nMapHeight]);

void Print(Node pNode[][nMapHeight])
{
	for (int n = 0; n < nMapWidth; ++n)
	{
		for(int m = 0; m < nMapHeight; ++m)
		{
			if (m == 0)
				cout<<endl;
			if (n == 0)
				cout<<pNode[n][m].nEnable/*<<"("<<" "<<pNode[n][m].nNodeMark<<")"*/<<"   ";
			else
				cout<<pNode[n][m].nEnable/*<<"("<<pNode[n][m].nNodeMark<<")"*/<<"   ";
		}
	}
}
//          OPenList 
void AddNodeToOpenList(Node* pNode,int nNum)
{
	if(!pNode || !(pNode->nEnable))
		return;
	if (m_OpenList.empty())
	{
		m_OpenList[pNode->nNodeMark] = nNum;
		m_KeyList.push_back(pNode->nNodeMark);
	}
	else
	{
		std::map<int,int>::iterator itr = m_OpenList.find(pNode->nNodeMark);
		if (itr == m_OpenList.end())
		{
			std::map<int,int>::iterator itrQ = m_CloseList.find(pNode->nNodeMark);
			if (itrQ != m_CloseList.end())
			{
				if (nNum < (*itrQ).second)
				{
					m_CloseList.erase(itrQ);
				}
				else
					return;
			}
			else
			{
				m_OpenList[pNode->nNodeMark] =nNum;
				m_KeyList.push_back(pNode->nNodeMark);
			}
		}
		else
		{
			if ((*itr).second > nNum)
			{
				m_OpenList[pNode->nNodeMark] =nNum;
			}
		}
	}
}
// openlist            CloseList 
void AddNodeToCloseList(Node* pNode,int nNum)
{
	if(!pNode)
		return;
	if (m_CloseList.empty())
	{
		m_CloseList[pNode->nNodeMark] = nNum;
		ComputerRound(pNode->x,pNode->y);
	}
	else
	{
		std::map<int,int>::iterator itrB = m_CloseList.find(pNode->nNodeMark);
		if(itrB == m_CloseList.end())
		{
			std::map<int,int>::iterator itrO = m_OpenList.find(pNode->nNodeMark);
			if (itrO != m_OpenList.end())
			{
				if ((*itrO).second < nNum)
				{
					return;
				}
				else
				{
					std::vector<int>::iterator itrK = std::find(m_KeyList.begin(),m_KeyList.end(),(*itrO).first);
					if (itrK != m_KeyList.end())
						m_KeyList.erase(itrK);
					m_OpenList.erase(itrO);	
				}
			}
			else
			{
				m_CloseList[pNode->nNodeMark] += nNum;
				ComputerRound(pNode->x,pNode->y);
			}
		}
		else
		{
			if (nNum < m_CloseList[pNode->nNodeMark])
				m_CloseList[pNode->nNodeMark] = nNum;
		}
	}
}
//         
void TryNode(int nx,int ny,int curx, int cury)
{
	if (nx < 0 || ny < 0 || nx >= nMapWidth || ny >= nMapWidth)
		return;

	if (m_MapNode[nx][ny].nEnable == 0)
		return;

	int nNum = abs(nx - curx) + abs(ny - cury);
	std::map<int,int>::iterator itr = m_CloseList.find(m_MapNode[curx][cury].nNodeMark);
	if(itr != m_CloseList.end())
		nNum += (*itr).second;
	AddNodeToOpenList(&(m_MapNode[nx][ny]),nNum);
}

#define  DesX  3
#define  DesY 4
void   ComputerRound(int   curx,int   cury)   
{//                

	TryNode(curx,cury+1,curx,cury);   

	TryNode(curx+1,cury,curx,cury);   

	TryNode(curx+1,cury+1,curx,cury);   

	TryNode(curx-1,cury,curx,cury);   

	TryNode(curx-1,cury-1,curx,cury);   

	TryNode(curx-1,cury+1,curx,cury);   

	TryNode(curx,cury-1,curx,cury);   

	TryNode(curx+1,cury-1,curx,cury);    
}
void main()
{
	
	int nMark = 0;
	for (int n = 0; n < nMapWidth; ++n)
	{
		for(int m = 0; m < nMapHeight; ++m)
		{
			if (n != 2 || m == 3 || m == 1)
				m_MapNode[n][m].nEnable = 1;
			if (n == 4 && (m != 6))
				m_MapNode[n][m].nEnable = 0;
			m_MapNode[n][m].nNodeMark = ++nMark;
			m_MapNode[n][m].x = n;
			m_MapNode[n][m].y = m;
		}
	}
	Print(m_MapNode);

	AddNodeToCloseList(&(m_MapNode[1][1]),0);
	
	std::map<int,int>::iterator itr;
	while(!m_KeyList.empty())
	{
		itr = m_OpenList.find(*(m_KeyList.begin()));
		int nV = (*itr).first;
		int nNum =(*itr).second;
		std::vector<int>::iterator itrK = std::find(m_KeyList.begin(),m_KeyList.end(),(*itr).first);
		if (itrK != m_KeyList.end())
			m_KeyList.erase(itrK);
		itr = m_OpenList.erase(itr);

		
		AddNodeToCloseList(&(m_MapNode[(nV-1)/nMapWidth][(nV-1)%nMapWidth]),nNum);
	
	}

	cout<<endl;
	cout<<endl;
	std::map<int,int>::iterator itrC;
	for (int n = 0; n < nMapWidth; ++n)
	{
		for(int m = 0; m < nMapHeight; ++m)
		{
			if (m == 0)
				cout<<endl;
			if (m == 1 && n == 1)
			{
				cout<<"ST"<<" ";
				continue;
			}
			itrC = m_CloseList.find(m_MapNode[n][m].nNodeMark);
			if (itrC != m_CloseList.end())
			{
				cout<<(*itrC).second<<"   ";
			}
			else
				cout<<"0"<<"   ";
		}
	}
	getchar();
}