Оптимизация для 8 решений головоломки для хранения в структуре деревьев

У меня есть широкий поиск в первую очередь, чтобы найти лучшее решение для 8 головоломки. Чтобы убедиться, что я не выполняю один и тот же вызов функции при одном и том же движении головоломки, я создал древовидную структуру. Он не хранит головоломку, он просто создает путь в дереве для 9 значений для 9 слотов в головоломке. Вот код:

static const int NUM_NODES = 9;

class TreeNode
{
public:
TreeNode *mylist[NUM_NODES];
TreeNode()
{
for (int x = 0; x < NUM_NODES; ++x)
mylist[x] = nullptr;
}
};

class Tree
{
private:
TreeNode *mynode;
public:
Tree()
{
mynode = new Node();
}
bool checkOrCreate(const Puzzle &p1)
{
Node *current_node = mynode;
bool found = true;
for (int x = 0; x < PUZZLE_SIZE; ++x)
{
for (int y = 0; y < PUZZLE_SIZE; ++y)
{
int index_value = p1.grid[x][y];
if (current_node->mylist[index_value] == nullptr)
{
found = false;
current_node->mylist[index_value] = new Node();
current_node = current_node->mylist[index_value];
}
else
current_node = current_node->mylist[index_value];
}
}
return found;
}
};

static Node* depth_Limited_Search(Problem &problem, int limit)
{
mylist.reset();
return recursive_Depth_Search(&Node(problem.initial_state, nullptr, START), problem, limit);
}
static Node *recursive_Depth_Search(Node *node, Problem &problem, int limit)
{
if (problem.goal_state == node->state)
return node;
else if (limit == 0)
return nullptr;
if (mylist.checkOrCreate(node->state)) //if state already exists, delete the node and return nullptr
return nullptr;
std::unique_ptr<int> xy(node->state.getCoordinates());
int xOfSpace = xy.get()[0];
int yOfSpace = xy.get()[1];
set <Action> actions = problem.actions(node->state); //gets actions
for (auto it = begin(actions); it != end(actions); ++it)
{
Action action = *it;
Node &child = child_node(problem, *node, action);
Node *answer = recursive_Depth_Search(&child, problem, limit - 1);
if (answer != nullptr)
return answer;
}
return nullptr;
}
static Node& child_node(Problem problem, Node &parent, Action action)
{
Node &child = *(new Node());
child.state = problem.result(parent.state, action);
child.parent = &parent;
child.action = action;
child.path_cost = parent.path_cost + problem.step_cost(parent.state, action);
return child;
}

Puzzle& result(const Puzzle &state, Action action)
{
// return a puzzle in the new state after perfroming action
Puzzle &new_state = *(new Puzzle(state));
int r = state.getCoordinates()[0], c = state.getCoordinates()[1];
if (action == UP)
new_state.swap(r, c, r - 1, c);
else if (action == RIGHT)
new_state.swap(r, c, r, c + 1);
else if (action == DOWN)
new_state.swap(r, c, r + 1, c);
else if (action == LEFT)
new_state.swap(r, c, r, c - 1);
return new_state;
}

Я использовал это по ширине, а также по ограниченному поиску с использованием рекурсии для решения. Использование этой структуры для хранения всех возможных решений для этих алгоритмов занимает много времени. Я считаю, что это как-то связано с распределением времени. Это причина? Я думал о том, чтобы попытаться просто создать кусок памяти, а затем назначить узлу этот адрес памяти вместо того, чтобы позволить программе сделать это. Это было бы лучшим решением, и как бы я это сделал? (Так как я использовал это для нескольких поисков, и все они занимают много времени, я не включил этот код.)

0

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …