โปรแกรมเติมผังเกม Min-max ใน Python

สมมติว่าเรามีไบนารีทรีที่แสดงถึงสถานะเกมของเกมที่มีผู้เล่นสองคน ทุกโหนดภายในจะเติมด้วย 0 และค่าการออกจากระบบแสดงถึงคะแนนสิ้นสุด ผู้เล่น 1 ต้องการเพิ่มคะแนนสุดท้ายให้สูงสุดในขณะที่ผู้เล่น 2 ต้องการลดคะแนนสุดท้ายให้น้อยที่สุด ผู้เล่น 1 จะทำการเคลื่อนไหวบนโหนดที่ระดับคู่เสมอ และผู้เล่น 2 จะทำการเคลื่อนไหวในระดับคี่เสมอ เราต้องกรอกเลขฐานสองด้วยคะแนนที่ได้ โดยถือว่าผู้เล่นทั้งคู่เล่นได้ดีที่สุด

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์ที่ได้จะเป็น

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน helper() สิ่งนี้จะทำการรูท h, currentHeight
• ถ้ารูทว่างก็
  • คืนสินค้า
• ตัวช่วย (ด้านซ้ายของรูท h ความสูงปัจจุบัน + 1)
• ตัวช่วย (ด้านขวาของรูท, h, ความสูงปัจจุบัน + 1)
• ถ้ากระแสสูง
• ถ้า currentHeight เท่ากัน
  • หากด้านซ้ายของรูทและด้านขวาของรูทไม่เป็นค่าว่าง
    • ค่าของรูท :=ค่าสูงสุดของค่าทางซ้ายของรูท ค่าของค่าทางขวาของรูท
  • มิฉะนั้น เมื่อรูทด้านซ้ายไม่เป็นโมฆะ
    • ค่าของรูท :=ค่าของรูทด้านซ้าย
  • มิฉะนั้น เมื่อสิทธิ์ของรูทไม่เป็นโมฆะ
    • ค่าของรูท :=ค่าของสิทธิ์ของรูท
• มิฉะนั้น
  • หากด้านซ้ายของรูทและด้านขวาของรูทไม่เป็นค่าว่าง
    • ค่าของรูท :=ค่าต่ำสุดของค่าทางซ้ายของรูท ค่าของค่าของรูททางขวา
  • มิฉะนั้น เมื่อรูทด้านซ้ายไม่เป็นโมฆะ
    • ค่าของรูท :=ค่าของรูทด้านซ้าย
  • มิฉะนั้น เมื่อสิทธิ์ของรูทไม่เป็นโมฆะ
    • ค่าของรูท :=ค่าของสิทธิ์ของรูท

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
class Solution:
   def helper(self, root, h, currentHeight):
      if not root:
         return
         self.helper(root.left, h, currentHeight + 1)
         self.helper(root.right, h, currentHeight + 1)
         if currentHeight < h:
            if currentHeight % 2 == 0:
               if root.left and root.right:
                  root.val = max(root.left.val, root.right.val)
               elif root.left:
                  root.val = root.left.val
               elif root.right:
                  root.val = root.right.val
               else:
                  if root.left and root.right:
                     root.val = min(root.left.val, root.right.val)
                  elif root.left:
                     root.val = root.left.val
                  elif root.right:
                     root.val = root.right.val
   def height(self, root):
      if not root:
         return 0
         return 1 + max(self.height(root.left), self.height(root.right))
   def solve(self, root):
         h = self.height(root)
         self.helper(root, h, 0)
         return root
   def print_tree(root):
      if root is not None:
         print_tree(root.left)
         print(root.val, end = ', ')
      print_tree(root.right)
ob = Solution()
root = TreeNode(0)
root.left = TreeNode(3)
root.right = TreeNode(0)
root.right.left = TreeNode(0)
root.right.right = TreeNode(0)
root.right.left.left = TreeNode(-3)
root.right.right.right = TreeNode(4)
print_tree(ob.solve(root))

อินพุต

root = TreeNode(0)
root.left = TreeNode(3)
root.right = TreeNode(0)
root.right.left = TreeNode(0)
root.right.right = TreeNode(0)
root.right.left.left = TreeNode(-3)
root.right.right.right = TreeNode(4)

ผลลัพธ์

3, 3, -3, -3, -3, 4, 4,