标签: graph-theory

我可以轻松地为有向图的节点定义数据类型.

data Node = Node String [Node] derving (Show, Read)

我可以使用show函数将图形保存到文件中,然后使用read恢复它.但是,节目不会应付一个周期.是否有一种保存和恢复图形的简单方法？

我有一个几何无向平面图,这是一个图,其中每个节点都有一个位置,没有2个边交叉,我想找到没有边穿过它们的所有周期.

这个问题有没有什么好的解决方案？

我打算做的是一种A*类似的解决方案:

• 将最小堆中的每个边插入路径
• 每个选项都可以扩展最短路径
• 循环回到其他路径的剔除路径(可能不需要)
• 剔除路径,这将是第三个使用ang给定边缘的路径

有没有人看到这个问题？它会工作吗？

我知道平面度测试可以在O(v)中进行(等效O(e),因为平面图具有O(v)边)时间.

我想知道它是否可以在O(1)摊销时间在线完成,因为每个边缘被添加(仍然是整个O(e)时间).

换句话说,在表示图形边缘的数据库表中,并且受约束表示所表示的图形是平面的,负责管理约束的DBMS需要多长时间才能验证每个建议的插入？(为简化起见,假设没有删除.)必须重新运行其中一个O(v)平面度测试算法来测试每个建议的插入或插入组吗？

好的,所以在拓扑排序中,取决于输入数据,通常有多个正确的解决方案,可以对图形进行"处理",以便所有依赖关系都在"依赖"它们的节点之前.但是,我正在寻找一个稍微不同的答案:

假设以下数据: a -> b和c -> d(a必须在之前b,c必须在之前d).
只有这两个限制,我们有多种候选方案:( ,,a b c d 等).但是,我正在寻找创建一种"分组"这些节点的方法,以便在处理组之后,下一组中的所有条目都会依赖它们的依赖关系.对于上面假设的数据,我会寻找像这样的分组.在每个组内,只要组1 在处理组2 中的任何一个之前完成,那么处理节点的顺序(在之前或之前等,反之亦然)并不重要.a c d bc a b d(a, c) (b, d)acbd(a, c)(b, d)

唯一额外的问题是每个节点应该尽可能在最早的组中.考虑以下:
a -> b -> c
d -> e -> f
x -> y

分组方案在(a, d) (b, e, x) (c, f, y)技术上是正确的,因为x在之前y,更优化的解决方案是(a, d, x) (b, e, …

这似乎是正确的,但我在网上找不到任何人说这是,所以我想确定.如果您同意,请告诉我,如果是,为什么.理想情况下是指向纸张的链接,或者,如果您不同意,则为反例.

我们G是一个有向图有一些负面的边缘.我们想要运行A*G.

首先,如果G从源头到达并且达到目标的负周期,则没有可接受的启发式,因为不可能低估达到目标的成本,因为它是-?.

但是,如果没有这样的循环,可能会有一些可接受的启发式.特别是,所有负边缘的总和将始终低估达到目标的成本.

我的印象是,在这种情况下,A*可以正常工作.

PS我可以在图上运行Bellman-Ford,检测负循环,如果没有,重新加权以消除负边缘.但是,如果我知道没有负循环,我可以跳过它并运行A*.

这是非常错误的.顶点的成本是启发式和到目前为止构建的路径的总和......而启发式低估了达到目标的成本,启发式和到目前为止所采用的路径的总和可能不是.千里马culpa.

似乎用一个低估了达到目标的成本的函数对开放集进行排序,而通过一个给定的顶点可能会工作......如果一个人使用<sum of negative edges in the graph>这样的函数,它看起来像退化为图遍历.

在Wiki页面说

通过选择其顶点的总顺序并将每个边缘从顺序中的较早端点定向到后一个端点,可以将任何无向图形制成DAG.

但我不知道如何获得无向图的总顺序.我应该使用DFS吗？如果是这样,我将如何进行？

更多信息:我正在研究一个有一个源和一个接收器的无向图.我试图引导这些边缘,以便沿着边缘方向我可以从源头到达接收器.

注意:由于旅行不是在它开始的同一个地方结束的事实,而且只要我仍然访问所有这些点,每个点都可以被访问多次这一事实,这不是真正的TSP变体,而是我之所以说是因为缺乏对问题的更好定义.

所以..

假设我正在徒步旅行,有n个兴趣点.这些景点都通过远足径相连.我有一张地图显示了所有距离的路径,给我一个有向图.

我的问题是如何近似一个从A点开始并且访问所有n个兴趣点的旅游,同时结束旅行的任何地方,但我开始的点,我希望旅游尽可能短.

由于远足的性质,我认为这可能不是一个对称问题(或者我可以将我的不对称图转换为对称图？),因为从高海拔到低海拔显然比其他方式更容易.

另外我认为它必须是一种适用于非度量图的算法,其中不满足三角不等式,因为从a到b到c可能比从a到c的真正漫长而奇怪的道路更快直.我确实考虑过三角不等式是否仍然存在,因为对于我访问每个点的次数没有限制,只要我访问所有这些,这意味着我总是选择从a到c的两条不同路径中最短的路径,从而永远不会抓住漫长而奇怪的道路.

我相信我的问题比TSP更容易,因此这些算法不适合这个问题.我考虑过使用最小生成树,但我很难说服自己可以将它们应用于非度量非对称有向图.

我真正想要的是关于如何能够提出近似算法的一些指示,该算法将通过所有n个点找到近乎最佳的旅行

我遇到了如下问题:

我们有一个G(V, E)带有正边和负边​​的加权非循环图代码.我们使用以下代码更改此图形的权重,以给出G无负边缘(G').如果V={1,2...,n}并且G_ij是边缘i到边缘j的权重.

Change_weight(G) 
 for i=i to n   
   for j=1 to n
      c_i=min c_ij for all j
      if c_i < 0 
          c_ij = c_ij-c_i  for all j
          c_ki = c_ki+c_i  for all k

我们有两个公理:

1)G中每两个顶点之间的最短路径与G'相同.

2)G中每两个顶点之间的最短路径长度与G'相同.

我们要验证这两句话.哪一个是真的,哪一个是假的.谁可以添加一些暗示为什么这些是真还是假？

我的解决方案

我认为两个是假的,如下面的反例,原始图形在左边给出,并且在算法运行之后,结果在右边,1到3之间的最短路径改变,它从顶点2传递但是在算法运行之后它从未从顶点2传递过.

我在比赛的某个地方发现了这个问题,但还没有找到解决方案.

我有正整数.我必须找到最长的子集,在每两个相邻元素中,一个除以另一个.

我正在做的是:我正在创建图形.然后我正在连接其中数字彼此分开的节点.之后我正在使用DFS(一个节点可以连接两个节点).

但并非所有测试用例都适用于系统.在使用之前我是否必须对数组进行排序DFS？也许有特殊的(动态)算法？

失败的测试用例:

N = 5
1 1 3 7 13

我的代码给出了输出4.但如果我arrange这个数组像这样:

3 1 7 1 13

输出是5,这是真正的答案.

我也使用了递归方法.但我需要更快的东西.

我最近了解了Flood-Fill Algorithm，这是一种可以获取图形并O(N)及时为每个节点分配组件编号的算法。

例如，可以使用 Flood-Fill 算法有效解决的一个常见问题是找到一块N*N板上最大的区域，其中该区域中的每个节点都与另一个具有相同 ID 的节点相邻，或者直接向上、向下、到向左，或向右。

在这个棋盘中，最大的区域都是 3，分别由全 1 和全 9 组成。

然而，我最近开始怀疑我们是否可以扩展这个问题；具体来说，如果我们能在图中找到最大的区域，使得该区域中的每个节点都与具有两个可能 ID 的另一个节点相邻。在上图中，最大的此类区域由 1 和 9 组成，大小为 7。

这是我试图解决这个问题的思考过程：

想法 1：O(N^4) 算法

我们可以O(N^4)使用基本的洪水填充算法及时解决这个问题。我们通过测试所有O(N^2)水平或垂直相邻的方块对来做到这一点。对于每一对方块，如果它们有不同的 ID，那么我们从两个方块中的一个运行填充。

然后，通过修改洪水填充算法，使其传播到具有两个可能 ID 之一的正方形，我们可以及时测试每一对O(N^2)--> O(N^2) pairs * O(N^2) flood fill per pair = O(N^4) algorithm。

然后，我有了一个洞见：An Possably O(N^2) Algorithm

首先，我们通过电路板运行常规的洪水填充并将电路板分成一个“组件图”（其中原始图中的每个组件都减少为单个节点）。

现在，我们通过组件图的边缘而不是节点进行洪水填充。我们用一对整数标记每条边，表示它连接的两个组件内的两个 ID，然后通过边填充，就好像它们本身是节点一样。

我相信，如果正确实施，将产生一种O(N^2)算法，因为N*N板中边数的上限是4*N*N.

现在，我的问题是，我的思维过程在逻辑上是否合理？如果没有，有人可以建议另一种算法来解决这个问题吗？