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