javascript - 递归算法未能在规定时间内完成测试

Question

我正在做一个测试，需要二进制层析成像的算法。提供了一组 38 个测试值来测试正确性，但也有 1 CPU 秒的时间限制来完成所有测试。问题如下:

如果存在一个 m×n 矩阵 A，且每个元素要么为 0 要么为 1，则输出"is"

否则输出“No”。

对于每个测试，提供了 2 个数组:

1. r(矩阵中每一行的总和)
2. c(矩阵中每一列的总和)

在等式中:

• m 是 r 数组的长度，其中 1 <= m
• n 是 c 数组的长度，其中 n <= 1000
• ri 是 r 的一个元素，其中 0 <= ri <= n
• cj 是 c 的一个元素，其中 0 <= cj <= m

一个"is"的例子

m = 3;n = 4;r = [2, 3, 2];c = [1, 1, 3, 2];

一个“否”的例子

m = 3;n = 3;r = [0, 0, 3];c = [0, 0, 3];

我有一个似乎可以给出正确答案的解决方案，但是在超过 1 秒的 CPU 时间之前它只管理了 12/38 次测试。

我最初用 ES5 编写代码，然后返回并转换为 ES3 以尝试从中获得更多性能。 (最初作为 ES5 管理 9 个测试)。似乎我可以对当前算法做很多事情来提高性能(除非我弄错了)。这使我相信我的算法有问题，必须有更快的算法来执行此操作。我读了很多书试图找到一个，结果头疼 :)

所以我求助于社区，看看是否有人可以提出比我目前使用的更快的算法。

'use strict';

const ZEROS = (function (seed) {
  let string = seed;
  for (let i = 0; i < 19; i += 1) {
    string += seed;
  }

  return string;
}('00000000000000000000000000000000000000000000000000'));

const ZEROSLEN = ZEROS.length;

const permutate = function (n, ri) {
  const result = [];
  const memoize = {};
  let count = 0;
  do {
    const bin = count.toString(2);
    if (ZEROSLEN + bin.length > ZEROSLEN + n) {
      break;
    }

    if (!memoize[bin] && (bin.split('1').length - 1) === ri) {
      const string = (ZEROS + bin).slice(-n);
      const sLen = string.length;
      const perm = new Array(sLen);
      for (let i = sLen - 1; i >= 0; i -= 1) {
        perm[i] = +string[i];
      }

      memoize[bin] = result.push(perm);
    }

    count += 1;
  } while (count);

  return result;
};

const getMatrixSum = function (n, matrix) {
  const mLength = matrix.length;
  const rows = new Array(mLength);
  const a = new Array(n);
  const last = mLength - 1;
  for (let x = n - 1; x >= 0; x -= 1) {
    for (let y = last; y >= 0; y -= 1) {
      rows[y] = matrix[y][x];
    }

    let sum = 0;
    for (let i = rows.length - 1; i >= 0; i -= 1) {
      sum += rows[i];
    }

    a[x] = sum;
  }

  return a;
};

const isEqual = function (a, b) {
  const length = a.length;
  if (length !== b.length) {
    return false;
  }

  for (let i = length - 1; i >= 0; i -= 1) {
    if (a[i] !== b[i]) {
      return false;
    }
  }

  return true;
};

const addRow = function (i, prev, r, c, result) {
  if (result) {
    return result;
  }

  const n = c.length;
  const ri = r[i];
  if (ri < 0 || ri > n) {
    throw new RangeError('ri out of range');
  }

  const p = permutate(n, ri);
  const m = r.length;
  const rsLast = m - 1;
  const nextI = i + 1;
  for (let x = p.length - 1; x >= 0; x -= 1) {
    const permutation = p[x];
    const next = prev.slice();
    next.push(permutation);
    const sums = getMatrixSum(n, next);
    if (i < rsLast) {
      let memo = 0;
      for (let j = sums.length - 1; j >= 0; j -= 1) {
        if (sums[j] > c[j]) {
          memo += 1;
        }
      }

      if (!memo && addRow(nextI, next, r, c, result)) {
        return true;
      }
    } else if (isEqual(sums, c)) {
      return true;
    }
  }

  return false;
};

const isSolvable = function (r, c) {
  const m = r.length;
  const n = c.length;
  if (m < 1 || n > 1000) {
    throw new Error('Bad data');
  }

  for (let j = n; j >= 0; j -= 1) {
    const cj = c[j];
    if (cj < 0 || cj > m) {
      throw new RangeError('cj out of range');
    }
  }
  
  return addRow(0, [], r, c, false) ? 'Yes' : 'No';
};

console.log(isSolvable([2, 3, 2], [1, 1, 3, 2]));

console.log(isSolvable([0, 0, 3], [0, 0, 3]));

可能值得注意的是，测试是在 SpiderMonkey JavaScript-C24.2.0 版本上运行的

引用:

https://en.wikipedia.org/wiki/Discrete_tomography

https://open.kattis.com/problems/tomography

Answer 1

由于排列屈服于蛮力，因此在开发与此类似的算法时，它们应该是最后的手段。大多数时候不需要它们。

正如我在上面评论的那样，我觉得一种策略可能是首先对 r 进行排序和 c数组降序并从较大的开始。我还没有时间实现一个 JS 代码来解决这个问题，所以我还没有机会彻底测试。请查看，如果您发现缺陷，请指出。

在下面的算法可视化表示中，我们尝试 r = [1,3,1,3]和 c = [3,2,1,2] . X表示一个被占用的单元格，一个红点表示一个不可触摸的单元格，而空的则显然是空闲单元格。因此，在表示单元格的实际算法中，我们需要像 {value: false, avail: false} 这样的数据类型。一个红点同时 {value: false, avail: true}将意味着一个自由空间。或者为了节省空间和速度，您可以使用类似 0b00 的数据类型对于红点，0b01免费空间和0b1X用于占用(这里的 X 表示不关心)单元格。

注意:值得一提的是第 3 步，我们处理 c[0] .在我们插入三个 X 之后我们必须检查 X 占用的行s 更新这些行中空单元格的状态。在这种情况下，对于 r[2]，所有空单元格都变得不可触及。

编辑:

嗯..好吧，因为我们不需要在类似结构的二维数组中构建解决方案，而只需要回答所提供的数据是否有意义，我想出了另一个更简单的想法，本质上是基于上述方法。我真的不认为它能比这更快。它在大约 50 毫秒内解决了 999 x 1000 电路板的问题。

让我们开始吧。

1. 输入是r = [2, 3, 2]; c = [1, 1, 3, 2];然而这里的一个重要条件是两者c和 r数组的总和应为相同的数字。我们可以在代码的开头简单地检查它或保留它，执行以下步骤，如果它们通过，则仅在 c 时检查全是0。以下代码更喜欢后一种方法。
2. 排序r如此下降； r = [3, 2, 2]; c = [1, 1, 3, 2];
3. 尝试减少 r[0] (第一种情况下为 3)c 的许多非零元素by 1.现在c变成 [0, 0, 2, 2] .如果失败则不再尝试并返回 false .
4. 现在我们已经完成了行 r[0] , 用 r = [2, 2]; c = [0, 0, 2, 2]; 递归调用函数同时 r.length大于 0 且 bool 参数 b是true .下一个电话将是 r = [2]; c = [0, 0, 1, 1];最后 r = []; c = [0, 0, 0, 0];
5. 如果最终递归调用为空 r被调用然后检查b是true和 c 的所有项目是 0 . (b && cs.every(n => !n))。

我相信这很好，但因为我没有您的测试用例，所以您可以尝试一下。我相信它会通过时间测试。这是最简单的代码。我在这里测试 rs = [7,3,5,4,6,2,8]和 cs = [7,1,6,3,4,5,2,7] .看起来像；

  71634527
7 x xxxxxx
3 x x    x
5 x x xx x
4 x x  x x
6 x xxxx x
2 x      x
8 xxxxxxxx

function nonogram(rs,cs){
  function runner(rs,cs, b = true){//console.log(rs,cs,b)
    return b && rs.length ? runner(rs.slice(1),                                 // rows argument
                                   cs.map(e => rs[0] ? e ? (b = !--rs[0], e-1)  // cols argument
                                                         : e
                                                     : e),
                                   b)                                           // bool argument
                          : b && cs.every(n => !n);
  }
return runner(rs.sort((a,b) => b-a), cs);
}

var rs = [7,3,5,4,6,2,8],
    cs = [7,1,6,3,4,5,2,7],
    result;
console.time("test");
result = nonogram(rs,cs);
console.timeEnd("test");
console.log(result);