graph-algorithm 相关问题

图算法是一系列明确定义的步骤,它们将解决与图论相关的问题,其中此上下文中的图是顶点(“节点”)和连接这些顶点的边的集合。

单连通图?

单连通图是有向图,从 u 到 v ∀ u,v 至多有 1 条路径。 我想到了以下解决方案: 从任意顶点运行 DFS。 现在再次运行 DFS,但这次开始...

回答 4 投票 0

RRT 和 RRT 的时间和空间复杂度*

RRT 和 RRT* 的时间和空间复杂度是多少?与基于图的增量启发式算法相比,基于增量采样的算法表现如何

回答 2 投票 0

有向无环图的拓扑排序为阶段

是否有一种算法,给定一个未加权的有向无环图,将所有节点排序到节点集列表中,使得 拓扑顺序被保留(即,对于所有边 u->v, v oc...

回答 2 投票 0

无回程且指定起止城市的旅行推销员

我正在寻找以下问题的名称:旅行推销员问题(每个城市恰好访问一次),但不返回起始城市并在结束时访问给定城市。在...

回答 2 投票 0

为什么要在下面给出的 WordSearch 问题中使用 Trie 数据结构?

给定一个 m x n 的字符板和一个字符串单词列表,返回板上的所有单词。 每个单词必须由连续相邻单元格的字母构成,其中相邻单元格是

回答 4 投票 0

将红盒包装在蓝盒中以优化成本是具有挑战性的

这主要是封装问题: 假设有 20 个不同尺寸 r1 到 r8 的红色盒子(因此每个尺寸可能存在多个),这些盒子应该使用蓝色包装盒 w...

回答 1 投票 0

验证线性时间内从每个节点到汇聚节点的最小成本

问题陈述: 设 G = (V,E) 为有向图,每条边 e ∈ E 上的成本为 ce ∈ ℝ。G 中不存在负循环。假设有一个汇节点 t ∈ V,并且对于每个节点 v ∈ V,有一个

回答 2 投票 0

在 DAG 中查找哈密顿路径的算法

我指的是斯基纳的算法书。 测试图 G 是否包含哈密顿路径的问题是 NP 困难的,其中哈密顿路径 P 是精确访问每个顶点的路径...

回答 2 投票 0

图中的最短路径,其成本取决于遍历的历史

我的目标是找到与道路(边)连接的给定城市(顶点)之间的最短路径(最低成本)。 每条道路和每个城市都有费用(成本),必须在进入该区域之前支付...

回答 4 投票 0

Sedgewick/Wayne“BellmanFordSP.java”:“findNegativeCycle”如何确保返回负循环?

在 Bellman-Ford 算法的 Sedgewick 和 Wayne 实现中 (https://algs4.cs.princeton.edu/44sp/BellmanFordSP.java),findNegativeCycle 方法使用 EdgeWeightedDirectedCycle (https:/...

回答 1 投票 0

用最陡爬坡函数寻找路径

使用最速爬山搜索时,当你到达一个无限循环时会发生什么——也就是说,你发现自己在相同的两个状态之间来回切换,因为它们都是最好的

回答 2 投票 0

到达图中特定节点的最可能路径

我们有一个系统,客户来这里进行交互,触发工作并执行许多操作。我们有 1000 多个这样的用户。每个作业都有一个名称,我们的后端数据库包含有关该作业的所有数据...

回答 3 投票 0

贝尔曼福特算法讲解

我读了贝尔曼福特算法。我不明白的是为什么有一个循环运行了 |V|-1 次(下一段中的上层循环)。 对于(我= 1;我<= V-1; i++) { for ...

回答 2 投票 0

为什么在这种情况下,BFS比DFS更有效率?

tldr; 你从3开始,想在4结束,总有一条保证的路径。你只能跳到1上。你像一个骑士一样,每次都向一个方向移动m个单位,向另一个方向移动n个单位。什么...

回答 1 投票 0

给定一个具有一定约束条件的数字列表的换元算法。

我正在寻找一种算法,给定一个n个值的集合,每个值可以是{0,1,...m},可以找到该集合是否有效。规则是 只能有一个值 > 1: n = 3, m = 5 ... ...

回答 1 投票 0

能否将一个有向图分成两组,使组内的节点不相互连接?

我正在寻找一种算法,检查给定的有向图的节点是否可以分成两组,使节点在其组内不相互连接,例如UPD I ...

回答 1 投票 0

寻找无重访图遍历路径(所有顶点)的优化策略。

为了让我有些生疏的编程技能蒙上灰尘,我正在尝试解决我遇到的这个图形遍历问题。我想找到一条路径,访问10x10的图上的所有坐标(顶点)。

回答 1 投票 0

python中的最小跨度树

我在计算一个简单图形的最小跨度树时遇到了问题 用的是下面的python代码。用手操作是很琐碎的,我把图形的图像和最小 ...

回答 1 投票 0

找出两点之间的最短距离,并有分段阻挡。

我需要找到平面内端点A,B之间的最短欧氏距离,但要受制于有一组N段S=[S1,S2,...],我的欧氏路径不能相交。

回答 1 投票 0

从MST中删除节点。与Kruskal重新连接

我有一个MST,需要删除一个节点。我知道有一个O(log^4(n))的算法,但是由于MST包含不到50个节点和2500条边,而且我已经对边进行了排序,我......

回答 1 投票 0

© www.soinside.com 2019 - 2024. All rights reserved.