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.
Die entsprechend erechneten Erträge (die Indizes entsprechen der Indizes in der Erztabelle):
Und mein Gauß-Algorithmus:
In $differences stehen die geforderten Ergebniswerte der entsprechenden Gleichungen.
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
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] => 5 ) )
[2] => Array ( [name] => Veldspar [volume] => 0.1 [needed] => 100 [yield] => Array ( [Tritanium] => 415 ) )
)
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 ) )
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;
}
}
}
LG
Kommentar