在jgraph中创建成本函数

Question

jgrapht支持在两个节点之间的边缘/顶点上放置wehight（成本）的想法。这可以使用DefaultWeightedEdge类来实现。

在我的图中，我确实有要求找不到最短的路径，但最便宜的。最便宜的路径可能会更长/有更多的跳跃节点可以在最短路径上行进。因此，可以使用DijkstraShortestPath算法来实现这一点。

但是，我的用例有点复杂：它还需要评估到达节点时需要执行的操作的成本。假设你有一个像国际象棋棋盘（8×8字段，每个字段都是一个节点）的图形。所有的边都有1的权重。要从一个汽车从左下角移动到对角线（右上角），有许多路径，成本为16.您可以采用zic zac风格的对角路径，或者您可以首先将所有节点向右移动，然后向上移动所有节点。 区别在于：在拍摄zic zac时，您需要按照移动的方向旋转自己。你旋转16次。 当首先向右移动然后向上时，您只需旋转一次（也许两次，取决于您的开始方向）。 所以zic zac路径从Djikstra的角度来看是完美的。从逻辑的角度来看，这是最糟糕的。

长话短说：我如何在节点或边缘上放置一些费用，具体取决于该路径中以前的边缘/节点？我没有在jgrapht的源代码中找到任何相关的东西。 还是有更好的算法使用？

Answer 1

这不是一个JGraphT问题，而是一个图算法问题。您需要考虑如何对此问题进行编码并将其更形式化，更详细地说

1. 合并顶点上的权重通常很容易。假设每个顶点都代表访问一个客户，这需要花费时间。这可以通过将a_i/2添加到节点i中每个输入弧的成本以及每个输出弧的成本的a_i/2来编码在图中。

2. 一个成本函数，其中从j到k依赖者在您用来前往j的弧（i，j）上移动的成本更为复杂。

方法a：使用动态规划（标记）算法。这也许是最简单的。您可以将您的成本函数定义为递归函数，其中遍历圆弧的成本取决于之前圆弧的成本。方法b .:使用一些技巧，您可以通过向图中添加额外的节点来对图中的成本进行编码。下面是一个例子：

给定一个具有顶点{a，b，c，d，e}，带有圆弧的图：（a，e），（e，b），（c，e），（e，d ）。该图表示顶点e位于中间的交叉路口。从a→e→b（直线）出发是免费的，但是从a→e→d转弯需要更多时间。类似于c-> e-> d（直线）是免费的，并且c-> e-> b（转弯）应该受到惩罚。 在4个新顶点中去耦顶点e：e1，e2，e3，e4。 （e1，e3），（e1，e4），（e1，e4），（e4， e2，e4）。 （e1，e4）和（e2，e3）可以具有正的权重来惩罚车削。