问题标签 [longest-path]

我正在尝试优化图形遍历问题，但无法找出解决它的最佳方法。它看起来既不是 A* 搜索问题（因为我们想要最大化路径而不是最小化它），也不是旅行商问题（因为我们不必访问所有城市）。它的简化版本是这样的：

我们有一组节点和连接/边。连接是任意的，节点可以有一个或多个。连接也有与之关联的接口/类型，并且接口不能支持多个连接。因此，例如，如果 nodeA可以连接到节点B或C通过 interface alpha，并且我们决定将其连接到 node B，则 node 上的接口A不再支持其他连接，因此C无法再连接A。但是，如果节点碰巧具有相同的接口，我们可以将节点连接C到节点。Dalpha

我还应该提到，这些接口就像锁和钥匙一样工作，所以A可以连接到B或，C但不能相互连接（接口就像一面镜子）。此外，虽然不能再通过接口连接到任何东西，因为它被 使用，如果它碰巧有另一个接口（）并且其他东西可以连接到，那么我们可以将多个节点连接到。目标是获得最大的连接节点组（丢弃所有较小的组）。BCAalphaBbravobravoA

我正在考虑一些启发式方法：

• 更喜欢具有更多接口的节点（我已经丢弃了没有对的接口）
• 更喜欢更流行的界面

上述两个规则可用于优先尝试连接到下一个节点（现在我天真地将它们分组为一个等级 - 可连接节点的总数），但我的直觉告诉我我可以做得更好。此外，我认为这不会有利于最佳解决方案。

我试图弄清楚我是否可以以某种方式反转启发式以创建一个变体，A* Search使得 A*“乐观启发式成本”规则仍然适用（即启发式成本 = 丢弃的节点数，但是，这破坏了实际成本计算 -因为我们将从丢弃除一个节点之外的所有节点开始）。

我的另一个想法是计算从起始节点到每个节点的距离（中间节点的数量），并将其平均值用作启发式方法，目标是连接所有节点。但是，我不能保证所有节点都会连接。

编辑： 这是一个例子

• 虚线表示允许（但未激活/经过）的连接
• 接口不允许连接同名的接口，但可以连接自己的'版本
• 接口只能使用一次（如果我们连接A到Bvia α，我们将无法再连接A，C因为A不再有α可用的接口）
• 节点的数量是任意的（但在算法执行期间是恒定的），并且应该假设非常大
• 每个节点的接口数将至少为一个，如果它使问题更容易，我们可以假设一个上限 - 即 3
• 可能的连接数只是接口兼容性的函数，接口定义节点可以连接的内容，是否/如何使用该接口取决于您
• 激活连接的方向/顺序无关紧要
• 目标是生成最大的连接节点集（我们不关心使用的连接或接口的数量）

我正在尝试制作一个 python 脚本，它可以让我获得给定矩阵中最长的重复字符（水平和垂直）。

例子：

我有这个矩阵：

给出这个矩阵作为输入，它应该得到：a 3

您可以看到矩阵的第 3 列充满了 a，而且它是矩阵中重复次数最多的字符。

我有的：

这是我的源代码。上面给出的示例也在源代码中使用。给出的结果是：r 2这是错误的......再次，应该是3

它有 4 个功能：main、search、stop 和 check_points。

• 主要是初始化事情，
• search 是我的递归函数，它接受一个参数（起点），并且应该递归地检查最长的字符串。我有另一个矩阵，长度与原始矩阵相同，只有 1 和 0。1 表示访问过的位置，0，不是。搜索功能在某个位置被搜索功能处理后，在正确的位置上设置 1。
• stop 正在检查 matrix2 是否全为 1，在这种情况下，矩阵已全部解析
• check_points 接受 2 个参数，2 个点列表，并返回重复次数最多的字符以及这些点的长度

什么不起作用：

大多数时候结果是给我错误的字符，即使有时计数可能是正确的。有时它会水平工作，有时则不会。我确定我做错了什么，但是......现在已经超过 1 周了，因为我试图弄清楚如何做到这一点。在stackoverflow上问了另一个问题，走得更远了，但......仍然卡住了。

任何建议表示赞赏。

假设我们需要绘制一个包含许多点的图形。例如输入：{1#2,2#3,3#11,1#11,4#11,4#5,5#6,4#12} 输出：7

一个节点可以直接连接到许多其他节点。我们需要在此图中找到最大连接节点，但不允许返回。

我已经尝试了很多算法来解决这个问题，但找不到。有人可以帮我吗？

提前致谢， 克里山

我正在研究一个必须用分支定界算法解决的问题。假设我们有 n 个加油站，距离起点不同。站有不同的利润。我们想要最大化利润，但每个站点必须远离至少 K 长度。我用动态算法解决了这个问题，但找不到分支定界算法的解决方案。实际上，我需要一个好的目标函数来确定界限。我尝试了很多功能，但都失败了。谢谢。

示例：n=5 k=10

距离值 l1= 5, l2=15, l3=23, l4=30, l5=38

利润：p1=7, p2=3, p3=10, p4=12, p5=6

我需要一种算法来在有向无环图中找到最长的加权路径networkx.MultiDiGraph()。我的图有加权边，许多边有一个空值作为权重。在networkx doc中，我没有找到任何解决此问题的方法。我的图表具有以下结构：

我找到了她，但我在实施时遇到了问题：

1. networkx：在有向图中有效地找到绝对最长的路径这个解决方案没有加权。
2. 如何使用 Python NetworkX 找到最长的路径？该解决方案将权重转换为负值，但我的图表具有空值……并且nx.dijkstra_path()不支持负值。

有没有人找到类似问题的想法或解决方案？

我尝试使用 python 解决地图（矩阵 4x4）的问题。

我想找到地图路径中的最大元素数，前提是下一个节点必须小于前一个节点以及矩阵中所有可能的元素组合。

运动就像从一个元素可以移动到东西南北

例如从 m[0][1] 可以移动到 m[0][2] 和 m[1][1] 4-> 8 或 2

这是示例代码，但我不知道如何递归检查每个元素。

如何递归这个函数循环到最后

例如，答案将类似于 8-5-3-2-1（具有递减因子的最长路径）

给定一个二维数组，找出最长的递减数序列。约束是： 1. 你不能对角比较元素。

例如：

答案是：7

对于下面的矩阵

答案是 25，因为我可以以 25 -> 24 -> 23 -> 22 -> .... 等方式移动......直到我达到 1。

有人可以帮我解决算法。

这是我的初始代码：

谢谢

图表要点：http ://gist.neo4j.org/?6182d024325343760cb4

我想按顺序获得一条（最长的）路径，并且在我添加 COLLECT 语句之前它按预期工作，是否有关于 Cypher 和 COLLECT 的内容我只是不理解或者这是一个错误？

此查询按预期工作，以正确的顺序返回路径中的节点：

这个没有 COLLECT 语句，以正确的顺序返回节点，但也返回部件和父级之间的节点（如预期的那样）。

此查询未按预期工作，以另一种顺序返回路径中的节点：

任何见解将不胜感激。

我有一个没有循环的加权有向图，我希望定义约束，以便我可以通过线性规划解决路径权重的最大化问题。但是，我无法解决如何做到这一点。

为此，我希望使用 LPSolve 工具。我曾想过制作一个邻接矩阵，但我不知道如何使用 LPSolve 来完成这项工作。

如何使用约束定义每个节点的可能路径，并使其足够通用，以便轻松适应其他图形？

我有一个有向循环加权图。我想找到一条权重最高的路径，长度为 X 个顶点，我不在乎目的地是什么。我只想找到最高的成本。