C++

Forum

 
Priority Queue Help

elite zero (106)
I am implementing a priority queue based on heuristic for an 8 piece puzzle program. I am wondering how to easily do this. How would I go about pushing in the nodes and having the priority based on Heuristic instead of the strings.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 

struct node
{
	string currentState;	// Holds currentState of this node
	int depth;				// Depth of node in tree
	int heuristic;			// How many nodes are out of place
};

void Heuristic_Calc(node& puzzle)	// Calculate Heuristic
{
	// This function calculates the heuristic based on 
	// Out-of-Place tiles by comparing the current node
	// to the Goal State and adding accordingly.

	for (int i = 0; i < 9; i++)
	{
		if (puzzle.currentState[i] == goalState[i])
		{
			continue;	// Compare to Goal
		}
		else
		{
			puzzle.heuristic++;	// Cost Increase
		}
	}
}//end void Heuristic_Calc

void ASS(node puzzle)	// A* Search w/ Heuristic
{
	// Expand(temp, ASSFringe);
	// This search algorithm will use cost based on
	// out of place tiles (Heuristic).

	clock_t t1, t2;				// Timer Start 
	t1 = clock();

	int check = 0;				// Double Check for solution
	counter = 0;
	priority_queue <node> ASSFringe;
	vector <node> container;
	node temp;

	Check_Map(puzzle);
	ASSFringe.push(puzzle);			// Initial Node

	while (!ASSFringe.empty())		// Loop for Expansions
	{
		temp = ASSFringe.top();		// Copy node at front of queue
		ASSFringe.pop();			// Pop node from queue

		if (Check_Goal(temp) == 0)	// Check Goal for return
		{
			// Goal found returns 0
			cout << "Goal Found at <" << temp.depth << "> Depth." << endl;
			cout << "Depth-First Search Complete!" << endl;
			check++;
			goto endASS;
		}
		else
		{
			// Goal not found returns 1
			container.clear();
			Expand(temp, container);	// Expand for next node

			for (int i = 0; i < container.size(); i++)	// Transfer
			{
				ASSFringe.push(container[i]);
			}

		}
	}

	if (ASSFringe.empty())	// Empty Queue
	{
		if (check == 0)		// Solution never found
		{
			cout << "Priority_Queue Empty! No Solution!" << endl;
		}
	}

	endASS:					// Branch if goal found

	visited_states.clear();	// Clear Map after search ends

	t2 = clock();			// Timer End

	timer(t1, t2);			// Run Time Calculator

}
elite zero (106)
I know, I know.... Never use 'goto' spaghetti code. I'll be removing it later, just increasing the speed so it doesnt want to empty the fringe
cire (8284)
Presumably you've implemented an operator< somewhere that makes this compile. Either have that operator return a value based on the heuristic, or supply a custom comparison function object to the priority_queue.
elite zero (106)
Not sure how I would go about that. I've seen a few examples of it, but I don't quite understand it.
cire (8284)
Custom comparison function:
1
2
3
4
 
bool less_heuristic(const node& a, const node& b)
{
    return a.heuristic < b.heuristic;
}


Priority queue which uses it:
priority_queue <node, std::vector<node>, decltype(less_heuristic)> ASSFringe(less_heuristic);

Or, if your compiler doesn't support C++11 (for decltype):
priority_queue <node, std::vector<node>, bool(*)(const node&, const node&)> ASSFringe(less_heuristic);
Last edited on
elite zero (106)
So, as this inserts nodes into the Fringe it will compare them with the other nodes and prioritize them as higher or lower based on the heuristic count.

I must be hitting an infinite loop somewhere in my code. Not sure, thank you for the info and help.
Topic archived. No new replies allowed.