Technology Sharing

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

1.Greedy Algorithmintroduce

1. Algorithm ideas

The basic idea of ​​the greedy algorithm is to proceed step by step from an initial solution to the problem. According to a certain optimization measure, each step must ensure that a local optimal solution can be obtained. Only one data is considered at each step, and its selection should meet the conditions of local optimization. If the next data is no longer a feasible solution when connected with the partial optimal solution, the data will not be added to the partial solution until all data are enumerated or the algorithm stops if no more data can be added.

The greedy algorithm generally proceeds as follows:

① Establishmentmathematical modelTo describe the problem.

② Divide the problem to be solved into several sub-problems.

③Solve each sub-problem and obtain the local optimal solution of the sub-problem.

④Synthesize the local optimal solution of the sub-problem into a solution to the original problem.

Greedy algorithm is a simpler and faster design technique for finding the optimal solution to some problems. The characteristic of greedy algorithm is that it proceeds step by step, often based on the current situation and making the best choice according to a certain optimization measure, without considering various possible overall situations, thus saving a lot of time that must be spent on exhausting all possibilities to find the optimal solution. Greedy algorithm adoptstop down, make successive greedy choices in an iterative way, and each time a greedy choice is made, the problem is simplified into a smaller sub-problem. Through each step of greedy choice, an optimal solution to the problem can be obtained. Although it is necessary to ensure that a local optimal solution can be obtained at each step, the resulting global solution is sometimes not necessarily optimal, so the greedy algorithm should not backtrack.

2. Code Introduction

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. Use the greedy algorithm to assign more appropriate scientific research projects to teachers

This code implements a function of allocating teachers to scientific research projects. Its core algorithm is the greedy algorithm. The following is an analysis of the algorithm used in the code:

1. Greedy algorithm: When selecting the person in charge of each research project, the algorithm tries to find a teacher who has not yet been assigned a project for each project. This is a typical application of the greedy algorithm because it makes a local optimal choice at each step (i.e., selects the best teacher currently available), hoping that such a local optimal decision can lead to the global optimal or near-optimal solution.

2. Sorting: The code first sorts the teachers and projects.
Teachers are sorted in descending order based on their position ID and title ID, which means that teachers with higher positions and titles are ranked first.
Projects are sorted in descending order based on budget, and projects with higher budgets are considered first; if the budgets are the same, they are sorted in ascending order based on start time, that is, projects with earlier start times are considered first.

3. Filtering and selection: Using Java 8’s Stream API, select teachers who have not been assigned a project by filtering them with the condition `.filter(teacher -> !teacherToProjectMap.containsKey(teacher.getTeacherID()))`. This is part of the selection algorithm and ensures that each teacher is assigned only one project.

4. Mapping relationship: Use `teacherToProjectMap` to record teachers who have been assigned projects, which helps avoid duplicate assignments.

5. Exception handling: Use the `try-catch` structure to handle possible exceptions and ensure the robustness of the program.

6. Database operation: In the try block, call the projectDao.updateResearchProject(project) method to update the allocation results to the database. This is the last step to implement the function and persist the recommendation results.

4. Summary

Although the term "greedy algorithm" is not explicitly mentioned in this code, the logic of the code actually reflects the idea of ​​greedy algorithm. A greedy algorithm is an algorithm that takes the best or optimal (i.e. most favorable) choice in the current state at each step, hoping to lead to the best or optimal result in the world.

Specifically, the greedy strategy in the code is reflected in the following aspects:

1. Teacher Assignment Strategy: When assigning teachers to projects, the code always selects the teacher with the highest position and title among the teachers who are not currently assigned to a project (i.e. the first teacher after sorting). This is a local optimal choice, hoping to achieve the global optimality (i.e., let teachers with higher positions and titles take charge of projects as much as possible).

2. Project Allocation Strategy: When assigning projects, the code always selects the project with the highest budget and the earliest start time. This is also a local optimal choice, hoping to achieve a global optimality (i.e., prioritize projects with the highest budget and the earliest start time as much as possible).

This code embodies the idea of ​​the greedy algorithm by taking the best option in the current state (i.e. the teacher with the highest position and title, the project with the highest budget and the earliest start time) at each step.