0

我有一个广度优先搜索来找到一个 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;
}

我已经在广度和深度有限的搜索中使用了它，使用递归来解决。使用这种结构来存储这些算法的所有可能解决方案需要很长时间。我相信这与分配需要时间有关。是这个原因吗？我正在考虑尝试创建一块内存，然后为节点分配该内存地址，而不是让程序来做。那将是最好的解决方案，我将如何做到这一点？（由于我已经在多次搜索中使用了它并且它们都需要很长时间才能执行，所以我没有包含该代码。）

4

0 回答 0