Comment utiliser un algorithme glouton pour obtenir la solution optimale du problème de l'arbre couvrant minimum en PHP ?

Comment utiliser un algorithme glouton pour obtenir la solution optimale du problème de l'arbre couvrant minimum en PHP ?

Le problème du Minimum Spanning Tree consiste à trouver un sous-arbre dans un graphe non orienté connecté tel que ce sous-arbre contienne tous les sommets du graphe et que la somme des poids de toutes les arêtes soit la plus petite. L'algorithme glouton est l'une des méthodes courantes pour résoudre ce problème. Il trouve progressivement la solution optimale globale en sélectionnant à chaque fois la solution optimale actuelle.

Tout d'abord, nous devons définir une classe de graphe pour stocker la structure du graphe et les poids des arêtes. Voici un exemple de code PHP :

class Graph {
    public $vertices; // 图的顶点集合
    public $edges; // 图的边集合

    public function __construct() {
        $this->vertices = [];
        $this->edges = [];
    }

    public function addVertex($v) {
        $this->vertices[] = $v;
    }

    public function addEdge($v1, $v2, $weight) {
        $this->edges[] = [$v1, $v2, $weight];
    }
}

Ensuite, nous pouvons utiliser l'algorithme glouton pour résoudre le problème de l'arbre couvrant minimum. Voici un exemple d'implémentation simple de l'algorithme Prim :

function prim($graph) {
    $vertices = $graph->vertices;
    $edges = $graph->edges;
    $numVertices = count($vertices);
    
    $visited = []; // 记录已访问的顶点
    $selectedEdges = []; // 记录最小生成树的边集合
    
    // 从第一个顶点开始构建最小生成树
    $visited[] = $vertices[0];
    
    while (count($selectedEdges) < $numVertices - 1) {
        $minWeight = PHP_INT_MAX; // 初始化最小权值为无穷大
        $selectedEdge = null; // 当前选中的边
        
        // 遍历已访问的顶点，找到与之相连的最小权值边
        foreach ($visited as $v) {
            foreach ($edges as $edge) {
                if ($v == $edge[0] && !in_array($edge[1], $visited) && $edge[2] < $minWeight) {
                    $minWeight = $edge[2];
                    $selectedEdge = $edge;
                }
            }
        }
        
        // 将选中的边添加到最小生成树的边集合中
        $selectedEdges[] = $selectedEdge;
        
        // 将与选中的边相连的顶点标记为已访问
        $visited[] = $selectedEdge[1];
    }
    
    return $selectedEdges;
}

// 创建一个示例图
$graph = new Graph();
$graph->addVertex('A');
$graph->addVertex('B');
$graph->addVertex('C');
$graph->addVertex('D');
$graph->addEdge('A', 'B', 1);
$graph->addEdge('A', 'C', 5);
$graph->addEdge('B', 'C', 3);
$graph->addEdge('B', 'D', 4);
$graph->addEdge('C', 'D', 2);

// 调用prim函数求解最小生成树
$selectedEdges = prim($graph);

// 输出最小生成树的边集合
foreach ($selectedEdges as $edge) {
    echo $edge[0] . '-' . $edge[1] . ': ' . $edge[2] . PHP_EOL;
}

Dans le code ci-dessus, nous créons d'abord une instance de graphe, puis ajoutons des informations sur les sommets et les arêtes. Ensuite, appelez la fonction prim pour résoudre l'arbre couvrant minimum et afficher l'ensemble de bords de l'arbre couvrant minimum. Dans l'exemple ci-dessus, l'ensemble minimum de bords d'arbre couvrant que nous obtenons est : A-C : 5, B-A : 1, C-D : 2.

À travers les exemples ci-dessus, nous pouvons voir que l'algorithme glouton est une méthode relativement simple et efficace pour obtenir la solution optimale au problème du spanning tree minimum en PHP. Bien entendu, dans les applications réelles, il peut y avoir des structures et des exigences graphiques plus complexes. À ce stade, nous devons procéder aux ajustements et améliorations appropriés en fonction des caractéristiques du problème spécifique.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!