Minimax Python - wie man effizient wechselnde Max- und Minwerte in einem Baum findet

Der folgende Code, den ich benutze, um einen Baum zu minimieren, sieht schrecklich aus. Sicherlich gibt es eine Möglichkeit, dies zu vereinfachen und eine Funktion statt eines int.MaxValueMinimax Python - wie man effizient wechselnde Max- und Minwerte in einem Baum findet

if depth%2==1: 
    min = 9999 
    for child in currentRoot.children: 
     if child.score < min: 
      min = child.score 
    currentRoot.score = min 
else: 
    max = -9999 
    for child in currentRoot.children: 
     if child.score > max: 
      max = child.score 
    currentRoot.score = max 
return currentRoot.score

Quelle

2016-06-22 Josh

Eine Idee, die ich hatte, war die Partitur auf jeder Ebene des Baumes negieren, so konnte ich immer den max finden, aber das scheint etwas heikel Recht zu bekommen, da ich sie alle reversed haben könnte und muß Minuten finden abhängig von der Tiefe der Blätter. – Josh

Siehe verknüpfte Frage https://stackoverflow.com/questions/37980286/python-find-minimum-object-using-special-comparator – Josh

Zuerst nicht min und max für Variable verwenden Namen als Schatten die eingebauten Funktionen. Zweitens, verwenden Sie diese integrierten Funktionen!

Sie können Ihre aktuelle Logik verwenden, um auszuwählen, ob Sie min oder max möchten, und dann einen Generatorausdruck übergeben, um auf die Punktzahl jedes Kindes zuzugreifen.

measure = min if depth % 2 else max 
return measure(c.score for c in currentRoot.children)

Quelle

2016-06-22 16:50:02

Oh, viel sauberer als meins. Ich fühle mich, als ob ich mich iterativ näherte, aber du hast mich dazu gebracht. – dwanderson

Wenn OP die Voreinstellung '-999' oder' 999' benötigt (wenn keine Kinder vorhanden sind), könnte man wahrscheinlich 'default = 999 wenn Tiefe% 2 else -999' verwenden und dann wie' measure (c. punkte für c in root.children, default = default) '(Ich habe auch gelernt, dass' min'/'max' ein' default' kw!) haben – dwanderson

@dwanderson Das ist cool! Ich brauche diese Standardwerte jedoch nicht. Aber ich würde gerne wissen, was der Standard ist, wenn ich es leer lasse – Josh

def findNewScore(isEven): 
    if isEven: 
     root.score = max([c.score for c in root.children] + [-999]) 
    else: 
     root.score = min([c.score for c in root.children] + [999]) 
    return root.score

oder auch nur zu verwenden:

def findNewScore(isEven): 
    s = sorted(c.score for score in root.children) 
    if isEven: 
     root.score = max([-999, s[-1]]) 
    else: 
     root.score = min([999, s[0]]) 
    return root.score

Quelle

2016-06-22 16:49:49 dwanderson

Minimax Python - wie man effizient wechselnde Max- und Minwerte in einem Baum findet

Antwort

Verwandte Themen