Comment écrire un algorithme glouton en utilisant PHP

Comment écrire un algorithme glouton en utilisant PHP

L'algorithme glouton (Greedy algorithm) est un algorithme simple et efficace utilisé pour résoudre un type de problème d'optimisation. Son idée fondamentale est de faire, à chaque étape, le choix qui semble le meilleur sur le moment, sans égard aux conséquences futures. Cet article expliquera comment écrire un algorithme glouton en utilisant PHP et fournira des exemples de code pertinents.

1. Description du problème

Avant d'expliquer l'algorithme glouton, définissons d'abord un problème spécifique pour une meilleure compréhension. Supposons qu'il existe un ensemble de tâches, chaque tâche a une heure de début et une heure de fin. L’objectif est de sélectionner autant de tâches que possible et de faire en sorte qu’elles ne soient pas en conflit les unes avec les autres, c’est-à-dire que leurs périodes ne se chevauchent pas. L'heure de la tâche peut être représentée par un tableau, chaque élément contient l'heure de début et l'heure de fin. Nous voulons trouver le nombre maximum de tâches.

2. Idée d'algorithme

L'algorithme glouton se compose généralement de trois étapes : la phase de sélection, la phase de vérification et la phase de mise à jour.

Phase de sélection : sélectionnez une tâche avec l'heure de fin la plus proche parmi toutes les tâches.

Phase de vérification : supprimez la tâche sélectionnée de la liste des tâches et ajoutez-la à la liste des résultats.

Phase de mise à jour : supprimez les autres tâches en conflit avec la tâche sélectionnée.

Répétez les étapes ci-dessus jusqu'à ce que la liste des tâches soit vide.

3. Implémentation du code

Ce qui suit est un exemple de code pour écrire un algorithme glouton en utilisant 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 Analyse de l'algorithme

La complexité temporelle d'un algorithme glouton est généralement O(nlogn), où n est le nombre. de tâches. Puisque la liste des tâches doit être triée, la complexité temporelle du tri est O(nlogn). Ensuite, la liste des tâches est parcourue et les tâches restantes doivent être filtrées à chaque fois. La complexité temporelle du filtrage est O(n). Par conséquent, la complexité temporelle de l’ensemble de l’algorithme est O(nlogn + n), ce qui correspond à O(nlogn).

5. Résumé

L'algorithme glouton est largement utilisé dans certains problèmes d'optimisation. Sa simplicité et son efficacité en font un algorithme couramment utilisé. Cet article explique comment écrire un algorithme glouton en utilisant PHP et donne un exemple de problème spécifique. J'espère que cet article sera utile pour comprendre et utiliser les algorithmes gloutons.

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!