如何应用 Dijkstra 算法找到逛购物中心的最佳时间
How to apply Dijkstra algorithm to find the optimal time for visiting shopping centres
我在 HackerRank 上尝试了这个 Synchronous Shopping 问题，但我不知道如何解决它。所以我看了社论，我很困惑。也许我误解了 Dijkstra 的单源最短路径算法是如何工作的。
这取自 editorial:
他说
The shortest distance to the state D(V, B) denotes the minimum time required
to visit shopping center V with fish from the mask B bought.
然后他描述了我们从一种状态转移到另一种状态的两种可能方式，然后他说
When all the minimal times are calculated....
我猜他的意思是，在我们到达节点 N 之后，我们应该考虑所有可能的获取鱼的方法。所有 2^k 种方式。比如，我们考虑
1）当我们到达节点N时，我们只有第一条鱼
2) 我们只有第二条鱼...
3）我们只有第一条鱼和第二条鱼..
等..
但是如果我们运行Dijkstra，它会计算从节点1到节点N的最短路径，但是我们必须走一条特定的路径才能从节点1到节点N。我们只会得到沿这些节点可用的鱼。我们如何计算所有其他状态？ （用不同的鱼组到达节点 N）
让我试着帮助你，因为我最近做了这个练习。我将尝试逐步构建解决方案或主要思想。
问题总结：有两只猫，它们从1号开始，一直走到N号，每次都买一组鱼，只有两只猫都买完鱼，它们才能停在N号.两只猫可以走不同的路，重游购物中心。
这道题objective是求出买完所有鱼的最短时间，也就是两只猫到达N，两只猫一起买完所有鱼的最长时间。
现在，让我们尝试构建解决方案：想象一下，你没有鱼，你只想知道一只猫从购物 1 到 N 需要的最短时间。Dijkstra 可以解决这个问题，对吧？它将计算从源（商店 1）到所有其他节点的所有最短时间。
下一步是添加鱼：现在，假设我们只有一只猫，我们必须在每一站都买鱼。尝试想象以下情况：不是您的图形的每个顶点只是购物中心，而是猫到目前为止购买的鱼的购物和组合，存储信息。
这意味着可以多次将购物添加到优先级队列中，这在 "normal" Dijkstra 算法中不会发生。这使您可以计算从源头开始的最短时间以及所有可能的组合，以达到购买鱼类的购物目的。不幸的是，这会将顶点数量增加到 O(N*2^(k-1))。确保为所有顶点存储最短时间，我们将在下一步中使用它。
另一个基本技巧是将鱼保存在位集中而不是列表或向量中，因为购买鱼是 OR 操作。大多数使用的按位运算都是常量 O(1).
最后一步是添加第二个 cat:If 您计算 Dijkstra 如下所述，您将获得所有顶点的所有最短时间，这些顶点是所有购物和购买的鱼的状态。我们只对我们在商店 N 并且猫 1 和猫 2 购买的鱼的组合等于购买的所有鱼的情况感兴趣。
已经考虑到如果一只猫到达N，它必须等待另一只猫到达，这意味着无论一只猫买了什么鱼，如果另一只猫到达，如果其余的，没关系。
从技术上讲，您将处理所有可用于购物 N 的可能场景，如果猫 1 和 2 的鱼的组合等于所有购买的鱼，您将获得最短的时间（所有可能性中的最小值） .
不幸的是，这是一种详尽的方法，但通过得很好。这是Dijkstra处理后的两个for stacked。
我在 HackerRank 上尝试了这个 Synchronous Shopping 问题，但我不知道如何解决它。所以我看了社论，我很困惑。也许我误解了 Dijkstra 的单源最短路径算法是如何工作的。
这取自 editorial:
他说
The shortest distance to the state
D(V, B)denotes the minimum time required to visit shopping centerVwith fish from the maskBbought.
然后他描述了我们从一种状态转移到另一种状态的两种可能方式，然后他说
When all the minimal times are calculated....
我猜他的意思是，在我们到达节点 N 之后，我们应该考虑所有可能的获取鱼的方法。所有 2^k 种方式。比如，我们考虑
1）当我们到达节点N时，我们只有第一条鱼
2) 我们只有第二条鱼...
3）我们只有第一条鱼和第二条鱼..
等..
但是如果我们运行Dijkstra，它会计算从节点1到节点N的最短路径，但是我们必须走一条特定的路径才能从节点1到节点N。我们只会得到沿这些节点可用的鱼。我们如何计算所有其他状态？ （用不同的鱼组到达节点 N）
让我试着帮助你，因为我最近做了这个练习。我将尝试逐步构建解决方案或主要思想。
问题总结：有两只猫，它们从1号开始，一直走到N号，每次都买一组鱼，只有两只猫都买完鱼，它们才能停在N号.两只猫可以走不同的路，重游购物中心。
这道题objective是求出买完所有鱼的最短时间，也就是两只猫到达N，两只猫一起买完所有鱼的最长时间。
现在，让我们尝试构建解决方案：想象一下，你没有鱼，你只想知道一只猫从购物 1 到 N 需要的最短时间。Dijkstra 可以解决这个问题，对吧？它将计算从源（商店 1）到所有其他节点的所有最短时间。
下一步是添加鱼：现在，假设我们只有一只猫，我们必须在每一站都买鱼。尝试想象以下情况：不是您的图形的每个顶点只是购物中心，而是猫到目前为止购买的鱼的购物和组合，存储信息。
这意味着可以多次将购物添加到优先级队列中，这在 "normal" Dijkstra 算法中不会发生。这使您可以计算从源头开始的最短时间以及所有可能的组合，以达到购买鱼类的购物目的。不幸的是，这会将顶点数量增加到 O(N*2^(k-1))。确保为所有顶点存储最短时间，我们将在下一步中使用它。
另一个基本技巧是将鱼保存在位集中而不是列表或向量中，因为购买鱼是 OR 操作。大多数使用的按位运算都是常量 O(1).
最后一步是添加第二个 cat:If 您计算 Dijkstra 如下所述，您将获得所有顶点的所有最短时间，这些顶点是所有购物和购买的鱼的状态。我们只对我们在商店 N 并且猫 1 和猫 2 购买的鱼的组合等于购买的所有鱼的情况感兴趣。
已经考虑到如果一只猫到达N，它必须等待另一只猫到达，这意味着无论一只猫买了什么鱼，如果另一只猫到达，如果其余的，没关系。
从技术上讲，您将处理所有可用于购物 N 的可能场景，如果猫 1 和 2 的鱼的组合等于所有购买的鱼，您将获得最短的时间（所有可能性中的最小值） . 不幸的是，这是一种详尽的方法，但通过得很好。这是Dijkstra处理后的两个for stacked。