3

I want to know the minimum number of lines covering all the Zeros for Hungarian Algorithm. Ive followed this link, but the code there is a greedy one.

Hungarian Algorithm: How to cover 0 elements with minimum lines?

For example,

{0,0,1,1},
{1,0,0,1},
{1,0,1,0},
{1,1,1,1},

This case fails. I should get output 3. But the output this solution gives is 4.

Any other ways of solving it would be a great help.

Thanks

Community
  • 1
  • 1
user650521
  • 583
  • 1
  • 9
  • 23
  • 2
    try http://codegolf.stackexchange.com/ I think this question would be more relevant there. – dmi3y Oct 10 '13 at 06:31
  • 1
    @dmi3y I doubt it. Code Golf is for writing a program with as few lines as possible, or that executes as fast as possible. Not for general approaches to algorithm questions. – Bernhard Barker Oct 10 '13 at 08:23
  • yes, TS mentioned minimum lines of algorithm, that's why I thought it might be more help on Code Golf than here on SF. – dmi3y Oct 10 '13 at 18:16
  • @dmi3y you misunderstood the question. The OP wants to cover the 0s with a miniumum number of lines. See [Hungarian algorithm](https://en.wikipedia.org/wiki/Hungarian_algorithm) on Wikipedia. – kinokijuf May 23 '14 at 19:34
  • @kinokijuf, thanks, yes I could see now I am wrong, but still not quite understand what is minimum number of lines? – dmi3y May 23 '14 at 19:54
  • @pathikrit, there are so many better resources for the Hungarian algorithm... – David Eisenstat Mar 09 '23 at 00:08
  • @pathikrit What should be the language? is there a defference between cpp, js, java for you? – Alijvhr Mar 14 '23 at 15:29

1 Answers1

1

Introduction

I didn't have access to a CPP compiler or java runtime. Wrote this using my browser using ES2017. At least it runs in your browser! If you need I can write it in other languages (cpp, java, php, python).

And I must add that I don't know anything about Hungarian Algorithm and I just created an algorithm to find the best minimum optimized lines!

I'm pushing this code and tests in a Github repo. So you can fire more Info, Codes, Documentations here

In matrix data presentation I used:

index 0 represents rows and index 1 represents columns.

Step 1

Go through input array and count the zeros and store it in a 2 dimensional array.

The #matrixPower indicates number of zeros in each column or row.

Step 2

In the next step we check row by row. Each row which have a value greater than 0 in #matrixPower[0] is a row contains zeros and we call them powered from now on.

Loop through powered row and check every column which crosses the current powered row on 0! If there was any column with power of 1 so we draw the line on the row! And decrease the power of every crossed column by 1. Because it is covered by current row!

Count the lines in the progress.

Do this for all rows!

Notice: When a column crosses a row on a zero the power would be at least 1 because of the zero in the cross!

Step 3

If any powered column remains we should draw the line on them!

That's it! now we have a map of lines and a number of minimum lines!

Note: inputMatrix is the variable which contains your matrix!

let colLength = inputMatrix[0].length;
let rowLength = inputMatrix.length;
let matrixPower = [Array(rowLength).fill(0), Array(colLength).fill(0)];
let matrixLine = [Array(rowLength).fill(0), Array(colLength).fill(0)];

for (let row = 0; row < rowLength; row++) {
    for (let col = 0; col < colLength; col++) {
        if (inputMatrix[row][col] == 0) {
            matrixPower[0][row]++;
            matrixPower[1][col]++;
        }
    }
}
let minimum = 0;
let len = [matrixPower[0].length, matrixPower[1].length], cross;
for (let row = 0; row < len[0]; row++) {
    cross = [];
    for (let col = 0; col < len[0]; col++) {
        if (inputMatrix[row][col] == 0) {
            cross.push(col);
            if (matrixPower[1][col] < 2) {
                matrixLine[0][row] = 1;
            }
        }
    }
    if (matrixLine[0][row] == 1) {
        minimum++;
        for (let i = 0; i < cross.length; i++)
            matrixPower[1][cross[i]]--;
    }
}
for (let col = 0; col < len[1]; col++) {
    if (matrixPower[1][col] > 0) {
        matrixLine[1][col] = 1;
        minimum++;
    }
}

console.log(minimum);

I tested the algorithm against an optimized brute force function 100 times with random 12*10 matrixes. The result was 100% OK!

average time of brute force: 0.036653s

average time of Optimized algorithm: 0.000019s

total time of brute force: 3.9180s

total time of Optimized algorithm: 0.0025s

I hundred tests brute force took ~4seconds but the algorithm took only 2.5milliseconds

I'm sure this can be more optimized through more work.

Alijvhr
  • 1,695
  • 1
  • 3
  • 22
  • 1
    Thank you for your answer! I think it is indeed correct - perhaps you can write a brute force solution checked which tries all possible 2^(row + column) ways by drawing all possible lines and sees if it works or not against your solution. – pathikrit Mar 15 '23 at 13:39
  • Also, for the sake of clarification for other readers, can you explain this part better "If a line zeros was covered by other lines in opposite direction the line will marked for removing. However if any of lines in opposite direction which is covering a zero from current line does not contain another zero, current line will be preserved and opposite line will be marked for removing."? I think I know what you mean - remove any lines which are not needed because its work is done by other lines but how do you pick which one is the redundant one - this one or the other one? – pathikrit Mar 15 '23 at 13:46
  • Thanks for the bounty. I will elaborate more in 2-3 hours. Actually I was sleepy during answering, so it might be a little unclear. – Alijvhr Mar 15 '23 at 14:17