Ankündigung

Einklappen
Keine Ankündigung bisher.

Optimierungsproblem im Mehrdimensionalen

Einklappen

Neue Werbung 2019

Einklappen
X
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Optimierungsproblem im Mehrdimensionalen

    Hallo zusammen,
    ich stehe momentan vor einem eher mathematischen Problem, wo ich allerdings nicht weiß wie genau ich das möglichst gescheit in PHP umsetzen kann.

    Ich habe mich daran versucht einen Rechner zu schreiben, der einem anhand eines mehrdimensionalen Arrays eine optimale Lösung präsentieren soll.
    Kurz als Hintergrund:
    In einem Spiel kann man verschiedene Erze abbauen, die dann jeweils unterschiedlichen Ertrag an Mineralien haben. Dabei kann ein Erz sowohl nur ein Mineral liefern aber auch mehrere verschiedene mit entsprechend verschiedenen Erträgen.
    Optimierung heißt in diesem Fall also, das möglichst wenig Erz(-volumen) abgebaut werden soll, um eine geforderte Menge an Mineralien zu erhalten.

    Zu diesem Zweck habe ich bereits einen Gauß-Algorithmus geschrieben, allerdings spuckt dieser mir am Ende lediglich "eine" Lösung aus, aber nicht die optimale.
    Soweit ich das sehen konnte kommt das daher, das ich das Array stur durchlaufe, ohne auf mögliche Maximalwerte der Erträge einzugehen. Hier weiß ich allerdings nicht, wie ich das anstellen kann ohne den Ablauf des Gauß-Algorithmus zu stören.
    Daher glaube ich das nicht mit dem Gauß-Algorithmus arbeiten kann..?
    Ich weiß auch das es einige Lösungsverfahren im für Optimierungsprobleme im n-dimensionalen gibt. Allerdings sind die doch teilweise sehr abstrakt und ich weiß nicht wie ich die in PHP umsetzen kann (mit Ableitungen etc.).

    Ich hoffe ihr könnt mir da helfen.

    Zur Veranschaulichung jetzt noch das, was ich bisher habe:

    Die Erztabelle (sind nicht alle, aber mehr habe ich bisher noch nicht mit reingenommen):
    Das Volumen ist das Volumen einer Erzeinheit, "needed" bedeutet man braucht 100 Einheiten für einen Stack und der Ertrag ("yield") bezieht sich dann immer auf einen Stack.
    PHP-Code:
    $ores = Array ( 
    [
    0] => Array ( [name] => Plagioclase [volume] => 0.35 [needed] => 100 [yield] => Array ( [Pyrite] => 213 [Tritanium] => 107 [Mexallon] => 107 ) )
     [
    1] => Array ( [name] => Pyroxeres [volume] => 0.3 [needed] => 100 [yield] => Array ( [Tritanium] => 351 [Mexallon] => 50 [Pyrite] => 25 [Noxcium] => ) ) 
    [
    2] => Array ( [name] => Veldspar [volume] => 0.1 [needed] => 100 [yield] => Array ( [Tritanium] => 415 ) ) 

    Die entsprechend erechneten Erträge (die Indizes entsprechen der Indizes in der Erztabelle):
    PHP-Code:
    $mineralYields = Array ( 
    [
    Pyrite] => Array ( [0] => 2.13 [1] => 0.25 
    [
    Tritanium] => Array ( [2] => 4.15 [1] => 3.51 [0] => 1.07 
    [
    Mexallon] => Array ( [0] => 1.07 [1] => 0.5 
    [
    Noxcium] => Array ( [1] => 0.05 ) ) 
    Und mein Gauß-Algorithmus:
    In $differences stehen die geforderten Ergebniswerte der entsprechenden Gleichungen.
    PHP-Code:
    //building the equations
    $equations = array();
    foreach (
    $differences as $mineral => $value) {
        
    $equations[$mineral]["total"] = $value;
    }
    $oreCount 0;
    foreach (
    $mineralYields as $mineral => $ore) {
        foreach (
    $ore as $i => $yield) {
            if (isset(
    $equations[$mineral]) && !in_array($equations[$mineral], $yield)) {
                
    $oreCount++;
                
    $equations[$mineral][$i] = $yield;
            }
        }
    }

    //sorting the equations according to number of summands
    $equationSys = array();
    foreach (
    $equations as $mineral => $equation) {
        
    $summands sizeof($equation) - 1;
        while (isset(
    $equationSys[$summands])) {
            
    $summands++;
        }
        if (isset(
    $equation["total"])) {
            for (
    $i 1$i <= $oreCount$i++) {
                if (
    $equation[$i 1] > 0) {
                    
    $equationSys[$summands][$i] = $equation[$i 1];
                }
            }
            
    $equationSys[$summands][0] = $equation["total"];
            
    ksort($equationSys[$summands]);
        }
    }
    rsort($equationSys);

    //solving the equationsystem down
    for ($i 0$i sizeof($equationSys); $i++) {
        
    //for each following equation
        
    for ($ii $i 1$ii <= sizeof($equationSys); $ii++) {
            
    //if summand exists
            
    if (isset($equationSys[$ii][$i])) {
                
    $factor $equationSys[$ii][$ii] / $equationSys[$i][$ii];
                
    //eliminating the summand in following equation
                
    for ($iii 0$iii sizeof($equationSys[$ii]); $iii++) {
                    
    $equationSys[$ii][$iii] -= $equationSys[$i][$iii] * $factor;
                }
            }
        }
    }
    //solving the equationsystem up
    for ($i sizeof($equationSys) - 1$i 0$i--) {
        
    //for each following equation
        
    for ($ii $i 1$ii 0$ii--) {
            
    //if summand exists
            
    if (isset($equationSys[$i][$ii])) {
                
    $factor $equationSys[$i 1][$ii] / $equationSys[$i][$ii];
                
    //eliminating the summand in following equation
                
    for ($iii 0$iii sizeof($equationSys[$i 1]); $iii++) {
                    
    $equationSys[$i 1][$iii] -= $equationSys[$i][$iii] * $factor;
                }
            }
        }
    }

    //putting the solution to base form
    for ($i 0$i sizeof($equationSys); $i++) {
        for (
    $ii 1$ii sizeof($equationSys[$i]); $ii++) {
            if (
    $equationSys[$i][$ii] != 0) {
                for (
    $iii 0$iii sizeof($equationSys[$i]); $iii++) {
                    
    $equationSys[$i][$iii] /= $equationSys[$i][$ii];
                }
                break;
            }
        }

    Der Algorithmus funktioniert auf jeden Fall so wie er soll, bis auf die "Schwachstelle" der Optimierung, wobei er dafür ja auch erstmal nicht ausgelegt ist. Aber für Kritik bin ich hier natürlich auch offen.

    LG


  • #2
    Welche Frage soll dein Code denn letztlich beantworten? Das habe ich nicht wirklich verstanden. Vielleicht zeigst du dafür mal ein Beispiel.

    Ich verstehe auch nicht, was an der Problemstellung mehrdimensional ist. Du meinst, weil du eine Liste als Eintrag in einem Array hast? Oder geht es dir um irgendeine „mathematische“ Mehrdimensionalität?

    Wenn man sich Beispielcode ansehen soll, ist es immer ganz schlecht, wenn darin Variablen nicht deklariert/initialisiert sind. Da solltest du dem Leser wirklich mehr entgegenkommen.

    Kommentar


    • #3
      Der Code soll mir am Ende sagen wie viele Einheiten (bzw. Volumen) ich von jedem Erz abbauen müsste um die geforderten Werte zu erreichen.

      Die Mehrdimensionalität meine ich tatsächlich im mathematischen Sinne. Bzw fasse ich das so auf^^

      Als Beispiel:
      Wenn ich jetzt zum Beispiel 50 Noxcium und 415 Tritanium bräuchte, dann wäre es das beste wenn ich jeweils 100 Einheiten Pyroxeres abbaue und noch einmal 100 Einheiten Veldspar. (insgesamt also rund 40m³ Erz)
      Nach aktuellem Code spuckt er mir aber aus ich solle 300 Einheiten Pyroxeres abbauen (was zum einen 100m³ Erz sind und zusätzlich hat man recht viel "Abfall" dabei).
      Zum selber rumprobieren hier auch der Link zum testen, da stehen auch die Werte der einzelnen Erze ein wenig aufgehübschter: Test

      Und welche Variablen sind denn nicht deklariert? Ich dachte eigentlich ich hätte alles.. $ores ist das erste Array und $mineralYields ist das zweite Array welches ich gepostet hatte. Habe es aber noch einmal eindeutiger gemacht im Ausgangspost.
      Wenn ich noch was übersehen habe gibts das natürlich auch noch hinterher!

      Kommentar

      Lädt...
      X