vendredi 2 octobre 2020

My A* Search algorithm enters an infinite loop when being executed, and I am really confused as to why. Can someone help me out?

I was asked, when given some pseudo-code, to program an A* Search algorithm in C++. I have programmed the algorithm, and it compiles successfully, but I am not getting the output that I need to receive to know that my algorithm is working properly. And now, i've been struggling for a couple days trying to ascertain the issues within in my programming.

Could someone kindly go over my current code and give me some tips and pointers on where I should look to fix my code? Or point me in the right direction?

Thanks a million if you choose to help me! I would greatly appreciate it.

Assignment Instructions, If Needed

SOME SIDE-NOTES: I replaced the int open and closed vectors with bool open and closed vectors. Just an fyi if you compare the instructions to my current code. Also, the "cout << " TEST 1 " << endl; // delete" statements were just me trying to test if the entire while loop and function was actually being executed. Thanks again if you choose to help me.

double ASTARSearch()
{

    const int nodesAmt = 8;
    char labels[nodesAmt] = {'S', 'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    
    double distanceMatrix[nodesAmt][nodesAmt] =
    {
        { INT_MAX, 3, INT_MAX, INT_MAX, 4, INT_MAX, INT_MAX, INT_MAX         },
        { 3, INT_MAX, 4, INT_MAX, 5, INT_MAX, INT_MAX, INT_MAX               },
        { INT_MAX, 4, INT_MAX, 4, INT_MAX, 5, INT_MAX, INT_MAX               },
        { INT_MAX, INT_MAX, 4, INT_MAX, INT_MAX, INT_MAX, 5, 1.4             },
        { 4, 5, INT_MAX, INT_MAX, INT_MAX, 2, INT_MAX, INT_MAX               },
        { INT_MAX, INT_MAX, 5, INT_MAX, 2, INT_MAX, 4, INT_MAX               },
        { INT_MAX, INT_MAX, INT_MAX, 5, INT_MAX, 4, INT_MAX, INT_MAX         },
        { INT_MAX, INT_MAX, INT_MAX, 1.4, INT_MAX, INT_MAX, INT_MAX, INT_MAX }
    };
    
    double heuristicCosts[nodesAmt] = {10, 10, 6, 1.4, 9, 7, 2, 0};
    
    vector<bool> open(nodesAmt);
    vector<bool> closed(nodesAmt);
    vector<int> gScore(nodesAmt, INT_MAX);
    vector<int> fScore(nodesAmt, INT_MAX);
    
    int cameFrom[nodesAmt];
    
    const int START = 0;
    
    open.at(START) = true;
    
    gScore[START] = 0;
    
    fScore[START] = heuristicCosts[START];
    
    cout << " TEST 1 " << endl; // delete
    
    bool empty = false;
    
    while (empty == false)
    {
        int minDist = INFINITY, current = 0;
        
        for (int i = 0; i < nodesAmt; i++)
        {
            if (open[i] == true)
            {
                if (fScore.at(i) < minDist)
                {
                    minDist = fScore.at(i);
                    current = i;
                }
            }
        }
        
        cout << " TEST 2 " << endl; // delete

        
        if (current == (nodesAmt - 1)) // all part 3 stuff
        {
            int to = nodesAmt - 1;
            int from = cameFrom[to];
            
            while (true)
            {
                cout << labels[from] << " -> " << labels[to] << endl;
                
                if (from == START)
                {
                    break;
                }
                
                to = from;
                from = cameFrom[to];
            }
            
            return 0;
        }
        
        cout << " TEST 3 " << endl; // delete

        
        open[current] = false;
        closed[current] = true;
        
        double neighbors[nodesAmt];
        
        for (int i = 0; i < nodesAmt; i++)
        {
            neighbors[i] = distanceMatrix[current][i];
        }
        
        for (int i = 0; i < nodesAmt; i++)
        {
            if (neighbors[i] == INT_MAX)
            {
                continue;
            }
            
            int g = gScore[current] + neighbors[i];
            int f = g + heuristicCosts[i];
            
            if (open[i] == false)
            {
                open[i] = true;
            }
            else if (open[i] == true && f >= fScore[i])
            {
                continue;
            }
            else if (open[i] == true && f < fScore[i])
            {
                cameFrom[i] = current;
                gScore[i] = g;
                fScore[i] = gScore[i] + heuristicCosts[i];
            }
            else if (closed[i] == true && f < fScore[i])
            {
                closed[i] = false;
                open[i] = true;
            }
            else
            {
                
            }
        }
        
        cout << " TEST 4 " << endl; // delete
        
        for (int i = 0; i < nodesAmt; i++)
        {
            int tally = 0;
            if (open[i] == false)
            {
                tally++;
            }
        
            if (tally == 8)
            {
                empty = true;
            }
            cout << " TEST 6 " << endl; // delete

        }

    }
    
    cout << " TEST 5 " << endl; // delete

    return 0;
}

Aucun commentaire:

Enregistrer un commentaire