Priority Queue Help

Nov 13, 2015 at 6:58pm
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

}
Nov 13, 2015 at 7:02pm
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
Nov 13, 2015 at 7:52pm
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.
Nov 13, 2015 at 8:00pm
Not sure how I would go about that. I've seen a few examples of it, but I don't quite understand it.
Nov 13, 2015 at 8:22pm
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 Nov 13, 2015 at 8:23pm
Nov 13, 2015 at 9:00pm
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.