Bagaimana untuk menggunakan algoritma tamak untuk mencapai penyelesaian optimum masalah pokok rentang minimum dalam PHP?

Bagaimana untuk menggunakan algoritma tamak untuk mencapai penyelesaian optimum kepada masalah pokok rentang minimum dalam PHP?

Masalah Pokok Rentang Minimum ialah mencari subpokok dalam graf tidak bersambung yang bersambung supaya subpokok ini mengandungi semua bucu dalam graf dan berat semua tepi ialah dan min. Algoritma tamak adalah salah satu kaedah biasa untuk menyelesaikan masalah ini secara beransur-ansur mencari penyelesaian optimum global dengan memilih penyelesaian optimum semasa setiap kali.

Pertama, kita perlu mentakrifkan kelas graf untuk menyimpan struktur graf dan pemberat tepi. Berikut ialah contoh kod 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];
    }
}

Seterusnya, kita boleh menggunakan algoritma tamak untuk menyelesaikan masalah pokok rentang minimum. Berikut ialah contoh pelaksanaan algoritma Prim yang mudah:

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;
}

Dalam kod di atas, kami mula-mula mencipta contoh graf, dan kemudian menambah maklumat bucu dan tepi. Seterusnya, panggil fungsi prim untuk menyelesaikan pokok rentang minimum dan keluarkan set tepi pokok rentang minimum. Dalam contoh di atas, set tepi pokok rentang minimum yang kami dapat ialah: A-C: 5, B-A: 1, C-D: 2.

Melalui contoh di atas, kita dapat melihat bahawa algoritma tamak adalah kaedah yang agak mudah dan cekap untuk mencapai penyelesaian optimum kepada masalah pokok rentang minimum dalam PHP. Sudah tentu, dalam aplikasi sebenar, mungkin terdapat struktur dan keperluan graf yang lebih kompleks Pada masa ini, kita perlu membuat pelarasan dan penambahbaikan yang sesuai berdasarkan ciri-ciri masalah tertentu.

Atas ialah kandungan terperinci Bagaimana untuk menggunakan algoritma tamak untuk mencapai penyelesaian optimum masalah pokok rentang minimum dalam PHP?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!