图搜索 - 找到最有效率的路线
Graph search - find most productive route
我正在研究可以提炼为以下更简单示例的图形搜索问题：
已更新以根据以下回复进行澄清
复活节兔子在森林里跳来跳去收集彩蛋。他知道每个灌木丛中会产多少卵，但每个灌木丛的卵数量都是唯一的。从任何给定的灌木丛中收集复活节兔子需要 30 分钟。复活节兔子每周寻找彩蛋 5 天，每天最多 8 小时。他通常在自己的洞穴中开始和结束，但周二他计划在朋友彼得兔的洞穴结束一天的活动。 Bunny 夫人给了他一些特定灌木丛的清单，以便在特定 days/times 访问 - 这些是必须到达的中间停靠点，但不要列出所有停靠点（每天可能 1-2 个）。 帮助复活节兔子设计一条在周末给他最多彩蛋的路线。
给定参数：无向图（g），节点间距离为行程时间，每天8小时时间，5个工作日，列表（node,time,day ) 元组 (r) , (startNode, endNode, day) 元组列表 (s)
问题：设计一条路线，使在 5 天内收集的价值最大化，而不会在任何给定的一天超过分配的时间。
约束：按规定time/day访问r中的每个节点。对于s中的每一天，开始和结束于对应的节点，其集合值为0。每周访问节点不能超过一次。
方法： 因为不会有太多的停靠点，考虑到每个停靠点的时间和旅行时间（大日子里可能需要 10-12 次）我的第一个想法是在正确的点强制所有 start/stop 的路由，并且只是 运行 这 5 次，删除所有访问过的节点。从那里，分别计算每个允许路由的收集值。然而，这并没有说明我在第一天的 "best" 路线可能会毁掉一条在第五天最好的路线，因为那天需要停靠。
为了解决这个问题，我考虑 运行通过连接所有日期并从 t = 0（一周的开始）到 t = 40（一周的结束）开始进行一次长时间的搜索，start/end 每一天的点数作为中间停靠点。这对于蛮力来说太长了。
我正在为如何解决这个问题而苦苦挣扎——这不是 TSP 问题——我只会访问所有节点的一小部分（可能是 200 个节点中的 50 个）。这也不是 dijkstra 的路径问题，最短路径通常是无处可去。我需要在分配的时间内最大化收集的总价值，从而进行所需的中间停留。任何关于如何进行的想法将不胜感激！现在我一直在 python.
中使用 networkx 来解决这个问题
编辑以下回复
作为对您编辑的回应——我正在寻找一种解决问题的方法——我可以稍后找出代码，我倾向于 A* 而不是 MDFS，因为我不需要只找到一个路径（那将相对较快），我需要找到最佳路径的近似值。我正在努力创建一种启发式方法来捕获时间限制（保持在下一站所需的时间之内），但也能捕获最多的鸡蛋。我不是很想要最短路径，我想要鸡蛋最多的"longest"路径。在评估下一步去哪里时，我可以很容易地做 eggs/min 并以最佳速度移动到灌木丛，但我需要弄清楚如何鼓励它慢慢地向目标移动。总会有解决方案的——我可以跳到第一个灌木丛，坐在那里一整天，然后找到解决方案（中间有 placement/time 总是可以解决的）
提出问题的方式没有充分的意义。最大化数字总和（受其他约束）确实是一个图形搜索问题，它可能可以通过蛮力解决，因为最终将被遍历的节点数量不一定会攀升到数百个（因为一次旅行）。
由于每个站点有 30 分钟的限制，每条路径可能有几个节点长。一天 8 小时，灌木丛之间的距离可以忽略不计，最多可以停靠 16 个站点。由于边缘成本不可忽略，这意味着每次行程应该有 <<16 个站点。
我们要的是5天收获的最大总和（五个数字的最大值）。每天的收获是 "successful" 路径上收集的鸡蛋的总和。
成功的路径定义为满足所有约束的路径：
- 路径在同一个节点上开始和结束。因此这是一个周期，除了星期二。周二的收获是一条路。
- 给定日期的周期包含兔子夫人指定的节点
那天的清单。
- 包括 30 分钟的收获时间在内，总行程时间不到 8 小时。
因此，您可以使用改进的深度优先搜索 (DFS) 算法。 DFS 本身可以为网络生成详尽的路径列表。但是，由于限制，这个 DFS 将不必遍历所有这些。
除了到目前为止访问过的节点之外，此 DFS 还跟踪到目前为止收集的 "travel time" 和 "eggs"，并在每个 "hop" 处检查是否满足所有约束。如果不是，则它回溯或放弃遍历的路径。此回溯操作 "self-limits" 枚举路径。
如果推理到目前为止与问题一致 (?)，这就是它似乎没有完全意义的原因。如果我们将每周收获过程重复 M 次以确定最佳的每日访问策略，那么我们将面临确定足够大的 M 以覆盖大部分路径的问题。相反，我们可以 运行 DFS 一次并确定一次最大收获的路线，这将导致 4*CycleDailyHarvest + TuePathHarvest 的简单解决方案。另一种选择是放宽 8 小时的限制，并说兔子先生每天最多可以收获 8 小时，而不是准确的 8 小时。
换句话说，如果所有参数都是静态的，那么就没有理由多次运行这个过程。例如，如果每个灌木丛按照特定的分布给出 "up to k eggs"，也许我们可以发现一个平均每日/每周访问策略，收益最大。 （或者我目前对问题的理解是错误的，在这种情况下，请澄清）。
周二的任务比较简单，好像在找"the path between source and target whose time sum is approximately 8hrs and sum of collected eggs is max"。这是为什么问题没有完全意义的另一个迹象。如果一切都是静态的（图形结构，eggs/bush，每日收获间隔）那么只有一条这样的路径，无需检查替代方案。
希望对您有所帮助。
编辑（问题更新后）：
更新并没有从根本上改变先前响应的核心，即 "Use a modified DFS (for the potential of exhaustively enumerating all paths / cycles) and encode the constraints as conditions on metrics (travel time, eggs harvested) that are updated on each hop"。它只修改约束的表示方式。最重要的改动是 "visit each bush once per week"。这意味着 DFS（访问节点的集合）的内存不会在循环结束时或一天结束时重置，而是在一周结束时重置。或者换句话说，DFS 现在可以从预先填充的 visited 集合开始。这很重要，因为它将进一步减少 "viable" 路径长度的数量。事实上，根据图的结构和 eggs/bush 问题甚至可能最终无法解决（即满足条件的零路径/循环）。
编辑2：
有一些 "problems" 我想在这里列出我认为你的观点尚未看到但不是争论性方式的有效观点：
"I don't need to just find one path (that will be relatively quick), I need to find an approximation of the best path."和"I want the "最长的“鸡蛋最多的路径。”有一点自相矛盾的陈述，但平均而言，它们只指向一条路径。之所以这么说，是因为说明要么题太难，要么理解不透(?)
启发式只会有助于创造风景。我们仍然需要遍历地形（例如最陡的下降/上升），并且会有很多振荡的机会，因为算法可能会陷入两个 "too-low"、"too-high" 备选方案之间或发现局部最小值 /最大值，没有明显的方法可以摆脱它们。
A*s main objective 仍然是 return 一条路径，必须对其进行修改以找到替代方案。
在对图进行操作时，无法"encourage"遍历到特定的目标，因为"traversing agent"不知道目标在哪里以及如何从权重的线性组合的意义上到达那里（例如"If you get too far, lower some Xp which will force the agent to start turning left heading back towards where it came from"。当兔子先生在他的洞穴时，他有所有 K 个选择，在第一个可能的选择之后他有 K-M1（M1
MDFS 将帮助跟踪允许根据图表指定的选择创建这些和的不同方式。 （毕竟，这是一个图形搜索问题）。
话虽如此，这里可能会采用替代的、次优的（在计算复杂性方面）解决方案。显而易见的（但虚假的）再次是建立两个相互竞争的过程来施加自我控制。一只试图把兔子先生从他的洞穴里救出来，一只试图把兔子先生带回他的洞穴里。这两个过程都是基于上面的MDFS，都在跟踪MOVEAWAY+GOBACK的代价，它们产生的路径是节点的并集。它可能看起来有点像 A*，但它在每次遍历时都会重置。它是这样运作的：
离开步骤：
- 从兔子先生的洞穴向外开始MDFS并跟踪距离/鸡蛋总和，移动到lowestCost/highestReward目标节点。
返回步骤：
- 现在，预填充 GO BACK MDFS 的
visited 集，并尝试通过未采用的路线返回家中。跟踪成本/回报。
再次回到家后，您就有了可能的收集途径。当生成的路径在时间规范内时重复上述操作。
这将产生一个路径调色板，您可以在一周内混合搭配这些路径（4 次重复 + 星期二路径）以获得最低成本/最高奖励选项。
这不是最佳选择，因为您可能会得到重复的路径（一次旅行的 AWAY 是另一次旅行的 BACK），并且因为这会快速消除访问过的节点，所以它可能仍然 运行 很快就没有解决方案。
我正在研究可以提炼为以下更简单示例的图形搜索问题：
已更新以根据以下回复进行澄清
复活节兔子在森林里跳来跳去收集彩蛋。他知道每个灌木丛中会产多少卵，但每个灌木丛的卵数量都是唯一的。从任何给定的灌木丛中收集复活节兔子需要 30 分钟。复活节兔子每周寻找彩蛋 5 天，每天最多 8 小时。他通常在自己的洞穴中开始和结束，但周二他计划在朋友彼得兔的洞穴结束一天的活动。 Bunny 夫人给了他一些特定灌木丛的清单，以便在特定 days/times 访问 - 这些是必须到达的中间停靠点，但不要列出所有停靠点（每天可能 1-2 个）。 帮助复活节兔子设计一条在周末给他最多彩蛋的路线。
给定参数：无向图（g），节点间距离为行程时间，每天8小时时间，5个工作日，列表（node,time,day ) 元组 (r) , (startNode, endNode, day) 元组列表 (s)
问题：设计一条路线，使在 5 天内收集的价值最大化，而不会在任何给定的一天超过分配的时间。
约束：按规定time/day访问r中的每个节点。对于s中的每一天，开始和结束于对应的节点，其集合值为0。每周访问节点不能超过一次。
方法： 因为不会有太多的停靠点，考虑到每个停靠点的时间和旅行时间（大日子里可能需要 10-12 次）我的第一个想法是在正确的点强制所有 start/stop 的路由，并且只是 运行 这 5 次，删除所有访问过的节点。从那里，分别计算每个允许路由的收集值。然而，这并没有说明我在第一天的 "best" 路线可能会毁掉一条在第五天最好的路线，因为那天需要停靠。
为了解决这个问题，我考虑 运行通过连接所有日期并从 t = 0（一周的开始）到 t = 40（一周的结束）开始进行一次长时间的搜索，start/end 每一天的点数作为中间停靠点。这对于蛮力来说太长了。
我正在为如何解决这个问题而苦苦挣扎——这不是 TSP 问题——我只会访问所有节点的一小部分（可能是 200 个节点中的 50 个）。这也不是 dijkstra 的路径问题，最短路径通常是无处可去。我需要在分配的时间内最大化收集的总价值，从而进行所需的中间停留。任何关于如何进行的想法将不胜感激！现在我一直在 python.
中使用 networkx 来解决这个问题编辑以下回复 作为对您编辑的回应——我正在寻找一种解决问题的方法——我可以稍后找出代码，我倾向于 A* 而不是 MDFS，因为我不需要只找到一个路径（那将相对较快），我需要找到最佳路径的近似值。我正在努力创建一种启发式方法来捕获时间限制（保持在下一站所需的时间之内），但也能捕获最多的鸡蛋。我不是很想要最短路径，我想要鸡蛋最多的"longest"路径。在评估下一步去哪里时，我可以很容易地做 eggs/min 并以最佳速度移动到灌木丛，但我需要弄清楚如何鼓励它慢慢地向目标移动。总会有解决方案的——我可以跳到第一个灌木丛，坐在那里一整天，然后找到解决方案（中间有 placement/time 总是可以解决的）
提出问题的方式没有充分的意义。最大化数字总和（受其他约束）确实是一个图形搜索问题，它可能可以通过蛮力解决，因为最终将被遍历的节点数量不一定会攀升到数百个（因为一次旅行）。
由于每个站点有 30 分钟的限制，每条路径可能有几个节点长。一天 8 小时，灌木丛之间的距离可以忽略不计，最多可以停靠 16 个站点。由于边缘成本不可忽略，这意味着每次行程应该有 <<16 个站点。
我们要的是5天收获的最大总和（五个数字的最大值）。每天的收获是 "successful" 路径上收集的鸡蛋的总和。 成功的路径定义为满足所有约束的路径：
- 路径在同一个节点上开始和结束。因此这是一个周期，除了星期二。周二的收获是一条路。
- 给定日期的周期包含兔子夫人指定的节点 那天的清单。
- 包括 30 分钟的收获时间在内，总行程时间不到 8 小时。
因此，您可以使用改进的深度优先搜索 (DFS) 算法。 DFS 本身可以为网络生成详尽的路径列表。但是，由于限制，这个 DFS 将不必遍历所有这些。
除了到目前为止访问过的节点之外，此 DFS 还跟踪到目前为止收集的 "travel time" 和 "eggs"，并在每个 "hop" 处检查是否满足所有约束。如果不是，则它回溯或放弃遍历的路径。此回溯操作 "self-limits" 枚举路径。
如果推理到目前为止与问题一致 (?)，这就是它似乎没有完全意义的原因。如果我们将每周收获过程重复 M 次以确定最佳的每日访问策略，那么我们将面临确定足够大的 M 以覆盖大部分路径的问题。相反，我们可以 运行 DFS 一次并确定一次最大收获的路线，这将导致 4*CycleDailyHarvest + TuePathHarvest 的简单解决方案。另一种选择是放宽 8 小时的限制，并说兔子先生每天最多可以收获 8 小时，而不是准确的 8 小时。
换句话说，如果所有参数都是静态的，那么就没有理由多次运行这个过程。例如，如果每个灌木丛按照特定的分布给出 "up to k eggs"，也许我们可以发现一个平均每日/每周访问策略，收益最大。 （或者我目前对问题的理解是错误的，在这种情况下，请澄清）。
周二的任务比较简单，好像在找"the path between source and target whose time sum is approximately 8hrs and sum of collected eggs is max"。这是为什么问题没有完全意义的另一个迹象。如果一切都是静态的（图形结构，eggs/bush，每日收获间隔）那么只有一条这样的路径，无需检查替代方案。
希望对您有所帮助。
编辑（问题更新后）：
更新并没有从根本上改变先前响应的核心，即 "Use a modified DFS (for the potential of exhaustively enumerating all paths / cycles) and encode the constraints as conditions on metrics (travel time, eggs harvested) that are updated on each hop"。它只修改约束的表示方式。最重要的改动是 "visit each bush once per week"。这意味着 DFS（访问节点的集合）的内存不会在循环结束时或一天结束时重置，而是在一周结束时重置。或者换句话说，DFS 现在可以从预先填充的 visited 集合开始。这很重要，因为它将进一步减少 "viable" 路径长度的数量。事实上，根据图的结构和 eggs/bush 问题甚至可能最终无法解决（即满足条件的零路径/循环）。
编辑2： 有一些 "problems" 我想在这里列出我认为你的观点尚未看到但不是争论性方式的有效观点：
"I don't need to just find one path (that will be relatively quick), I need to find an approximation of the best path."和"I want the "最长的“鸡蛋最多的路径。”有一点自相矛盾的陈述，但平均而言，它们只指向一条路径。之所以这么说，是因为说明要么题太难，要么理解不透(?)
启发式只会有助于创造风景。我们仍然需要遍历地形（例如最陡的下降/上升），并且会有很多振荡的机会，因为算法可能会陷入两个 "too-low"、"too-high" 备选方案之间或发现局部最小值 /最大值，没有明显的方法可以摆脱它们。
A*s main objective 仍然是 return 一条路径，必须对其进行修改以找到替代方案。
在对图进行操作时，无法"encourage"遍历到特定的目标，因为"traversing agent"不知道目标在哪里以及如何从权重的线性组合的意义上到达那里（例如"If you get too far, lower some Xp which will force the agent to start turning left heading back towards where it came from"。当兔子先生在他的洞穴时，他有所有 K 个选择，在第一个可能的选择之后他有 K-M1（M1
MDFS 将帮助跟踪允许根据图表指定的选择创建这些和的不同方式。 （毕竟，这是一个图形搜索问题）。
话虽如此，这里可能会采用替代的、次优的（在计算复杂性方面）解决方案。显而易见的（但虚假的）再次是建立两个相互竞争的过程来施加自我控制。一只试图把兔子先生从他的洞穴里救出来，一只试图把兔子先生带回他的洞穴里。这两个过程都是基于上面的MDFS，都在跟踪MOVEAWAY+GOBACK的代价，它们产生的路径是节点的并集。它可能看起来有点像 A*，但它在每次遍历时都会重置。它是这样运作的：
离开步骤：
- 从兔子先生的洞穴向外开始MDFS并跟踪距离/鸡蛋总和，移动到lowestCost/highestReward目标节点。
返回步骤：
- 现在，预填充 GO BACK MDFS 的
visited集，并尝试通过未采用的路线返回家中。跟踪成本/回报。
- 现在，预填充 GO BACK MDFS 的
再次回到家后，您就有了可能的收集途径。当生成的路径在时间规范内时重复上述操作。
这将产生一个路径调色板，您可以在一周内混合搭配这些路径（4 次重复 + 星期二路径）以获得最低成本/最高奖励选项。
这不是最佳选择，因为您可能会得到重复的路径（一次旅行的 AWAY 是另一次旅行的 BACK），并且因为这会快速消除访问过的节点，所以它可能仍然 运行 很快就没有解决方案。