Partage de technologie

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1.algorithme gourmandintroduire

1. Idée d'algorithme

L'idée de base de l'algorithme glouton est de procéder étape par étape à partir d'une solution initiale au problème. Selon une mesure d'optimisation, chaque étape doit garantir qu'une solution optimale locale peut être obtenue. Une seule donnée est considérée à chaque étape, et sa sélection doit répondre aux conditions d'optimisation locale. Si les données suivantes et la solution optimale partielle sont connectées ensemble et que ce n'est plus une solution réalisable, les données ne seront pas ajoutées à la solution partielle jusqu'à ce que toutes les données soient énumérées ou que l'algorithme ne puisse plus être ajouté et que l'algorithme s'arrête.

L’algorithme glouton procède généralement de la manière suivante :

①Établirmodèle mathématiquepour décrire le problème.

② Divisez le problème à résoudre en plusieurs sous-problèmes.

③ Résolvez chaque sous-problème et obtenez la solution optimale locale du sous-problème.

④ Combiner la solution optimale locale du sous-problème en une solution au problème d'origine.

L'algorithme glouton est une technique de conception plus simple et plus rapide pour certains problèmes de solution optimale. La caractéristique de l'algorithme glouton est qu'il procède étape par étape, en faisant souvent des choix optimaux basés sur la situation actuelle et sur la base d'une mesure d'optimisation, sans considérer toutes les situations globales possibles, éliminant ainsi le besoin d'épuiser toutes les possibilités pour trouver la solution optimale. Beaucoup de temps passé.L'algorithme gourmand utilisede haut en bas , faites des choix gloutons successifs dans une méthode itérative. Chaque fois qu'un choix glouton est fait, le problème souhaité est simplifié en un sous-problème plus petit. À chaque étape du choix glouton, une solution optimale au problème peut être obtenue. Bien qu’il soit nécessaire de s’assurer que la solution optimale locale puisse être obtenue à chaque étape, la solution globale résultante n’est parfois pas nécessairement optimale, donc les algorithmes gloutons ne reviennent pas en arrière.

2. Présentation du code

private static void assignTeachersToProjects(TeacherDao teacherDao, ResearchProjectDao projectDao) {
        // 从TeacherDao获取所有教师的列表
        List<Teacher> teachers = teacherDao.getAllTeachers();
        // 从ResearchProjectDao获取所有科研项目的列表
        List<ResearchProject> projects = projectDao.getAllResearchProjects();
 
        // 使用职务ID和职称ID对教师进行排序，职务和职称越高的教师排在前面
        // 这里reversed()表示降序排序
        Collections.sort(teachers, Comparator.comparing(Teacher::getPositionID)
                .reversed().thenComparing(Teacher::getTitleID).reversed());
 
        // 使用预算和开始时间对项目进行排序，预算越高和开始时间越早的项目排在前面
        // 预算高的排在前面，如果预算相同，则开始时间早的排在前面
        Collections.sort(projects, Comparator.comparing(ResearchProject::getBudget)
                .reversed().thenComparing(ResearchProject::getStartDate));
 
        // 创建一个映射，用于记录教师与项目之间的分配关系
        Map<Integer, Integer> teacherToProjectMap = new HashMap<>();
 
        try {
            // 遍历每个项目
            for (ResearchProject project : projects) {
                // 使用Stream API寻找尚未分配项目的教师
                // filter条件确保只考虑那些还没有分配项目的教师
                Teacher bestTeacher = teachers.stream()
                        .filter(teacher -> !teacherToProjectMap.containsKey(teacher.getTeacherID()))
                        .findFirst().orElse(null);
 
                // 如果找到了合适的教师
                if (bestTeacher != null) {
                    // 将教师ID设置为项目的负责人ID
                    project.setTeacherInChargeID(bestTeacher.getTeacherID());
                    // 将教师ID和项目ID添加到映射中，表示教师已被分配项目
                    teacherToProjectMap.put(bestTeacher.getTeacherID(), project.getProjectID());
                    // 打印推荐信息
                    System.out.println("推荐项目 '" + project.getTitle() + "' 分配给教师 " + bestTeacher.getName());
 
                    // 调用ResearchProjectDao的updateResearchProject方法更新数据库中的项目分配信息
                    projectDao.updateResearchProject(project);
                } else {
                    // 如果没有找到合适的教师，打印无法推荐的消息
                    System.out.println("未找到未分配的教师，无法推荐项目 '" + project.getTitle() + "'");
                }
            }
 
        } catch (Exception e) {
            // 如果发生异常，打印错误信息并打印堆栈跟踪
            System.out.println("更新数据库时发生错误：" + e.getMessage());
            e.printStackTrace();
        }
 
        // 打印教师和项目的总数信息
        System.out.println("教师总数：" + teachers.size());
        System.out.println("项目总数：" + projects.size());
    }

3. Utiliser un algorithme glouton pour attribuer des projets de recherche scientifique plus adaptés aux enseignants

Ce code implémente une fonction d'affectation d'enseignants et de projets de recherche scientifique, et son idée d'algorithme de base est un algorithme glouton. Ce qui suit est une analyse des algorithmes utilisés dans le code :

1. Algorithme gourmand : Lors de la sélection d'un responsable pour chaque projet de recherche scientifique, l'algorithme essaie de trouver pour chaque projet un enseignant qui n'a pas encore été affecté à un projet. Il s'agit d'une application typique de l'algorithme glouton, car il effectue un choix optimal local à chaque étape (c'est-à-dire, sélectionner le meilleur enseignant actuellement disponible), en espérant qu'une telle décision optimale locale puisse conduire au dénouement optimal global ou optimal approximatif.

2. Tri : Le code trie d'abord les enseignants et les projets.
Les enseignants sont triés par ordre décroissant en fonction de leur identifiant de poste et de leur titre professionnel, ce qui signifie que les enseignants ayant des postes et des titres professionnels plus élevés seront classés en premier.
Les projets sont triés par ordre décroissant en fonction du budget, et les projets avec des budgets plus élevés sont considérés en premier ; si les budgets sont identiques, ils sont triés par ordre croissant en fonction de l'heure de début, c'est-à-dire que les projets avec une heure de début plus précoce sont considérés en premier.

3. Filtrer et sélectionner : utilisez l'API Stream de Java 8 pour sélectionner les enseignants qui n'ont pas encore reçu de projets via la condition de filtre `.filter(teacher -> !teacherToProjectMap.containsKey(teacher.getTeacherID()))`. Cela fait partie de l’algorithme de sélection qui garantit que chaque enseignant ne se voit attribuer qu’un seul projet.

4. Relation de cartographie : utilisez « teacherToProjectMap » pour enregistrer les enseignants à qui des projets ont été assignés, ce qui permet d'éviter des affectations répétées.

5. Gestion des exceptions : utilisez la structure `try-catch` pour gérer les exceptions possibles afin de garantir la robustesse du programme.

6. Fonctionnement de la base de données : dans le bloc `try`, mettez à jour les résultats de l'allocation dans la base de données en appelant la méthode `projectDao.updateResearchProject(project)`. Il s'agit de la dernière étape pour implémenter la fonctionnalité, en conservant les résultats des recommandations.

4. Généraliser

Dans ce code, bien que le terme « algorithme glouton » ne soit pas explicitement mentionné, la logique du code reflète en réalité l'idée d'un algorithme glouton. Un algorithme glouton est un algorithme qui prend le meilleur ou le meilleur choix (c'est-à-dire le plus avantageux) dans l'état actuel à chaque étape, en espérant que le résultat sera le meilleur ou l'optimal global.

Plus précisément, la stratégie gourmande du code se reflète dans les aspects suivants :

1. Stratégie d'affectation des enseignants : Lors de l'affectation des enseignants aux projets, le code sélectionne toujours l'enseignant ayant le poste et le titre professionnel le plus élevé parmi les enseignants actuellement non affectés au projet (c'est-à-dire le premier enseignant après tri). Il s'agit d'un choix optimal local, dans l'espoir d'atteindre l'optimum global (c'est-à-dire laisser autant que possible les enseignants occupant des postes élevés et des titres professionnels être responsables du projet).

2. Stratégie d'allocation de projets : Lors de l'attribution des projets, le code sélectionne toujours le projet avec le budget le plus élevé et l'heure de début la plus précoce. Il s'agit également d'un choix optimal local, dans l'espoir d'atteindre une optimalité globale (c'est-à-dire que les projets avec des budgets élevés et des délais de démarrage précoces doivent être alloués en premier autant que possible).

Ce code incarne l'idée d'un algorithme glouton en prenant le meilleur choix dans l'état actuel (c'est-à-dire l'enseignant avec le poste et le titre professionnel le plus élevé, le projet avec le budget le plus élevé et l'heure de début la plus précoce) à chaque étape de sélection.