algorithm - 基于两个指标(距离、成本)的图形中的最佳(折衷)路径

Question

正如您从我的统计数据中看到的那样，尽管我多年来一直使用 stackoverflow.com 作为我的编程问题的答案来源，但我在这个论坛上还是个新手。我祈祷你能忽略我可能犯下的任何小失礼，并在下面分享你对我的小问题的想法。

我想知道是否有一种路由/路径查找算法能够随着时间和可能路径的成本找到最佳路径。理想情况下，我可以指定对时间、成本或最佳成本的最佳时间的偏好。

我一直在使用 Dijksta 算法在有向加权矩形网络上路由最短路径。所有节点都通过有向边连接到它们的左、右、上、下以及它们的 45° 邻居。这意味着所有节点都有 8 条边，减去外部边界处不存在的边。所有节点都可达，但可以增加度量(距离)以反射(reflect)更高的成本。我可以在相同节点上运行具有不同边缘列表的路线查找器，代表遍历它们时的成本(或距离)方面，从而找到最低成本或快速路线。它为我提供了具有距离度量的最短路线(角边为 1 或 SQRT(2))。

现在我一直想知道一种方法，可以通过简单地将距离和成本方面相乘并生成混合指标来将它们融合在一起。您如何看待这种方法，或者是一种让路由算法选择不同的“最佳”邻居以找到最佳路由的方法，无论是时间、成本还是妥协。

谢谢。

Answer 1

您可以在新代数中使用任何已知算法(Dijkstra、Floyd–Warshall)。
将您的距离视为具有两个字段的结构:

struct Distance {
    int cost, distance;
}

现在您需要定义 operator< 和 operator+。如果您想以最佳成本获得最佳时间，您应该使用:

bool operator<(Distance d1, Distance d2) {   
   if (d1.cost == d2.cost) 
       return d1.time1 < d2.time
   else 
       return d1.cost < d2.cost; 
}

或一些权重:

bool operator<(Distance d1, Distance d2) {   
   return wCost*d1.cost + wDistance*d1.distance < wCost*d2.cost + wDistance*d2.distance
}