图形搜索找到最有效率的rou

Question

我正在研究一个图形搜索问题，它可以归结为以下更简单的示例：

根据以下回复更新以澄清

复活节兔子在森林里跳来跳去收集彩蛋。他知道从每一丛灌木中可以得到多少个鸡蛋，但是每一个灌木都有一个独特的鸡蛋数量。复活节兔子要花30分钟才能从任何给定的灌木丛中收集。复活节兔子每周5天搜寻彩蛋，每天最多8小时。他通常在他的洞穴开始和结束，但周二他计划在他的朋友彼得兔子的洞穴结束他的一天。邦尼太太给了他一张单子，上面列出了在特定日期/时间访问的一些特定灌木丛——这些都是必须到达的中间站点，但不要列出所有站点（可能每天1-2次）。帮助复活节兔子设计一条在周末给他最多鸡蛋的路线。

给定参数：无向图（g），节点之间的距离为旅行时间，每天8小时，5个工作日，（节点，时间，日）元组列表（r），（起始节点，结束节点，日）元组列表

问题：设计一条路线，在不超过任何一天分配的时间的情况下，将5天内收集的价值最大化。在

约束：在规定的时间/天访问r中的每个节点。对于s中的每一天，在相应的节点开始和结束，收集值为0。每周访问节点不能超过一次。在

方法：由于没有太多的站点，考虑到每个站点的时间和旅行时间（在一个大的一天中可能是10-12），我的第一个想法是暴力强制所有在正确的点开始/停止的路线，然后运行这5次，删除所有访问的节点。在此基础上，分别计算每个允许路径的收集值。然而，这并不能解释这样一个事实，即我在第一天的“最佳”路线可能会毁掉第五天最好的路线，因为这一天需要停站。在

为了解决这个问题，我考虑运行一个长的搜索，将所有的日子串联起来，从t=0（周初）到t=40（周末），每天的开始/结束点作为中间站。这太长了，无法使用暴力。在

我正在努力解决这个问题-这不是一个TSP问题-我只访问所有节点的一小部分（可能是200个节点中的50个）。这也不是dijkstra的路径问题，最短的路径通常是无处可去。我需要在分配的时间内使收集到的总价值最大化，进行所需的中间停留。如有任何关于如何进行的想法，我们将不胜感激！现在我一直在使用python中的networkx来处理这个问题。在

编辑以下响应 作为对您的编辑的回应-我正在寻找一种解决问题的方法-我可以稍后再找出代码，我倾向于A*而不是MDFS，因为我不需要只找到一条路径（这将相对较快），我需要找到最佳路径的近似值。我正在努力创造一个启发式方法来捕捉时间限制（在下一站停留所需的时间），但也包括最大蛋数。我不想走最短的路，我要的是“最长”的路，鸡蛋最多。在评估下一步的发展方向时，我可以很容易地每分钟做一次鸡蛋，然后以最好的速度移动到灌木丛中，但我需要找出如何鼓励它慢慢地朝目标前进。总会有一个解决方案-我可以跳到第一个树丛，坐在那里一整天，然后去解决问题（在那里的位置/时间间隔是这样，它总是可以解决的）

Answer 1

提出问题的方式没有充分的意义。这确实是一个图搜索问题，最大化一个数之和（受其他约束），这可能是可以通过蛮力解决的，因为最终要遍历的节点数不一定会攀升到数百个（对于一次行程）。在

由于每个站点的30分钟约束，每条路径可能都有几个节点长。一天8小时，灌木丛之间的距离可以忽略不计，最多可以停16站。由于边缘成本不可忽略，这意味着每趟行程应该有<；<；16站。在

我们所追求的是5天收获的最大总和（最多5个数字）。每一天的收获是通过一条“成功”的道路收集到的鸡蛋的总和。 成功的路径被定义为满足以下所有约束条件的路径：

• 在同一个节点上结束。因此，除了星期二，这是一个周期。星期二的收获是一条小路。在
• 给定日期的周期包含Bunny夫人的 当天的名单。在
• 旅行时间总和少于8小时，包括30分钟的收获时间。在

因此，可以使用改进的深度优先搜索（DFS）算法。DFS本身可以为网络生成一个详尽的路径列表。但是，由于限制，这个DFS将不必遍历所有的DFS。在

除了到目前为止访问的节点外，这个DFS还跟踪迄今收集的“旅行时间”和“鸡蛋”，并且在每个“跳跃”时检查是否满足所有约束条件。如果不是，则它会回溯或放弃遍历的路径。此回溯动作“自我限制”枚举路径。在

如果推理到目前为止与问题一致（？），这就是为什么它似乎没有完全意义。如果我们将每周收获过程重复M次，以确定最佳的每日访问策略，那么我们将面临一个问题：确定一个足够大的M来覆盖大多数路径。相反，我们可以运行一次DFS并确定一次最大收获的路径，这将导致4*CycleDailyHarvest+TuePathHarvest的简单解决方案。另一个选择是放松8小时的限制，并说邦尼先生每天最多可以收获8小时，而不是8小时。在

换句话说，如果所有参数都是静态的，那么就没有理由多次运行此进程。例如，如果每个灌木在特定的分布范围内提供“最多k个鸡蛋”，也许我们可以找到一个平均每天/每周访问策略，并获得最大的产量。（或者到目前为止我对这个问题的看法是错误的，在这种情况下，请澄清）。在

星期二的任务更容易，就好像在寻找“源和目标之间的路径，时间总和大约为8小时，收集到的鸡蛋总数是最大的”。这也是为什么这个问题没有完全意义的另一个迹象。如果一切都是静态的（图结构，鸡蛋/灌木，每日收获间隔），那么只有一条这样的路径，不需要检查替代品。在

希望这有帮助。在

编辑（以下问题更新）： 更新并没有彻底改变之前的响应的核心，即“使用一个修改的DFS（用于彻底枚举所有路径/循环的可能性），并将约束编码为在每个跳上更新的度量（旅行时间、收获的卵）的条件”。它只修改约束的表示方式。最重要的改变是“每星期访问一次灌木”。这意味着DFS（访问的节点集）的内存不会在一个周期结束或一天结束时重置，而是在一周结束时重置。或者换句话说，DFS现在可以从预填充的visited集开始。这一点很重要，因为它将进一步减少“可行”路径长度的数量。事实上，取决于图形和鸡蛋的结构/bush问题甚至可能最终无法解决（即满足条件的零路径/循环）。在

编辑2: 这种方法有几个“问题”，我想在这里列出我认为你的观点还没有看到的有效点，但不是以辩论的方式：

• “我不需要只找到一条路径（这将相对快速），我需要找到一条最佳路径的近似值。”和“我要的是“最长”路径和最多的鸡蛋。”这两种说法有点矛盾，但平均而言，它们只指向一条路径。我之所以这么说，是因为它表明问题要么太难，要么没有完全理解

• 启发式只会有助于创造一个景观。如果没有两个最陡的路径，我们可能会有很多的“最小/最大值”的下降路径。

• A*的主要目标仍然是返回一条路径，必须对其进行修改以找到替代方案。

• 在图上操作时，不可能“鼓励”遍历朝特定目标移动，因为“遍历代理”不知道目标在哪里以及如何在权重的线性组合意义上到达目标（例如，“如果你走得太远，降低一些经验值，这将迫使代理开始左转返回其来源地。当兔子先生在他的洞穴里时，他有所有的K选择，在第一个可能的选择之后，他有K-M1（M1

• mdf将有助于跟踪根据图中指定的选择创建这些和的不同方式。（毕竟，这是一个图搜索问题）。

尽管如此，这里可能会采用其他的、次优的（在计算复杂性方面）解决方案。最明显的（但又是假的）是建立两个相互竞争的过程来实施自我控制。一个是想让兔子先生离开他的洞穴，另一个是试图让兔子先生回到他的洞穴。这两个进程都基于上述mdf，并跟踪MOVEAWAY+GOBACK的成本，它们产生的路径是节点的并集。它可能看起来有点像一个*但这个在每次遍历时都会被重置。它是这样运作的：

• 离开步骤：

  • 从Bunny先生的洞穴向外启动一个MDFS，并跟踪距离/鸡蛋总数，移动到成本最低/成本最高的目标节点。在

• 返回步骤：

  • 现在，预填充返回mdf的visited集，并尝试通过迄今为止未采用的路径返回原点。跟踪成本/回报。在

• 一旦你再次到家，你就有了一条可能的收集路径。当生成的路径在时间规范内时，重复上述操作。

这将产生一个路径调色板，您可以在一周内混合和匹配（4次重复+周二路径），以获得最低成本/最高回报选项。在

它不是最佳的，因为您可能会得到重复的路径（一个行程的结束是另一个行程的后面），而且因为这可以快速消除访问的节点，所以可能仍然很快就用完了解决方案。在