| Name : perl-Algorithm-Munkres
| |
| Version : 0.80.0
| Vendor : obs://build_opensuse_org/devel:languages:perl
|
| Release : lp155.1.1
| Date : 2024-07-15 22:15:26
|
| Group : Unspecified
| Source RPM : perl-Algorithm-Munkres-0.80.0-lp155.1.1.src.rpm
|
| Size : 0.02 MB
| |
| Packager : https://www_suse_com/
| |
| Summary : Munkres.pm
|
Description :
Assignment Problem: Given N jobs, N workers and the time taken by
each worker to complete a job then how should the assignment of a
Worker to a Job be done, so as to minimize the time taken.
Thus if we have 3 jobs p,q,r and 3 workers x,y,z such that:
x y z
p 2 4 7
q 3 9 5
r 8 2 9
where the cell values of the above matrix give the time required
for the worker(given by column name) to complete the job(given by
the row name)
then possible solutions are:
Total
1. 2, 9, 9 20
2. 2, 2, 5 9
3. 3, 4, 9 16
4. 3, 2, 7 12
5. 8, 9, 7 24
6. 8, 4, 5 17
Thus (2) is the optimal solution for the above problem.
This kind of brute-force approach of solving Assignment problem
quickly becomes slow and bulky as N grows, because the number of
possible solution are N! and thus the task is to evaluate each
and then find the optimal solution.(If N=10, number of possible
solutions: 3628800 !)
Munkres\' gives us a solution to this problem, which is implemented
in this module.
This module also solves Assignment problem for rectangular matrices
(M x N) by converting them to square matrices by padding zeros. ex:
If input matrix is:
[2, 4, 7, 9],
[3, 9, 5, 1],
[8, 2, 9, 7]
i.e 3 x 4 then we will convert it to 4 x 4 and the modified input
matrix will be:
[2, 4, 7, 9],
[3, 9, 5, 1],
[8, 2, 9, 7],
[0, 0, 0, 0]
|
RPM found in directory: /packages/linux-pbone/ftp5.gwdg.de/pub/opensuse/repositories/devel:/languages:/perl/15.5/noarch |
