具有扩张状态对象的c a*算法

为了解决以下问题,我正在尝试实现a*算法:

1. 我有一个初始状态
2. 我可以申请“行动”从一个州到另一个州
3. 我想用最少的行动达到最后的状态
4. 对给定状态应用操作很简单(=快速)
5. 整个状态是一个复杂的对象(内存大,克隆速度慢)

这个问题来自5/点。

事实上,当从当前状态中寻找可能的子级时,我不能每次都创建一个全新的状态,因为这样做代价太大(无论是在内存还是速度方面)。因此,我使用的是一个单独的状态,当将操作应用于前一个状态时,我会对其进行变异以反映结果状态。(我可以回滚操作)。我想用下面的方法实现a*

    //_state; //represent the "singleton" states that I can apply and rollback actions instead of cloning it
    while (openNodes.Any())
    {
        var currentNode = openNodes.DeQueue();
        currentNode.AdvanceFromStart(_state); //make _state such as all action on the path from the root to currentNode are played

        if (IsFinal(_state))
            return;

        AddToVisitedStates(_state);
        foreach(var transition in currentNode.GetPossibleActions())
        {
            var childNode = new Node(initialState:_state,action:transition.Action);
            //here _state is still reflecting the situation from the currentNode point of view
            childNode.ApplyAction(_state);
            //now _state reflect the situation from childNode point of view
            if (WasVisited(_state))
            {
                childNode.RollbackAction(_state);                
                continue;
            }

            if (childNode.CostToReachNode == 0 ||
                currentNode.CostToReachNode + transition.Cost < childNode.CostToReachNode)
            {
                childNode.CostToReachNode = node.CostToReachNode + transition.CostToReachNode;
                childNode.CostToReachFinal = childNode.CostToReachNode + HeuristicToReachFinalFromState(_state);
                openNodes.ReOrder(childNode);
            }
            if (!openNodes.Contains(childNode))
                openNodes.Add(childNode);

            childNode.RollbackAction(_state);
        }
        currentNode.RollbackToInitialState(_state);//make _state as initially setup
    }

我不喜欢这个解决方案。A*算法中有没有我遗漏的有用的东西?我还没有完成实现,你看到一些新的问题/一些需要提出的问题了吗?

也许a*不是正确的算法,我愿意接受任何不同的结果。

PD:如果相关的话,这是一个C实现