transpositiontable.cpp

来自「N数码问题 本程序采用全局择优的启发式搜索算法来解决八数码难题」· C++ 代码 · 共 87 行

// TranspositionTable.cpp: implementation of the CTranspositionTable class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "TranspositionTable.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CTranspositionTable::CTranspositionTable()
{
	InitHashKey();
}

CTranspositionTable::~CTranspositionTable()
{

}

//生成32位随机数
LONG CTranspositionTable::Rand32()
{
    return rand()^((LONG)rand()<<15)^((LONG)rand()<<30);
}

void CTranspositionTable::InitHashKey()
{
	int i,j,k;
	
	srand((unsigned)time(NULL));
	
	//填充随机数组
	for(i=0;i<10;i++)
		for(j=0;j<3;j++)
			for(k=0;k<3;k++)
				m_nHashKey32[i][j][k]=Rand32();
}

void CTranspositionTable::EnterHashTable(BYTE byBoard[][3])
{
	int iPos=CalHashKey(byBoard);

	if(m_byBoardList[iPos][0][0]>=9 || m_byBoardList[iPos][0][0]<0)
		goto Copy;

	while(m_byBoardList[iPos][0][0]<9 && m_byBoardList[iPos][0][0]>=0)
		iPos=(iPos+1)%1000;

Copy:
	memcpy(m_byBoardList[iPos],byBoard,9);
}

bool CTranspositionTable::LookUpHashTable(BYTE byBoard[][3])
{
	int iPos=CalHashKey(byBoard);

	if(m_byBoardList[iPos][0][0]>=9 || m_byBoardList[iPos][0][0]<0)
		return 0;

	if(memcmp(m_byBoardList[iPos],byBoard,9))
	{
		int iPosBU=iPos;

		while(memcmp(m_byBoardList[iPos],byBoard,9) && iPosBU!=iPos)
			iPos=(iPos+1)%1000;

		if(memcmp(m_byBoardList[iPos],byBoard,9))
			return 0;

		return 1;
	}

	return 1;
}

UINT CTranspositionTable::CalHashKey(BYTE byBoard[][3])
{
	UINT uiRet=0;

	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			uiRet+=m_nHashKey32[byBoard[i][j]][i][j];

	return uiRet%1000;
}