貪欲なアルゴリズム - 大学の科学研究管理システムを例として

貪欲なアルゴリズム - 大学の科学研究管理システムを例に

2024-07-12

1.貪欲なアルゴリズム導入

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()))` を通じてプロジェクトがまだ割り当てられていない教師を選択します。これは、各教師に 1 つのプロジェクトのみが割り当てられるようにする選択アルゴリズムの一部です。

4. マッピング関係: `TeacherToProjectMap` を使用して、プロジェクトを割り当てられた教師を記録します。これは、繰り返しの割り当てを避けるのに役立ちます。

5. 例外処理: `try-catch` 構造を使用して、考えられる例外を処理し、プログラムの堅牢性を確保します。

6. データベース操作: 「try」ブロックで、「projectDao.updateResearchProject(project)」メソッドを呼び出して、データベースへの割り当て結果を更新します。これは機能を実装する最後のステップであり、推奨結果を永続化します。

4. 一般化する

このコードでは、「貪欲アルゴリズム」という用語は明示的に言及されていませんが、コードのロジックは実際には貪欲アルゴリズムの考え方を反映しています。貪欲アルゴリズムは、各ステップの現在の状態で最良または最適 (つまり、最も有利な) 選択をとり、その結果が全体的に最良または最適になることを期待するアルゴリズムです。

具体的には、コード内の貪欲な戦略は次の側面に反映されています。

教師の割り当て戦略 : 教師をプロジェクトに割り当てるとき、コードは常に、現在プロジェクトに割り当てられていない教師の中で最も高い職位と専門的肩書きを持つ教師 (つまり、並べ替え後の最初の教師) を選択します。これは、全体最適 (つまり、高い地位と専門的肩書きを持つ教師にできる限りプロジェクトの責任を負わせる) を達成することを期待した、局所最適の選択です。
プロジェクト割り当て戦略 : プロジェクトを割り当てるとき、コードは常に、予算が最も高く、開始時間が最も早いプロジェクトを選択します。これは、全体的な最適性を達成することを期待した、局所的な最適な選択でもあります (つまり、予算が高く、開始時期が早いプロジェクトをできるだけ最初に割り当てる必要があります)。

このコードは、現在の状態で最良の選択 (つまり、最も高い地位と専門職名を持つ教師、最も高い予算と最も早い開始時間を持つプロジェクト) を各ステップで採用することにより、貪欲なアルゴリズムのアイデアを具体化しています。選択。

技術共有