在直接权重图中找出从节点A到节点B的所有简单路径，其权重之和小于某个值？ [英] Find all simple path from node A to node B in direct weighted graph with the sum of weighs less a certain value?

问题描述

我有一个有向加权图G =（V，E），可能有循环

。

我正在尝试确定完成任务的最佳时间有效算法：o在源和目标节点之间找到G中的所有简单路径，并且此路径中边的总权重小于某个值（为了方便起见我们将这个值表示为PATH_WEIGHT_LIMIT）

所有权重都是正数，并且可以是浮点数。

所以，原型我的函数将会是：

$ $ $ $ $ c $ def> find_paths（G，source，target，path_weight_limit）

结果路径可能重叠，很好。

很像这里讨论的那些，例如：
$ b $ ol

算法用于在加权定向循环图中查找从A到B的不同路径的数量 li>

在UNDERICTED图（NP问题）中找到所有简单路径

但我没有找到一个算法解决我在上面提出的具体任务，以便在源和目标节点之间找到G（有向，加权，循环）中的所有简单路径，并且此路径中边的总权重小于某个值

我认为应该使用修改后的DFS算法，重点关注路径当前部分的权重。但我认为它不是有效的，也许有更好的算法来解决这个问题。

>

理论上，每个节点的权重都是1+，所以循环不会成为问题，因为随着路径的增长权重会增加。但是......如果你的任何节点的成本/重量<= 0，那么你应该包括一个最大时间或深度，以停止寻路。

如果你需要完美的路径，使用Djikstra的算法。如果您不关心完美性，请使用A *。当您创建候选节点列表时，请在将它们添加到搜索列表之前进行验证。任何总重量超过最大值的节点都应该从候选名单中删除。

所以像这样：

 当前节点 - >候选节点列表 - （它们是否少？） - >下一个节点列表
合并（搜索节点列表，下一个节点列表）
  

在找到目标节点时停止，将目标节点添加到列表并在完成寻路时创建路径。大多数寻路节点的实现如下所示：

 节点
  - 节点以前的
  - 深度，成本
  - 其他数据（坐标，hp，黄金，地形，实体）
  

追踪路径很简单：将目标节点添加到列表中，然后将以前的添加到列表，直到previous = null 。这个列表是你的路径。

Pathfinding是一个非常强大的工具，但大部分算法和指南都可以在网上找到，其中包括介绍，甚至是我发现的最佳指南，Amit Patel的 A *教程并不是很深。

许多寻路系统只能找到一条路径，因为它们太专业化了，所以我推广了这些算法。下面，您会发现一个深入的寻路指南，其中包含的信息比您在Google上找到的信息要多。我将它包含的原因是因为它允许您从多个起始位置开始，甚至管理执行时间，从而获得更强大的寻路算法，例如查找多个路径和目标。它将帮助你实现你的算法。

深入探索指南

系统

寻路的本质就是这种算法：

1. 从列表_开始开始节点（通常包含1个项目） 选择最有前途的 ¹ 节点
>

2. 
   
   • 如果节点是一个目标 ² ，请将其添加到_目标
   
   
   • 如果节点有效，则生成一个相邻的 ³ 候选节点（列表 _cand ）列表
     


3. 对于每个候选人，如果它是无效的 ⁴ ，请从列表 _cand 中将其删除。然后，将list _cand 添加到 _open 列表中。 从列表_打开中删除所选节点并添加它列出_关闭


4. 重复步骤2，同时寻找路径 ⁵

注：

[1]：这是大多数寻路算法分歧的地方;他们对节点进行不同的优先级。

• 先进先出（最早）是最简单的算法;只需按照添加到列表 _open 的顺序检查节点。通常看起来像BFS。


• First In，Last Out（最新）选择添加到列表中的最新节点。它可以看起来很像DFS，具体取决于您的节点生成器。


• BFS搜索最小深度，通常不是最佳选择算法。


• DFS优先考虑深度最大的节点。它倾向于选择一条路径，并继续沿着它走下去，即使它永远消失。


• 贪婪选择移动到的最低成本/重量。搜索可能会陷入高成本区域，最终会出现与完美解决方案相比成本非常高的路径。通常A *是速度和最优性之间更好的折中方案。


• Dijkstra选择一个节点的成本/重量最低。它在很大的范围内速度很慢，但如果您想要完美的解决方案，那么这是一个不错的选择。
  
• Best-first选择具有最低（估计）剩余成本的节点来实现目标。在许多情况下，估计值是实际到达目标的距离（欧几里得，曼哈顿等），但并不总是可以知道的。


• A *是Dijkstra + Best-first。这两种启发式方法相互抵消，以便在开放区域，A *快速移动，但不会卡住。 A *并不完美，但它比Dijkstra更快。您可以衡量启发式算法，使算法更加贪婪或更优化，还可以添加其他成本函数，如距离卫生套件，封面或敌方玩家。


• 自定义启发式当你的节点包含大量数据时，你就可以参与进来。这通常意味着你已经从寻找状态转移到状态空间搜索领域，比如预测你的对手将在国际象棋中做出的下一步棋。涉及资源管理的问题将使用自定义启发式方法来确定每个资源的优先级，以确定节点的权重。
  
  
  

  [2] ：有时目标节点不是单个位置。可能有时候你想找到任何具有特定对象的节点，比如健康工具包，商店或者易于杀死的敌方玩家。通过使用 goal（）函数检查节点，可以定义多个端点。
  
  

  [ 3]：候选节点不需要在彼此旁边。你正在做的是使用一个函数 f（node）= list（nodes）。在搜索游戏状态以获得玩家黄金或健康状态时，您可以为JUMP，ATTACK，REST等操作创建节点。在某些情况下，您需要在之前验证生成的节点列表 >添加它们。

  
  
  

  [4]：无效的节点通常只是列表 _closed 中以前搜索过的节点。但是，它们可能是过多的节点，与墙壁碰撞的节点（真的很常见），会使玩家的健康状况降至0的节点等等。如果您决定不使用节点不在关闭列表作为一个条件，那么你的算法可以回溯（可以创建无限循环）。

  
  
  

  [5]：你可以实现在某些条件满足时停止的算法。通常这被认为是找到了1个目标节点，但是你可以用这个做很多事情！您可以在一段时间后停止寻路，这对游戏引擎非常有用，因为您可能需要暂停以渲染帧并防止滞后。您也可以停止搜索节点列表是否变得太大，从而保持内存使用率较低。一旦你有了一定数量的解决方案，你甚至可以停下来。

  
  
  

  这个布尔停止条件/函数允许你在探路者花费太长时间，进入无限循环。在单线程中，这通常意味着你不再需要探路者。对于游戏引擎，在线游戏客户端和GUI应用程序，我喜欢在第二个线程中运行探路者，并在需要时将其唤醒。如果探路者找不到足够快的路径，愚蠢的人工智能会迅速作出决定，直到寻路结束。

  
  

I have a directed weighted graph G=(V,E), which may have loops.

I am trying to determine the best time efficient algorithm to accomplish task: to find all simple path in G between source and target node with total weight of edges in this path less than certain value (for convenience we denote this value as PATH_WEIGHT_LIMIT)

All weights is positive and can be float.

So, a prototype of my function will be:

def find_paths(G, source, target, path_weight_limit) 

Result paths may overlap, its fine.

Much like those discussed here, e.g.:

1. algorithm for finding NUMBER of distinct paths from A to B in weighted, directed, cyclic graph
2. find all simple path in UNDERICTED graph (NP-problem)

But I didn't find an algorithm to solve this specifically task that I posed above to find all simple path in G (directed, weighted, cyclic) between source and target node with total weight of edges in this path less than certain value

I think that should be used modified DFS algorithm with a focus on weights of current part of path. But I think it is not effective and maybe there are better algorithms to solve this.

解决方案

An answer to your question

Theoretically, every node has a weight of 1+, so loops won't be a problem because weight increases as a path grows. But... if any of your nodes have a cost/weight <= 0, then you should include a maximum time or depth in order to stop pathfinding.

If you want perfect paths, use Djikstra's algorithm. If you don't care about perfection, use A*. When you create a list of candidate nodes, validate them before adding them to the search list. Any nodes that have a higher total weight than your maximum should be removed from the candidate list.

So something like this:

Current node -> List of candidate nodes --(are they less?)-> List of next nodes
merge(list of search nodes, list of next nodes)

Instead of stopping when you find a goal node, add goal nodes to a list and make paths when you finish pathfinding. Most implementations of pathfinding nodes look like this:

Node
- Node previous
- depth, cost
- misc data (coordinates, hp, gold, terrain, entity)

Tracing the path is pretty easy: add the goal node to a list, then add previous to the list until previous = null. The list is your path.

Pathfinding is a very powerful tool, but most of the algorithms and guides you can find online are introductions and even the best guide I found, Amit Patel's A* Tutorial, isn't very deep.

Many pathfinding systems can only find one path because they're too specialized, so I generalized the algorithms. Below, you'll find an in-depth guide to pathfinding that has more information than you can find with google. The reason I include it is because it allows you to derive much more powerful pathfinding algorithms, such as finding multiple paths and goals, beginning from multiple starting locations, or even managing execution time. It will help you implement your algorithm.

In-depth Pathfinding Guide

Everything you need to make new pathfinding systems

The essence of pathfinding is this algorithm:

1. Start with a list_open of nodes (usually contains 1 item)
2. Select the most promising¹ node
3. • If the node is a goal², add it to a list_goal
   • if the node is valid, generate a list of adjacent³ candidate nodes (list_cand)
4. For each candidate, if it is invalid⁴, remove it from list_cand. Afterwards, add list_cand to list_open.
5. Remove the selected node from list_open and add it to list_closed
6. Repeat step 2 while pathfinding⁵

Notes:

[1]: This is where most pathfinding algorithms diverge; they prioritize nodes differently.

• First In, First Out (oldest) is the simplest algorithm; just check nodes in the order they are added to list_open. Often looks like BFS.
• First In, Last Out (newest) chooses the newest nodes added to the list. It can look a lot like DFS depending on your node generator.
• BFS searches the least depth and isn't usually the best algorithm to choose.
• DFS prioritizes the node with the greatest depth. It tends to choose a path and keep walking down it, even if it goes forever.
• Greedy chooses the lowest cost/weight to move to. The search can get stuck in a high cost area and end up with a path that has a very high cost compared to the perfect solution. Usually A* is a better compromise between speed and optimality.
• Dijkstra's chooses a node with the lowest total cost/weight. It is very slow in large areas but if you want perfect solutions, it is a good choice.
• Best-first chooses the node with the lowest (estimated) remaining cost to reach the goal. In many cases, the estimate is the actual distance to goal (euclidean, manhattan, etc.), but it is not always possible to know.
• A* is Dijkstra + Best-first. These two heuristics cancel eachother out so that in open areas, A* moves quickly, but doesn't get stuck. A* is not perfect, but it's much faster than Dijkstra's. You can weight either heuristic to make the algorithm more greedy or more optimal, and you can also add other cost functions like distance to health kits, cover, or enemy players.
• Custom heuristics usually come into play when your nodes contain a lot of data. This usually means that you've moved from pathfinding into the realm of state-space searches like predicting the next move your opponent will make in chess. Problems that involve resource management will use a custom heuristic to prioritize each resource in order to determine the weight of a node.

[2]: Sometimes the goal node isn't a single location. There may be times that you want to find any node that has a certain object like a health kit, a shop, or an enemy player that's easy to kill. By checking the node with a goal() function, it becomes possible to define multiple end-points.

[3]: candidate nodes don't need to be beside eachother. What you are doing is using a function f(node) = list(nodes). When searching a gamestate to get gold or health for a player, you can create nodes for actions like JUMP, ATTACK, REST, etc. In some cases, you'll want to validate the list of generated nodes before you add them.

[4]: Invalid nodes are usually just nodes in list_closed that have been searched before. However, they can be nodes that are too far, nodes that collide with walls (really common), nodes that would reduce your player health to 0, etc. If you decide not to use node isn't in closed list as a condition, then your algorithm is allowed to backtrack (which can create infinite loops).

[5]: You can implement the algorithm to stop when certain conditions are fulfilled. Normally this is assumed to be that 1 goal node is found, but there's so much you can do with this! You can stop pathfinding after a certain amount of time, which is excellent for game engines because you may need to pause to render frames and prevent lag. You can also stop searching if the node list becomes too big, keeping memory usage low. You can even stop once you have a certain amount of solutions.

This boolean stop condition/function allows you to abort pathfinding whenever the pathfinder takes too long, hogs resources or falls into an infinite loop. On a single thread, this usually means you no longer need the pathfinder. For game engines, online game clients and GUI applications, I like to run the pathfinder in a second thread and wake it up whenever I need it. If the pathfinder doesn't find a path fast enough, a dumb AI makes quick decisions until pathfinding finishes.

这篇关于在直接权重图中找出从节点A到节点B的所有简单路径，其权重之和小于某个值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！