Informe escrito a mano sobre el problema del camino más corto
Primero, algoritmos relacionados
1. Algoritmo de Dijkstra
El algoritmo de Dijkstra es un algoritmo clásico de ruta más corta. Su idea básica es: establecer un conjunto S Para almacenar el. Para los vértices que han encontrado el camino más corto, el estado inicial de S solo contiene el punto fuente V. Para vi∈V-S, se supone que el borde dirigido desde el punto fuente V a vi es el camino más corto. Después de encontrar cada camino más corto V,...,vk, agregue vk al conjunto S, compare el camino V,...,vk,vi con la hipótesis original, seleccione el camino más corto y repita el proceso anterior hasta que todos Los vértices del conjunto V se suman al conjunto S y este algoritmo se utiliza para encontrar el camino más corto globalmente óptimo. Cuando hay una gran cantidad de nodos de red y una gran cantidad de bordes de red, existen desventajas como un gran uso de memoria y una alta complejidad de tiempo. El algoritmo de Dijkstra no puede resolver bien el problema de la ruta más corta con las restricciones de puntos necesarias.
2. Algoritmo de Floyd
Características del algoritmo:
El algoritmo de Floyd es un algoritmo para encontrar el camino más corto entre dos puntos que puede manejar con precisión. el problema del camino más corto de gráficos dirigidos o gráficos dirigidos o pesos negativos (pero no puede tener ciclos de pesos negativos), y también se utiliza para calcular el cierre transitivo de gráficos dirigidos.
Floyd necesita introducir dos matrices al calcular el camino más corto para cada vértice en G=(V, E). El elemento a[j] en la matriz S representa la distancia desde el vértice I (el I-ésimo vértice) al vértice J (el J-ésimo vértice). El elemento b[j] en la matriz p representa el vértice del vértice I al vértice J representado por el valor registrado por b[j].
Suponiendo que el número de vértices del gráfico G es n, el La matriz D necesita ser actualizada y la matriz P n veces. Inicialmente, la distancia del vértice a[j] en la matriz D es el peso del vértice I al vértice J si I y J no son adyacentes, entonces a[j]=∞, el valor de la matriz P es el J del vértice b; [j] valor. A continuación, la matriz d se actualiza n veces. En la primera actualización, si "distancia de a[j]" > "A+a[j]" (A+a[j] significa "la distancia entre I y J que pasa por el primer vértice"), actualice a[ j] a "A+A[J]", actualice B[J] = B. De manera similar, si "distancia de A[J]">; ", luego actualice a[j] a "a[k-1]+a[k-1][j]", b [j] [1]
3 .Algoritmo de colonia de hormigas
& gtEl algoritmo de colonia de hormigas fue propuesto por primera vez por Dorigo, Maniezzo y Colorni en 1991. Se originó a partir del comportamiento de búsqueda de alimento de las hormigas. A través de investigaciones se descubrió que las hormigas transmiten información a través de una especie de feromona. Al caminar, las hormigas pueden sentir la intensidad de las feromonas circundantes y moverse en la dirección con una alta concentración de feromonas. Después de que las hormigas encuentran comida, liberan feromonas como marcadores en su camino de regreso al nido. Después de que sus compañeros las encuentren, seguirán este camino para encontrar comida. Cuando muchas hormigas en la compañía han encontrado comida pero los caminos son de diferentes longitudes, dado que el tiempo requerido para que las hormigas viajen de un lado a otro en un camino corto es relativamente corto, cuantas más hormigas pasen por unidad de tiempo, mayor será la concentración de feromonas. en este camino será poderoso. Por lo tanto, habrá cada vez más hormigas en este camino y gradualmente se seleccionará un camino óptimo.
En segundo lugar, clasificación
Se puede dividir en dos subproblemas, a saber, el problema de la ruta más corta de una sola fuente y el problema de la ruta más corta entre todos los pares de vértices. El primero consiste en encontrar el camino más corto desde un vértice a todos los demás vértices del gráfico. Los algoritmos principales incluyen el algoritmo de Dixcher, etc. Este último consiste en encontrar el camino más corto entre cada par de vértices del gráfico. El algoritmo principal es el algoritmo de Freud.
Tercero, aplicación
1. Campo de comunicación
Con el desarrollo continuo de la tecnología y las aplicaciones de Internet, la demanda de tráfico de comunicación de red está aumentando. Los métodos de transmisión de gran tráfico, alta velocidad y bajo costo son la clave para la transmisión de la red. La ruta más corta y el enrutamiento de red de menor costo pueden reducir en gran medida los costos de comunicación, ahorrar recursos de la red y mejorar la utilización de los recursos de la red.
2. Transporte
El problema del camino más corto es el problema más básico en la asignación de tráfico, que se refiere al camino con la menor resistencia total entre un par de nodos.
Casi todos los métodos de asignación de flujo de tráfico lo utilizan como un subproceso básico que se llama repetidamente.