问题标签 [graph-traversal]

给定一个无向正加权图G ， G的一些边具​​有未知权重。例如，

其中边缘（B，C）的权重未知。

从A穿越到B花费你7。我们可以通过从B遍历到C来推导出未知的权重e = weight(B,C) ，反之亦然，并花费你e，最终成为一个已知的权重。从A走到C通过B总共花费你e+7。

我的问题是，当给定一个起点时，我们能以多快的速度获得所有未知的重量？也就是说，以尽可能小的成本从起点（例如A ）遍历所有未知的权重边。

未知权重的个数为1的情况很简单。您可以先找出从起点到所需边的顶点的最短路径，然后遍历未知权重边。但是，当未知权重边的数量大于 1 时，我不知道如何解决。

谁能弄清楚如何做到这一点？

所以我有一个无向无权图。它包含循环。我想找到访问最多节点而不重复访问任何节点的路径。由于这是一个图遍历，你可以在任何你喜欢的节点开始和结束。

背景研究： 我看过旅行商问题（TSP）；这个问题是不同的，不允许你从你开始的地方完成并且没有重量。我查看了其他几种算法，但没有发现适合这个问题的算法。

Graph Size：图中有100个节点；有 10 个断开连接的节点。

更新：我已将此移至：https ://math.stackexchange.com/questions/243375/what-is-the-maximum-number-of-nodes-i-can-traverse-in-an-undirected-graph-访问i

我必须设计一个分支定界算法，每次都解决笛卡尔平面上图形的最优路径。我已经得到提示，在运行时早期识别无望的分支将复合成一个运行“快一百倍”的程序。我的想法是假设连接到开始/结束节点的最短边将是巡回赛中的第一条或最后一条边，但薄菱形图证明并非如此。有没有人对如何消除这些无望的分支或谈论这个的参考有想法？

基本上，有没有比仅按字典顺序更好地分支到解决方案子集的更好方法，例如。第一个分支包含和排除边缘 ab，第二个分支包含和排除分支 ac

我正在遍历我设置为一个类的图，使用向量来存储顶点和边。我在图表上使用深度优先搜索来显示路径，但我想以某种方式让我的代码在通过它们时按顺序显示顶点，格式如下：

其中“u”和“v”都是起始顶点（我希望它在同一个顶点开始和结束），“i”值是它沿途经过的顶点。

这是我目前拥有的 DFS 功能，我已经对其进行了简化，以便可以将其用作一般参考。我可以在这里修改什么以使其显示我想要的内容吗？（当前未设置为显示任何内容）。

简而言之，我的问题是——我是否可以修改 Neo4j 使用的遍历逻辑——在可达性计算期间，如何控制哪些边被遍历，哪些不被遍历。

详细描述：

我正在考虑从我们当前的数据库迁移到 neo4j，我想知道 neo4j 是否适合以下任务：

我们有大约 1000 万个简单节点的大图——它们的属性只有一个 id。
我们也有 3 种边缘 - “标准”、“打开”和“关闭”。"opening" 和 "closeing" 也有一个 "color" 属性，所以它们是匹配的。每个“开放”边都有一个匹配的“关闭”边“。例如，有一个颜色为“3”的开放边缘，所以也有一个颜色相同的关闭边缘。

我们需要解决两个节点之间的可达性问题，其中遍历规则相当简单：您可以随意通过标准边，也可以根据需要通过开放边，同时保持访问的“开放”边的顺序堆栈但是（这是棘手的部分）当你来到一个有几个“关闭”边缘的交叉点时，你必须穿过与遇到的最后一个“打开”边缘匹配的关闭边缘，然后从堆。

例如：

a -[标准]->B-[打开颜色：3]->C-[标准]->D-[关闭颜色：3]->E
还有
D-[关闭颜色：4]->F

请注意，D 有两个“闭合”边缘，颜色不同。根据上面定义的规则，A 可以访问 E，因为颜色堆栈的顶部有 [3]。
然而，A 无法到达 F。

可以为这样的图遍历逻辑配置 neo4j 吗？谢谢！！

对于给定的一组公司节点，我们正在尝试使用 Traversal API 仅检索提供产品节点列表中包含的所有产品的公司节点。之前使用 Cypher 的尝试效果不佳。在这个例子中：

如果所有 3 家公司都包含在公司列表查询中，并且产品 A 和 C 在查询的产品列表中，我们希望只返回公司 2 和 3，因为它们提供产品 A 和 C。这是我们的查询：

如果我们使用 ，Evaluator.includeWhereEndNodeIs(productNodes)我们将返回列表中提供任何产品的productNodes所有公司（以上示例中的所有 3 家公司）。如果我们使用Evaluators.includeIfContainsAll(productNodes)评估器，如果产品节点列表中有多个产品，我们将不会返回任何公司节点。

任何建议表示赞赏。

我有一个带有无向加权边的完整图，需要通过图节点的子集找到最低成本循环。与Traveling Salesman不同，任何节点都可以被访问不止一次，而不是所有节点都需要访问，我的意思是路径应该具有最小的遍历边权重之和。

例如，这是一个邻接矩阵形式的图：

其中每条边的权重用于每个元素。开始和结束于a并包括的周期[b,d]看起来像

是否有一个最佳算法，或者一个非常好的启发式算法？

我试图找出使用 4 位和连续移位的可能组合的数量。我有一组 4 个光传感器读取带有白色和黑色标记的纸条。我想弄清楚它的位置。

我需要知道不重复的唯一可能性的最大数量，我尝试手动计算但无法超过 14。如果可能的话，我想达到 16。

这是我的顺序：

顺便说一句，我失踪0101了1010

假设我有一个行*列网格，网格上的每个节点都有一个整数（状态）值。

如果值

state[row][0] == state[row][NUMBER_OF_COLUMNS -1]

我想检查是否存在仅由这两点相同状态组成的“路径”..

通过路径，我的意思是左侧、右侧、底部或顶部的状态与原始状态相同。

我不确定它是否重要，但可以说状态是二进制的（# 或 -）所以如果我正在检查状态 ==“-”的路径，如果状态到 N，我们可以继续路径， E,S,W 也是 == "-"

结束行必须等于开始行。

成功案例：

或者

或者

失败的例子：

或者

或者

会失败。

我该怎么做呢？我在 Objective C 中编写代码，但帮助我理解这些步骤的伪代码就足够了。

除了检查路径是否存在 BOOL 之外，我还想返回路径中所有网格坐标的数组。

这很容易实现还是我有点过头了？

我正在使用Neo4j图形数据库，并使用 Java 从中提取路径。我有如下路径：

我想用它们的属性替换路径中的节点 ID。前任。对于具有属性的节点 id 3 "name=ABC"，输出应该像"[(ABC)--[KNOWS,5]....]" How it can be done?