Implementierungsbeispiel eines PHP-Greedy-Algorithmus

In diesem Artikel wird hauptsächlich der in PHP implementierte Greedy-Algorithmus vorgestellt, das Konzept und das Prinzip des Greedy-Algorithmus kurz erläutert und die relevanten Bedienfähigkeiten des in PHP implementierten Greedy-Algorithmus anhand von Beispielen analysiert it

Die Beispiele in diesem Artikel beschreiben den in PHP implementierten Greedy-Algorithmus. Teilen Sie es als Referenz mit allen:

Hintergrundeinführung: Gieriger Algorithmus und Datenstruktur-Wissensdatenbankalgorithmus sind der Algorithmus, der unserem Leben am nächsten kommt sind immer gierig. Das Design dieses Algorithmus entspricht also sehr gut der menschlichen Natur. Der Grund, warum ich das sage, ist, dass Menschen absichtlich oder unabsichtlich gierige Algorithmen verwenden, um Probleme in ihrem Leben zu lösen. Am häufigsten ist es, Wechselgeld zu geben. Jeder hat nie gelernt, wie man Wechselgeld macht, aber wenn in allen Konfessionen genug Geld vorhanden ist, wird jeder die gleiche Kombination finden, um das Geld zu bekommen, das er braucht. Tatsächlich ist hier der Greedy-Algorithmus am Werk.

Designidee: Die Designidee der Greedy-Methode kann aus zwei Aspekten verstanden werden, nämlich intuitiv und mathematisch. Das intuitive Verständnis des Greedy-Algorithmus besteht darin, die schnellste Methode zur Lösung des Problems zu verwenden. Hier ist „schnell“ das Hauptziel. Im obigen Beispiel des Geldwechsels beträgt das Wechselgeld beispielsweise 6,6 Yuan. Dann besorgen Sie sich zunächst ein 5-Yuan-Ticket, denn so wächst das gesammelte Geld am schnellsten. Wenn der RMB einen Nennwert von 6 Yuan hat, werden Sie auf jeden Fall die 6 Yuan wählen, anstatt zwei andere zu verwenden, um 6 Yuan zu bilden. Mathematisch gesehen besteht der gierige Algorithmus darin, bei der Beurteilung auf die aktuell optimale Lösung abzuzielen, ähnlich der Optimierungsmethode „Steepest Descent“. In . Der Vorteil dieser Methode besteht darin, dass das Problem extrem schnell gelöst werden kann und grundsätzlich in einem Durchgang erledigt werden kann.

Fehler des Algorithmus: So wie eine Person nicht zu gierig sein kann, weist der gierige Algorithmus selbst schwerwiegende Mängel auf, die seinen Anwendungshintergrund stark einschränken. Da der Algorithmus die lokal optimale Lösung annimmt, berücksichtigt er zukünftige Probleme nicht. Das ist wie bei einem egoistischen Menschen. Obwohl er in kurzer Zeit einige Vorteile erzielen kann, ist es auf lange Sicht schwierig, große Erfolge zu erzielen. Natürlich ist die Gesellschaft sehr komplex und es kann Menschen geben, die weiterhin egoistisch sind und ein ziemlich gutes Leben führen. Dies spiegelt sich im Algorithmus wider. In einigen Fällen (siehe unten) kann der gierige Algorithmus die optimale Lösung erhalten, was natürlich eine gute Sache für das Algorithmusdesign ist.

/*
* 贪婪算法
* $arr   array  处理数组
* $volume  int   盒子容量
*/
function greedy($arr, $volume){
    $box = array();
    $boxNum = 0;
    $num = count( $arr );
    for ($i = 0; $i < $num; $i++) {
      $boxCode = true;
      for ($j = 0; $j < $boxNum; $j++) {
        if ($arr[$i] + $box[$j][&#39;v&#39;] <= $volume) {
          $box[$j][&#39;v&#39;] += $arr[$i];
          $box[$j][&#39;k&#39;][] = $i;
          $boxCode = false;
          break;
        }
      }
      if ($boxCode) {
        $box[$boxNum][&#39;v&#39;] = $arr[$i];
        $box[$boxNum][&#39;k&#39;][] = $i;
        $boxNum++;
      }
    }
    return $box;
}

Das obige ist der detaillierte Inhalt vonImplementierungsbeispiel eines PHP-Greedy-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!