Technologieaustausch

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

1.Gieriger Algorithmuseinführen

1. Algorithmusidee

Die Grundidee des Greedy-Algorithmus besteht darin, ausgehend von einer anfänglichen Lösung des Problems Schritt für Schritt vorzugehen. Gemäß einer Optimierungsmaßnahme muss jeder Schritt sicherstellen, dass eine lokal optimale Lösung erhalten werden kann. In jedem Schritt wird nur ein Datentyp berücksichtigt, und seine Auswahl sollte den Bedingungen der lokalen Optimierung entsprechen. Wenn die nächsten Daten und die partielle optimale Lösung miteinander verbunden sind und es sich nicht mehr um eine realisierbare Lösung handelt, werden die Daten nicht zur partiellen Lösung hinzugefügt, bis alle Daten aufgezählt sind oder der Algorithmus nicht mehr hinzugefügt werden kann und der Algorithmus stoppt.

Der Greedy-Algorithmus geht im Allgemeinen wie folgt vor:

①Einrichtenmathematisches Modellum das Problem zu beschreiben.

② Teilen Sie das zu lösende Problem in mehrere Teilprobleme auf.

③ Lösen Sie jedes Teilproblem und erhalten Sie die lokal optimale Lösung des Teilproblems.

④ Kombinieren Sie die lokal optimale Lösung des Teilproblems zu einer Lösung des ursprünglichen Problems.

Der Greedy-Algorithmus ist eine einfachere und schnellere Entwurfstechnik für bestimmte optimale Lösungsprobleme. Das Charakteristikum des Greedy-Algorithmus besteht darin, dass er Schritt für Schritt vorgeht und häufig optimale Entscheidungen auf der Grundlage der aktuellen Situation und auf der Grundlage einer Optimierungsmaßnahme trifft, ohne alle möglichen Gesamtsituationen zu berücksichtigen, wodurch die Notwendigkeit entfällt, alle Möglichkeiten auszuschöpfen, um die optimale Lösung zu finden. Viel Zeit aufgewendet.Greedy-Algorithmus verwendetvon oben nach unten Treffen Sie aufeinanderfolgende gierige Entscheidungen in einer iterativen Methode. Jedes Mal, wenn eine gierige Wahl getroffen wird, wird das gewünschte Problem in ein kleineres Teilproblem vereinfacht. Durch jeden Schritt der gierigen Wahl kann eine optimale Lösung für das Problem erhalten werden. Obwohl bei jedem Schritt sichergestellt werden muss, dass die lokal optimale Lösung erhalten werden kann, ist die resultierende globale Lösung manchmal nicht unbedingt optimal, sodass gierige Algorithmen keinen Rückzieher machen.

2. Code-Einführung

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. Verwenden Sie einen Greedy-Algorithmus, um Lehrern geeignetere wissenschaftliche Forschungsprojekte zuzuweisen

Dieser Code implementiert eine Funktion zur Zuweisung von Lehrern und wissenschaftlichen Forschungsprojekten, und seine Kernalgorithmusidee ist ein gieriger Algorithmus. Das Folgende ist eine Analyse der im Code verwendeten Algorithmen:

1. Greedy-Algorithmus: Bei der Auswahl einer verantwortlichen Person für jedes wissenschaftliche Forschungsprojekt versucht der Algorithmus, für jedes Projekt einen Lehrer zu finden, dem noch kein Projekt zugewiesen wurde. Dies ist eine typische Anwendung des Greedy-Algorithmus, da er bei jedem Schritt eine lokal optimale Wahl trifft (d. h. den besten derzeit verfügbaren Lehrer auswählt) und hofft, dass eine solche lokal optimale Entscheidung zum globalen Optimum oder zur angenäherten optimalen Lösung führen kann.

2. Sortieren: Der Code sortiert zunächst Lehrer und Projekte.
Die Lehrer werden in absteigender Reihenfolge nach ihrer Positions-ID und Berufsbezeichnungs-ID sortiert, was bedeutet, dass Lehrer mit höheren Positionen und Berufsbezeichnungen zuerst gereiht werden.
Die Projekte werden in absteigender Reihenfolge nach Budget sortiert, wobei Projekte mit höherem Budget zuerst berücksichtigt werden; bei gleichem Budget werden sie in aufsteigender Reihenfolge nach Startzeitpunkt sortiert, d.h. Projekte mit früherem Startzeitpunkt werden zuerst berücksichtigt.

3. Filtern und auswählen: Verwenden Sie die Stream-API von Java 8, um Lehrer, denen noch keine Projekte zugewiesen wurden, über die Filterbedingung „.filter(teacher -> !teacherToProjectMap.containsKey(teacher.getTeacherID()))“ auszuwählen. Dies ist Teil des Auswahlalgorithmus, der sicherstellt, dass jedem Lehrer nur ein Projekt zugewiesen wird.

4. Zuordnungsbeziehung: Verwenden Sie „teacherToProjectMap“, um Lehrer aufzuzeichnen, denen Projekte zugewiesen wurden, wodurch wiederholte Zuweisungen vermieden werden.

5. Ausnahmebehandlung: Verwenden Sie die „try-catch“-Struktur, um mögliche Ausnahmen zu behandeln und die Robustheit des Programms sicherzustellen.

6. Datenbankbetrieb: Aktualisieren Sie im Block „try“ die Zuordnungsergebnisse zur Datenbank, indem Sie die Methode „projectDao.updateResearchProject(project)“ aufrufen. Dies ist der letzte Schritt zur Implementierung der Funktionalität und zur Beibehaltung der Empfehlungsergebnisse.

4. Verallgemeinern Sie

Obwohl in diesem Code der Begriff „gieriger Algorithmus“ nicht explizit erwähnt wird, spiegelt die Logik des Codes tatsächlich die Idee eines gierigen Algorithmus wider. Ein Greedy-Algorithmus ist ein Algorithmus, der bei jedem Schritt die beste oder optimale (d. h. vorteilhafteste) Wahl im aktuellen Zustand trifft, in der Hoffnung, dass das Ergebnis das global beste oder optimale Ergebnis ist.

Konkret spiegelt sich die Greedy-Strategie im Code in den folgenden Aspekten wider:

1. Strategie für die Zuweisung von Lehrern : Bei der Zuordnung von Lehrern zu Projekten wählt der Code immer den Lehrer mit der höchsten Position und Berufsbezeichnung unter den Lehrern aus, die dem Projekt derzeit nicht zugewiesen sind (d. h. der erste Lehrer nach der Sortierung). Dies ist eine lokal optimale Wahl, in der Hoffnung, das globale Optimum zu erreichen (das heißt, Lehrer mit hohen Positionen und Berufsbezeichnungen so weit wie möglich für das Projekt verantwortlich zu machen).

2. Projektallokationsstrategie : Beim Zuweisen von Projekten wählt der Code immer das Projekt mit dem höchsten Budget und der frühesten Startzeit aus. Dies ist auch eine lokal optimale Wahl, in der Hoffnung, eine globale Optimalität zu erreichen (d. h. Projekte mit hohen Budgets und frühen Startzeiten sollten so weit wie möglich zuerst zugewiesen werden).

Dieser Code verkörpert die Idee eines gierigen Algorithmus, indem er in jedem Schritt die beste Wahl im aktuellen Zustand trifft (d. h. den Lehrer mit der höchsten Position und Berufsbezeichnung, das Projekt mit dem höchsten Budget und dem frühesten Startzeitpunkt). Auswahl.