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))\)