Cost Matrix - Categoría¶
propuesta
Advertencia
Funciones propuestas para el próximo lanzamineto.
No están oficialmente en la versión actual.
Es probable que oficialmente formen parte del próximo lanzamiento:
Las funciones hacen uso de ANY-INTEGER y ANY-NUMERICAL
Es posible que el nombre no cambie. (Pero todavía puede)
Es posible que la firma no cambie. (Pero todavía puede)
Es posible que la funcionalidad no cambie. (Pero todavía puede)
Se han hecho pruebas de pgTap. Pero tal vez necesite más.
Es posible que la documentación necesite un refinamiento.
Información general¶
Sinopsis¶
Vendedor Viajante - Familia de funciones necesita como entrada una matriz de costos simétrica y sin borde (u, v), debe valorar \(\infty\).
Esta colección de funciones devolverá una matriz de costes en forma de tabla.
Características¶
Las características principales son:
Se puede utilizar como entrada para pgr_TSP.
- directamente
cuando la matriz resultante es simétrica y no hay valor \(\infty\)
Será responsabilidad de los usuarios hacer que la matriz sea simétrica.
Mediante el uso de la media geométrica o armónica de los valores no simétricos.
Mediante el uso de max o min, los valores no simétricos.
Estableciendo el triángulo superior para que sea la imagen reflejada del triángulo inferior.
Estableciendo el triángulo inferior para que sea la imagen reflejada del triángulo superior.
También es responsabilidad de los usuarios para fijar un valor \(\infty\) value.
Cada función funciona como parte de la familia a la que pertenece.
No devuelve una ruta.
Devuelve la suma de los costos de la ruta más corta para la combinación de pares de nodos en el grafo.
El proceso se realiza sólo en las aristas con costos positivos.
Valores son regresados cuando hay un camino.
Los valores devueltos tienen la forma de un conjunto de (start_vid, end_vid, agg_cost).
Cuando el vértice inicial y el vértice final son iguales, no hay camino.
El agg_cost en los valores no incluidos de (v, v) es 0.
Cuando el vértice inicial y el vértice final son diferentes y no hay ninguna ruta.
El “agg_cost” en los valores no incluidos de (u, v) es \(\infty\).
Sea el caso, los valores devueltos se almacenan en una tabla, por lo que el índice único sería el par: “(start_vid, end_vid)”.
Dependiendo de la función y sus parámetros, los resultados pueden ser simétricos.
El agg_cost de (u, v) es el mismo que para (v, u).
Se omite cualquier valor duplicado en start_vids.
Los valores regresados se ordenan:
start_vid ascendente
end_vid ascendente
Tiempo de ejecución: aproximadamente \(O(| start\_vids | * (V \log V + E))\)
Ver también¶
Índices y tablas