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