贪心算法-以高校科研管理系统为例

1.贪心算法介绍 

1.算法思路

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一 步都要确保能获得局部最优解。每一步只考虑一 个数据，其选取应该满足局部优化的条件。若下 一个数据和部分最优解连在一起不再是可行解时， 就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。 

贪心算法一般按如下步骤进行： 

①建立数学模型来描述问题 。

②把求解的问题分成若干个子问题 。

③对每个子问题求解，得到子问题的局部最优解 。

④把子问题的解局部最优解合成原来解问题的一个解 。

贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪心算法不要回溯 。

2.代码介绍

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.使用贪心算法为教师分配较为合适的科研项目

这段代码实现了一个教师与科研项目分配的功能，其核心算法思想是贪心算法。以下是代码中使用的算法分析：

1. 贪心算法：在为每个科研项目选择负责人时，算法尝试为每个项目找到一个尚未分配项目的教师。这是贪心算法的一个典型应用，因为它在每一步都做出局部最优的选择（即选择当前可用的最佳教师），希望这样的局部最优决策能够导致全局的最优或近似最优解。

2. 排序：代码首先对教师和项目进行排序。
   教师根据职务ID和职称ID降序排序，意味着职务和职称较高的教师会被排在前面。
   项目根据预算降序排序，预算越高的项目越先被考虑；如果预算相同，则根据开始时间升序排序，即开始时间越早的项目越先被考虑。

3. 过滤和选择：使用Java 8的Stream API，通过过滤条件`.filter(teacher -> !teacherToProjectMap.containsKey(teacher.getTeacherID()))`选择尚未分配项目的教师。这是选择算法的一部分，确保每个教师只被分配一个项目。

4. 映射关系：使用`teacherToProjectMap`来记录已经分配项目的教师，有助于避免重复分配。

5. 异常处理：使用`try-catch`结构来处理可能发生的异常，确保程序的健壮性。

6. 数据库操作：在`try`块中，通过调用`projectDao.updateResearchProject(project)`方法将分配结果更新到数据库。这是实现功能的最后一步，将推荐结果持久化。

4.概括

在这段代码中，虽然没有明确提到“贪心算法”这个术语，但实际上代码的逻辑体现了贪心算法的思想。贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。

具体来说，代码中的贪心策略体现在以下几个方面：

1. 教师分配策略：在分配教师到项目时，代码总是选择当前未分配项目的教师中职务和职称最高的教师（即排序后的第一个教师）。这是一种局部最优选择，希望以此来达到全局最优（即尽可能让职务和职称高的教师负责项目）。

2. 项目分配策略：在分配项目时，代码总是选择预算最高且开始时间最早的项目。这也是一种局部最优选择，希望以此来达到全局最优（即尽可能让预算高且开始时间早的项目得到优先分配）。

这段代码通过在每一步选择中都采取当前状态下最优的选择（即职务和职称最高的教师、预算最高且开始时间最早的项目），体现了贪心算法的思想。