标签: graph-algorithm

鉴于以下三个数字序列,我想弄清楚如何对数字进行分组以找到它们之间最密切的关系.

1,2,3,4
4,3,5
2,1,3
...

我不确定我正在寻找的算法是什么,但我们可以看到与某些数字的关系比与其他数字的关系更强.

这些数字一起出现两次:

1 & 2
1 & 3
2 & 3
3 & 4

一起一次:

1 & 4
2 & 4
3 & 5
4 & 5

因此,例如,我们可以看到必须存在关系,1, 2, & 3因为它们一起出现至少两次.你也可以说3 & 4它们密切相关,因为它们也会出现两次.但是,算法可能会选择[1,2,3](过度[3,4]),因为它是一个更大的分组(更具包容性).

如果我们将最常用的数字组合在一个组中,我们可以形成以下任何分组:

[1,2,3] & [4,5]
[1,2]   & [3,4]   & [5]
[1,2]   & [3,4,5]
[1,2]   & [3,4]   & [5]

如果允许重复,您甚至可以得到以下组:

[1,2,3,4] [1,2,3] [3,4] [5]

我不能说哪种分组最"正确",但所有这四种组合都找到了不同的方法来对这些数字进行半正确分组.我不是在寻找一个特定的分组 - 只是一个通用的集群算法,它运行得相当好并且易于理解.

我确信还有很多其他方法可以使用事件计数来对它们进行分组.什么是这些良好的基础分组算法？Go,Javascript或PHP中的样本是首选.

给定一系列操作:

A*B*A*B*A*A*B*A*B

有没有办法获得最佳细分以启用子串的重用.

制造

a*b*a*b*a*a*b*a*b => c*a*c,其中c = a*b*a*b

然后看到了

a*b*a*b => d*d,其中d = a*b

总而言之,将8个初始操作减少到这里描述的4个？

(c =(d = a*b)*d)*a*c

当然,目标是尽量减少操作次数

我正在考虑各种后缀.

我对线性时间启发式或解决方案特别感兴趣.'*'操作实际上是矩阵乘法.

我想知道TSP没有问题的名称是什么,考虑回到起点的方式以及解决这个问题的算法是什么.

我查看了最短路径问题,但这不是我想要的,问题只能找到2个指定点的最短路径.但我正在寻找的是我们给出n分并仅输入1个起点的问题.然后,找到所有点正好行进一次的最短路径.(终点可以是任何一点.)

我也研究了汉密尔顿路径问题,但似乎没有解决我定义的问题,而是找出是否存在汉密尔顿路径.

请指教我,谢谢!

问题

我有一个位数组,表示"瓷砖"的二维"地图".此图像提供了位数组中位的图形示例:

我需要确定数组中存在多少个连续的"区域"位.在上面的例子中,有两个这样的连续"区域",如下所示:

瓷砖必须直接位于瓷砖的N,S,E或W上才能被认为是"连续的".对角线触摸的瓷砖不计算在内.

我到目前为止

因为这些位数组可能变得相对较大(大小为几MB),所以我故意避免在我的算法中使用任何类型的递归.

伪代码如下:

LET S BE SOURCE DATA ARRAY
LET C BE ARRAY OF IDENTICAL LENGTH TO SOURCE DATA USED TO TRACK "CHECKED" BITS
FOREACH INDEX I IN S
    IF C[I] THEN 
        CONTINUE 
    ELSE
        SET C[I]
        IF S[I] THEN
            EXTRACT_AREA(S, C, I)

EXTRACT_AREA(S, C, I):
    LET T BE TARGET DATA ARRAY FOR STORING BITS OF THE AREA WE'RE EXTRACTING
    LET F BE STACK OF TILES TO SEARCH NEXT
    PUSH I UNTO F
    SET T[I]
    WHILE F …

我有一个50 x 50的2D网格.网格单元可以具有以下三种状态之一:

1: "inside"
2: "empty"
3: "wall"

我的初始配置是一个网格,其中一些单元格(可能是其中的10%,大部分是连续的)标记为"内部".随机也有一些"墙"细胞.其他单元格是"空的".

我试图找到我可以围绕"内部"单元构建的最短栅栏,以便所有"内部"单元被围起来(围栏是通过将"空"单元改为"墙"单元构建的).如果我们对解决方案进行评分,那么最佳解决方案将最小化需要更改为"墙"单元的"空"单元的数量.

更严格地说,在最终配置中,存在约束,即对于每个"内部"单元,没有到达不通过"墙"单元的网格边缘的路径.就我而言,允许对角线移动.

我猜我可以做一些巧妙的涉及距离变换,或计算网格的拓扑骨架,但这对我来说并不是很明显.如果这是一个经典的优化问题,我不知道谷歌的条款.

是否有O(n ^ 2)算法来寻找最短的栅栏？

编辑:它不像找到"内部"单元格的凸包那么容易,因为预先存在的"墙"单元是自由的.想象一个"C"形的预先存在的墙块,在C的内部有所有"内部"单元格.大多数时候,用"墙"单元格完成C将比在所有墙上绘制凸包更便宜"内部"细胞.这就是使这个问题变得困难的原因.

我需要一些建议.我正在开发一种类似于Flow Free的游戏,其中游戏板由网格和彩色点组成,用户必须将相同的彩色点连接在一起而不与其他线重叠,并且用尽所有板中的空闲空间.

我的问题是关于水平创造.我希望随机生成各级(并且至少应该能够自己解决,以便它可以给玩家提示)并且我在使用什么算法.有什么建议？

注意:图像显示了Flow Free的目标,它与我正在开发的目标相同.

谢谢你的帮助.:)

我搜索过网络,找不到任何DFS算法的解释,用于查找图形的所有关节顶点.甚至没有维基页面.

从阅读中,我从这里了解了基本事实.PDF

每个节点都有一个变量,它实际上是在观察后边缘并找到朝向根节点的最近和最上面的节点.在处理完所有边缘之后,它将被找到.

但我不明白如何在执行DFS期间在每个节点上找到这个向下和向上变量.这个变量到底是做什么的？

请解释算法.

谢谢.

我试图按顺序沿路径排序3D坐标数组.一个样品:

points = np.array([[ 0.81127451,  0.22794118,  0.52009804],
                   [ 0.62986425,  0.4546003 ,  0.12971342],
                   [ 0.50666667,  0.41137255,  0.65215686],
                   [ 0.79526144,  0.58186275,  0.04738562],
                   [ 0.55163399,  0.49803922,  0.24117647],
                   [ 0.47385621,  0.64084967,  0.10653595]])

这些点是随机顺序的,但总是有一条通过它们的路径.我正在使用LKH解算器(Helsgaun 2009)找到适应旅行商问题(TSP)的路径.它涉及两个修改:

• 在原点处或附近添加一个点.这是我到目前为止所处理的每个实例中的最佳起点.这是我的想法,我没有其他依据.
• 在每个点的零距离处添加一个点.这使得求解器找到到路径另一端的路径.这个想法来自这个问题.

请注意,TSP不涉及位置,只涉及节点之间的距离.所以求解者确实"知道"(或关心)我在3D中工作.我只是像这样制作一个距离矩阵:

import numpy as np
from scipy.spatial.distance import pdist, squareform

# Add a point near the origin.
points = np.vstack([[[0.25, 0, 0.5]], points])
dists = squareform(pdist(points, 'euclidean'))

# Normalize to int16s because the solver likes it.
d = 32767 * …

我指的是Skienna的算法书.

测试图是否G包含a的问题Hamiltonian path是NP-hard,哈密顿路径P是一个只访问每个顶点一次的路径.与汉密尔顿循环问题不同,从结束顶点到P的起始顶点不一定有G的边缘.

给定有向非循环图G(DAG),给出O(n + m)时间算法来测试它是否包含哈密顿路径.

我的方法,

我打算用DFS和Topological sorting.但我不知道如何将这两个概念联系起来解决问题.如何使用拓扑排序来确定解决方案.

有什么建议？

我是整数线性编程的新手.我计划使用整数线性编程求解器来解决我的组合优化问题.我更熟悉IDE上的C++ /面向对象编程.现在我使用NetBeans和Cygwin一起编写我的应用程序.

我可以问一下,对我来说是否有一个简单易用的ILP求解器？或者这取决于我想解决的问题？我正在尝试做一些资源映射优化.如果需要任何进一步的信息,请告诉我.

非常感谢,Cassie.