我正在嘗試評估決議樹的最終結果（True或者False）。在這樣的樹中，節點對應于邏輯運算子 (AND或OR)，而葉對應于原子條件，即Trueor False。我用嵌套串列表示我的樹：
# Generic class from which all operators derive
class Node(list):
@property
def label(self):
return self.__class__.__name__
def __repr__(self):
return self.label super().__repr__()
# Subclass for each operator
class AND(Node):
pass
class OR(Node):
pass
在決議和評估原子條件后，我得到以下物件：
AND[OR[AND[True, True], AND[False, True, False], AND[True, True, AND[True, False]]], AND[True, True, True, False], OR[True, False]]
當然，對于 AND 節點，所有條件都必須為真。對于 OR 條件，只有一個必須為真。最后，我想得到最終結果，True或者False說是所有這些子條件合并的結果。
這是我為實作此邏輯而撰寫的代碼：
def evaluate(root, parent = None):
if(depth(root) == 0):
return root
if depth(root) > 1:
return root.__class__(evaluate(item, root) for item in root)
elif depth(root) == 1:
operator = root.label
if(operator == "AND"):
if False not in root:
return True
if(operator == "OR"):
if True in root:
return True
return False
我的主要功能只是呼叫evaluate(result)
我得到的結果是：
AND[OR[True, False, AND[True, True, False]], False, True]
我認為我現在需要的是在評估孩子的結果后做一些反向 DFS。就像解構嵌套串列以獲得最終結果一樣。
有什么建議嗎？
uj5u.com熱心網友回復：
在您現有的evaluate功能中，這就是問題所在 -
if depth(root) > 1:
return root.__class__(evaluate(item, root) for item in root)
在每個節點上，我們應該operator在該節點的子節點回傳的值上使用 at 該節點。
這是該函式的相應偽代碼evaluate（我無法測驗它，因為問題中缺少完整的類定義）
def evaluate(root):
if(depth(root) == 0):
# would we ever go in this block?
return root
elif depth(root) == 1:
operator = root.label
if(operator == "AND"):
return all(root)
elif(operator == "OR"):
return any(root)
return False
# depth(root) > 1
if root.label == "AND":
return all(evaluate(child) for child in root)
elif root.label == "OR"
return any(evaluate(child) for child in root)
使用all()andany()將有助于盡早縮短評估，以防我們遇到在給定節點處導致明確答案的子樹。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/427978.html
上一篇：大O表示法和凱撒密碼