Recompensa por puntuación alta por tarea de algoritmo codicioso
1. Pensamiento algorítmico
La idea básica del método codicioso:
——Comenzar desde una solución inicial al problema y acercarse gradualmente a lo dado. objetivo para intentar alcanzar el objetivo. Es posible obtener una mejor solución rápidamente. Cuando se alcanza un determinado paso en un algoritmo y no se puede avanzar más, el algoritmo se detiene.
Hay problemas con este algoritmo:
1. No hay garantía de que la solución final obtenida sea la mejor
2. encontrar la solución máxima o mínima Pregunta;
3. Solo se puede encontrar el rango de soluciones factibles que satisfacen ciertas restricciones.
El proceso de implementación de este algoritmo:
Comienza desde una determinada solución inicial al problema;
mientras se puede dar un paso adelante hacia el objetivo general dado
Encuentre un elemento de solución de una solución factible
Todos los elementos de la solución se combinan en una solución factible del problema
2. Análisis de ejemplo
;1, [Problema de la mochila] Hay una mochila con una capacidad de M=150. Hay 7 artículos y los artículos se pueden dividir en cualquier tamaño.
Se requiere maximizar el valor total de los artículos empaquetados en la mochila tanto como sea posible, pero no puede exceder la capacidad total.
Artículo A
B
C
D
E
F
G
Peso
35
30
60
50
40
10
25
Valor
10
40
30
50
35
40
30
Análisis:
Función objetivo: ∑pimax
La restricción es que el peso total de los artículos cargados no exceda la capacidad de la mochila: ∑wi<=M(M=150)
(1 ) Según la codicia La estrategia es elegir los artículos con mayor valor y ponerlos en la mochila cada vez. ¿El resultado es el mejor?
(2) ¿Se puede obtener la solución óptima seleccionando cada vez los elementos que ocupan el menor espacio?
(3) Seleccionar el artículo con mayor valor por unidad de capacidad cada vez se convierte en la estrategia para resolver este problema. ?
2. [Ruta más corta de fuente única] Un gráfico dirigido G, cada borde del cual tiene un peso no negativo c [i, j], y la "longitud de la ruta" es la ruta atravesada. La suma de los pesos de todos los bordes. Para el punto de origen, debe encontrar la ruta más corta desde el punto de origen hasta todos los demás nodos.
El algoritmo codicioso inventado por E.Dijkstra puede resolver el problema del camino más corto. La idea principal del algoritmo es encontrar el camino más corto paso a paso, y cada paso genera un camino más corto hacia el nuevo vértice de destino. El vértice de destino al que se puede llegar en el siguiente paso se selecciona mediante el siguiente criterio codicioso: entre los vértices que no generan el camino más corto, seleccione el vértice de destino con el camino más corto.
Configure un conjunto de vértices S y realice continuamente selecciones codiciosas para expandir este conjunto. Un vértice pertenece al conjunto S si y sólo si se conoce el camino más corto de un vértice a otro. Inicialmente, S contiene sólo fuentes.
Sea u un vértice en G. Llamamos a la ruta desde el punto fuente hasta u y pasando solo los vértices en el conjunto S una ruta especial desde la fuente hasta u, y registramos esta ruta especial (para ejemplo, dist[i, j] en el programa).
Cada vez, seleccione el vértice u con la longitud de ruta especial más corta de V-S, agregue u a S y realice las modificaciones necesarias a la longitud de ruta especial. Una vez que V = S, se obtiene el camino más corto desde la fuente a todos los demás vértices y se obtiene la solución al problema.
stra.pas
3. [Programación de máquinas] Hay N tareas y máquinas ilimitadas. Las tareas se pueden procesar en la máquina. El tiempo de inicio y finalización de cada tarea es el siguiente:
Tarea a b c d e f g
Inicio (si) 0 3 4 9 7 1 6
Completar (fi ) 2 7 7 11 10 5 8
Cada máquina en la asignación factible puede procesar como máximo una tarea a la vez.
La asignación óptima se refiere al plan de asignación factible que utiliza la menor cantidad de máquinas. Encuentre la asignación óptima según las condiciones dadas en esta pregunta. 3. Preguntas de práctica:
Se sabe que hay vuelos que entregan correos electrónicos entre 5 ciudades. El propósito es encontrar una ruta de vuelo que consuma menos combustible. La red de contactos de las 5 ciudades se muestra en la figura. Los nodos numerados en la figura representan ciudades, y el valor en la línea entre las dos ciudades representa el consumo de combustible del vuelo a lo largo de la ruta. Se supone que el consumo de combustible de la ciudad i a j y de la ciudad j a i es el mismo. .
Análisis:
1. Utilice el pensamiento codicioso:
En cada paso adelante, elija la ruta con el menor consumo de combustible en relación con la ciudad actual;
p>
p>
2. Diagrama: Si se parte del 1, queda una imagen:
Consumo total de combustible = 14 1-2-5-3-4-1
Pero si la ruta se cambia a: 1-5-3-4-2-1, entonces el consumo total de combustible = 13
Entonces, un método tan codicioso no puede obtener la mejor solución. .
3. Plan de mejora:
Partir del proceso de confianza de todas las ciudades y encontrar la óptima.
Programación:
1. Estructura de datos:
Descripción del gráfico de la red de conexión urbana (descripción de la matriz de adyacencia del gráfico):
const
c=matriz[1..5,1..5] de entero=((0,1,2,7,5),
(1 ,0, 4,4,3),
(2,4,0,1,2),
(7,4,1,0,3));
2. Proceso codicioso:
comenzar
Inicializar las banderas de ruta de cálculo de todas las ciudades;
Establecer la ciudad inicial V;
para i:=1 a n-1 hacer {n-1 ciudades}
comenzar
s:=El borde concentró el consumo de combustible de V a todas las ciudades no visitadas La ciudad con menor;
Consumo acumulado de combustible;
V:=s;
Establecer la bandera de visita de la ciudad V;
fin;
La última ciudad regresa a la primera ciudad y se acumula el consumo de combustible;
fin;
3.
comenzar
for i:=1 to n do
comenzar
costo1:=maxint;
Llame al proceso codicioso y devuelva el costo del consumo de combustible de esta búsqueda;
si el costo fin; Salida; fin