swift - 如何修改递归分支定界树节点遍历以避免堆栈溢出？

Question

我创建了以下 Swift 3 程序来使用深度优先分支定界解决背包问题。不幸的是，它是递归的。它适用于多达 20 个项目。但是对于更多的项目(30个或更多)，它会导致堆栈溢出。 (~5400 级深)。

如何改为非递归版本？

public enum BBState {
case created
case active
case death
}

public enum Direction {
case left
case right
}

public class BBTreeNode {
    public var artifact: Artifact
    public var nodeState: BBState
    public var level: Int
    public var path = [Direction]()
    public var weightSoFar: Int = 0
    public var optimumTotalValue: Int = 0
    public var estimatedOptTotalValue: Double = 0
    public weak  var parentNode: BBTreeNode?
    public var leftNode: BBTreeNode?
    public var rightNode: BBTreeNode?
    static var currentCompletedOptimumValues: Int = 0
    static var currentCompletedEstimatedOptimumValues: Double = 0
    static var currentOptimumPath = [Direction]()

// Initialization
public convenience init(artifact: Artifact) {
    self.init(artifact: artifact, level: 0, path: [], parent: nil, left: nil, right: nil)
}

public init(artifact: Artifact, level: Int, path: [Direction], parent: BBTreeNode?, left: BBTreeNode?, right: BBTreeNode?) {
    self.artifact = artifact
    self.nodeState = .created
    self.level = level
    self.path = path
    self.parentNode = parent
    self.leftNode = left
    self.rightNode = right
}


// BBTree
private func createRootAndInitiateBB(artifacts: [Artifact]) {
    // return the optimum value from Depth-First branch and bound
    let maxLevel = artifacts.count - 1
    print("Max Level: \(maxLevel)")
    // create dummy Root to start
    let root = BBTreeNode(artifact: Artifact(value: 0, weight: 0))
    root.estimatedOptTotalValue = Knapsack.calculateEstimatedOptimumValue(availableArtifacts: artifacts)
    root.nodeState = .active
    root.weightSoFar = Knapsack.capacity
    // loop here for each artifact# - selected(left) / not(right) but going recursive to left until
    // we have death node, then backtrack

    func depthFirstTraversal(bbNode: BBTreeNode?, level: Int) {
        guard let bbNode = bbNode  // not nil
            else { return }

        guard level <= maxLevel
            else { return }

        print("Currently on path: \(bbNode.path)")

        // switch to active is last state was created, else ignore
        bbNode.nodeState =  bbNode.nodeState == .created ?  .active : bbNode.nodeState

        // stop traverse down and traceback if calculated optimumValue < currentCompletedOptimumValue,
        // or current weightSoFar is 0 or less than 0
        // move up to parent
        if bbNode.estimatedOptTotalValue < BBTreeNode.currentCompletedEstimatedOptimumValues ||
            bbNode.weightSoFar < 0 {
            print("Case for estimatedOptTotalValue: \(bbNode.estimatedOptTotalValue) < currentCompletedEstimatedOptimumValues: \(BBTreeNode.currentCompletedEstimatedOptimumValues)")
            print("Or weight: \(bbNode.weightSoFar) < 0" )
            bbNode.nodeState = .death
            // remove references to children
            bbNode.leftNode = nil
            bbNode.rightNode = nil
            depthFirstTraversal(bbNode: bbNode.parentNode, level: bbNode.level - 1)
        } else if (bbNode.leftNode?.nodeState == .death &&
                bbNode.rightNode?.nodeState == .death) || level ==  maxLevel  {

            print("Case for no more path available. Need to backtrack. ")
            print("Current level: \(level)")
            // stop, record and traceback if at maxLevel or when both children are death
            if level == maxLevel && bbNode.estimatedOptTotalValue > BBTreeNode.currentCompletedEstimatedOptimumValues {
                BBTreeNode.currentCompletedEstimatedOptimumValues = bbNode.estimatedOptTotalValue
                BBTreeNode.currentCompletedOptimumValues = bbNode.optimumTotalValue
                BBTreeNode.currentOptimumPath = bbNode.path
                print("blah...")
                print("Candidate for optimum: \(bbNode.path)")
                print("Completed optimum path: \(BBTreeNode.currentCompletedOptimumValues)")
                print("Estimated optimum value: \(BBTreeNode.currentCompletedEstimatedOptimumValues)")
            }
            bbNode.nodeState = .death
            // remove references to children
            bbNode.leftNode = nil
            bbNode.rightNode = nil
            let _ = path.popLast()
            depthFirstTraversal(bbNode: bbNode.parentNode, level: bbNode.level - 1)
        } else if bbNode.leftNode == nil {
            // create left child
            print("create left child node")
            let childLeftNode = createBBNode(leftChild: true, parent: bbNode, path: bbNode.path + [.left])
            bbNode.leftNode = childLeftNode
            depthFirstTraversal(bbNode: childLeftNode, level: childLeftNode.level)
        } else if bbNode.rightNode == nil {
            // create right child
            print("create right child node")
            let childRightNode = createBBNode(leftChild: false, parent: bbNode, path: bbNode.path + [.right])
            bbNode.rightNode = childRightNode
            depthFirstTraversal(bbNode: childRightNode, level: childRightNode.level)
        }

    }

    func createBBNode(leftChild: Bool, parent: BBTreeNode, path: [Direction]) -> BBTreeNode {
        let level = parent.level + 1
        let artifact = artifacts[level]
        let newBBNode = BBTreeNode(artifact: artifact, level: level, path: path, parent: parent, left: nil, right: nil )
        if leftChild {
            newBBNode.optimumTotalValue =  parent.optimumTotalValue + artifact.value
            newBBNode.estimatedOptTotalValue = parent.estimatedOptTotalValue
            newBBNode.weightSoFar = parent.weightSoFar - artifact.weight
        } else {
            // right direction, we don't pick this item
            // Artifact is a struct,  artifacts is array of Artifact, so we don't need to write deep copy 
            var artifactsWithItemsRemoved = artifacts

            print("Current artifacts before any removal: \(artifactsWithItemsRemoved)")
            print("for path \(newBBNode.path) we are going to remove artifacts...")
            // first remove the dummy artifact 
            artifactsWithItemsRemoved.remove(at: 0)
            // now the real artifacts
            var indexOfItemForRemoval = [Int]()
            for (index,direction) in path.enumerated() {
                if direction == .right {
                    indexOfItemForRemoval.append(index)
                }
            }
            // actual removal, need to reverse the array index to avoid out of range index
            for idx in indexOfItemForRemoval.reversed() {
                artifactsWithItemsRemoved.remove(at: idx)
            }

            print("Artifacts with items removed: \(artifactsWithItemsRemoved)")

            newBBNode.optimumTotalValue = parent.optimumTotalValue
            newBBNode.estimatedOptTotalValue = Knapsack.calculateEstimatedOptimumValue(availableArtifacts: artifactsWithItemsRemoved)
            print("New estimatedOptValue for \(newBBNode.path) is \(newBBNode.estimatedOptTotalValue)")
            // no weight deduction if we don't pick
            newBBNode.weightSoFar = parent.weightSoFar
        }
        return newBBNode
    }

    depthFirstTraversal(bbNode: root, level: 0)
}

public func findOptimumValueAndPath(artifacts: [Artifact]) -> (Int,[Direction], Double) {
    createRootAndInitiateBB(artifacts: artifacts)
    return (BBTreeNode.currentCompletedOptimumValues, BBTreeNode.currentOptimumPath, BBTreeNode.currentCompletedEstimatedOptimumValues)
}

}

====更新===

我设法将递归深度限制在某个限制，例如 4000，一旦计数器达到限制，我将 currentNode 信息返回给调用者。然后使用 currentNode 再次调用“depthFirstTraversal”，但使用全新的堆栈。

这是我的做法:

1. 将 createRootAndInitiateBB 和 findOptimumValueAndPath 移至调用方。

2. 更新 depthFirstTraversal 以具有如下函数签名:

   static func depthFirstTraversal(bbNode: BBTreeNode, level: Int, recursiveCount: Int, complete completeFlag: inout Bool, currentProcessedNode: inout BBTreeNode)

3. 其他一些重构工作可保持计数器计数并修复一些错误。 (例如 parentNode 不应该是弱的，否则在返回到调用者之后，currentNode 的父节点变为 nil，我们失去回溯到更高节点的能力)。

Answer 1

这是一个可能会帮助您或其他人偶然发现您的问题的示例:

https://github.com/evansjohnson/DynamicProgrammingWithSwift/blob/master/ProblemSet8Playground.playground/Contents.swift