在直接加权图中找到从节点A到节点B的所有简单路径，权重之和小于某个值？

  • Z时代
  • 2024-01-10
  • 分类：问答

我有一个有 图G =（V，E），它 。

我正在尝试确定最佳的省时算法来完成任务：t

（为方便起见，我们将该值表示为PATH_WEIGHT_LIMIT）

所有权重均为正，可以浮动。

因此，我的函数原型将是：

def find_paths(G, source, target, path_weight_limit)

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

与此处讨论的内容非常相似，例如：

  1. 查找加权有向循环图中从A到B的不同路径的数量的算法

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

但是我没有找到一种算法来解决上面提出的特定任务，该算法无法找到

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

回答：

回答：

从理论上讲，每个节点的权重都为1+，因此循环不会成为问题，因为权重会随着路径的增长而增加。但是…如果您的任何节点的成本/权重<=

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。该列表是您的路径。

寻路是一个非常强大的工具，但是您可以在网上找到的大多数算法和指南都是引言，甚至我找到的最佳指南Amit Patel的A *

Tutorial也不是很深入。

许多寻路系统只能找到一条路径，因为它们太专业了，因此我对算法进行了概括。在下面，您会找到深入的寻路指南，该指南包含的信息比Google所能找到的更多。我之所以加入它，是因为它使您能够导出功能更强大的寻路算法，例如从多个起始位置开始甚至从执行起始时间开始，找到多个路径和目标。这将帮助您实现算法。

深度寻路指南

建立新的寻路系统所需的一切

寻路的本质是以下算法：

  1. 从打开的节点列表开始（通常包含1个项目）

  2. 选择最有前途的1个节点

    • 如果节点是目标2，则将其添加到列表目标

    • 如果节点有效，则生成相邻3个候选节点的列表（list cand）

  4. 对于每个候选者，如果它无效4，请将其从列表cand中删除。然后，将list cand添加到list open。

  5. 从打开的列表中删除所选节点，并将其添加到关闭的列表中

  6. 寻路5时重复步骤2

笔记：

[1]：这是大多数寻路算法有所不同的地方；他们对节点的优先顺序不同。

  • 先进先出（最早）是最简单的算法；只是检查节点在它们添加到列表中的顺序开放。通常看起来像BFS。

  • 先进先出（最新）选择添加到列表中的最新节点。根据您的节点生成器，它看起来很像DFS。

  • BFS搜索的深度最少，通常不是最佳选择。

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

  • 贪婪选择最低的成本/重量。与完美的解决方案相比，搜索可能会陷入高成本区域，并最终导致成本很高的路径。通常，A *是速度和最佳性之间的更好折衷。

  • Dijkstra选择 总 成本/重量最低的节点。在大范围内速度很慢，但是如果您需要完美的解决方案，那是一个不错的选择。

  • 最佳优先选择具有最低（估计）剩余成本的节点来达到目标​​。在许多情况下，估算值是到目标的实际距离（欧几里得，曼哈顿等），但并非总是可以知道。

  • A 是Dijkstra +最佳第一。这两种启发式方法相互抵消，因此在开放区域中，A 会快速移动，但不会卡住。A

    *并不完美，但是它比Dijkstra的速度快得多。您可以权衡试探法以使算法更贪婪或更优化，也可以添加其他成本函数，例如与医疗包，掩护或敌方玩家的距离。

    *

    当您的节点包含大量数据时，自定义试探法通常会发挥作用。这通常意味着您已经从寻路进入了状态空间搜索领域，例如预测对手在国际象棋中将采取的下一步行动。涉及资源管理的问题将使用自定义试探法对每个资源进行优先级排序，以确定节点的权重。

[2]：有时目标节点不是一个位置。有时候，您可能想找到具有特定对象的 任何

节点，例如健康包，商店或容易杀死的敌方玩家。通过使用goal()功能检查节点，可以定义多个端点。

[3]：候选节点不必彼此相邻。您正在使用的是函数f(node) =

list(nodes)。在搜索游戏状态以获取玩家的生命值或生命值时，可以为动作创建节点，例如JUMP，ATTACK，REST等。在某些情况下，您需要先验证生成的节点列表，

然后 再添加它们。

[4]：无效节点通常只是列表关闭之前已搜索过的节点。但是，它们可以是距离太远的节点，与墙壁碰撞的节点（实际上是常见的），将玩家健康状况降低到0的节点等。如果您决定不使用node

isn't in closed list该条件，则可以允许您的算法回溯（可以创建无限循环）。

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

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

以上是 在直接加权图中找到从节点A到节点B的所有简单路径，权重之和小于某个值？ 的全部内容， 来源链接： utcz.com/qa/423364.html

回到顶部