javascript - 反转二进制网络

Question

如何反转二元方程，以便找到哪些输入会产生给定的输出。

例子:

Inputs: i0 through i8
Outputs: o0 through o8
Operators: ^ = XOR, & = AND

二元方程:

(1&i0) ^ (1&i1) ^ (0&i2) ^ (1&i3) ^ (0&i4) ^ (0&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o0
(0&i0) ^ (1&i1) ^ (0&i2) ^ (1&i3) ^ (1&i4) ^ (0&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o1
(0&i0) ^ (1&i1) ^ (1&i2) ^ (0&i3) ^ (0&i4) ^ (1&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o2
(1&i0) ^ (0&i1) ^ (0&i2) ^ (1&i3) ^ (0&i4) ^ (0&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o3
(0&i0) ^ (1&i1) ^ (0&i2) ^ (1&i3) ^ (1&i4) ^ (0&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o4
(0&i0) ^ (0&i1) ^ (0&i2) ^ (0&i3) ^ (0&i4) ^ (1&i5) ^ (0&i6) ^ (0&i7) ^ (0&i8) = o5
(0&i0) ^ (0&i1) ^ (0&i2) ^ (1&i3) ^ (0&i4) ^ (0&i5) ^ (1&i6) ^ (0&i7) ^ (0&i8) = o6
(0&i0) ^ (0&i1) ^ (0&i2) ^ (1&i3) ^ (1&i4) ^ (0&i5) ^ (1&i6) ^ (1&i7) ^ (0&i8) = o7
(0&i0) ^ (0&i1) ^ (0&i2) ^ (0&i3) ^ (0&i4) ^ (1&i5) ^ (0&i6) ^ (0&i7) ^ (1&i8) = o8

矩阵形式:

1,1,0,1,0,0,0,0,0,1
0,1,0,1,1,0,0,0,0,1
0,1,1,0,0,1,0,0,0,1
1,0,0,1,0,0,0,0,0,1
0,1,0,1,1,0,0,0,0,1
0,0,0,0,0,1,0,0,0,1
0,0,0,1,0,0,1,0,0,1
0,0,0,1,1,0,1,1,0,1
0,0,0,0,0,1,0,0,1,1

附加限制:

• 素数对 Angular 线总是1
• 我感兴趣的是是否有解决方案，而不是解决方案本身

我如何通过算法找到输入 i0 -i8 使得输出 o0 - o8 为 1？我真正想找到的是是否有这样的解决方案。

我需要一种可扩展到更大网络的算法，至少有 100 个输入/输出。

Answer 1

使用 XOR(而不是 OR)，乍一看似乎某种形式的 Gauss–Jordan elimination至少可以简化问题。改编维基百科关于减少 row echelon form 的文章中的伪代码，我们得到:

function ToReducedRowEchelonForm(Matrix M) is
    // 'lead' is the column index in a row of the leading 1
    lead := 0
    rowCount := the number of rows in M
    columnCount := the number of columns in M
    for 0 ≤ r < rowCount do
        if columnCount ≤ lead then
            stop
        end if
        i = r
        // Find row with lead point
        while M[i, lead] = 0 do
            i = i + 1
            if rowCount = i then
            // no pivot in this column, move to next
                i = r
                lead = lead + 1
                if columnCount = lead then
                    stop
                end if
            end if
        end while
        Swap rows i and r
        for 0 ≤ i < rowCount do
            if i ≠ r do
                Set row i to row i XOR row r
            end if
        end for
        lead = lead + 1
    end for
end function

这会将示例转换为:

1,0,0,0,0,0,0,1,0,0
0,1,0,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
0,0,0,1,0,0,0,1,0,1
0,0,0,0,1,0,0,1,0,0
0,0,0,0,0,1,0,0,0,1
0,0,0,0,0,0,1,1,0,0
0,0,0,0,0,0,0,0,1,0
0,0,0,0,0,0,0,0,0,0

从那里，您可以调整 integer partitioning为一行生成可能的输入的算法，同时考虑到先前行的分区。生成分区非常适合内存。

仍然需要进行时序分析以查看上述是否值得。