llist.h

VC中利用人工智能解决八迷宫问题。这是一个很有趣的人工智能小程序

// llist.h By Chris Stones
// Class to hold a variable number of CStates.

enum SIDE { LEFT, RIGHT };

struct Link {
	Link   *LeftLink;
	Link   *RightLink;
	CState *Data;
};

class CLList {

private:

	Link* LeftPointer;
	Link* RightPointer;
	double ListLen;
	
	void EmptyUsedMemory() {
		// Removes EVERYTHING from memory (Links, AND the state data they point to)
		CState *temp;
		while(!IsListEmpty()) {
			temp = Pop(LEFT);
			delete temp;
		}
	}

public:
	
	class ERROR_CANT_POP_EMPTY_LIST{}; // Error Exception

	CLList() {
		// initialise all private variables
		LeftPointer  = new Link;
		RightPointer = new Link;
		ListLen      = 0;

		LeftPointer->LeftLink = 0;
		LeftPointer->RightLink = RightPointer;
		RightPointer->RightLink = 0;
		RightPointer->LeftLink = LeftPointer;
	}

	~CLList() {
		EmptyUsedMemory();
	}

	inline double GetListLen() {
		return ListLen;
	}
	
	inline bool IsListEmpty() {
		return (LeftPointer->RightLink == RightPointer);
	}

	CState* Pop(SIDE Side) {

		Link  ForReturn;
		Link* ForDelete;
			
		if (!IsListEmpty()) {

			ListLen--;
			if (Side == LEFT) {

				ForReturn                      = *(LeftPointer->RightLink);
				ForDelete                      = LeftPointer->RightLink;
				LeftPointer->RightLink         = ForReturn.RightLink;
				ForReturn.RightLink->LeftLink  = LeftPointer;

			}
			else {

				ForReturn                      = *(RightPointer->LeftLink);
				ForDelete                      = RightPointer->LeftLink;
				RightPointer->LeftLink         = ForReturn.LeftLink;
				ForReturn.LeftLink->RightLink  = RightPointer; 
			}

			delete ForDelete;
			return ForReturn.Data;
		}
		return 0;
	}

	void Push(SIDE Side, CState* What) {
		Link* NewLink = new Link;
		NewLink->Data = What;
		ListLen++;

		if (Side == LEFT) {

			NewLink->RightLink           = LeftPointer->RightLink;
			NewLink->LeftLink            = LeftPointer;
			LeftPointer->RightLink       = NewLink;
			NewLink->RightLink->LeftLink = NewLink;
		}
		else {

			NewLink->RightLink           = RightPointer;
			NewLink->LeftLink            = RightPointer->LeftLink;
			RightPointer->LeftLink       = NewLink;
			NewLink->LeftLink->RightLink = NewLink;
		}
	}

	CState* PopBestByHeuristics(HEURISTIC heuristic) {

		int   BestValue=9999;
		int   Temp=0;
		Link* BestState = 0;
		Link* Current = LeftPointer;
		CState* ForReturn = 0;
		
		if(!IsListEmpty()) {

		// Find BEST State By Wrong tile number heuristic
			while(Current->RightLink != RightPointer) {

				Current = Current->RightLink;
				
				if(heuristic == MANHATTAN_DISTANCE) {
					Temp = Current->Data->GetManhattanDistance();
				}
				else {
					Temp = Current->Data->GetWrongTiles();
				}

				if(Temp < BestValue) {
					BestValue = Temp;
					BestState = Current;
				}
			}

			// POP the value out the List.
			// Make the link to the right's left pointer point to the link on the left.
			BestState->RightLink->LeftLink = BestState->LeftLink;
			BestState->LeftLink->RightLink = BestState->RightLink;

			ForReturn = BestState->Data;
			delete BestState;

			return ForReturn;
		}
		return 0;
	}

	CState* PeekByBestHueristics(HEURISTIC heuristic) {
	

		int   BestValue=9999;
		int   Temp=0;
		Link* BestState = 0;
		Link* Current = LeftPointer;
		CState* ForReturn = 0;
		
		if(!IsListEmpty()) {

		// Find BEST State By Wrong tile number heuristic
			while(Current->RightLink != RightPointer) {

				Current = Current->RightLink;
				
				if(heuristic == MANHATTAN_DISTANCE) {
					Temp = Current->Data->GetManhattanDistance();
				}
				else {
					Temp = Current->Data->GetWrongTiles();
				}

				if(Temp < BestValue) {
					BestValue = Temp;
					BestState = Current;
				}
			}

			ForReturn = BestState->Data;

			return ForReturn;
		}
		return 0;
	}

};