标签: graph-algorithm

我正在研究一个可以简化为图优化问题的问题,如下所示.

• 给出了一组彩色节点.它们都是未连接的,即图中没有边缘.

• 边缘将插入节点之间.

• 一个节点最多只能有4个边.

• 表格提供了边缘利润贡献的规则.

  例如.,

  • 连接红色到红色的边缘:利润为10

  • 连接红色到蓝色的边缘:利润是20

• 节点总数约为100.

• 颜色总数通常在20到30左右,但它可以高达50个.相应地,利润表(边缘)将是一个很长的列表,但它不会列出所有可能的组合.表中未指定的边的利润假定为零.

问题是优化连接(边缘),以使总利润最大化.

我想知道这个问题,或许是以某种其他方式,是已知的.如果是这样,请提供可能有帮助的任何指示.谢谢.

我有一个像图中所示的三角形镶嵌.

给定N曲面细分中的三角形数量,我有一个N X 3 X 3数组存储(x, y, z)每个三角形的所有三个顶点的坐标.我的目标是为每个三角形找到共享相同边缘的相邻三角形.这是一个错综复杂的部分是我不重复邻居计数的整个设置.也就是说,如果三角形j已被计为三角形的邻居i,则三角形i不应再次计为三角形的邻居j.这样,我想有一个地图存储每个索引三角形的邻居列表.如果我从索引中的三角形开始i,那么索引i将有三个邻居,而所有其他的将有两个或更少.举个例子,假设我有一个存储三角形顶点的数组:

import numpy as np
vertices = np.array([[[2.0, 1.0, 3.0],[3.0, 1.0, 2.0],[1.2, 2.5, -2.0]],
                     [[3.0, 1.0, 2.0],[1.0, 2.0, 3.0],[1.2, -2.5, -2.0]],
                     [[1.0, 2.0, 3.0],[2.0, 1.0, 3.0],[3.0, 1.0, 2.0]],
                     [[1.0, 2.0, 3.0],[2.0, 1.0, 3.0],[2.2, 2.0, 1.0]],
                     [[1.0, 2.0, 3.0],[2.2, 2.0, 1.0],[4.0, 1.0, 0.0]],
                     [[2.0, 1.0, 3.0],[2.2, 2.0, 1.0],[-4.0, 1.0, 0.0]]])

假设我从顶点索引开始计数2,即具有顶点的那个[[1.0, 2.0, 3.0],[2.0, …

假设我有一个图表,其中节点存储在排序列表中.我现在想要对这个图进行拓扑排序,同时保持拓扑顺序未定义的原始顺序.这有什么好的算法吗？

我正试图找到一个叫做Twiddle的小益智游戏的最佳解决方案(这个游戏的applet可以在这里找到).游戏有一个3x3矩阵,数字从1到9.目标是使用最少的移动量使数字按正确的顺序排列.在每次移动中,您可以顺时针或逆时针旋转2x2方格.

即如果你有这种状态

6 3 9
8 7 5
1 2 4

然后顺时针旋转左上方的2x2方形

8 6 9
7 3 5
1 2 4

我正在使用A*搜索找到最佳解决方案.我的f()只是所需的旋转次数.我的启发式功能已经导致最佳解决方案(如果我修改它,请参见最后的通知),但我不认为这是你能找到的最好的解决方案.我当前的启发式获取每个角落,查看角落处的数字并计算到该数字在解决状态下将具有的位置的曼哈顿距离(这给出了将数字带到此位置所需的旋转次数)并将所有数量相加这些价值观.即你采取上面的例子:

6 3 9
8 7 5
1 2 4

这个结束状态

1 2 3
4 5 6
7 8 9 

然后启发式做了以下事情

6 is currently at index 0 and should by at index 5: 3 rotations needed
9 is currently at index 2 and should by at index 8: 2 rotations needed
1 is currently at index 6 …

在我正在考虑的算法课程中,据说深度优先搜索(DFS)比广度优先搜索(BFS)更具空间效率.

这是为什么？

虽然它们基本上都在做同样的事情,但在DFS中我们正在堆叠当前节点的后继者,而在BFS中我们将后续队列入队.

我知道Prim的算法,我知道它的实现,但我总是跳过一个我想问的部分.有人写道,Prim与Fibonacci堆的算法实现是O(E + V log(V)),我的问题是:

• 什么是斐波纳契堆？
• 它是如何实现的？和
• 如何用Fibonacci堆实现Prim的算法？

我最近一直在阅读关于Java和Javascript图形库的相关内容,但我还没有找到一个很好的方法来做我想做的事情.

基本上我有一组关于一堆元素的集合(最多几千).这些组可以完全或部分重叠,完全覆盖或完全彼此不相交.我想要做的是显示以下信息:

• 集合的大小(与其他集合相关)
• 根据其涵盖的元素计算的集合的"热量"值(颜色代码)
• 单个图形中集合的完整拓扑(以便向用户显示重叠,交叉点等)

编辑:也许我应该举例说明我的意思是集合和元素以及部分重叠的层次结构.以下是我处理的那种集合的过度简化版本(请注意数字1- 10和字母a- h并X表示彼此相当的元素):

Set1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
Set2 = {1, 2, 3, 4, 5, 6}
Set3 = {1, 2, 3}
Set4 = {1, 4, 5, 6, 7}
Set5 = {a, b, c, d, e, f, g, h}
Set6 = {a, b, c, d, e}
Set7 = {a, b, c, 7}
Set8 = {2, 4, 7, 8, c, …

我需要的是纯数学图的JavaScript实现.要明确我不是指像sigma.js或d3.js这样的图形可视化库.

我正在寻找的库将实现以下功能:

• 创建有向和无向图形对象
• 创建加权和未加权的graps对象
• 向图表添加/删除顶点和边缘
• 向顶点和边添加标签(即附加元数据)
• 实现基本类似图搜索和遍历算法,深度优先搜索,广度优先搜索,Dijkstra算法,A*和他人.

有谁知道一个人是否已经存在？

Prim和Kruskal的算法用于查找连接和无向图的最小生成树.为什么它们不能用于指向的图形？

我的一个朋友刚刚在谷歌接受采访并被拒绝,因为他无法解决这个问题.

我在几天内有自己的面试,似乎无法找到解决问题的方法.

这是问题:

给你一个模式,比如[abab].你也会得到一个字符串,例如"redblueredblue".我需要编写一个程序来告诉字符串是否遵循给定的模式.

几个例子:

模式:[abba]字符串:catdogdogcat返回1

模式:[abab]字符串:redblueredblue返回1

模式:[abba]字符串:redblueredblue返回0

我想到了一些方法,比如获取模式中唯一字符的数量,然后找到字符串的许多唯一子字符串,然后使用hashmap与模式进行比较.然而,如果a的子串是b的一部分,那么结果证明是个问题.

如果你们中的任何人能够帮助我,那真的很棒.:)

更新:

添加信息:模式中可以有任意数量的字符(az).两个字符不代表相同的子字符串.此外,字符不能表示空字符串.