탐욕 알고리즘 - 대학 과학 연구 관리 시스템을 예로 삼다

탐욕 알고리즘 - 대학 과학 연구 관리 시스템을 예로 들다

2024-07-12

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. 탐욕 알고리즘(Greedy Algorithm): 각 과학 연구 프로젝트의 책임자를 선정할 때 알고리즘은 아직 프로젝트가 할당되지 않은 각 프로젝트의 교사를 찾으려고 시도합니다. 이는 그리디 알고리즘의 대표적인 응용으로, 이러한 로컬 최적 결정이 전역 최적 또는 근사 최적 풀이로 이어질 수 있기를 바라면서 각 단계에서 로컬 최적 선택(즉, 현재 가능한 최고의 교사 선택)을 하기 때문입니다.

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. 일반화

이 코드에서는 "그리디 알고리즘"이라는 용어가 명시적으로 언급되지는 않았지만 코드의 논리는 실제로 그리디 알고리즘의 아이디어를 반영합니다. 그리디 알고리즘(Greedy Algorithm)은 그 결과가 전체적으로 최고이거나 최적이기를 바라면서 각 단계에서 현재 상태에서 최선 또는 최적(즉, 가장 유리한) 선택을 취하는 알고리즘이다.

구체적으로 코드의 그리디 전략은 다음과 같은 측면에 반영됩니다.

교사 배정 전략 : 프로젝트에 교사를 배정할 때 코드는 항상 현재 프로젝트에 배정되지 않은 교사 중 가장 높은 직위와 직위를 가진 교사를 선택합니다(즉, 정렬 후 첫 번째 교사). 이는 글로벌 최적(즉, 높은 직책과 전문 직함을 가진 교사가 프로젝트를 최대한 책임지게 하는 것)을 달성하기를 희망하는 로컬 최적 선택입니다.
프로젝트 할당 전략 : 프로젝트를 배정할 때 코드는 항상 예산이 가장 많고 시작 시간이 가장 빠른 프로젝트를 선택합니다. 이는 또한 글로벌 최적성을 달성하기를 희망하는 로컬 최적의 선택이기도 합니다(즉, 예산이 많고 시작 시간이 빠른 프로젝트에 최대한 먼저 할당해야 함).

이 코드는 각 단계에서 현재 상태에서 최선의 선택(즉, 가장 높은 직위와 직함을 가진 교사, 가장 많은 예산과 가장 빠른 시작 시간을 가진 프로젝트)을 선택하여 그리디 알고리즘의 아이디어를 구현합니다. 선택.

기술나눔