问题标签 [graph-algorithm]

首先……问题来了……

举一个有向图 G = (V, E) 的例子，V 中的一个源顶点 s，以及 E 中包含的一组树边 F，使得对于 V 中包含的每个顶点，图中唯一的简单路径 ( V, F) 从 s 到 v 是 G 中的最短路径，但是无论顶点在每个邻接表中如何排序，都不能通过在 G 上运行 BFS 来生成边集 F。

现在......因为这是家庭作业，我不想要一个直截了当的答案，而是更多关于要查看/尝试的想法的想法。但是，这就是我到目前为止所想到的......

我基本上认为我可以创建一个图形，该图形具有到特定顶点的几条最短路径。当然，这些路径之一将在 BFS 中找到。但是，我可以使用替代路线之一来适应 F。但是，让我失望的部分是“无论顶点如何排序”......我不确定如何将其包含在我的过程。我已经尝试过循环，各种不同的方向流，但还没有。

还有其他想法吗？

我正在用 C# 实现一个组织树图 - 从上到下或从左到右 - 并寻找一个好的算法来绘制树。有什么建议吗？

谢谢

更新

我终于有一些时间来处理它，所以最终编写了我自己的库来通过创建一个自定义面板来存储和绘制树，不确定我是否遵循特定的算法，我只是写了自己的 - 回到笔和纸+时间:)

添加完所有我想要的功能后，我打算在 codeplex 上将其开源。将在 codeplex 上发布另一个更新。

谢谢

流行语言（如 Java、C#、Ruby、JavaScript 等）中是否存在某种成熟的无三行问题算法？

谢谢。

我遇到了以下问题：

• 有两个不相交的集合，A并且B
• 对于每对元素 ( a, b)（a属于 set A，其中b属于 set B），预先知道一个概率pij。它表示匹配 的概率（确定性级别）a，b或者换句话说，a匹配b的紧密程度（反之亦然，因为pij== pji）。
• 我必须找到具有最高概率/确定性的匹配并找出描述匹配的对 ( a, )b
• 每个元素必须与另一个集合中的另一个元素匹配/配对一次（就像在标准的二分匹配问题中一样）
• 如果可能的话，我想计算一个数字，该数字近似表示所获得匹配的不确定性级别（假设 0 代表随机猜测，1 代表确定性）

下面描述了一个需要这种算法的简单实际示例（这实际上不是我要解决的问题！）：

• 要求两个人在一张纸上写字母 a - z
• 对于每对字母 ( a, )，我们运行一个模式匹配器来确定person写的字母代表person写的b字母的概率。这给了我们一个概率矩阵，它表示每对字母 ( , )的某种相似性相关性aAbBab
• 对于那个人写的每封信A，我们需要找到这个人写的对应的信B

当前方法： 我想知道我是否可以只分配与确定性水平的对数/集合中的元素与集合中的元素匹配的概率成比例的权重，然后a运行A最大加权二分匹配以找到最大总和。对数是因为我想最大化多个匹配的总概率，并且由于单个匹配（表示为匹配元素对-bBab) 形成一个事件链，它是概率的乘积，通过取对数，我们将其转换为概率之和，然后使用加权二分匹配算法（例如匈牙利算法）轻松最大化概率之和。但我不知何故怀疑这种方法能否确保在统计预期最大值方面的最佳匹配。

经过一番搜索，我发现最接近的问题是两阶段随机最大加权匹配问题，这是 NP-hard，但我实际上需要某种“单阶段”随机最大加权匹配问题。

请花一点时间了解我的情况。如果不能理解，请在评论中告诉我。

我有一个航点的 ArrayList。这些航点没有任何顺序。航点具有以下属性：
{int type, float z, float y, float x, float rotation}

这适用于 3 维世界，但由于我的寻路不应该关心高度（因此将世界视为 2 维世界），因此忽略 y 值。旋转对于这个问题并不重要。

• 在这个二维世界中，x 代表 x 轴，z 代表 y 轴。
• 如果 x 增加，则世界中的物体向东移动。如果 x 减小，则世界中的物体向西移动。
• 如果 z 增加，则世界中的物体向北移动。如果 z 减小，则世界中的物体向南移动。

因此，这些“新”航点可以简化为waypoint = {float x, float y}：

现在，这些航路点代表对象的 X 轴 (x) 和 Y 轴 (z) 位置。此外，还有一个当前位置：curLocation = {float x, float y}和一个目标位置：tarLocation = {float x, float y}。

这就是我想要得到的：在以下严格条件下将导致从到的
所有航路点组合（又名：路径或路线） ：curLocationtarLocation

1. 每个航路点之间的距离不得大于(float) maxInbetweenDistance。这包括从到第一个航路点的初始距离curLocation和从最后一个航路点到 的距离tarLocation。如果不可能有这样的航路点组合，则应返回 null。
2. 当maxInbetweenDistance从通向目标航路点的航路点中找到多个航路点时，应选择最近的航路点（如果稍微远一点的替代航路点会导致一条距离更长的新路径也返回）。
3. 返回的航路点组合（路径）的顺序应该是从最短路线（最小距离）到最长路线（最大距离）

最后，请考虑以下几点：

1. 这是我唯一需要明智地进行 AI/寻路的事情，这就是为什么我不希望使用完整的寻路或 AI 框架。我相信一个功能应该能够处理上述问题。
2. 如果返回所有可能的航路点组合会导致过多的开销，那么如果可以指定最大数量的组合（但仍然从最近到最远排序）也很好。例如。5 个最近的路径。

我将如何实现这一目标？任何反馈表示赞赏。

我是这样写的，但它只在 50% 的情况下有效。有人可以告诉你出了什么问题吗？

谢谢：）

我在这里询问了最短路径算法： 2D waypoint pathfinding:combinations of WPs to go from curLocation to targetLocation

（要了解我的情况，请阅读该问题以及此问题。）

看来 Dijkstra 最短路径算法能够满足我的需要。但是，我的路线图中大约有 500 到 1000 个节点。

到目前为止，我看到的实现将节点的数量限制在 50 以下。我的问题是：我应该仍然使用 Dijkstra 最短路径算法，还是替代方案？Java中是否有任何实现？

在询问了一些关于最短路径算法的一般建议（2D 航路点寻路：从 curLocation 到 targetLocation 的 WP 组合），然后询问更具体的实现（500 多个航路点/节点的最短路径算法（例如 Dijkstra 的）？）已决定使用 JUNG 库（http://jung.sf.net/）。

我现在的目标是通过使用点列表（大小〜1000）中的任意点组合来获得从点 A 到点 B 的最短路径，其中每个点都直接连接到 x 距离内的所有点。

为此，我需要设置一个树形图。我相信这是一个树图实现列表：http: //jung.sourceforge.net/doc/api/edu/uci/ics/jung/graph/class-use/Hypergraph.html#edu.uci.ics。 jung.algorithms.shortestpath

那是对的吗？现在，所有这些实现都仅限于稀疏树图，但我必须创建一个相当密集的树图。

那么，我应该在 JUNG 中使用什么树形图来实现我的目标？

我怎样才能打开这个树形结构

....进入这个“反向树”结构，它基本上包含从所有叶节点到 1（根）的路径：

结果甚至不必构造为树，以正确顺序排列的四个平面数组也可以。

看起来深度优先搜索可能是一种相关算法，但我无法理解伪代码（incidentEdges() 返回什么？），所以我很困惑。

如果有人可以提供一种 Ruby 方法（或非常容易理解的伪代码）将原始嵌套数组转换为结果数组，我将不胜感激。

这不是家庭作业，而是因为我学习时间太长了......我需要这个来为问题跟踪器中的给定问题以正确的顺序打印依赖关系树。

Qt 中是否有图形数据结构的实现，内置节点和边的默认操作？