首页 文章

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

提问于
浏览 次
0

我有一个 directed weighted 图G =（V，E），其中 may have loops .

我正在尝试确定完成任务的最佳时间效率算法：t o find all simple path in G between source and target node with total weight of edges in this path less than certain value （为方便起见，我们将此值表示为PATH_WEIGHT_LIMIT）

所有重量均为正值，可以浮动 .

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

def find_paths(G, source, target, path_weight_limit)

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

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

  • 算法，用于在加权定向循环图中查找从A到B的不同路径的NUMBER

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

但我没有找到一个算法来解决我在上面提出的具体任务 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

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

algorithm graph graph-algorithm graph-theory path-finding

1 回答

  • 1

    回答你的问题

    从理论上讲，每个节点的权重都为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，都不是很深 .

    许多寻路系统只能找到一条路径，因为它们过于专业化，所以我推广了算法 . 下面，您将找到一个深入的寻路指南，其中包含的信息比谷歌找到的更多 . 我加入它的原因是因为它允许您派生更强大的寻路算法，例如从多个起始位置开始查找多个路径和目标，甚至管理执行时间 . 它将帮助您实现算法 .

    深入寻路指南

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

    寻路的本质是这个算法：

    以列表打开节点开始（通常包含1个项目）选择最有前途的1节点如果节点是goal2，如果节点有效则将其添加到listgoal，生成相邻3个候选节点的列表（listcand）对于每个候选节点，如果它是无效的4，将其从listcand中删除 . 然后，将listcand添加到listopen . 从listopen中删除所选节点并将其添加到listclosed重复步骤2 while pathfinding5注意：[1]：这是大多数寻路算法发散的地方;他们以不同方式优先考虑节点 . 先进先出（最老）是最简单的算法;只需按照添加到listopen的顺序检查节点 . 通常看起来像BFS . First In，Last Out（最新）选择添加到列表中的最新节点 . 它看起来很像DFS，具体取决于您的节点生成器 . BFS搜索的深度最小，通常不是最佳选择算法 . DFS对具有最大深度的节点进行优先级排序 . 它倾向于选择一条路径并继续沿着它行走，即使它永远消失 . 贪婪选择最低的成本/重量去 . 搜索可能会陷入高成本区域，并且与完美解决方案相比，最终会出现成本非常高的路径 . 通常A *是速度和最优性之间更好的折衷 . Dijkstra选择总成本/重量最低的节点 . 它在很大的范围内非常慢，但如果你想要完美的解决方案，它是一个不错的选择 . Best-first选择具有最低（估计）剩余成本的节点来达到目标 . 在许多情况下，估计是到目标的实际距离（欧几里德，曼哈顿等），但并不总是可以知道 . A *是Dijkstra Best-first . 这两个启发式方法相互抵消，因此在开放区域，A *移动很快，但不会卡住 . A *并不完美，但它比Dijkstra快得多 . 您可以加权启发式以使算法更贪婪或更优化，还可以添加其他成本函数，例如距离 Health 工具包，封面或敌方玩家 . 当您的节点包含大量数据时，自定义启发式通常会发挥作用 . 这通常意味着你已经从寻路移动到状态空间搜索领域，比如预测对手将在国际象棋中进行的下一步动作 . 涉及资源管理的问题将使用自定义启发式来确定每个优先级资源以确定节点的权重 . [2]：有时目标节点不是单个位置 . 有时您可能希望找到任何具有特定对象的节点，例如 Health 工具包，商店或易于杀死的敌方玩家 . 通过使用goal（）函数检查节点，可以定义多个 endpoints . [3]：候选节点不需要彼此相邻 . 你正在做的是使用函数f（node）= list（nodes） . 当搜索游戏状态以获得玩家的黄金或 Health 时，您可以为JUMP，ATTACK，REST等操作创建节点 . 在某些情况下，您需要在添加之前验证生成的节点列表 . [4]：无效节点通常只是listclosed中之前搜索过的节点 . 但是，它们可能是太远的节点，与墙壁碰撞的节点（真的很常见），会将玩家 Health 状况降低到0的节点等等 . 如果您决定不使用节点不在封闭列表中作为条件，然后允许你的算法回溯（这可以创建无限循环） . [5]：您可以实现算法以在满足某些条件时停止 . 通常这被认为是找到了1个目标节点，但是你可以做到这一点！您可以在一定时间后停止寻路，这对于游戏引擎非常有用，因为您可能需要暂停以渲染帧并防止延迟 . 如果节点列表变得太大，您也可以停止搜索，从而保持较低的内存使用率 . 一旦你有一定数量的解决方案，你甚至可以停止 . 这个布尔停止条件/函数允许您在路径查找器耗时太长，占用资源或陷入无限循环时中止路径寻找 . 在单个线程上，这通常意味着您不再需要路径查找器 . 对于游戏引擎，在线游戏客户端和GUI应用程序，我喜欢在第二个线程中运行路径查找器，并在需要时将其唤醒 . 如果探路者找不到足够快的路径，那么愚蠢的AI会快速做出决定，直到寻路结束 .

    回复于

相关问题