SHARE
TWEET

Untitled

a guest Oct 13th, 2019 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void getSolution(int initial[N][N])
  2. {
  3.     int loopStop = 0; //for debug
  4.     //for keeping track which goal matching board has the lowest cost
  5.     Board* bestSolution = NULL;
  6.     int bestCost = INT_MAX;
  7.     //create queue to find next board to process based on lowest hueristic
  8.     priority_queue<Board*, vector<Board*>,compare > pq, pq2;
  9.    
  10.     //find intial coords of zero
  11.     int X,Y;
  12.     bool foundZero = false;
  13.     for(int i = 0; i < N; i++)
  14.     {
  15.         for(int j = 0; j < N; j++)
  16.         {
  17.             if(initial[i][j] == 0)
  18.             {
  19.                 foundZero = true;
  20.                 X = i;
  21.                 Y = j;
  22.                 break;
  23.             }
  24.         }
  25.         if(foundZero)
  26.             break;         
  27.     }
  28.     if(debug)cout<<X<<", "<<Y<<endl;
  29.     //create root node
  30.     Board* root = new Board(initial,X,Y);
  31.     //check if intial is already equal to goal
  32.     if(root->isGoal(GOAL))
  33.     {
  34.         cout << "initial state is equal to the goal state";
  35.         exit(-1);
  36.     }
  37.     else
  38.     {
  39.         //calc cost of root node and push to queue
  40.         root->hueristic = manhattanSum(root)+root->costFromRoot;
  41.         if(debug){cout<<"root board:"<<endl;printBoardStats(root);}
  42.         pq.push(root);
  43.        
  44.         //for debug
  45.         Board* lowest = NULL;
  46.  
  47.         while(!pq.empty() && loopStop < 3)
  48.         {
  49.             //******************************************************
  50.             //******************************************************
  51.             pq2 = priority_queue<Board*, vector<Board*>,compare >(pq);
  52.             if (debug)
  53.             {
  54.                 cout << "******************" <<endl<<"whats in priority queue"<<endl;
  55.                 while(!pq2.empty())
  56.                 {
  57.                     printBoardOnly(pq2.top());
  58.                     pq2.pop();
  59.                 }
  60.                 // for(int i = 0; i < stack.size(); i++)
  61.                 //  pq.push(stack[i]);
  62.                 cout<<"end of priority queue"<<endl<<"**************"<<endl;
  63.             }
  64.             //******************************************************
  65.             //******************************************************
  66.             int thisMoveCost = 0;
  67.             lowest = pq.top();
  68.             if(debug){cout<<"\ntop should be"<<endl;printBoardOnly(pq.top());cout<<"^^^top^^^\n";}
  69.             pq.pop();
  70.             if(debug){cout<<"board with lowest hueristics"<<endl;printBoardStats(lowest);}
  71.            
  72.             //check if this is the best solution
  73.             if(lowest->isGoal(GOAL) && lowest->costFromRoot < bestCost)
  74.             {
  75.                 if(debug)cout<<"gonna set best solution"<<endl;
  76.                 bestSolution = lowest;
  77.                 bestCost = lowest->costFromRoot;
  78.             }
  79.             else if (!lowest->isGoal(GOAL))
  80.             {              
  81.                 //add neighbors
  82.                 if (lowest->zeroX > 0)
  83.                 {
  84.                     Board* up = newBoard(lowest);
  85.                     int newX = up->zeroX - 1;
  86.                     thisMoveCost = up->array[newX][up->zeroY];
  87.                     up->array[up->zeroX][up->zeroY] = up->array[newX][up->zeroY];
  88.                     up->array[newX][up->zeroY] = 0;
  89.                     //if(debug){cout<<"up move:"<<endl;printBoardStats(up);}
  90.                     if(!up->isEqual(lowest->parent))
  91.                     {
  92.                         up->costFromRoot = thisMoveCost + lowest->costFromRoot;
  93.                         up->manhattan = manhattanSum(up);
  94.                         up->hueristic = up->manhattan + up->costFromRoot;
  95.                         up->zeroX = newX;
  96.                         if(debug){cout<<"up move:"<<endl;printBoardStats(up);}
  97.                         pq.push(up);
  98.                     }  
  99.                 }
  100.                    
  101.                 if (lowest->zeroY > 0)
  102.                 {
  103.                     Board* left = newBoard(lowest);
  104.                     int newY = left->zeroY - 1;
  105.                     thisMoveCost = left->array[left->zeroX][newY];
  106.                     left->array[left->zeroX][left->zeroY] = left->array[left->zeroX][newY];
  107.                     left->array[left->zeroX][newY] = 0;
  108.                     //if(debug){cout<<"left move:"<<endl;printBoardStats(left);}
  109.                     if(!left->isEqual(lowest->parent))
  110.                     {
  111.                         left->costFromRoot = thisMoveCost + lowest->costFromRoot;
  112.                         left->manhattan = manhattanSum(left);
  113.                         left->hueristic = left->manhattan + left->costFromRoot;
  114.                         left->zeroY = newY;
  115.                         if(debug){cout<<"left move:"<<endl;printBoardStats(left);}
  116.                         pq.push(left);
  117.                     }
  118.                 }
  119.                
  120.                 if (lowest->zeroX < 2)
  121.                 {
  122.                     Board* down = newBoard(lowest);
  123.                     int newX = down->zeroX + 1;
  124.                     thisMoveCost = down->array[newX][down->zeroY];
  125.                     down->array[down->zeroX][down->zeroY] = down->array[newX][down->zeroY];
  126.                     down->array[newX][down->zeroY] = 0;
  127.                     //if(debug){cout<<"down move:"<<endl;printBoardStats(down);}
  128.                     if(!down->isEqual(lowest->parent))
  129.                     {
  130.                         down->costFromRoot = thisMoveCost + lowest->costFromRoot;
  131.                         down->manhattan = manhattanSum(down);
  132.                         down->hueristic = down->manhattan+ down->costFromRoot;
  133.                         down->zeroX = newX;
  134.                         if(debug){cout<<"down move:"<<endl;printBoardStats(down);}
  135.                         pq.push(down);
  136.                     }
  137.                 }
  138.                
  139.                 if (lowest->zeroY < 2)
  140.                 {
  141.                     Board* right = newBoard(lowest);
  142.                     int newY = right->zeroY + 1;
  143.                     thisMoveCost = right->array[right->zeroX][newY];
  144.                     right->array[right->zeroX][right->zeroY] = right->array[right->zeroX][newY];
  145.                     right->array[right->zeroX][newY] = 0;
  146.                     //if(debug){cout<<"right move:"<<endl;printBoardStats(right);}
  147.                     if(!right->isEqual(lowest->parent))
  148.                     {
  149.                         right->costFromRoot = thisMoveCost + lowest->costFromRoot;
  150.                         right->manhattan = manhattanSum(right);
  151.                         right->hueristic = right->manhattan+ right->costFromRoot;
  152.                         right->zeroY = newY;
  153.                         if(debug){cout<<"right move:"<<endl;printBoardStats(right);}
  154.                         pq.push(right);
  155.                     }
  156.                 }
  157.             }
  158.             loopStop++;//for debug
  159.         }
  160.     }
  161.     printSolution(bestSolution);
  162.     cout << "The total cost for this path is " << bestSolution->costFromRoot;
  163. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top