当前位置: 动力学知识库 > 问答 > 编程问答 >

javascript - Inverting binary networks

问题描述:

How can I invert a binary equation, such that I can find which inputs will produce a given output.

Example:

Inputs: i0 through i8

Outputs: o0 through o8

Operators: ^ = XOR, & = AND

Binary equations:

(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

In matrix form:

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

Additional limitations:

  • The prime diagonal is always 1
  • I am interested if there is a solution or not, more then the solution itself

How can I, algorithmically find inputs i0 -i8 such that outputs o0 - o8 are 1? What I really want to find is if there is such a solution or not.

I need an algorithm which is scalable to larger networks, at least up to 100 inputs/outputs.

网友答案:

With XOR (rather than OR), it seems at first glance that some form of Gauss–Jordan elimination can at least simplify the problem. Adapting the pseudocode from the Wikipedia article on reduced row echelon form, we get:

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

This converts the sample to:

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

From there, you could adapt an integer partitioning algorithm to generate the possible inputs for a row, taking in to account the partitions for previous rows. Generating a partition is a great candidate for memoization.

Still need to do a timing analysis to see if the above is worthwhile.

网友答案:

One interesting thing about xor is that:

a ^ b ^ b = a

This allows for nice manipulations, let's say you have:

a ^ b = c

Then you can easily figure out a by xoring both sides with b, getting:

a = c ^ b

If I was in your place, I'd use this trick to get the input from the outputs. The anding that appears in your equations only have the effect of removing some input variables from some equations, so it poses no problem to this approach.

First off, you must know, there might not be a solution for particular coefficient matrices, for example, if the input never appears in any equation (that is, a column of all-zeros in the matrix), or if an equation appears twice (that is, two identical rows), or if an equation is a combination of two other equations.

Now, assuming the matrix you have does yield a solution to your problem, the approach would be use each equation to find one of the inputs. For each equation, xor both sides for all the inputs except one input (and varry this input for each equation). For example, let's say I want to use the first equation to find i0 and the second to find i1 (notice the input has to appear in the equation to make this value), I would now have:

i0 = o0 ^ i1 ^ i3
i1 = o1 ^ i3 ^ i4

Continue for the other equations, then substitute all inputs on the right side with their values from the equations. Repeat recursively till the right side only contains outputs. If you repeat for all equations, you'll find the values of all inputs.

I am sure this approach can be optimized using already-established methods in solving a linear system of equations, especially utilizing the matrix form.

网友答案:

You can solve the 2-SAT problem in polynomial time, see here.

Here's the link to a paper with a fast algorithm (heavy math I'll keep looking for a better link).

Another link with heavy math and pseudocode.

Edit: While I found many papers on this I didn't see much implementable code. Most of the work was on proving satisfiability. You'll probably have to streamline the clauses (remove the ones with zeroes on each run), then use a recursive algorithm to prove unsatifiability, and if you find you've satifisfied it, then you've solved it.

分享给朋友:
您可能感兴趣的文章:
随机阅读: