根据兰彻斯特平方定律在图中找到伤亡最少的路径

Question

我正在尝试使用 Bellman-Ford 算法在图中找到最佳路径。但是，我不希望使用所有边的总和来计算路径长度，而是希望伤亡最少的路径。我们使用以下公式计算伤亡人数：remainingSoldiers = sqrt(a^2 - b^2)，其中 A 是我军，B 是敌军，remainingSoldiers 是战斗结束后我方士兵的数量。

举个例子：假设我们要征服城市 D。我们从顶点 A 开始，部队人数为 100。我们的军队行进到顶点 B，那里有一支人数为 50 的敌军巡逻。根据我们的公式，我们有 86士兵离开了。接下来我军前往顶点C，所以我们86名士兵与40名巡逻顶点C的士兵战斗，我们还剩下76名士兵。最后，我们的 76 名士兵前往由 70 名敌方士兵守卫的顶点 D。根据我们的公式，我们用 29 名士兵征服了顶点 D。

所以为了找到最佳路径，我们必须计算走哪条路径才能使伤亡最少。我得到的提示是将我军的力量和敌军的力量设置为边的权重，并使用带有改进松弛算法的Bellman-Ford来找到最佳查找路径。这正是我在下面的代码中所做的。

我意识到，为了找到最佳路径，我必须找到伤亡人数最少的路径，而不是剩余士兵人数最多的路径，因为找到人数最多的路径是一个 NP 完全问题。

我的代码如下（我正在为图形使用自定义库，但它应该非常简单易懂）：

public Map<Vertex, Double> bellmanFord(Vertex s) {

            Map<Vertex, Double> d = g.createVertexMap(Double.POSITIVE_INFINITY);

            d.put(s, 0d);

            for (int i = 0; i < g.getVertices().size(); i++)

                    for (Edge e : g.getEdges())

                            relax(e, d);

            return d;

    }

    public void relax(Edge e, Map<Vertex, Double> d) {

            Vertex u = e.getSource();

            Vertex v = e.getTarget();

            if (d.get(u) + e.getWeight() < d.get(v))

                    d.put(v, d.get(u) + e.getWeight());

    }

下面是我为放松而修改的代码：

    public void relax(Edge e, Map<Vertex, Double> d) {

            Vertex u = e.getSource();

            Vertex v = e.getTarget();

            if (d.get(u) - formula(g.getEdge(u, v).getWeight(), g.getEdge(v, u).getWeight()) > d.get(v))

                d.put(v, d.get(u) - formula(g.getEdge(u, v).getWeight(), g.getEdge(v, u).getWeight()));

    }

但是，我的代码输出的完全是胡说八道。你能帮我解决我的问题并在 Bellman-Ford 算法的松弛方法中实现公式吗？

这是我启动代码时使用的图表（不是边缘情况，只是用于测试基本功能的随机图表）：https://i.imgur.com/Y2OhfDj.png。我们试图从A市攻克H市，我们120人的军队位于A市。当运行我修改后的代码时，bellman-ford 输出以下内容：{a=Infinity, d=Infinity, f=Infinity, g=Infinity, b=Infinity, c=Infinity, h=Infinity, e=Infinity}.我想我必须以某种方式修改代表我的军队力量的边，因为我的算法（我可以在任何边上使用方法 .setWeight() ..），但是不确定如何实施。我尝试了很多放松的变体，但到目前为止没有一个接近正确答案。

谢谢！

Answer 1

我发现您的代码存在三个问题：在图表中存储你的起始力会产生歧义，因为你无法判断这条边是你的力量还是敌人的力量作为权重。如果两个城市相互连接，这将是一个问题，因为你会得到双边。在您的示例中，而是使用变量将其存储在图形类中的某个位置&nbsp;double startingForce = 120;你的放松号召在剩余部队和伤亡之间以错误的方式切换。对于调用公式，您需要剩余的部队，但输出需要再次转换为伤亡人数。double&nbsp;casualtiesWithCurrentPath&nbsp;=&nbsp;startingForce&nbsp;-&nbsp;formula(startingForce&nbsp;-&nbsp;d.get(u),&nbsp;e.getWeight()); if&nbsp;(casualtiesWithCurrentPath&nbsp;<&nbsp;d.get(v)) &nbsp;&nbsp;&nbsp;&nbsp;d.put(v,&nbsp;casualtiesWithCurrentPath);如果一个节点无法到达，它就会有infinity人员伤亡，导致-infinity该节点的剩余部队。然而，通过将它们平方在formula符号中会迷路，导致无限的力量，所以你需要计算double&nbsp;a&nbsp;=&nbsp;Math.signum(ourCity)&nbsp;*&nbsp;Math.pow(ourCity,&nbsp;2);反而通过这些更改，我进入{a=13.229217479686895, b=17.043698590130006, c=11.372195087997852, d=12.761947052363922, e=4.241630972097752, f=0.41739256898601695, g=1.678404338007681, h=0.0}了示例