优化图中节点之间的连接
我正在研究一个可以简化为以下图优化问题的问题. 给出了一组彩色节点. 给出了一组有关节点成本贡献的规则. 例如. 如果未连接红色节点，则成本为100 如果红色节点连接到红色节点，则成本为10 如果红色节点连接到蓝色节点，则成本为20 任何节点最多只能有4个连接. 问题在于优化连接(顶点)，以使总成本最小化，并且最终图形遵循规则. 我想知道是否可
..
graph-algorithm相关内容
连接节点以最大程度地增加边缘总重量
我正在研究一个可以简化为以下图优化问题的问题. 给出了一组彩色节点.它们都是未连接的，即图中没有边. 要在节点之间插入边. 一个节点最多只能有4条边. 一个表提供了从边缘贡献利润的规则. 例如 一条连接红色和红色的边:利润为10 一条连接红色和蓝色的边:利润为20 节点总数约为100. 颜色的总数通常约为20到30，但可以高达50.相应地，利润
..
从序列中减去一个数字后，剩下的多少个数字是正数?
我有一个长度为 N 的数字序列. 我将必须对此编号序列执行 Q 操作. 在每个操作中，我将得到三个整数 P，Q，V ，其中 P≤Q≤N ，并将从每个整数中减去 V iᵗʰ整数，其中 P≤i≤Q . 每次操作后，我将再得到两个整数 X，Y ，其中 X≤Y≤N .我将不得不回答Xᵗʰ和Yᵗʰ(含)整数之间有多少个整数为正数. Q 大约为 10 5 .我将必须执行所有操作并在1/2秒内
..
两组截然不同大小的顶点的最大加权二部匹配
抽象问题 我想在一个完整的加权二部图中找到最佳的最大匹配，其中两组顶点的大小截然不同，即一组顶点很大，而另一组很小. 匈牙利算法不是解决此问题的好方法，因为它会向其添加虚拟顶点较小的集合，以使两个集合具有相同的大小，因此我损失了其中一个顶点集很小的潜在效率收益. 更具体地 我已将对象(边界框)分为两组，并且对任意两个对象的相似度都有相似性度量(Jaccard重叠).我想产生
..
使用map reduce在bfs上遍历图形的有效方法是什么?
这是招聘人员问我的一个面试问题，问题基本上是计算所有节点到每个节点的最短路径，我的解决方法是以下 启动所有可能的边(没有反向A-B与B-A相同) 每个节点都将以以下形式表示(src，cost，current_list，dest)，而src和dest基本上是我们先前发起的所有可能的边缘 地图: for each edge you traverse, you duplicate
..
我该如何纠正错误'AttributeError:'dict_keys'对象没有属性'remove''?
我正在尝试使用dijkstra算法的最短路径查找器，但似乎不起作用.无法找出问题所在.这是代码和错误消息. (我正在使用Python 3.5. https://www.youtube.com/watch?v= LHCVNtxb4ss ) graph = { 'A': {'B': 10, 'D': 4, 'F': 10}, 'B': {'E': 5, 'J': 10, 'I':
..
查找范围的最大相交子集
如果您有一组范围，例如下面的简单示例... [ [12, 25], #1 [14, 27], #2 [15, 22], #3 [17, 21], #4 [20, 65], #5 [62, 70], #6 [64, 80] #7 ] ...您如何计算最大相交子集(不确定如何表达它，但我的意思是“相交并具有最高基数的范围子集")并确定
..
在O(E logV)中的图形中找到单调最短路径
来自此页面的问题34. 单调最短路径.给定边加权的有向图，找到从s到其他顶点的单调最短路径.如果路径上每个边缘的权重都严格增加或严格减少，则该路径是单调的. 部分解决方案:以升序放宽边缘并找到最佳路径；然后以降序放宽边缘并找到最佳路径. 我的问题: 假设我们以降序放宽边缘，并且在一个点上可以选择1个以上的边缘.我们将在什么基础上选择下一个优势?理想情况下，我们应该选择较小的
..
如何遍历对象列表并分配子项？
我有一个Location POJO，用于存储从JSON文件解析的Location对象，我想将其映射到图形。图中每个节点的位置对应于它的id字段，其中id =“1”是起始节点，id =“10”是目标节点。 要解决我改编了一个Node类，包括 setWeight（）， addChildLocation（）等方法，但我是不确定如何从我的位置列表创建图表。我知道如何通过硬编码位置和调用addChil
..
迭代深化星（IDA *）来解决Java中的n-puzzle（滑动拼图）
我已经实施了一个能够用A *解决 n-puzzle问题的程序。由于状态的空间太大，我无法预编译它，我必须在运行时计算可能的状态。通过这种方式，A *适用于3拼图，但对于4拼图可能需要太长时间。使用曼哈顿距离调整线性冲突，如果最佳解决方案需要大约25次移动仍然很快，大约35次需要10秒，40次需要180秒。我还没有尝试过更多。 我认为这是因为我必须保留所有访问过的状态，因为我使用的功能是可以接
..
将集合层次结构可视化为颜色编码图形
我最近一直在阅读有关Java和Javascript图形库的相关内容，但我还没有找到一个很好的方法来做我想做的事情。 基本上我有一组关于一堆元素的集合（最多几千个）。这些组可以完全或部分重叠，完全覆盖或完全彼此不相交。我想要做的是显示以下信息： 集合的大小（与其他集合相关） 根据其涵盖的元素计算的集合的“热”值（颜色代码） 单个图中集的完整拓扑（这样就可以向用户显示重叠，交叉点等）
..
扭曲的最短路径
我有 n 顶点和 m 它们之间的无向加权边（权重代表分钟）。每个顶点包含在该顶点上喝咖啡所需的分钟数。 我想确定从顶点 v 到顶点 w 但是附加限制条件是我必须在从 v 到 w ）。 示例： （顶点的数字是喝咖啡所需的分钟数，边缘的重量代表了这个边缘所需的分钟数） 从 v 到 w 并在途中喝一杯咖啡，输出最短的必要时间（输出应为30 ）。 我目前的做法是找到Dijks
..
Python：如何优化所有可能的最短路径的数量？
在 3x3 网络中，我希望能够确定任何两个节点之间的所有最短路径。然后，对于网络中的每个节点，我想计算一个特定节点有多少最短路径。 这需要使用 nx。 all_shortest_paths（G，source，target）函数，它返回一个 generator 。这与使用 nx.all_pairs_shortest_path（G）不同，如此处。不同的是，在前一种情况下，函数计算任意两个节点之间
..
通过匹配N个顶点构建一个无向加权图
我想通过比较他/她的“兴趣”与所有其他人的兴趣来为特定用户推荐最匹配的前10名匹配。我在用户之间构建了一个无向加权图，其中weight =两个用户之间的匹配分数。 我已经有一组N个用户： S.对于S中的任何用户U，我有一组兴趣I.经过很长时间（一个星期？）之后，我创建了一个具有一组兴趣的新用户U并将其添加到S.为了生成这个新的图用户，我将迭代地比较新用户的兴趣集I和S中所有用户的兴趣集。问题
..
从图中消除顶点
从Skiena的书中，设计一个线性时间算法，通过将边（u，v）和（v）替换为图2中的每个顶点v， ，w）由边（u，w）表示。我们还试图通过用单个边替换它们来消除多个边的副本。请注意，删除边的多个副本可能会创建一个新度数为2的顶点，必须将其移除，并且删除度数为2的顶点可能会创建多个边，这些边也必须移除。 一般来说，我至少有一个办法，对于这个问题，我很无奈。这不是Hw，而仅仅是我自己的面试准备。
..
用1个有效的哈密尔顿周期生成图
我的要求是生成一个图形而不是解决一个解决方案。 我正在寻找一种算法来生成一个只有1个哈密尔顿循环的图（NxN网格）。请注意，只有一个独特的解决方案至关重要。该图将是N×N的节点网格，每个网格只有4个相邻节点，即顶部，右侧，底部，左侧。节点只能访问一次。除此之外，还可以有一些特殊的节点。 死亡节点即它们没有边缘连接 固定入口和出口节点，即已经定义了入口和出口节点，没有其他节点可以连接给
..
查找DAG上两个节点之间的所有路径
我有一个拥有以下相邻列表的DAG L | G，B，P G | P，I B |我 P | I I | R R | \ 我想从 L 到 R 。我知道我必须做某种DFS，而这正是我目前为止所做的。 （请原谅Javascript） pre $ 函数dfs（G，start_vertex）{ const fringe = [] const visi
..
检查权重不等于0的周期
我有一个连接图 g ，其中 n 顶点和 m 边缘。 每条边都可以从两个方向穿过，而在一个方向穿过它们时，它们的重量是正的，穿过它们的另一个方向，它们的重量是负的。 > 因此，对于每一条边 u - > v 加权 w 存在一个边 v - > u c $ c> -w 。 我的目标： 对于给定的顶点 v ，检查是否存在回到 v （一个循环）的路径该路径的边权重总和不等于 0 。如果
..
我们可以将Bellman-Ford算法应用于无向图吗？
我知道Bellman-Ford算法适用于有向图。它会适用于无向图吗？看起来，对于无向图，它将无法检测周期，因为并行边将被视为周期。这是真的还是不？算法是否可以应用？ 解决方案 事实上，任何无向图也是有向图。 b $ b 你只需要指定任何边{u，v}两次（u，v）和（v，u）。 但不要忘记，这也意味着任何具有负重量的边缘都会被视为一个循环。 由于Bellman-Ford算法仅适用
..
仅查找权重为1和2的生成树的算法
给定一个加权的，连通的，简单的无向图G，在每条边上权重只有1和2，找到O中的G的MST（V + E）。 有什么想法？ 对于这个问题的表述抱歉，我尽可能地尽力翻译它。 Prim的算法，您需要一种存储活动边的方式，以便您可以访问和删除权重最低的边。通常情况下，权重范围和某种堆数据结构用于存储边缘。 然而，在这种情况下，权重是1或2，所以您可以简单地将边缘存储在2个单独的列表中，其中一个用
..