Un conductor de un camión contenedor debe transportar un camión de mercancías desde el punto A al punto B en el menor tiempo. La red de carreteras del punto A al punto B está entrecruzada, por lo que existen muchas rutas de conducción. ¿Qué ruta debe elegir el conductor? Suponiendo que la velocidad de marcha del camión contenedor permanece constante, este problema equivale a encontrar el camino más corto de A a B.
2 Problema de conexión de la autopista
Hay varias ciudades grandes en un área determinada. Ahora estamos planeando construir autopistas para conectar estas ciudades, de modo que cualquier ciudad pueda acceder directamente a la autopista. O llegar a otra ciudad de forma indirecta. Suponiendo que se conoce el costo de construir una carretera entre dos ciudades cualesquiera, ¿cómo deberíamos decidir en qué ciudades construir una carretera para minimizar el costo total?
3 Problema de asignación
Un directivo de una empresa va a encargar a 20 empleados la realización de 20 tareas, una para cada persona. Debido a las diferentes características de los empleados, diferentes empleados recibirán diferentes recompensas por completar las mismas tareas. ¿Cómo asignar planes de trabajo para maximizar el retorno total?
4 Problema del cartero chino (CPP-Problema del cartero chino)
El cartero es el responsable de entregar el correo en un determinado barrio. ¿Cómo diseñar la ruta de entrega más corta para él o ella (comenzando desde la oficina de correos, pasando por cada calle del área de entrega al menos una vez y finalmente regresando a la oficina de correos)? Debido a que este problema fue planteado por primera vez por el profesor chino Guan Meigu en 1960, se lo conoce internacionalmente como el problema del cartero chino.
5 Problema del viajante (TSP-Traveling Salesman Problem)
Un vendedor se dirige a varias ciudades a vender su producto. ¿Cómo diseñar la ruta de viaje más corta para él o ella (comenzando desde la estación, pasando por cada ciudad exactamente una vez y finalmente regresando a la estación)? Este problema tiene una larga historia de investigación y a menudo se le llama el problema del viajante.
6 Problema de transporte
Algunas materias primas tienen orígenes, y ahora es necesario transportarlas desde los orígenes hasta las fábricas que utilizan estas materias primas. Supongamos que se conocen la producción de un origen y la demanda de dos fábricas, y que se conoce el costo de envío de una unidad de producto desde cualquier origen a cualquier fábrica. ¿Cómo organizar el plan de transporte para minimizar el costo total de transporte?
7. Existe un algoritmo maduro para el camino más corto: el algoritmo de Dijkstra.
8. Para calcular el camino más corto entre cada par de vértices en un gráfico ponderado, obviamente puedes llamar al algoritmo de Dijkstra. El método específico es: tomar un vértice diferente como punto de partida cada vez y utilizar el algoritmo de Dijkstra para encontrar el camino más corto desde este punto de partida hasta los vértices restantes. Repita esta operación n veces para obtener el camino más corto desde cada vértice a otros vértices. . La complejidad temporal de este algoritmo es O (n 3). La segunda forma de resolver este problema es un algoritmo propuesto por Floyd R W, llamado algoritmo de Floyd. (Puede resolver el primer problema)
9.El algoritmo Prim y el algoritmo Kruskal construyen el árbol de expansión mínimo (conectando todos los puntos).
10. El algoritmo húngaro y el algoritmo de Kuhn-Munkes resuelven el problema de asignación de personal.
Algoritmo Fleury de 11. Bucle de Euler (problema del cartero chino)
12. Un algoritmo para el flujo máximo - método de etiquetado) La idea básica del método de etiquetado para encontrar el flujo máximo de la red es encontrar la órbita creciente, de modo que el tráfico de la red continúa aumentando hasta alcanzar el máximo. )
Mi computadora no es buena y uso MATLAB. Se puede encontrar mucha información en Internet en Baidu. El programa es tan sencillo que todos los algoritmos correspondientes de Baidu están convertidos en C...
Hay muchos algoritmos que Baidu puede lograr...