Bagaimana untuk menulis algoritma tamak menggunakan PHP

Cara menulis algoritma tamak menggunakan PHP

Algoritma tamak (Algoritma tamak) ialah algoritma yang mudah dan berkesan digunakan untuk menyelesaikan jenis masalah pengoptimuman. Idea asasnya adalah untuk membuat pilihan pada setiap langkah yang kelihatan terbaik pada masa ini, tanpa mengambil kira akibat masa depan. Artikel ini akan memperkenalkan cara menulis algoritma tamak menggunakan PHP dan memberikan contoh kod yang berkaitan.

1. Penerangan masalah

Sebelum menerangkan algoritma tamak, mari kita tentukan masalah khusus untuk pemahaman yang lebih baik. Katakan anda mempunyai satu set tugasan, setiap tugasan mempunyai masa mula dan masa tamat. Matlamatnya adalah untuk memilih seberapa banyak tugas yang mungkin dan menjadikannya tidak bercanggah antara satu sama lain, iaitu tempoh masa mereka tidak bertindih. Masa tugas boleh diwakili oleh tatasusunan, setiap elemen mengandungi masa mula dan masa tamat. Kami ingin mencari bilangan maksimum tugas.

2. Idea algoritma

Algoritma tamak biasanya terdiri daripada tiga langkah: fasa pemilihan, fasa pengesahan dan fasa kemas kini.

Fasa pemilihan: Pilih tugasan dengan masa tamat paling awal daripada semua tugasan.

Fasa pengesahan: Alih keluar tugasan yang dipilih daripada senarai tugasan dan tambahkannya pada senarai keputusan.

Fasa kemas kini: Alih keluar tugas lain yang bercanggah dengan tugasan yang dipilih.

Ulang langkah di atas sehingga senarai tugasan kosong.

3. Pelaksanaan kod

Berikut ialah contoh kod untuk menulis algoritma tamak menggunakan PHP:

function greedyAlgorithm($tasks) {
    // 按结束时间对任务进行排序
    usort($tasks, function($a, $b) {
        return $a['end'] - $b['end'];
    });
  
    $result = []; // 结果列表
    while (!empty($tasks)) {
        $task = array_shift($tasks); // 选择具有最早结束时间的任务
        $result[] = $task; // 将任务添加到结果列表中
        
        // 移除与所选任务冲突的其他任务
        $tasks = array_filter($tasks, function($item) use ($task) {
            return $item['start'] >= $task['end'];
        });
    }
  
    return $result;
}

// 测试
$tasks = [
    ['start' => 1, 'end' => 3],
    ['start' => 2, 'end' => 4],
    ['start' => 3, 'end' => 6],
    ['start' => 5, 'end' => 7],
    ['start' => 6, 'end' => 8],
    ['start' => 8, 'end' => 10]
];
$result = greedyAlgorithm($tasks);
print_r($result);

4 Analisis algoritma

Kerumitan masa algoritma tamak biasanya O(nlogn), di mana n ialah nombor. daripada tugasan. Oleh kerana senarai tugasan perlu diisih, kerumitan masa pengisihan ialah O(nlogn). Kemudian, senarai tugasan dilalui, dan tugasan yang selebihnya perlu ditapis setiap kali Kerumitan masa penapisan ialah O(n). Oleh itu, kerumitan masa bagi keseluruhan algoritma ialah O(nlogn + n), iaitu O(nlogn).

5. Ringkasan

Algoritma tamak digunakan secara meluas dalam beberapa masalah pengoptimuman Kesederhanaan dan kecekapannya menjadikannya algoritma yang biasa digunakan. Artikel ini menerangkan cara menulis algoritma tamak menggunakan PHP dan memberikan contoh masalah tertentu. Saya harap artikel ini membantu dalam memahami dan menggunakan algoritma tamak.

Atas ialah kandungan terperinci Bagaimana untuk menulis algoritma tamak menggunakan PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!