支配集贪婪近似最坏情况示例
要找到无向图G的最小控制集，可以使用如下贪婪算法:从一个空的集合D开始.直到D是一个主导集合，然后添加一个顶点v，该顶点v的未覆盖邻居数量最大. 该算法通常找不到最佳解，它是lnΔ近似值.(如果Delta是G中顶点的最大程度) 现在，我正在寻找一个简单的示例，其中贪心算法无法找到最佳解决方案.我发现的唯一一个是布景问题的相关实例.( 有人知道一个小例子吗? 预先感谢 解决
..
graph-algorithm相关内容
图:用Python语言重新路由问题测试
您的公司有 N 个服务器.信息通过连接从一台服务器流向另一台服务器. 如果信息从服务器 i 流向服务器 j ，则连接(i)= j.可能存在某些服务器连接(i)= i，这意味着信息不会进一步传播. 为您提供了一个由N个整数组成的数组连接.您的任务是对连接数组值进行最少的更改，以使来自所有服务器的信息可以到达整个网络中恰好位于其终止位置的一台服务器. 如果节点 X 是终端服务器，则连
..
绘制“顶点覆盖"图；蛮力算法
给一个电网，它是一组发电机，电线之间被拉伸.电线至少有一根电流发电机在电线的一端工作.找到与需要打开电源以提供最小数量的发电机当前到整个网络. 我发现了一些可以提供帮助的其他信息.这是“顶点覆盖问题". 现在，我们知道它没有特殊的算法.让我们蛮力吗? 解决方案 正如您在问题中所指出的，这是顶点覆盖问题.这是一个经典的NP难题，这意味着在有效扩展到较大的输入时，没有已知的算法能给
..
通过Python生成器以有序顺序排列有向无环图中的所有唯一路径吗?
我有一个有向无环图(DAG)，它由层组成，其中包括两层随后的层完全是两部分的(非常类似于神经网络)，如下所示: something 调用以前的值或种子.为了简单起见，让我们使用平凡的线性序列 f(n)= f(n-1)+ 5(mod 18).这将给出序列 0 5 10 15 2 7 12 17 ... 现在，让路径生成器在每次迭代中调用此函数.只需将返回的“随机"数字转换为给定基本序列的
..
正方形网格中的多边形
我正在寻找一种算法，以找到包围没有孔的正方形连续网格的多边形，如下所示:
..
Python中从A到B算法的路径切割所需的最小已删除节点
我正在尝试解决与图论相关的问题，但似乎无法记住/发现/理解正确/最佳方法，因此我想请教专家... 我有一个来自两个节点的路径列表(示例代码中为1和10).我正在尝试找到要删除以削减所有路径的最小节点数.我也只能删除某些节点. 我目前已将其实现为暴力搜索.这在我的测试集上工作正常，但在按比例缩放到在100K中具有路径而在100中具有可用节点的图形时，这将是一个问题(因果关系).现在，我不
..
为什么在图形中找到最长的路径是NP难的
此链接提到: 加权图中两个给定顶点s和t之间的最长路径G与从G通过以下公式得出的图-G中的最短路径相同改变每一个分量到它的否定.因此，如果路径最短可以在-G中找到，然后最长的路径也可以在G中找到. 那么，如果这种转换可以将最长路径简化为最短路径问题，那么为什么找到最长路径却是NP难题呢? 转换后，我们有以下几种情况: -G 具有负周期，在这种情况下，无法找到 -G 中的最短
..
如何在CART决策树算法中分割连续属性?
我不了解如何在CART(分类和回归树)算法中拆分连续属性，因为我们知道CART既可以拆分类别属性又可以拆分连续属性. 我读了许多论文，并说要分割点的值是顺序中的中间值.我不明白.您能给我解释一下这是什么意思，并举一些例子吗? 谢谢 解决方案 一般过程是扫描任何给定预测变量上的候选拆分值，测量每个拆分的质量并选择最佳拆分.为了提高效率，扫描可能不会尝试所有可能的拆分，而是尝试每个
..
在图形中查找最近的边
我想找到图形中最接近的边.考虑以下示例: 四叉树 ，用于基于边界框的所有边缘.然后，您只需提取最接近查询点的一组边并对其进行迭代以找到最接近的边. 四叉树返回的提取的边缘集应该比原始的1500万个边缘小许多因素，因此迭代所需的成本要低得多. 与R树相比，四叉树是一种更简单的数据结构.它相当普遍，在许多环境中都应该容易获得.例如，在Java中， JTS拓扑套件具有结构 QuadTree
..
C中具有邻接矩阵的图
我有这个struct: struct graph { int** adj; /**
..
查找无向图的所有派系
如何列出无向图的所有派系? (并非所有最大派系都像Bron-Kerbosch算法一样) 解决方案 最优解决方案是这样的，因为在一个完整的图中有2 ^ n个团.考虑使用递归函数的所有节点子集.对于每个子集，如果子集的节点之间都存在所有边，则将1加到您的计数器中:(这几乎是C ++中的伪代码) int clique_counter = 0; int n; //number of node
..
BFS使用哪种启发式方法来解决此“游戏"(查找路径)?
我想解决一个“游戏". 我有5个圆圈，我们可以将圆圈旋转到左侧或右侧(90度). 示例: 我正在使用BFS查找路径，但是我无法发明启发式函数(我的每个解决方案都不好).我正在尝试曼哈顿距离和其他距离...(也许想法不错，但是我的解决方案出了点问题).请帮忙！ 解决方案 一个简单的保守(允许的)启发式方法是: 对于每个数字1
..
这个遍历问题有解决方案吗?
假设我们有一个矩阵M x N，给定两个随机指定的exit和entrance， 找到从entrance到exit的路径(上，下，左，右)，该路径仅覆盖矩阵中的每个节点一次? 解决方案 这显然并不总是可以解决的.假设您有这个矩阵，其中A是入口，B是出口: +---+---+ | A | | +---+---+ | | B | +---+---+ 您如何解决这个问题?
..
BGL中的Lengauer Tarjan算法(增强图库)
我需要为给定的图形创建一个控制树.我编写的代码可以正确运行并运行，但输出看起来与输入完全相同. 我为图形定义了以下类型(待分析) typedef boost::adjacency_list Graph; ，我想让另一个对象包含相应的
..
可多次访问顶点的TSP
我正在解决一个有加权有向图，并且我必须从原点开始，至少访问所有顶点一次并以尽可能短的路径返回原点的问题.从本质上讲，这将是TSP的经典示例，除了我请勿有一个约束，即每个顶点只能被访问一次.在我的情况下，沿路径可以多次访问除原点以外的任何顶点，如果这样做会使路径更短.因此，例如在包含顶点V1, V2, V3的图形中，这样的路径将是有效的，因为它是最短的路径: ORIGIN -> V1 -> V
..
在有向循环图中找到所有路径作为正则表达式
令G =(V，E，r)有根有向图，它由一组顶点V和一组具有指定根节点r的边E定义. 图中可能包含循环.任务:给定V的两个顶点x和y，找到从x到y的 all 路径. 由于允许循环，所以路径的集合显然可能是无限的.因此，我想以正则表达式(Kleene Algebra)的形式找到路径集.以下是一些示例:示例图.乘法表示序列，因此路径abc首先表示a，然后是b，然后是c.一组路径a(b + c +
..
最短路径图算法有助于Boost
我有一个矩形网格DAG，其中水平边缘始终指向右侧，垂直边缘始终指向下方.边缘具有与之相关的正成本.由于是矩形格式，因此使用从零开始的行/列来引用节点.这是一个示例图: 现在，我要执行搜索.起始顶点将始终位于左列(索引为0的列)和图形的上半部分.这意味着我将开始选择为(0,0)，(1,0)，(2,0)，(3,0)或(4,0).目标顶点始终在右列(索引为6的列)中，并且“对应"起始顶点:
..
阻止仙人掌图上的有向路径
我想在仙人掌图上找到最长的路径距离定向路径. 例如，如果我们有以下4个节点， 这意味着 如果我们访问1，我们将无法前往2 即，1→ 2和1-> 3->不允许2个. 然而，2→允许1个. 类似 不能从2行驶到3 不能从3行驶到1 不能从1到0行驶 可以旅行其他任何人 因此我们具有路径(1、3、2)，(0、2、1)等.因此，最长距离为3. 在这种情
..
具有多父节点的有向无环图
给定:带有加权边的有向无环图，其中一个节点可以有多个父级. 问题:对于根节点的每个子节点，找到从此类子节点到可以到达的某些叶子的最小成本(权重之和)路径.一个节点只能出现在一条这样的最小成本路径中. 示例图: 在上图中，对于节点2，所有可用路径为: 2 -> 5 2 -> 1 -> 9 -> 6 2 -> 1 -> 10 -> 6 Among which 2 -> 1
..
寻找三角镶嵌的最近邻居
我有一个三角形的镶嵌，如图所示. 考虑到细分中三角形的数量N，我有一个N X 3 X 3数组，该数组存储每个三角形的所有三个顶点的(x, y, z)坐标.我的目标是为每个三角形找到共享相同边的相邻三角形.这是一个复杂的部分，是我不重复邻居计数的整个设置.也就是说，如果三角形j已经被算作三角形i的邻居，那么三角形i不应再被算作三角形j的邻居.这样，我想有一个地图存储每个索引三角形的邻居列表.如果我从
..