  Home  |  About Us  |  Link To Us  |  FAQ  |  Contact  # Algorithm::Munkres 0.06

Date Added: November 04, 2010  |  Visits: 842 Report Broken Link Printer Friendly Version Product Homepage Download (92 downloads)

Algorithm::Munkres is a Perl extension for Munkres solution to classical Assignment problem for square and rectangular matrices. This module extends the solution of Assignment problem for square matrices to rectangular matrices by padding zeros. Thus a rectangular matrix is converted to square matrix by padding necessary zeros. SYNOPSIS use Algorithm::Munkres; @mat = ( [2, 4, 7, 9], [3, 9, 5, 1], [8, 2, 9, 7], ); assign(@mat,@out_mat); Then the @out_mat array will have the output as: (0,3,1,2), where 0th element indicates that 0th row is assigned 0th column i.e value=2 1st element indicates that 1st row is assigned 3rd column i.e.value=1 2nd element indicates that 2nd row is assigned 1st column.i.e.value=2 3rd element indicates that 3rd row is assigned 2nd column.i.e.value=0 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].

 Requirements: No special requirements Platforms: Linux Keyword: Algorithmmunkres,  Assignment,  Assignment Problem,  Libraries,  Programming Users rating: 0/10

 License: Freeware Size: 9.22 KB  USER REVIEWS
 More Reviews or Write Review  ALGORITHM::MUNKRES RELATED
 Development Tools  -  LAPJV - Jonker-Volgenant Algorithm for Linear Assignment Problem 1.0 The Jonker-Volgenant algorithm is much faster than the famous Hungarian algorithm for the Linear Assignment Problem (LAP). This Matlab implementation is modified from the original C++ code made by Roy Jonker, one of the inventors of the algorithm.... 10 KB Development Tools  -  Functions for the rectangular assignment problem 1.0 With this package, I provide some MATLAB-functions regarding the rectangular assignment problem. This problem appears for example in tracking applications, where one has M existing tracks and N new measurements. For each possible assignment, a... 20.48 KB Development Tools  -  assignprob.zip 1.0 Functions related to the assignment problem. Main functions: hungarian - calculate a solution of the square assignment problem. See HELP for a reference. 10 KB Development Tools  -  Munkres Assignment Algorithm 1.0 Munkres algorithm (also known as Hungarian algorithm) is an efficient algorithm to solve the assignment problem in polynomial-time. The algorithm has many applications in combinatorial optimization, for example in Traveling Salesman problem.There... 10 KB Development Tools  -  bghungar 1.0 "Hungarian algorithm" to solve the square assignment problem (original & pure MATLAB implementation). The Hungarian algorithm can also be used as a sub-solver in a B&B solver for the travelling salesman problem.How to match N (e.g. N=6) pairs of... 10 KB Libraries  -  Ham Radio Control Libraries 1.2.6.2 Ham Radio Control Libraries is a development effort to provide a consistent interface for programmers wanting to incorporate radio control in their programs. Hamlib is not a complete user application, rather, it is a software layer intended to... 1.4 MB Libraries  -  Aapl C++ Template Library 2.14 Aapl is a C++ template library for generic programming. Aapl supports different generic programming paradigms by providing variations of standard data structures. For example, a by-value linked list template may be used to store a user supplied... 122.88 KB Libraries  -  DAEMon Raco Libraries 0.3 DAEMon Raco Libraries (DRLibs) is a collection of useful functions, objects, and routines for C++. Whats New in This Release: - This release adds new libraries to manage object lists: doublelist.dr.h, simplelist.dr.h, and sortedlist.dr.h.. 28.67 KB Libraries  -  Adobe Source Libraries 1.0.29 The Adobe Source Libraries (ASL) are a collection of C++ libraries building foundation technology to allow the construction of commercial applications by assembling generic algorithms through declarative descriptions. Whats New in This Release:... 8.2 MB Libraries  -  PoJoe Component Libraries 1.1 PoJoe Component Libraries project is a set of Java POJO components, originally developed for OSMQ. Developers have found these components useful in building robust enterprise applications. Of note are: a FIFO queue that utilizes memory until a... 890.88 KB    