好的一些背景
我一直在从事这个项目,这是我在大学时就开始的(不再在学校,但想扩展它以帮助我提高对 C++ 的理解)。我离题了……问题是通过矩阵找到最佳路径。我生成一个矩阵,其中填充了一组整数值,比方说 9。然后我沿着外边缘(第 0 行,第 1 列长度)创建一条路径,以便沿着它的所有值都是 1。
目标是我的程序会跑遍所有可能的路径,并确定最佳路径。为了简化问题,我决定只计算路径 SUM,然后将其与应用程序计算的 SUM 进行比较。
(题目是小姐领导 S=单线程 P=多线程)
好吧,我的问题。
在一个部分中,算法会进行一些简单的逐位移位以得出迭代的界限。我的问题是这些移位究竟是如何工作的,以便完全遍历整个矩阵(或 MxN 数组)?
void AltitudeMapPath::bestPath(unsigned int threadCount, unsigned int threadIndex) {
unsigned int tempPathCode;
unsigned int toPathSum, toRow, toCol;
unsigned int fromPathSum, fromRow, fromCol;
Coordinates startCoord, endCoord, toCoord, fromCoord;
// To and From split matrix in half along the diagonal
unsigned int currentPathCode = threadIndex;
unsigned int maxPathCode = ((unsigned int)1 << (numRows - 1));
while (currentPathCode < maxPathCode) {
tempPathCode = currentPathCode;
// Setup to path iteration
startCoord = pathedMap(0, 0);
toPathSum = startCoord.z;
toRow = 0;
toCol = 0;
// Setup from path iteration
endCoord = pathedMap(numRows - 1, numCols - 1);
fromPathSum = endCoord.z;
fromRow = numRows - 1;
fromCol = numCols - 1;
for (unsigned int index = 0; index < numRows - 1; index++) {
if (tempPathCode % 2 == 0) {
toCol++;
fromCol--;
}
else {
toRow++;
fromRow--;
}
toCoord = pathedMap(toRow, toCol);
toPathSum += toCoord.z;
fromCoord = pathedMap(fromRow, fromCol);
fromPathSum += fromCoord.z;
tempPathCode = tempPathCode >> 1;
}
if (toPathSum < bestToPathSum[threadIndex][toRow]) {
bestToPathSum[threadIndex][toRow] = toPathSum;
bestToPathCode[threadIndex][toRow] = currentPathCode;
}
if (fromPathSum < bestFromPathSum[threadIndex][fromRow]) {
bestFromPathSum[threadIndex][fromRow] = fromPathSum;
bestFromPathCode[threadIndex][fromRow] = currentPathCode;
}
currentPathCode += threadCount;
}
}
我简化了代码,因为所有额外的东西只会分散问题的注意力。此外,如果人们想知道我编写了大部分应用程序,但使用按位运算符的想法是我过去的导师教给我的。
编辑:
我添加了每个线程执行的整个算法。整个项目仍在进行中,但如果有人感兴趣,这里是整个项目的源代码 [GITHUB]
最佳答案
向右移位相当于将移位的位数除以 2 的幂。即 1 >> 2 = 1/(2 ^ 2) = 1/4
向左移位相当于将移位的位数乘以 2 的幂。即 1 << 2 = 1 * 2 ^ 2 = 1 * 4
我不完全确定该算法的作用以及为什么它需要乘以 2^(行数 - 1)然后逐渐除以 2。
关于c++ - 矩阵迭代的逐位移位?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32644296/