标签: graph-algorithm

在通过冲突驱动子句学习解决 SAT 问题时，每次求解器检测到一组候选变量分配导致冲突时，它必须查看冲突的原因，从中导出一个子句（即，根据整体问题）并将其添加到已知子句集中。这需要在蕴涵图中选择一个切口，从中导出引理。

执行此操作的常见方法是选择第一个唯一蕴含点。

根据https://users.aalto.fi/~tjunttil/2020-DP-AUT/notes-sat/cdcl.html

如果从最新决策文字顶点到冲突顶点的所有路径都经过 l，则蕴涵图中的顶点 l 是唯一蕴含点 (UIP)。

标准术语中的第一个UIP 是从冲突回溯时遇到的第一个 UIP。

用替代术语来说，UIP 是蕴含图上相对于最新决策点和冲突的主导者。因此，可以通过构建蕴含图并使用标准算法来查找支配者来找到它。

但寻找支配者可能会花费大量的 CPU 时间，而且我的印象是实用的 CDCL 求解器使用特定于此上下文的更快算法。然而，我找不到比“获取第一个 UIP”更具体的内容。

查找第一个 UIP 的最著名算法是什么？

我正在尝试解决编码挑战，但我的解决方案性能不是很好，我正在寻找有关如何改进算法的意见或建议。

谜题如下：

给你一个代表果园的单元格网格，每个单元格可以是空地 (0) 或果树 (1)。一位农民希望知道果园内距离所有果树 k 距离内有多少个空点。

使用出租车几何形状计算距离，例如：

k = 1

[1, 0]
[0, 0]

the answer is 2 as only the bottom right spot is >k distance from all trees.

我的解决方案是这样的：

1. 循环网格并存储所有树位置
2. 从第一个树位置开始进行 BFS 并存储所有空点，直到我们到达超出 k 距离的邻居
3. 从下一个树位置开始进行 BFS 并存储空点的交集
4. 重复步骤 3，直到迭代完所有树位置
5. 返回所有交叉点后剩余的空点数量

我发现对于 k 值较大的大型网格，我的算法变得非常慢，因为我最终多次检查网格中的每个点。经过一些研究，我找到了一些类似问题的解决方案，建议采用两个最极端的目标节点，然后仅比较与它们的距离：

• https://www.codingninjas.com/codestudio/problem-details/count-nodes-within-k-distance_992849
• https://www.geeksforgeeks.org/count-nodes-within-k-distance-from-all-nodes-in-a-set/

然而，鉴于某些输入，这对我的挑战不起作用，如下所示：

k = 4

[0, 0, 0, 1]
[0, 1, 0, 0]
[0, 0, 0, 0]
[1, 0, 0, 0]
[0, 0, 0, 0]

使用极端节点方法，即使右下角的空点距中间树 5 距离，也会对其进行计数。

有人能指出我一种更有效的方法吗？我对这些类型的问题仍然很陌生，所以我发现很难看到我应该采取的下一步。

我一直想知道帕斯卡三角形是否有任何实际应用，而不仅仅是二项式展开式的系数。

我试图解决这个问题：

但是，如果我添加 K 个单位的水，并且想要找到一个水含量最少的玻璃杯，该怎么办：

其中，Glass 将被发现为： 第 -th 行c中的 -th glassr

我相信。如果我们能找到这个，那么我们就不难找到任意玻璃杯中的水量了。{i<r and j<c}

\n

• 问题：

  \n

  输入\n添加的水 - K 单位，每个玻璃杯的容量为 1- 单位

  \n

  预期输出：第排c中的第一个玻璃杯r中的水最少。

  \n
\n

我试图通过记录每行开始溢出时的容量来解决问题：\n并想知道如何继续使用此方法。

      1       max = 1, cap = 1\n     1 1      max = 1, sum(coefficients)=2**1 = 2, cap = 2/1 \n    1 2 1     max = 2, sum = 2**2, cap = 4/2 = …

请帮我找到解决这个问题的好方法.

我们有n个3维的盒子.我们可以定位它们,我们希望将它们放在另一个上面以获得最大高度.如果2个尺寸(宽度和长度)低于下面方框的尺寸,我们可以将盒子放在另一个盒子的顶部.

为了exapmle我们有3个维度w*D*h,我们可以显示它(h*d,d*h,w*d,d*W,h*w,w*h)请帮我解决它图论.在这个问题上我们不能把(2*3)放在上面(2*4),因为它有相同的宽度.所以2维应该小于盒子

灵感来自这个漫画http://xkcd.com/173/

我知道有很多算法可以找到加权图的最小生成树,但是我一直在努力寻找能够找到最小跨越"路径"的任何算法.

对于漫画,如果我们基于每个对关系加权每个边缘,那么社会最优布置将是最小跨越"路径",即跨越所有顶点的路径.有人可以帮忙吗？

我有一个循环加权有向图,目标是删除路径中存在的循环.

例如:路径如下,

from | to | weight
------------------
a    -> b | 0.5
a    -> c | 0.5
c    -> e | 1
b    -> d | 1
d    -> a | 0.25
d    -> f | 0.75

图中的循环由路径d - > a引入.任何人都可以建议通过调整其他节点的权重来删除循环d - > a的算法.得到的非循环图在将权重传递给末端节点e,f方面是等效的.

谢谢,Vivek

我正在尝试为世界海洋上的探路者编程。我以前在包含陆地和水细胞的单元网格上使用了A *算法。但是我认为更好的解决方案是拥有大洲，岛屿和多边形。计算之间的空间的可见性网格（仅一次）；然后在可见性图表中包括起点和终点；然后在结果图上求解A *。环顾四周，我发现了一本名为“计算几何”的书，其中描述了一种计算可见度图的算法。但是，在尝试用C ++实现之前-听起来像个好主意吗？

据我所知，已经提出了许多不同的算法来计算可见度图，但具有不同的数值复杂度。在我看来，这是一个活跃的领域，而不是永久解决的问题。所以在我看来，这是一个真正的问题。如果您有其他意见，请告诉我原因！

编辑：我现在实现了一种算法，该算法首先在包含约5,000个顶点的多边形组成的世界地图上计算可见性图。在第二步中，A *在可见性图上运行。就运行时间和内存而言，映射的详细程度可能存在限制。目前，在笔记本电脑上计算可见性图大约需要10分钟（我相信该算法非常有效；但是我也相信我的代码不是很有效，可以大大加快速度）。一旦计算了可见度图，A *就会非常快。再次非常感谢您给出的答案和评论！

数学问题

让2n个人,C(i,j)让i和j一起工作的"成本" (函数C快速计算,在我的例子中它是一个给定的矩阵,并且是对称的).问题是找到2n对人的安排,最小化每对人的成本之和.

这应该在n中的多项式复杂度中完成,并且在Scilab语言中相对容易地实现(输入:成本矩阵,输出:配对,例如n -by-2索引矩阵).我知道"相对容易"需要解释......

以前的研究

这个问题实际上是由Blossom算法解决的.例如,参见本文.

然而,这个(及其变体)看起来像是一个噩梦.我真正的问题是n = 20,所以虽然蛮力(=尝试所有可能的配对)不行(暴力强迫n = 8花了一个小时在我的电脑上),几乎任何比蛮力更好的应该做的伎俩; 如果我能以一小时的计算成本避免一周的编码.

我正在考虑在2n- by- 2n阵列上使用匈牙利/ Munkres算法,用对称成本矩阵填充对角线和其他元素,然后以某种方式从结果置换中选择相关的配对,但我找不到一个可靠的方法来做到这一点.(注意,匈牙利语算法已经编码为单独的部分,因此您可以免费使用它来实现"易于实现"的要求.)+%inf

我希望与开花算法问题相比,图的完整性允许一些捷径...... (编辑:请参阅下面的DE评论,由于半明显的原因,这是错误的)

我目前正在编写一个将学生映射到课程的程序.目前,我正在使用SAT-Solver,但我正在尝试实现一个多项式时间/非贪心算法,它解决了以下子问题:

• 有学生(50-150)
• 有科目(10-20),例如'数学','生物','艺术'
• 每个科目(至少一门)都有课程,例如'math-1','math-2','biology-1','art-1','art-2','art-3'
• 学生选择一些(固定的)科目(10-12),并且对于每个科目,学生必须被分配到现有的一门课程(如果可能的话).选择哪个课程'math-1'或'math-2'并不重要.
• 这些课程允许的学生人数最多(20-34)
• 每门课程都在一个固定的区块内(=时间段1到13)
• 学生可能不会被分配到同一区块的课程

我现在描述到目前为止我所做的事情.

(1)忽略课程 - 学生限制

我能够用匈牙利算法/二分匹配来解决这个问题.每个学生可以通过如下建模来单独计算:

• 左节点代表主题'数学','生物','艺术'(学生)
• 右节点表示块'1','2',....'13'
• 从"主题"到"阻止"的每个过程插入一条边

通过这种方式,学生被分配到课程的每个科目,而不参加同一区块的课程.但课程限制被忽略了.

(2)忽略学生的选定科目

我能够用max-flow-algorithm解决这个问题.对于每个学生,建模如下:

• 第1层:从源到每个学生,流量为13
• 第2层:从每个学生到他/她的个人区块,流量为1
• 第3层:从每个学生块到该块中的每个课程,流程为1
• 第4层:通过'max-student-limit'从每个球场到水槽

通过这种方式,学生选择任意课程,并且课程限制已满.但是他/她可能不幸并被分配到'数学-1','数学-2'和'数学-3'而无视主题'生物'和'艺术'.

(3)贪婪的匈牙利人

我的另一个想法是一次匹配一个学生与匈牙利算法并调整权重,以便"更多空课程"是首选.例如,可以建模:

• 左节点是学生的主题
• 右边节点是块
• 对于每个球场,插入一个边缘从主体到球场的块重量=自由座位数

然后计算最大权重匹配.

我真的很感激任何建议/帮助.

谢谢!

给定无向图G =(V,E),没有负权重.检查给定图中每个顶点的最短路径唯一性的复杂性是多少？