The snap thing didn't work for me

The details of the heavy-lifting steps of covering zeros with minimum lines and the final assignment based on the zeros are omitted.

@mateusmelo5095

4 жыл бұрын

The same happens everywhere I search. Do you have some material over this topic? I've been searching for days.

@MartinVotruba4

4 жыл бұрын

You can find the final assignment by searching for maximum cardinality matching of graph, which is induced by edges with zero cost. To do this: 1) having the table with zeros create a graph, where the nodes are jobs and worker. Create an edge between worker and job whenever there is zero cost in the matrix. 2) find the maximum cardinality matching - you are trying to select maximum possible subset of edges so that no node has more than one edge incident (you wont every worker to work at one task and every task to have assigned one worker). This can be solved by Ford Fulkerson algorithm - add source node connecting to all workers, add sink node connecting to all jobs, set upper bounds to all edges to u=1, solve the maximum flow problem, the edges going from workers to jobs with non zero flow are the matching. 3) If the found matching is perfect (all workers/jobs have an incident edge], you are done. Otherwise go to step 4.

@christopherstein2024

Жыл бұрын

I have never seen this properly explained in any video but I think I figured it out. Read this while following the instructions on paper after you have created a zero in every row and column: Drawing the lines: You may only draw along the grid. Look for the column or row that has the most un covered zeros. That's your first line, then repeat until all zeros are covered. Do you have more lines that there are rows? You have made a mistake. Do you have fewer lines as there are rows? You shall procede as shown in the video. Do you have as many lines as there are rows? You can start selecting your final zeros Selecting the zeros: For this you have to start with the zeros with the fewest "neighbor zeros". Finding neighbors for the zeros: Choose a zero. Look at it's row and colum. You will look at a cross or L shaped area containing the zero of your choice plus it's neighboring zeros. (If you know chess you can imagine that your zero is a rook and see how many over zeros it can reach.) Selecting: Select one of the zeros with the fewest neighbor, then cross out it's neighbors, they can't be selected because each row and column may only have one marked zero. Proceed with the remaining zero(s) that has/have the fewest neighbors. There can be multiple right answer with you can check by calculating if they end up with the same cost.

i literally loved everything about this video. i can say this is the first video lesson that made me feel positive and the explanation was really nice. i finally understood.

Cool explanation!! Honestly also mesmerized by how you edited the explanation, it feels very snappy and fun to watch

Thank you for the video! Time complexity regarding step 3 is a little confusing. Some explanation on how to find the minimum lines required to cover all zeros would be helpful.

Thank you for this video. Finally had that aha moment for this algorithm regarding picking the assignments.

THANK YOU SO MUCH , i needed this for a test i have in 2 days from now , and it covered everything i need to know about this !

You editing is super good, thanks!

That was very well explained, thanks!

Great and simple explanation. Keep up the good work! You've just gotten a new subscriber! I'll spread the word around. Cheers!

Guys make more videos like this. This just saved my time...!!

Returning to this second time, very very helpful. Thank you!

Thank you it was very helpful! I used it for reassigning labels for k-means clustering.

i see this video only one time and i learn a lot.very nice style to teach nice job ;)

Dude, this was awesome. Saved me on my assignment.

Many thanks for the clear explanation!

*Thanos* My child you will achieve what I could not with that snap

A very lovely video. Thank you!

Such a great explanation!

Really good explanation. Thank you for this video

Thank you very much! This was so helpful

Great work. Thanks!

Nice explanation!

thank you for the clear explanation brother

This was amazing, when you know that you have to find zeros that are alone in step 3 then this is the perfect video ;)

perfect explanation! thanks

Thank you for the video!

subscriber for life after this

This is a very nice explanatio

Thank you.

thanks a lot for the help

Fantastic graphics. Please make videos on SYSTEM DESIGN topic

But won't it still be very hard to find the correct zeros in nxn matrices when n is very large? Anyway great video

Can somebody share the final C code for this? StackOverflow is not pointing to one answer.

Wonderful

What happens when the number of lines it takes to cover all zeros exceeds n?

Thanks, you just saved me for a test tomorow 😂

Question 1: How do you find the least number of lines to cover all zeros in Step 3? Question 2: What if there are multiple solutions to step 3 (different ways to cover zeros with the same number of lines)? Will they all result in optimal solutions to the assignment problem?

@compsci711

8 жыл бұрын

1. Here we are simply doing it by 'eye'. There are, however, various algorithms out there for completing this step. 2. Yes, they will both result in the same solution!

@khazza930

8 жыл бұрын

Thanks for the reply. Could you give examples (or links) of some of these algorithms, please?

@compsci711

8 жыл бұрын

This should get you going in the right direction: stackoverflow.com/questions/23379660/hungarian-algorithm-finding-minimum-number-of-lines-to-cover-zeroes

@khazza930

8 жыл бұрын

awesome, thanks!

perfect explanation and animations! Tip: Set your voice volume a little higher or the sound effects a little lower.

is the Algorithm only works N * N grid? does it work for N * M grid? If yes, step 3, the numbers of lines should be determined by the total row or total of column ?

@garrettryan701

5 жыл бұрын

You can add extra numbers to make it square and just assign them as really small numbers while noting they are not "real" assignments in the solutions.

For step 3, how can we ensure that an assignment is optimal. I’m convinced that finding some assignment is O(n**2) but I don’t know how you’d find an optimal one in that time. What could I look up to understand this?

@davidenzler1691

2 жыл бұрын

first add up the number of 0s in each row and column. Then select rows and columns to "draw" a line through starting with the row or column with the highest number of 0s. After every line is drawn, recalc the number of 0s in each row and column excluding the ones with lines drawn through them.. I realize this post is over a year old but I hope it helps future people!

THANK YOUUUUUUUUU

What algorithm is used to find a minimum covering of the zeros? I have seen many instances of this algorithm but that detail is glossed over. It may be easy to come up with the covering using a pencil and my eyes but this seems like a useless algorithm without that step.

Please make more tutorial videos!!!!

Mate make more videos please.

Good one! Will you start making algorithm videos on a regular basis?

@compsci711

8 жыл бұрын

This video was actually made for a uni assignment, although we're open to making more!

@khazza930

8 жыл бұрын

Yeah, it would be great if you would start making more more of these! You never when you'd end up saving a student's entire degree with a video on an algorithm!

I could be wrong but I think I would add 10 to the cross two line value

amaazing

Step three took me some time to get it right. you should've explained it better. But overall good job!!

big thaaaankkkkk you!!! you just saved me.

@compsci711

8 жыл бұрын

No problem!

step 3 in example 2 looks not correct. The first line should be the last column line not the first-row line.

0:48 I dont see whats wrong with those matrices. Obviously no two workers work one job, and no two jobs are given to the same worker. But in 0:55 I dont see whats different about the "correct" matrix.

Clutch

maybe overdoing the sound effects...

Bombs Away. 3 . Consecutives. Tree. Now.

1:54

The sound effects are way louder than your voice. I have to close this because it is way too loud to watch at school.

@martinn.6082

5 жыл бұрын

Use headphones? Why do you watch it at school anyway? In a class or something?

Not helpful at all If there are no implementation details explained. How am I supposed to know how to select fewest lines to cover all zeros?

I don’t get why the algorithm works

started out great but confused the hell out of me with the stupid snap crap. People use youtube because they are visual learners.

I have no idea what this dude is talking about

You get views because of savva

Horrible snapping ruins the video