Compartir tecnología

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

1.algoritmo codiciosointroducir

1. Idea de algoritmo

La idea básica del algoritmo codicioso es avanzar paso a paso a partir de una solución inicial al problema. Según una medida de optimización, cada paso debe garantizar que se pueda obtener una solución óptima local. En cada paso solo se considera un dato y su selección debe cumplir las condiciones de optimización local. Si los siguientes datos y la solución óptima parcial están conectados entre sí y ya no es una solución factible, los datos no se agregarán a la solución parcial hasta que se enumeren todos los datos o el algoritmo ya no se pueda agregar y el algoritmo se detenga.

El algoritmo codicioso generalmente procede de la siguiente manera:

①Establecermodelo matemáticopara describir el problema.

② Divida el problema a resolver en varios subproblemas.

③ Resuelva cada subproblema y obtenga la solución óptima local del subproblema.

④ Combine la solución óptima local del subproblema en una solución al problema original.

El algoritmo codicioso es una técnica de diseño más simple y rápida para ciertos problemas de solución óptima. La característica del algoritmo codicioso es que avanza paso a paso, a menudo tomando decisiones óptimas basadas en la situación actual y en función de una medida de optimización, sin considerar todas las situaciones generales posibles, eliminando la necesidad de agotar todas las posibilidades para encontrar la solución óptima. Mucho tiempo invertido.Usos del algoritmo codiciosoDe arriba hacia abajo , Tome decisiones codiciosas sucesivas en un método iterativo. Cada vez que se realiza una elección codiciosa, el problema deseado se simplifica en un subproblema más pequeño. A través de cada paso de la elección codiciosa, se puede obtener una solución óptima al problema. Aunque es necesario garantizar que se pueda obtener la solución óptima local en cada paso, la solución global resultante a veces no es necesariamente óptima, por lo que los algoritmos codiciosos no retroceden.

2. Introducción al código

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. Utilice un algoritmo codicioso para asignar proyectos de investigación científica más adecuados a los profesores.

Este código implementa una función de asignación de profesores y proyectos de investigación científica, y su idea de algoritmo central es un algoritmo codicioso. El siguiente es un análisis de los algoritmos utilizados en el código:

1. Algoritmo codicioso: Al seleccionar un responsable para cada proyecto de investigación científica, el algoritmo intenta encontrar un profesor para cada proyecto al que aún no se le ha asignado ningún proyecto. Esta es una aplicación típica del algoritmo codicioso, porque realiza una elección óptima local en cada paso (es decir, selecciona al mejor maestro disponible actualmente), con la esperanza de que dicha decisión óptima local pueda conducir al desvinculación óptimo global o óptimo aproximado.

2. Clasificación: el código primero clasifica los profesores y los proyectos.
Los docentes se clasifican en orden descendente según su ID de puesto y ID de título profesional, lo que significa que los profesores con puestos y títulos profesionales más altos ocuparán el primer lugar.
Los proyectos se ordenan en orden descendente según el presupuesto y los proyectos con presupuestos más altos se consideran primero; si los presupuestos son iguales, se ordenan en orden ascendente según la hora de inicio, es decir, los proyectos con una hora de inicio anterior se consideran primero.

3. Filtrar y seleccionar: Utilice Stream API de Java 8 para seleccionar profesores a los que aún no se les han asignado proyectos a través de la condición de filtro `.filter(teacher -> !teacherToProjectMap.containsKey(teacher.getTeacherID()))`. Esto es parte del algoritmo de selección que garantiza que a cada profesor se le asigne un solo proyecto.

4. Relación de mapeo: utilice `teacherToProjectMap` para registrar los maestros a quienes se les han asignado proyectos, lo que ayuda a evitar asignaciones repetidas.

5. Manejo de excepciones: utilice la estructura `try-catch` para manejar posibles excepciones y garantizar la solidez del programa.

6. Operación de la base de datos: en el bloque `try`, actualice los resultados de la asignación a la base de datos llamando al método `projectDao.updateResearchProject(project)`. Este es el paso final para implementar la funcionalidad, manteniendo los resultados de la recomendación.

4. Generalizar

En este código, aunque el término "algoritmo codicioso" no se menciona explícitamente, la lógica del código en realidad refleja la idea de un algoritmo codicioso. Un algoritmo codicioso es un algoritmo que toma la opción mejor u óptima (es decir, la más ventajosa) en el estado actual en cada paso, con la esperanza de que el resultado sea el mejor u óptimo global.

Específicamente, la estrategia codiciosa en el código se refleja en los siguientes aspectos:

1. Estrategia de asignación de docentes : Al asignar profesores a proyectos, el código siempre selecciona al profesor con el puesto y título profesional más alto entre los profesores actualmente no asignados al proyecto (es decir, el primer profesor después de la clasificación). Esta es una opción óptima local, con la esperanza de lograr el óptimo global (es decir, permitir que los profesores con altos cargos y títulos profesionales sean responsables del proyecto tanto como sea posible).

2. Estrategia de asignación de proyectos : Al asignar proyectos, el código siempre selecciona el proyecto con el presupuesto más alto y la hora de inicio más temprana. Esta también es una opción óptima local, con la esperanza de lograr la optimización global (es decir, los proyectos con presupuestos altos y tiempos de inicio tempranos deben asignarse primero tanto como sea posible).

Este código incorpora la idea de un algoritmo codicioso al tomar la mejor opción en el estado actual (es decir, el maestro con el puesto y título profesional más alto, el proyecto con el presupuesto más alto y el tiempo de inicio más temprano) en cada paso de selección.