The hungarian algorithm for weighted assignments
ฝัง
- เผยแพร่เมื่อ 20 ต.ค. 2024
- Find 100's more videos linked to the Australia Senior Maths Curriculum at mathsvideosaust...
There are videos for:
Queensland: General Mathematics
Queensland: Mathematical Methods
Queensland: Mathematics Specialist
Western Australia: Mathematics Applications
Western Australia: Mathematics Methods
Western Australia: Mathematics Specialist
Thanks for the video man, this video explains the Hungarian method in great detail and really helped me with studying for my test.
Thank you sir. Your videos really helped me to do well on my exam today!
I'm really happy to hear that. I'd wish you luck for tomorrow, but it doesn't sound like you need it!
@@JoelSperanzaMath Haha thank you! I'm studying hard :)
Thank you so much sir!! Your videos help me so much ❤️
Great explanations
Excellent nicely explained ❤❤❤
This is really interesting. My biggest problem is how could you code this in Python?
pip install scipy
import numpy as np
from scipy.optimize import linear_sum_assignment
# Example cost matrix (replace this with your own matrix)
cost_matrix = np.array([[4, 1, 3],
[2, 0, 5],
[3, 2, 2]])
# Apply the Hungarian algorithm
row_ind, col_ind = linear_sum_assignment(cost_matrix)
# Get the optimal assignment and the total cost
optimal_assignment = list(zip(row_ind, col_ind))
total_cost = cost_matrix[row_ind, col_ind].sum()
print("Optimal assignment:", optimal_assignment)
print("Total cost:", total_cost)
this is probably gonna be in the exam tomorrow ^_^ this helps!
I think you're probably right. Good luck!
Very Informative
It's because of people like Harold Kuhn that employees are considered just numbers in an excell spreadsheet
Great video!
Can we also solve it with a genetic algorithm (tournament + random mutations)
Is this kuhn-munkres algorithm?
If I got zero at the last step after drew a bipartite graph, and that zero was weighted zero in the original matrix, does it count as a perfect match?
for example:
Matrix:
[10 20 30 40]
[ 5 0 17 12]
[ 6 9 1 10]
[ 8 14 3 15]
After the first two steps:
I got: 4 lines zero
[0 10 20 21]
[ 5 0 17 3]
[ 5 9 0 0]
[ 5 11 0 3]
I'm lost here, what is the next step, and how could I find the perfect match?
Anything would help.
Thanks
great clip-used it in my class today
very helpful
Very useful!
Yep definitely just like the Hungarian language
But WHY? What's the WHY behind all these magical computations? What's the intuition? It's like teaching a bunch of goats to follow other goats without any reasoning! It's frustrating to learn fro lectures like this.
A fair critique. Some lectures are about the why, some lectures are about the how.
If you are genuinely interested in the why, you can discover it yourself by trying this with a simple 2 x 2 assignment problem. When you do, make sure each person is better at the first job than the second job. It will then become very clear why we do the row calculation in step 1, and the column calculation in step 2.
Once you've done that, try a 3x3 matrix, and ask yourself what conditions it needs to meet to require step 3 (subtracting lowest uncovered zero, from uncovered zero). It should then be self-evident what this step achieves.
@@JoelSperanzaMath I will definitely do and may be add some comments by the end of this week. Thanks for the tips Joel. Sorry about the rant I’m deeply passionate about teaching and could have critiqued in a better way while I’m learning things for free from you 🙏🏽