如何应用Dijkstra算法找到前往购物中心的最佳时间

Question

我在HackerRank上尝试过此Synchronous Shopping问题，但不知道如何解决。所以我看了社论，我很困惑。也许我误解了Dijkstra的单一来源最短路径算法的工作原理。

取自editorial：

他说

到状态D(V, B)的最短距离表示所需的最短时间带着从面具V买来的鱼参观购物中心B。

然后他描述了我们可能从一种状态转移到另一种状态的两种可能方式，然后他说

计算所有最短时间后....

我想他是说，到达节点N后，我们应该考虑所有可能的方法来获取鱼。所有2 ^ k种方式。就像，我们考虑

1）当我们到达节点N时，我们只有第一条鱼

2）我们只有第二条鱼...

3）我们只有第一条鱼和第二条鱼。.

等。

但是如果我们运行Dijkstra，它将计算从节点1到节点N的最短路径，但是我们必须经过一条特定的路径才能从节点1到节点N。并且，我们将仅沿这些节点获得鱼。我们如何计算所有其他状态？ （到达节点N的鱼类不同）

Answer 1

让我尝试帮助您，就像我最近做的练习一样。我将尝试逐步构建解决方案或主要思想。

问题的摘要：有两只猫，它们从购物1开始，一直到N。在每次购物中，他们都买了一套鱼，如果两只猫都买了所有鱼，他们只能在N停下来。两只猫可以走不同的路并重游购物中心。

问题的目的是找到购买所有鱼类的最短时间，这是两只猫达到N且两个人一起购买所有可用鱼类之间的最长时间。

现在，让我们尝试建立解决方案：想象您没有鱼，而您只想知道猫从购物1到购物N所需的最短时间。Dijkstra可以解决这个问题，对吗？它将计算从源（车间1）到所有其他节点的所有最短时间。

[下一步是添加鱼：现在，假设我们只有一只猫，并且我们必须在每个站点购买鱼。试想一下以下情况：到目前为止，购物和这只猫购买的各种鱼类的组合并不仅仅是购物商场，而是存储信息。

这意味着购物可以多次添加到优先级队列中，这在“常规” Dijkstra算法中不会发生。这使您可以从来源和所有可能的组合中计算出最短的时间，以购买的鱼类达到购物的目的。不幸的是，这将顶点的数量增加到O（N * 2 ^（k-1））。确保存储所有顶点的时间最短，我们将在下一步中使用它。

[另一个基本技巧是将鱼保留在位集中，而不是列表或向量，因为购买鱼是“或”运算。使用的大多数按位运算是常量O（1）。

最后一步是添加第二只猫：如果您按照如下所述计算Dijkstra，您将获得所有顶点的最短时间，这是所有购物和所购鱼类的状态。我们只对在N店的情况感兴趣，猫1和2购买的鱼的组合等于所有购买的鱼。

[已考虑到的是，如果一只猫到达N，则必须等待另一只猫到达，这意味着无论一只猫买了什么鱼，如果另一只猫买了，其余的都可以。

[从技术上讲，您将处理可用于购物N的所有可能方案，并且如果猫1和2的鱼的组合等于所购买的所有鱼，则得到的时间最短（所有可能性中的最小值）。不幸的是，这是一种详尽的方法，但是效果很好。这是在Dijkstra处理后用于堆叠的两个。

Answer 2

1. 为了简化问题，让我们考虑只有1猫。然后，对于每种鱼类组合，我们都可以为猫计算出到达目的地的最佳时间n。这是可行的，因为鱼的类型数量有限，因此只有2^10组合。
2. 现在，由于找到了所有可能的组合，每只2猫将到达拥有其中一只的目的地n。但是，为了找到两只猫的最佳时间，我们应该检查包含所有产品类型的每对配置，并选择最短的最佳时间。
3. 实际上，使用这种方法，我们可以找到任意数量的猫的解决方案-唯一的不同是最后（寻找最短时间）的for个循环数。对于3猫，它应该是3，对于4猫，它应该是4，依此类推。

现在，代码：

public class Solution {
    private static final class Shop {
        private final int shopId;
        private final int time;

        public Shop(int shopId, int time) {
            this.shopId = shopId;
            this.time = time;
        }
    }

    private static final class ShopAssortment {
        private final int shopId;
        private final int assortment;

        public ShopAssortment(int shopId, int assortment) {
            this.shopId = shopId;
            this.assortment = assortment;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] nmk = scanner.nextLine().split("\\s+");
        int n = Integer.parseInt(nmk[0]);
        int m = Integer.parseInt(nmk[1]);
        int k = Integer.parseInt(nmk[2]);

        int[] fishTypesAtShop = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            String[] ta = scanner.nextLine().split("\\s+");
            int numOfFishTypes = Integer.parseInt(ta[0]);

            // encode fish types into an integer 
            for (int j = 1; j <= numOfFishTypes; j++) {
                int type = Integer.parseInt(ta[j]) - 1;
                fishTypesAtShop[i] |= (1 << type);
            }
        }

        // initialise connections map so that key denotes a shop and value - list of shops connected to it
        Map<Integer, List<Shop>> connections = new HashMap<>();
        for (Integer i = 1; i <= n ; i++) {
            connections.put(i, new ArrayList<Shop>());
        }
        for(int i = 0; i < m; i++) {
            String[] roadsLine = scanner.nextLine().split("\\s+");
            int startShopId = Integer.parseInt(roadsLine[0]);
            int endShopId = Integer.parseInt(roadsLine[1]);
            int time = Integer.parseInt(roadsLine[2]);

            connections.get(startShopId).add(new Shop(endShopId, time));
            connections.get(endShopId).add(new Shop(startShopId, time));
        }

        int numOfFishTypeCombinations = 1 << k;
        // optimalTime denotes the optimal time for every node with any fish type combination
        int[][] optimalTime = new int[n + 1][numOfFishTypeCombinations];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < numOfFishTypeCombinations; j++) {
                optimalTime[i][j] = Integer.MAX_VALUE;    
            }
        }
        optimalTime[1][fishTypesAtShop[1]] = 0;

        Queue<ShopAssortment> queue = new LinkedList<>();
        queue.add(new ShopAssortment(1, fishTypesAtShop[1]));
        while(!queue.isEmpty()) {
            ShopAssortment shopAssortment = queue.remove();
            int time = optimalTime[shopAssortment.shopId][shopAssortment.assortment];
            int shopId = shopAssortment.shopId;
            int assortment = shopAssortment.assortment;

            for (Shop nextShop : connections.get(shopId)) {
                int nextShopId = nextShop.shopId;
                int expectedTime = time + nextShop.time;
                int nextAssortment = assortment | fishTypesAtShop[nextShopId];

                // IMPORTANT: traverse nextShopId shop only if it's optimal from time prospective
                // It can happen in 2 cases - either it's the first time visit or we're trying to get there another time from a different shop
                if (expectedTime < optimalTime[nextShopId][nextAssortment]) {
                    optimalTime[nextShopId][nextAssortment] = expectedTime;
                    queue.add(new ShopAssortment(nextShopId, nextAssortment));
                }
            }
        }

        int allFishTypes = (1 << k) - 1;
        int minTime = optimalTime[n][allFishTypes];
        // traverse each pair of configurations and pick the pair resulting into the full set of fish types and minimal optimal time
        for (int i = 1; i <= allFishTypes; i++) {
            for (int j = i; j <= allFishTypes; j++) {
                if ((i | j) == allFishTypes) {
                    minTime = Math.min(minTime, Math.max(optimalTime[n][i], optimalTime[n][j]));
                }    
            }
        }

        System.out.println(minTime);
    }
}

该解决方案通过了[[Hackerrank上的所有测试。