具有扩展状态对象的 C# A* 算法

Question

我正在尝试实现 A* 算法以解决以下问题:

1. 我有一个初始状态
2. 我可以应用“ Action ”从一种状态前进到另一种状态
3. 我想以最少的 Action 达到最终状态
4. 将 Action 应用到给定状态很简单 (=fast)
5. 整个状态是一个复杂的对象(=内存巨大且克隆速度慢)

问题来自第 5/点。

的确，当从当前状态中寻找可能的子状态时，我不能每次都创建一个全新的状态，因为它的成本太高(无论是内存还是速度)。因此，我使用的是单一状态，当我对之前的状态应用操作时，我会改变它以反射(reflect)结果状态。 (我能够回滚一个 Action )。我正在考虑使用以下内容实现 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# 实现的

Answer 1

您可以通过在每个对象中存储而不是状态，而是从导致它的初始状态开始采取的决策序列，使其看起来更像普通的 A*。当你想处理一个状态时，查看导致当前状态的决策顺序，回溯到你需要进入的状态的共同祖先，然后沿着那组记录的决策进行下去。这种变化的成本至多是某个常数因子乘以决策树的深度。如果这是大量分支和平衡的，它可能不会那么深。

另一种选择是 https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search 的某个版本或有限差异搜索，使用迄今为止(从以前的迭代中)找到的最佳答案以及 A* 启发式算法来避免可能无法得出可能答案的节点。当您在(修剪后)当前对差异或深度的限制实际上并没有阻止您调查您想要的每个节点时完成一次通过，您就知道您已经找到了最佳答案。