Been a while since I posted computer junk no one understands. I know folks have been missing it so . . . #include #include using namespace std; #include pqvi.cpp int main() { Priority_Q B, *A = &B; Node new_node; Node *traveler; // travels the neighborhood int puzzle[3][3], tile; cout frontier_size); /* (j = 1; j frontier_size; j++){ printf(j= %d cost=%d\n,j,B -> array[j] -> cost); } // end for ExtractMaxPriority_Q(B); printf(after extracting frontier size now= %d\n,B->frontier_size); for(j=1;jfrontier_size;j++) { printf(j= %d cost= %d\n,j,B->array[j]->cost); } // end for InsertPriority_Q(B,&e); for(j=1;jfrontier_size;j++) printf(j=%d cost=%d\n,j,B->array[j]->cost);*/ system(PAUSE); return 0; } // end main #include #include //#include pq.h #include using namespace std; #define MAX_SIZE 500 class Node { public: Node (int state[3][3], int path_cost, Node parent); Node(); void swap(Node**, Node**); int SetGoalCost(); void SetNeighbors(); void copyState(int to_copy[][3], int master[][3]); void printNodeState(); //void FindBlank(int[], int); // members int cost; int state[3][3]; int path_cost; int goal_cost; Node *left; Node *right; Node *up; Node *down; Node *parent; }; // end class Node class Priority_Q{ public: Priority_Q (); Priority_Q InitializePriority_Q(); bool EmptyPriority_Q(); bool FullPriority_Q(); bool InsertPriority_Q(Node *Node); void HEAPIFY(Priority_Q *queue, int i); Node *ExtractMaxPriority_Q(Priority_Q *queue); // members Node *array[MAX_SIZE]; int frontier_size; }; // end class Priority_Q //Node constructor Node::Node (int state[3][3], int path_cost, Node parent){ copyState(state, this -> state); this -> path_cost = path_cost; //parent cost + 1 this -> goal_cost = SetGoalCost(); this -> cost = this -> path_cost + this -> goal_cost; this -> parent = &parent; } Node::Node(){//Default constructor does nothing } //Priority_Q constructor Priority_Q::Priority_Q () { Node *array[MAX_SIZE]; // array of pointers to nodes */ this -> frontier_size = 0; // number of nodes in a priority queue } bool Priority_Q::EmptyPriority_Q() { return this -> frontier_size == 0; } bool Priority_Q::FullPriority_Q() { return this -> frontier_size == (MAX_SIZE-1); } bool Priority_Q::InsertPriority_Q(Node *queued_Node) { if (queued_Node == NULL){/*Do nothing*/} else { this -> array[frontier_size] = queued_Node; this -> frontier_size++; } } // figures Manhattan distance int Node::SetGoalCost(){ int difference = 0; for (int horiz = 0; horiz < 3; horiz++) { for (int vert = 0; vert < 3; vert++){ difference += abs(horiz - (this -> state[horiz][vert] - 1)/3); difference += abs(vert - (this -> state[horiz][vert] - 1)%3); } // end for vert } // end for horiz return difference; } // end SetGoalCost() void Node::SetNeighbors(){ //find the blank to determine configuration of neighbhorhood int loc_z[2]; for (int horiz = 0; horiz < 3; horiz++) { for (int vert = 0; vert < 3; vert++){ if (this -> state[horiz][vert] == 0){ loc_z[0] = horiz; loc_z[1] = vert; } // end if } // end vert } // end horiz // begin creating neighbors int copy[3][3]; // holds state for new node for (int horiz = 0; horiz < 3; horiz++) { for (int vert = 0; vert < 3; vert++){ if ((abs(horiz - loc_z[0]) + abs(vert - loc_z[1]) == 1)) { if (loc_z[0] > 0) { // not already at top //create up copyState(copy, this -> state); copy[loc_z[0]][loc_z[1]] = this -> state[loc_z[0]][loc_z[1]-1]; // cell which previously held 0 now holds value of cell above copy[loc_z[0]][loc_z[1]-1] = 0; Node up_node (copy, (this -> cost + 1), *this); this -> up = &up_node; } else { this -> up = NULL; } // end up if (loc_z[0] < 2) { // bottom //create down copyState(copy, this -> state); copy[loc_z[0]][loc_z[1]] = this -> state[loc_z[0]][loc_z[1]+1]; // below copy[loc_z[0]][loc_z[1]+1] = 0; Node down_node (copy, (this -> cost + 1), *this); this -> down = &down_node; } else { this -> down = NULL; } // end down if (loc_z[1] > 0) {// left //create left copyState(copy, this -> state); copy[loc_z[0]][loc_z[1]] = this -> state[loc_z[0]-1][loc_z[1]]; // below copy[loc_z[0]-1][loc_z[1]] = 0; Node left_node (copy, (this -> cost + 1), *this); this -> left = &left_node; } else { this -> left = NULL; } // end left if (loc_z[2] < 2) { // right //create right copyState(copy, this -> state); copy[loc_z[0]][loc_z[1]] = this -> state[loc_z[0]+1][loc_z[1]]; // below copy[loc_z[0]+1][loc_z[1]] = 0; Node right_node (copy, (this -> cost + 1), *this); this -> right = &right_node; } else { this -> right = NULL; } // end right } } } } // end SetNeighbors*/ void Node::copyState(int copy[][3], int master[][3]) { for (int horiz = 0; horiz < 3; horiz++) { for (int vert = 0; vert < 3; vert++) { copy[horiz][vert] = master[horiz][vert]; } } } void Node::printNodeState() { int **num; for (int horiz = 0; horiz < 3; horiz++) { cout state[horiz][vert]; cout
Posted on: Sat, 29 Mar 2014 20:57:11 +0000