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

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()));
    }

    public double formula(double ourCity, double enemyCity) {
            double a = Math.pow(ourCity, 2);
            double b = Math.pow(enemyCity, 2);
            double result = a - b;
            return Math.sqrt(result);
    }

但是，我的代码输出的完全是胡说八道。你能帮我解决我的问题并在 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( ) 在任何边缘..)，但不确定如何实现它。我尝试了多种放松方式，但 none 到目前为止接近正确答案。

谢谢！

Answer 1

我发现您的代码存在三个问题：

在图表中存储你的起始力会产生歧义，因为你无法判断这条边是你的力量还是敌人的力量作为权重。如果两个城市相互连接，这将是一个问题，因为你会得到双边。在您的示例中，而是使用变量将其存储在图表 class 中的某处 double startingForce = 120;

你对 relax 的呼唤在剩余部队和伤亡人员之间的切换是错误的。调用公式需要你的剩余兵力，但输出需要再次转化为伤亡。

double casualtiesWithCurrentPath = startingForce - formula(startingForce - d.get(u), e.getWeight());
if (casualtiesWithCurrentPath < d.get(v))
    d.put(v, casualtiesWithCurrentPath);

如果一个节点无法到达，它会造成 infinity 人伤亡，导致该节点中 -infinity 剩余部队。然而，通过在 formula 中对它们进行平方，符号会丢失，导致无限强度，因此您需要使用
进行计算
```
double a = Math.signum(ourCity) * Math.pow(ourCity, 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}

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

Finding the path in a graph with the least casualties according to the lanchester square law

java

shortest-path

bellman-ford