我的数据结构:
class Cell
{
public:
struct CellLink
{
Cell *cell;
int weight;
};
public:
int row;
int column;
vector<CellLink> neighbors;
State state;
int totalCost = 0;
};
主要功能:
void AI::IterativeDeepeningSearch(Cell* cell)
{
Cell* temp;
int bound = 0;
while (true)
{
naturalFailure = false;
temp = IDShelper(cell, bound);
if (IsExit(temp))
{
break;
}
bound++;
}
}
helper :
Cell* AI::IDShelper(Cell* cell, int bound)
{
Cell* temp = cell;
SetEnvironment(cell, State::visited);
PrintEnvironment();
if (bound > 0)
{
for (int i = 0; i < cell->neighbors.size(); i++)
{
temp = IDShelper(cell->neighbors[i].cell, bound - 1);
if (IsExit(temp))
{
naturalFailure = true;
return temp;
}
}
}
else if (IsExit(cell))
{
return cell;
}
return temp;
}
我对迷宫进行了迭代深化搜索。问题是在 21x21 迷宫中完成搜索实际上需要几个小时,而其他算法需要几秒钟。
我知道 IDS 应该很慢,但它应该那么慢吗?
最佳答案
我想我明白为什么这很慢了。
在你的助手中,你像这样访问邻居:
if (bound > 0)
{
for (int i = 0; i < cell->neighbors.size(); i++)
{
temp = IDShelper(cell->neighbors[i].cell, bound - 1);
if (IsExit(temp))
{
naturalFailure = true;
return temp;
}
}
}
但您永远不会使用过去的结果。您将某些内容标记为已访问,但从不检查它是否已被访问。
关于c++ - 迭代深化搜索应该那么慢吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20033969/