在直接加权图中找到从节点 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)，可能有环。
我正在尝试确定完成任务的最佳时间效率算法：to 找到 G 中源节点和目标节点之间的所有简单路径，该路径中边的总权重小于特定值（为方便起见，我们将此值表示为 PATH_WEIGHT_LIMIT）
所有权重都是正数，可以是浮点数。
因此，我的函数原型将是：
def find_paths(G, source, target, path_weight_limit)
结果路径可能重叠，没关系。
很像这里讨论的那些，例如：
- 用于在加权、有向、循环图中查找从 A 到 B 的不同路径的 NUMBER 条算法
- 找到未定义图中的所有简单路径（NP 问题）
但是我没有找到算法来解决我在上面提出的这个特定任务找到 G 中源节点和目标节点之间总权重为的所有简单路径（有向、加权、循环）此路径中的边小于特定值
我认为应该使用修改后的 DFS 算法，重点关注路径当前部分的权重。但我认为它不是有效的，也许有更好的算法可以解决这个问题。
您问题的答案
理论上，每个节点的权重都是 1+，因此循环不会成为问题，因为权重会随着路径的增长而增加。但是...如果您的任何节点有 cost/weight <= 0，那么您应该包括最大时间或深度以停止寻路。
如果您想要完美路径，请使用 Djikstra 算法。如果您不在乎完美，请使用 A*。创建候选节点列表时，请在将它们添加到搜索列表之前对其进行验证。任何总权重高于最大值的节点都应从候选列表中删除。
所以像这样：
Current node -> List of candidate nodes --(are they less?)-> List of next nodes
merge(list of search nodes, list of next nodes)
不要在找到目标节点时停止，而是将目标节点添加到列表中，并在完成寻路后创建路径。大多数寻路节点的实现如下所示：
Node
- Node previous
- depth, cost
- misc data (coordinates, hp, gold, terrain, entity)
跟踪路径非常简单：将目标节点添加到列表，然后将 previous 添加到列表 until previous = null。该列表是您的路径。
Pathfinding 是一个非常强大的工具，但是您可以在网上找到的大多数算法和指南都是介绍性的，即使是我找到的最好的指南，Amit Patel 的 A* Tutorial，也不是很深。
很多寻路系统只能找到一条路径，因为它们太专业了，所以我把算法概括了。在下面，您将找到一份深入的寻路指南，其中包含的信息比您在 google 中找到的信息更多。我包含它的原因是因为它允许您派生出更强大的寻路算法，例如寻找多条路径和目标，从多个起始位置开始，甚至管理执行时间。它将帮助您实现您的算法。
深度寻路指南
制作新寻路系统所需的一切
寻路的本质就是这个算法：
- Start with a listopen of nodes (usually contains 1 item)
- Select the most promising1 node
-
- If the node is a goal2, add it to a listgoal
- if the node is valid, generate a list of adjacent3 candidate nodes (listcand)
- For each candidate, if it is invalid4, remove it from listcand. Afterwards, add listcand to listopen.
- Remove the selected node from listopen and add it to listclosed
- Repeat step 2 while pathfinding5
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 listopen. 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 listclosed 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.
我有一个有向加权图G=(V,E)，可能有环。
我正在尝试确定完成任务的最佳时间效率算法：to 找到 G 中源节点和目标节点之间的所有简单路径，该路径中边的总权重小于特定值（为方便起见，我们将此值表示为 PATH_WEIGHT_LIMIT）
所有权重都是正数，可以是浮点数。
因此，我的函数原型将是：
def find_paths(G, source, target, path_weight_limit)
结果路径可能重叠，没关系。
很像这里讨论的那些，例如：
- 用于在加权、有向、循环图中查找从 A 到 B 的不同路径的 NUMBER 条算法
- 找到未定义图中的所有简单路径（NP 问题）
但是我没有找到算法来解决我在上面提出的这个特定任务找到 G 中源节点和目标节点之间总权重为的所有简单路径（有向、加权、循环）此路径中的边小于特定值
我认为应该使用修改后的 DFS 算法，重点关注路径当前部分的权重。但我认为它不是有效的，也许有更好的算法可以解决这个问题。
您问题的答案
理论上，每个节点的权重都是 1+，因此循环不会成为问题，因为权重会随着路径的增长而增加。但是...如果您的任何节点有 cost/weight <= 0，那么您应该包括最大时间或深度以停止寻路。
如果您想要完美路径，请使用 Djikstra 算法。如果您不在乎完美，请使用 A*。创建候选节点列表时，请在将它们添加到搜索列表之前对其进行验证。任何总权重高于最大值的节点都应从候选列表中删除。
所以像这样：
Current node -> List of candidate nodes --(are they less?)-> List of next nodes
merge(list of search nodes, list of next nodes)
不要在找到目标节点时停止，而是将目标节点添加到列表中，并在完成寻路后创建路径。大多数寻路节点的实现如下所示：
Node
- Node previous
- depth, cost
- misc data (coordinates, hp, gold, terrain, entity)
跟踪路径非常简单：将目标节点添加到列表，然后将 previous 添加到列表 until previous = null。该列表是您的路径。
Pathfinding 是一个非常强大的工具，但是您可以在网上找到的大多数算法和指南都是介绍性的，即使是我找到的最好的指南，Amit Patel 的 A* Tutorial，也不是很深。
很多寻路系统只能找到一条路径，因为它们太专业了，所以我把算法概括了。在下面，您将找到一份深入的寻路指南，其中包含的信息比您在 google 中找到的信息更多。我包含它的原因是因为它允许您派生出更强大的寻路算法，例如寻找多条路径和目标，从多个起始位置开始，甚至管理执行时间。它将帮助您实现您的算法。
深度寻路指南
制作新寻路系统所需的一切
寻路的本质就是这个算法：
- Start with a listopen of nodes (usually contains 1 item)
- Select the most promising1 node
- If the node is a goal2, add it to a listgoal
- if the node is valid, generate a list of adjacent3 candidate nodes (listcand)
- For each candidate, if it is invalid4, remove it from listcand. Afterwards, add listcand to listopen.
- Remove the selected node from listopen and add it to listclosed
- Repeat step 2 while pathfinding5
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 listopen. 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 listclosed 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 listas 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.