在直接加权图中找到从节点 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)，它可能有环.

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

所有权重都是正数，可以浮动.

所以，我的函数原型是:

def find_paths(G, source, target, path_weight_limit)

结果路径可能会重叠，没关系.

很像这里讨论的那些，例如:

1. 在加权、有向、循环图中查找从 A 到 B 的不同路径数的算法
2. 在 UNDERICTED 图中找到所有简单的路径(NP 问题)

但是我没有找到一种算法来解决我上面提出的这个特定任务找到源节点和目标节点之间的 G 中的所有简单路径(有向、加权、循环)以及这条路径中边的总权重小于一定值

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

解决方案

问题的答案

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

如果您想要完美的路径，请使用 Djikstra 的算法.如果您不在乎完美，请使用 A*.创建候选节点列表时，请先验证它们，然后再将它们添加到搜索列表中.任何总权重高于最大权重的节点都应从候选列表中删除.

就像这样:

当前节点 ->候选节点列表--(它们更少吗?)->下一个节点列表合并(搜索节点列表，下一个节点列表)

不是在找到目标节点时停止，而是将目标节点添加到列表中，并在完成寻路后创建路径.大多数寻路节点的实现看起来像这样:

节点- 上一个节点- 深度，成本- 其他数据(坐标、hp、黄金、地形、实体)

跟踪路径非常简单:将目标节点添加到列表中，然后将previous 添加到列表until previous = null.列表就是你的路径.

寻路是一个非常强大的工具，但你可以在网上找到的大多数算法和指南都是介绍，甚至是我找到的最好的指南，Amit Patel 的 A* 教程，不是很深入.

许多寻路系统只能找到一条路径，因为它们太专业了，所以我对算法进行了概括.在下面，您将找到一份深入的寻路指南，其中包含的信息比您使用 google 所能找到的要多.我包含它的原因是因为它允许您派生出更强大的寻路算法，例如寻找多个路径和目标，从多个起始位置开始，甚至管理执行时间.它将帮助您实现您的算法.

深度寻路指南

制作新寻路系统所需的一切

寻路的本质就是这个算法:

<块引用>

1. 从节点列表_打开开始(通常包含 1 个项目)
2. 选择最有希望的¹节点
3. • 如果节点是目标²，则将其添加到列表中_goal
   • 如果节点有效，则生成相邻³候选节点的列表(list_cand)
4. 对于每个候选，如果无效⁴，将其从列表中删除_cand.然后，将 list_cand 添加到 list_open.
5. 从列表中移除选中的节点_open并将其添加到列表_closed
6. 寻路时重复第 2 步⁵

注意事项:

[1]:这是大多数寻路算法的分歧所在；他们对节点的优先级不同.

• 先进先出(最古老)是最简单的算法；只需按照节点添加到 list_open 的顺序检查节点.通常看起来像 BFS.
• 先进后出(最新)选择添加到列表中的最新节点.根据您的节点生成器，它可能看起来很像 DFS.
• BFS 搜索的深度最少，通常不是最好的算法选择.
• DFS 优先考虑具有最大深度的节点.它倾向于选择一条路径并继续沿着它走下去，即使它会永远走下去.
• Greedy 会选择成本/重量最低的移动目标.搜索可能会陷入高成本区域，最终会得到一条与完美解决方案相比成本非常高的路径.通常，A* 是速度和最优性之间更好的折衷方案.
• Dijkstra 选择具有最低总成本/权重的节点.它在大面积上很慢，但如果你想要完美的解决方案，它是一个不错的选择.
• Best-first 选择具有最低(估计)剩余成本的节点来达到目标​​.在许多情况下，估算值是到目标(欧几里得、曼哈顿等)的实际距离，但并不总是可能知道.
• A* 是 Dijkstra + Best-first.这两个启发式相互抵消，因此在开放区域中，A* 移动迅速，但不会卡住.A* 并不完美，但它比 Dijkstra 快得多.您可以对启发式算法进行加权以使算法更贪婪或更优化，还可以添加其他成本函数，例如与医疗包、掩体或敌方玩家的距离.
• 自定义启发式通常在您的节点包含大量数据时发挥作用.这通常意味着您已经从寻路转移到状态空间搜索领域，例如预测对手在国际象棋中的下一步行动.涉及资源管理的问题将使用自定义启发式方法来确定每个资源的优先级，以确定节点的权重.

[2]:有时目标节点不是单个位置.有时您可能希望找到任何具有特定对象的节点，例如医疗包、商店或易于杀死的敌方玩家.通过使用 goal() 函数检查节点，可以定义多个端点.

[3]:候选节点不需要彼此相邻.您正在做的是使用函数 f(node) = list(nodes).在搜索游戏状态以获取玩家的金币或生命值时，您可以为跳跃、攻击、休息等操作创建节点.在某些情况下，您需要之前验证生成的节点列表> 你添加它们.

[4]:无效节点通常只是列表_closed中之前已经搜索过的节点.但是，它们可能是太远的节点、与墙壁碰撞的节点(非常常见)、将玩家健康值降低到 0 的节点等.如果您决定不使用 node is not in closed list 作为条件，那么你的算法就可以回溯(这会产生无限循环).

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

这个布尔停止条件/函数允许您在探路者花费太长时间、占用资源或陷入无限循环时中止寻路.在单个线程上，这通常意味着您不再需要探路者.对于游戏引擎、在线游戏客户端和 GUI 应用程序，我喜欢在第二个线程中运行探路者，并在需要时将其唤醒.如果探路者找不到足够快的路径，愚蠢的 AI 会快速做出决定，直到寻路完成.

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屋！