0
デプスファーストブランチとバウンドを使ってナップザック問題を解決するために、次のSwift 3プログラムを作成しました。残念ながら、再帰的です。それは20項目までうまく動作します。しかし、アイテム数（30以上）が増えると、スタックオーバーフローが発生します。 （〜5400レベルの深さ）。スタックオーバーフローを避けるために再帰的ブランチとバインドされたツリーノードのトラバーサルを変更するにはどうすればよいですか？
非再帰バージョンに変更するにはどうすればよいですか？私は4000のような一定の限界に再帰の深さを制限するために管理
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)
}
}
====更新===
は、カウンタリーチ制限一度、私はcurrentNodeの情報を呼び出し側に返さ。次に、currentNodeを使って新しい深層スタックを使って 'depthFirstTraversal'をもう一度呼び出します。ここで
は、私はそれを行う方法は次のとおりです。呼び出し元に
- 移動createRootAndInitiateBBとfindOptimumValueAndPath。
静的depthFirstTraversal FUNC（bbNode：BBTreeNode、レベル：INT、recursiveCount：INT、完全completeFlag：ブールINOUT、currentProcessedNode：BBTreeNode INOUT）
一部
更新depthFirstTraversalは、このような関数シグネチャを有すること他のリファクタリング作業でカウンタ数を維持し、いくつかのバグを修正しました。 （例えば、parentNodeは弱くあってはならず、そうでなければ呼び出し側に戻り、currentNodeの親はnilになり、より高いノードにバックトラックする能力を失う）。ここで