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.

Versiones anteriores de esta página

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