Condivisione della tecnologia

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

1.algoritmo avidointrodurre

1. Idea di algoritmo

L’idea di base dell’algoritmo greedy è quella di procedere passo dopo passo partendo da una soluzione iniziale del problema. Secondo una misura di ottimizzazione, ogni passo deve garantire che si possa ottenere una soluzione ottima locale. In ogni passaggio viene considerato un solo dato e la sua selezione deve soddisfare le condizioni di ottimizzazione locale. Se i dati successivi e la soluzione ottima parziale sono collegati tra loro e non è più una soluzione fattibile, i dati non verranno aggiunti alla soluzione parziale finché tutti i dati non saranno enumerati o finché l'algoritmo non potrà più essere aggiunto e l'algoritmo si arresterà.

L’algoritmo greedy generalmente procede nel modo seguente:

①Stabiliremodello matematicoper descrivere il problema.

② Dividere il problema da risolvere in più sottoproblemi.

③ Risolvi ogni sottoproblema e ottieni la soluzione ottima locale del sottoproblema.

④ Combina la soluzione ottima locale del sottoproblema in una soluzione del problema originale.

L'algoritmo greedy è una tecnica di progettazione più semplice e veloce per alcuni problemi di soluzione ottima. La caratteristica dell'algoritmo greedy è che procede passo dopo passo, spesso facendo scelte ottimali basate sulla situazione attuale e sulla base di una misura di ottimizzazione, senza considerare tutte le possibili situazioni complessive, eliminando la necessità di esaurire tutte le possibilità per trovare la soluzione ottimale. Trascorso molto tempo.Utilizza l'algoritmo golosodall'alto al basso , effettuare scelte avide successive in un metodo iterativo. Ogni volta che viene effettuata una scelta avida, il problema desiderato viene semplificato in un sottoproblema più piccolo. Attraverso ogni passaggio della scelta avida, è possibile ottenere una soluzione ottimale al problema. Sebbene sia necessario garantire che la soluzione ottimale locale possa essere ottenuta in ogni passaggio, la soluzione globale risultante a volte non è necessariamente ottimale, quindi gli algoritmi greedy non tornano sui propri passi.

2. Introduzione al codice

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. Utilizzare un algoritmo avido per assegnare agli insegnanti progetti di ricerca scientifica più adeguati

Questo codice implementa una funzione di assegnazione di insegnanti e progetti di ricerca scientifica e la sua idea di algoritmo principale è un algoritmo avido. Quella che segue è un'analisi degli algoritmi utilizzati nel codice:

1. Algoritmo Greedy: Quando si seleziona un responsabile per ogni progetto di ricerca scientifica, l'algoritmo cerca di trovare per ogni progetto un docente a cui non è stato ancora assegnato un progetto. Questa è una tipica applicazione dell'algoritmo greedy, perché ad ogni passo effettua una scelta ottimale locale (ovvero, seleziona il miglior insegnante attualmente disponibile), sperando che tale decisione ottimale locale possa portare allo svincolo ottimale globale o approssimato.

2. Ordinamento: il codice ordina innanzitutto insegnanti e progetti.
Gli insegnanti sono ordinati in ordine decrescente in base all'ID della posizione e all'ID del titolo professionale, il che significa che gli insegnanti con posizioni e titoli professionali più elevati verranno classificati per primi.
I progetti vengono ordinati in ordine decrescente in base al budget e i progetti con budget più elevati vengono considerati per primi; se i budget sono uguali, vengono ordinati in ordine crescente in base all'ora di inizio, ovvero vengono considerati per primi i progetti con ora di inizio precedente.

3. Filtra e seleziona: utilizza l'API Stream di Java 8 per selezionare gli insegnanti a cui non sono ancora stati assegnati progetti attraverso la condizione di filtro `.filter(teacher -> !teacherToProjectMap.containsKey(teacher.getTeacherID()))`. Questo fa parte dell'algoritmo di selezione che garantisce che a ogni insegnante venga assegnato un solo progetto.

4. Relazione di mappatura: utilizza `teacherToProjectMap` per registrare gli insegnanti a cui sono stati assegnati progetti, il che aiuta a evitare incarichi ripetuti.

5. Gestione delle eccezioni: utilizzare la struttura `try-catch` per gestire possibili eccezioni per garantire la robustezza del programma.

6. Operazione del database: nel blocco "try", aggiorna i risultati dell'allocazione nel database chiamando il metodo "projectDao.updateResearchProject(project)". Questo è il passaggio finale per implementare la funzionalità, mantenendo i risultati dei suggerimenti.

4. Generalizzare

In questo codice, sebbene il termine “algoritmo greedy” non sia menzionato esplicitamente, la logica del codice riflette in realtà l’idea di un algoritmo greedy. Un algoritmo greedy è un algoritmo che prende la scelta migliore o ottimale (cioè la più vantaggiosa) nello stato corrente in ogni passaggio, sperando che il risultato sia il migliore o ottimale globale.

Nello specifico, la strategia golosa del codice si riflette nei seguenti aspetti:

1. Strategia di assegnazione degli insegnanti : Nell'assegnare i docenti ai progetti, il codice seleziona sempre il docente con la posizione e il titolo professionale più alto tra i docenti attualmente non assegnati al progetto (ovvero il primo docente dopo l'ordinamento). Si tratta di una scelta ottimale locale, nella speranza di raggiungere l’ottimale globale (vale a dire, lasciare che gli insegnanti con posizioni e titoli professionali elevati siano il più possibile responsabili del progetto).

2. Strategia di allocazione del progetto : Quando si assegnano progetti, il codice seleziona sempre il progetto con il budget più alto e la prima ora di inizio. Questa è anche una scelta ottimale locale, nella speranza di raggiungere l’ottimalità globale (vale a dire, i progetti con budget elevati e tempi di inizio anticipati dovrebbero essere allocati per primi, per quanto possibile).

Questo codice incarna l'idea di un algoritmo avido che fa la scelta migliore allo stato attuale (vale a dire, l'insegnante con la posizione e il titolo professionale più alti, il progetto con il budget più alto e la prima ora di inizio) in ogni fase del processo. selezione.