Hallo AutoIt Community,
nach langer Zeit mal wieder ein Skript von mir.
Das Skript ist für das Algorithmusentwurfsverfahren Greedy, mit dem Ich mich wegen der Teilnahme am Informatikwettbewerb Brandenburg auseinandersetzen muss.
In den nächsten Tagen folgen 2 weitere Skripte zum Divide-and-Conquer und Plane-sweeping Verfahren.
Bis zum 4 März sollte ich alles rauf und runter und im Schlaf können, dann sehen meine Chancen für die Einzelaufgabe gut aus.
Der Code ist eine Sauerei aber der Algorithmus funktioniert.
Errechnet wird einmal das Lokale Optimum des Greedy Algorithmus, sofern ein globales Optimum existiert wird dieses auch berechnet und eine Gegenüberstellung gemacht.
Greedy
;Beispiel zum Greedy Algorithmus
#include <Array.au3>
Global $Number = Random(1130, 123912, 1)
Global $Steps[3] = ["Errechnende Zahl: " & $Number]
Global $GValidNumbers[10] = [1, 5, 10, 25, 30, 45, 60, 90, 100, 110]
Global $ValidNumbers[10] = [1, 5, 10, 25, 30, 45, 60, 90, 100, 110]
Global $EndNumber
Global $Anumber = _GetHighest($GValidNumbers)
Global $Timer = TimerInit()
While $EndNumber < $Number
Do
$EndNumber += $Anumber
If $EndNumber <= $Number Then
_ArrayAdd($Steps, $Anumber)
EndIf
Until $EndNumber > $Number
$EndNumber -= $Anumber
$Anumber = _GetHighest($GValidNumbers)
WEnd
$Timer = Round(TimerDiff($Timer))
$Steps[2] = "Benötigte Zeit: " & $Timer & " ms"
$Steps[1] = "Benötigte Schritte: " & UBound($Steps) - 3
_ArrayDisplay($Steps, "Greedy Algorithmus")
$iArray = _GOptimum($ValidNumbers, $Number)
If Not IsArray($iArray) Then
MsgBox(0, "Global", "Kein globales Optimum. (Ausnahme 1)")
Exit
Else
_ArrayDisplay($iArray, "Globales Optimum")
EndIf
MsgBox(0, "Auswertung", "Greedy - Lokales Optimum"&@CRLF&"Benötigte Zeit: "&$Timer&" ms"&@CRLF&"Benötigte Steps: "&UBound($Steps)-3&@CRLF&@CRLF&"Globales Optimum"&@CRLF&"Benötigte Zeit: "&$iArray[2]&"ms"&@CRLF&"Benötigte Steps: "&UBound($iArray) -3)
Func _GetHighest(ByRef $Array);Ermittelt höchsten Wert des Arrays mit Nummern (nur für Greedy)
Local $Highest = $Array[0]
For $i = 0 To UBound($Array) - 1
If $Array[$i] > $Highest Then $Highest = $Array[$i]
Next
For $i = 0 To UBound($Array) - 1
If $Array[$i] = $Highest Then $Array[$i] *= -1
Next
Return $Highest
EndFunc ;==>_GetHighest
Func _GOptimum($Array, $Number)
$GTimer = TimerInit()
Local $EArray[1] = [0]
Local $UArray = $Array
For $i = 0 To UBound($UArray) - 1
If IsInt($Number / $UArray[$i]) Then
_ArrayAdd($EArray, $UArray[$i])
$EArray[0] = 1
EndIf
Next
Local $Highest = _GetHighest($EArray)
If $Highest = 1 Then
Return False
Else
Local $Steps[3] = ["Errechnende Zahl: " & $Number]
Local $LNumber
Do
_ArrayAdd($Steps, $Highest)
$LNumber += $Highest
Until $LNumber = $Number
$Steps[2] = "Benötigte Zeit: " & Round(TimerDiff($GTimer)) & " ms"
$Steps[1] = "Benötigte Schritte: " & UBound($Steps) - 3
Return $Steps
EndIf
EndFunc ;==>_GOptimum
Anhang:
Eine kurze Erläuterung des Greedy Algorithmus
Der Greedy Algorithmus ,oder auch "gieriger Algorithmus" genannt, ist gedacht um mit einem Schritt so viel wie möglich zu lösen.
Wir wollen z.B. 15 Äpfel zurückgeben, haben 11er Packs, 5er Packs 1 Apfel.
Da der Greedy Algorithmus mit einem Schritt so viel zurückgeben will, wie möglich, nimmt er natürlich als erstes das 11er Pack und dann jeweils 4 einzelne Äpfel.
Damit hätte er 5 Teilschritte gebraucht, deshalb ist dies das Lokale Optimum.
Zum Verhältnis wäre das globale Optimum: 5 + 5 + 5 = 15, 3 Teilschritte.
Hat man allerdings z.B. 79 ct Rückgeld so nimmt der Greedy Algorithmus: 50 + 20 + 5 + 2 + 2 + 1; somit ist er am schnellsten und optimalsten Lösung gekommen.
MfG Mattthias