Download Shareware and Freeware Software for Windows, Linux, Macintosh, PDA

line Home  |  About Us  |  Link To Us  |  FAQ  |  Contact

Serving Software Downloads in 976 Categories, Downloaded 39.806.857 Times

Algorithm::Munkres 0.06

  Date Added: November 04, 2010  |  Visits: 842

Algorithm::Munkres

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  
NEW DOWNLOADS IN PROGRAMMING, LIBRARIES
Programming  -  Cedalion for Linux 0.2.6
Cedalion is a programming language that allows its users to add new abstractions and define (and use) internal DSLs. Its innovation is in the fact that it uses projectional editing to allow the new abstractions to have no syntactic limitations.
471.04 KB  
Programming  -  Math::GMPf 0.29
Math::GMPf - perl interface to the GMP library's floating point (mpf) functions.
30.72 KB  
Programming  -  Net::Wire10 1.08
Net::Wire10 is a Pure Perl connector that talks to Sphinx, MySQL and Drizzle servers. Net::Wire10 implements the low-level network protocol, alias the MySQL wire protocol version 10, necessary for talking to one of the aforementioned...
30.72 KB  
Programming  -  logilab-common 0.56.2
a bunch of modules providing low level functionnalities shared among some python projects devel Please note that some of the modules have some extra dependencies. For instance, logilab.common.db will require a db-api 2.0 compliant...
174.08 KB  
Programming  -  OpenSSL for linux 1.0.0a
The OpenSSL Project is a collaborative effort to develop a robust, commercial-grade, full-featured, and Open Source toolkit implementing the Secure Sockets Layer (SSL v2/v3) and Transport Layer Security (TLS v1) protocols as well as a...
3.83 MB  
Libraries  -  wolfSSL 4.0.0
The wolfSSL embedded SSL/TLS library is a lightweight SSL library written in ANSI standard C and targeted for embedded and RTOS environments - primarily because of its small size, speed, and feature set. It is commonly used in standard operating...
3.88 MB  
Libraries  -  EuGTK 4.8.9
Makes it easy to develop good- looking, fast, cross-platform programs that run on Linux, OS X, and Windows. Euphoria is a very fast interpreted/compiled language with straight-forward syntax. EuGTK allows programming in a clean, object-oriented...
10.68 MB  
Libraries  -  Linux User Group Library Manager 1.0
The LUG Library Manager is a project to help Linux User Groups start their own library. A LUG library is helpful to the community at large because it increases access to information, and gives everyone the opportunity to become more knowledgeable.
5.35 KB  
Libraries  -  Module::MakefilePL::Parse 0.12
Module::MakefilePL::Parse is a Perl module to parse required modules from Makefile.PL. SYNOPSIS use Module::MakefilePL::Parse; open $fh, Makefile.PL; $parser = Module::MakefilePL::Parse->new( join("", ) ); $info = $parser->required;...
8.19 KB  
Libraries  -  sqlpp 0.06
sqlpp Perl package is a SQL preprocessor. sqlpp is a conventional cpp-alike preprocessor taught to understand SQL ( PgSQL, in particular) syntax specificities. In addition to the standard #define/#ifdef/#else/#endif cohort, provides also...
10.24 KB