时间戳

首页 > 解决方案 > 根据兰彻斯特平方定律在图中找到伤亡最少的路径

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

问题描述

我正在尝试使用 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() ..），但是不确定如何实现它。我尝试了许多放松的变体，但到目前为止没有一个接近正确答案。

谢谢！

标签： javashortest-pathbellman-ford

解决方案

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

  1. 将您的起始力量存储在图表中会产生歧义，因为您无法判断该边缘是否具有您的力量或敌人的力量作为权重。如果两个城市相互连接，这将是一个问题，因为您将获得双刃。而是使用变量将其存储在图形类中的某个位置，在您的示例中 double startingForce = 120;

  2. 您的呼叫放松在剩余部队和伤亡之间切换错误的方式。要调用公式，您需要剩余的部队，但输出需要再次转换为伤亡人数。

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

  3. 如果一个节点无法到达，它就会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}在示例中得到

推荐阅读