MATLAB: The shortest way to find the sequence of all 1s to all 0s

algorithm

The sequence P has a total of N bits, given the initial state (0 or 1). The given number d is the number of changes each time. Find the least number of changes method process (including the process) from A to all 0 sequence.
For example: P=[1 1 1 1], d=2, then the shortest change sequence is [0 0 1 1]->[0 0 0 0].
Of course, there are also sequences that can never be changed successfully.
The code I wrote, it can only give all the results that can be changed, but not necessarily the least number of times. For example, A=[1 1 1 1 1 1 1 1 1 1 1 1], D=9. The correct result should be [0 0 0 0 0 0 0 0 0 1 1 1]->[1 1 1 1 1 1 0 0 0 0 0 0]->[0 0 0 1 1 1 1 1 1 1 1 1 1] ->[0 0 0 0 0 0 0 0 0 0 0 0].
This is the code I wrote:
clear
global LEN G H d
P=[1 1 1 1 1 1 1 1 1 1 1 1];
d=6;
LEN=length(P);
H=length(find(P==0));
G=graph();
G=G.addnode(num2str(P));
dd(P);
p=plot(G);
function dd(P)
global LEN G H d
C=nchoosek(1:LEN,d);
for i=1:length(C)
    D=P;
    D(C(i,:))=~D(C(i,:));
    L=length(find(D==0));
    if ~any(H==L)
        H=[H L];
        G=G.addnode(num2str(D));
        G=G.addedge(num2str(P),num2str(D));
        dd(D);
    end
end
end
How can I change the code to make it the shortest or is there any new way to solve this problem?

Best Answer

Build full Graph and select the shortest path
N = 12; % number of bits
D = 9;  % number of flips for each step, <= N
E0 = (0:N)+(-N:0)';
D0 = (0:N)-(0:N)';
A = mod(D0,2)==mod(D,2) & abs(D0)<=D & abs(E0)<=N-D;
P = shortestpath(graph(A),1,N+1);
if length(P) <= 1
    fprintf('No solution\n');
    return
end
% Build the binary arrays
% between two sucessive rows are D-bit flips
B = zeros(length(P),N);
B(1,:) = 1;
i = 1;
b = B(1,:);
for q=2:length(P)
    j = P(q);
    d0 = (D+i-j)/2;
    i0 = find(b==0);
    i1 = find(b==1);
    b(i0(1:d0)) = 1;
    b(i1(1:(D-d0))) = 0;
    B(q,:) = b;
    i = j;
end
% Print the result
char(B+'0')
Binary arrays transformation, between two sucessive arrays are 9 bits flips
111111111111
000000000111
111111000000
000111111111
000000000000
Related Question