我正在尝试一系列不同的算法来寻找旅行商问题的近似最优解,其中一种方法是蛮力方法 - 检查n个城市之间的每条可能路径,并简单地返回最佳路径.这是一个O(n!)算法,因此很自然地需要很长时间才能执行大量城市.
我想提高我的暴力实施的效率,我注意到的一件事是你不必检查城市的每一个排列.例如,如果您有城市1,2,3和4,则路径(1-2-3-4)与路径(2-3-4-1)的长度相同.路径(3-4-1-2)和(4-1-2-3)也是如此.通过利用这一事实,我们应该能够将蛮力算法的复杂性从O(n!)降低到O((n-1)!),甚至O((n-1)!/ 2)如果我们意识到所有路径都可以反转而不影响它们的长度.
基本上,我正在寻找一种能够从一组不同的整数生成循环排列的算法.如果算法将"镜像"排列视为等效(例如1-2-3和3-2-1是相同的,因此只需要其中一个),这也是很好的.有谁知道这样做的方法？Java实现会很精彩,但我会采取任何措施!
我正在尝试将R文档文件(扩展名.Rd)转换为纯文本.我知道RdUtils包含一个名为Rdconv的工具,但据我所知它只能在命令行中使用.有没有办法从R会话中访问Rdconv(或类似的转换工具)？
我正在编写一些需要能够处理具有任意维数的 NumPy ndarray 的 Cython 代码。目前，我只有不同的函数来接受不同大小的 ndarrays，有点像：
def func1(np.ndarray[DTYPE_float64_t, ndim=1] arr):
# Do something with the 1-D ndarray.
def func2(np.ndarray[DTYPE_float64_t, ndim=2] arr):
# Do something with the 2-D ndarray.
def func3(np.ndarray[DTYPE_float64_t, ndim=3] arr):
# Do something with the 3-D ndarray.
但是我想编写一个以任意维度的 ndarray 作为参数的通用函数。我试着简单地忽略“ndim”参数，但是 Cython 假设 ndim=1，这不好。
有没有办法做到这一点，还是我只需要为每个维数编写一个函数？
假设我有一个3x3的频率值矩阵.此矩阵中的每个单元格表示在某个位置检测到的实体数量(有关这些位置的详细信息对我们的目的无关紧要).例如,在第1行第1列中检测到0个实体; 在第2行第3列中检测到3个实体; 等等
[,1] [,2] [,3]
[1,] 0 1 0
[2,] 1 2 3
[3,] 0 1 1
我想将此矩阵转换为nx2数据帧,其中n是在所有位置检测到的实体总数.在这种情况下,应该有9行,因为总共检测到9个实体.在我们创建的数据框中,第1列应包含实体的行索引,第2列应包含实体的列索引.
我们可以使用以下代码来完成此任务,但对于较大的矩阵,此方法非常慢.
mat <- matrix(c(0,1,0,1,2,3,0,1,1), nrow = 3, byrow = TRUE)
x <- rep(NA, 9)
y <- rep(NA, 9)
count <- 0
for(i in 1:3){
for(j in 1:3){
while(mat[i,j] > 0){
count <- count + 1
x[count] <- i
y[count] <- j
mat[i,j] <- mat[i,j] - 1
}
}
}
df <- data.frame(x, y)
此代码为我们提供了以下9x2数据框:
x y
1 2
2 1
2 …