PROJECT 5 .- Assignment (matching): Hungarian algorithm Assignment (matching): Hungarian algorithm INTRODUCTION
start by describing as assignment (matching) _
Given a graph a matching V-U is a set of edges not adjacent to each other.
We say that a vertex is matched (assigned) if it is contiguous with an edge in the matching.
Otherwise, the vertex is unmatched (free).
A perfect matching is a matching covering all vertices of the graph. That is, each vertex is saturated under the matching.
2. Matchings in bipartite graphs The bipartite graphs are usually represented graphically with two columns (or rows) of vertices and edges connecting vertices of columns (or rows) different.
The two sets U and V can be thought of as a graph coloring with two colors: if the vertices in U painted blue and the green-dev Verica get a two-colored graph where each edge has one blue and one vertex green. On the other hand, if a graph does not have the property that can be colored with two colors is not bipartisan.
matching problems are often related to bipartite graphs. Finding a maximum bipartite matching (often called maximum cardinality of a bipartite graph) in a bipartite graph is perhaps the simplest problem.
In a weighted bipartite graph, each edge has an associated value.
A bipartite maximum weighted matching is defined as a perfect matching where the sum of the values \u200b\u200bof its arcs in the matching has maximal value. If the graph is not complete bipartite, missing arcs are introduced zero.
Find this matching problem is known as assignment.
The more specialized is the Hungarian algorithm that solves the problem of cost allocation of time. DEFINITION: The first known version of the Hungarian method, was invented and published by
Harold Kuhn in 1955.
porJames Munkres This was reviewed in 1957 and has been known as the Hungarian algorithm, the algorithm deasignación Munkres, or Kuhn-Munkres algorithm.
The algorithm models a problem as a matrix deasignación cost mn × , where each element represents the cost of assigning the n worker m work.
The algorithm performs the minimization on elementos de la matriz como en el caso de un problema de minimización de precios.
Seutiliza el método de eliminación Gaussiana para hacer aparecer ceros (al menos un ceropor línea y por columna). Sin embargo, en el caso de un problema de maximización de beneficio, el costo de la matriz necesita ser modificada de modo que la minimización de sus elementos resulte maximizar los valores de costo originales.
En un problema de costo infinito, la matriz de costo inicial puede ser remodelada restando cada elemento de cada línea del valor máximo del elemento de esa línea (o la columna respectivamente). En un problema de costo finito, todos los elementos son restados del maximum value of the entire matrix.
PHASES METHOD FOR THE APPLICATION OF HUNGARIAN:
phases for implementation of the Hungarian method are: first
1 .- Find the smallest element in each row of cost matrix m * m must build a new matrix by subtracting from each cost the minimum cost of each row, find for this new matrix, the minimum cost in each column. Next you must build a new matrix (called matrix reucidos costs) by subtracting from each cost the minimum cost of your spine. 2 .- (In some texts this step is attributed to Flood), consists of drawing the minimum number of lines (horizontal or vertical or both of these ways only), required to cover all the zeros in the matrix of reduced costs, if they need more lines to cover all zeros, you have an optimal solution between covered zeros matrix. If it takes less than m lines to cover all zeroes, continue with step 3. The number of lines to cover the zeros is equal to the number of assignments to date can be performed.
3 .- Find the smallest nonzero element (called k) in the reduced cost matrix, which is not covered by the lines drawn in step 2, then you must subtract k from each uncovered element of matrix reduced costs and add k to each element of the matrix of reduced costs covered by two lines (intersection). Finally it deve return to step 2.
NOTES: A) To solve an allocation problem in which the goal is to maximize the objective function, multiply the payoff matrix by negative one (-1) and solve the problem as a minimization .
B) If the number of rows and columns in the matrix of costs are different, the problem of allocation is unbalanced. The Hungarian method can provide an incorrect solution if the problem is not balanced, because of the above, it should balance any issues first assignment (adding rows ficiticias or columns) before using the Hungarian method to solve it.
C) In a big problem, it may be difficult to obtain the minimum number of rows needed to cover all the zeros in the current cost matrix. It can be shown that if j lines are needed to cover all zeroes, then j can be assigned only work at zero cost in the current matrix, which accounts for over when they need more lines.
IF SET OPTIMIZATION OF DECISION OR: The Hungarian algorithm is a combinatorial optimization algorithm
that solves problems of allocation in time n (O) 3.
Optimization combinatorial optimization combinatorial is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory. It interacts with other fields such as artificial intelligence and software engineering. Combinatorial optimization algorithms solve instances of problems that are believed to be difficult in general, exploring the solution space (usually large) for these instances. Combinatorial optimization algorithms accomplish this by reducing the effective size of the space, and exploring the search space efficiently.
combinatorial optimization algorithms are often implemented in imperative languages \u200b\u200blike C and C + + in software programming languages \u200b\u200bsuch as Prolog, or even multi-paradigm languages \u200b\u200bsuch as Oz.
By studying the theory of computational complexity is possible to understand the importance of combinatorial optimization. Combinatorial optimization algorithms are commonly associated with NP-hard. These general problems are not resolved effectively, however, several approximations of complexity theory suggests that some instances (eg "small" instances) of these problems can be solved efficiently. Such instances often have important practical ramifications.
COMPUTATIONAL COMPLEXITY:
The complexity is O (n3) cubic complexity.
often occur in loops with triple nesting. If n is doubled, the execution time is multiplied by eight. For a large value of n starts to grow dramatically.
computadoracapaz ◦ We have a process data in 10-4 sec. This computer runs an algorithm that reads records from a database, this algorithm has exponential complexity 2n How long does it take to process an input n data?
◦ Now you have the same computer capable of processing data in 10-4 sec. But running an algorithm that does the same work cited above, but this algorithm has cubic complexity n3, how long will it take to process a data entry no?
can say that only an efficient algorithm with a low order of complexity, can handle large volumes of data, it is reasoned that an algorithm is:
"Very efficient if its complexity is order log n
-Efficient if its complexity is of order na -inefficient if its complexity is of order 2n
"He considers that a problem is tractable if there is an algorithm that solves it with complexity less than 2n, and that is untreatable or devoid of solution otherwise.
Pseudocode of the algorithm:
This is the link where I found detailed information about each step, and what is to be taken into account.
http://www.public.iastate.edu/ ~ ddoty / HungarianAlgorithm.html
asymptotic analysis of the algorithm (logarithmic, polynomial, exponential): This algorithm is of class P, since there is an algorithm that can be solved in polynomial time, which for reasonable values \u200b\u200bcan be solved on a computer using an appropriate program.
data structure used (arrays, lists, queues, stacks, trees): The structure used is: queues, it provides a theoretical basis of the type of service we can espeerar of a particular resource, such as the way in which that action can be designed to provide a certain level of service to its customers.
queuing systems are computer models that provide service. As a model can determine any system where customers come looking for work or service of any kind, and leave the service after it has been treated.
We can model such systems, as well as simple lines or as an interconnected system of casting, forming a network of queues. EXAMPLE
(manual, scheduled, busy): http://www.tu.tv/videos/metodo-hungaro 1. Locate the smallest element of each row and subtract the other parts of the same line. Repeat this procedure for each column where the column minimum is determined after the remaining items.
2. Determine if there is an assignment likely to involve zero costs in the revised cost matrix. If there is such an allocation is optimal. If there continue to step 3.
3. Cover all the zeros in the revised cost matrix with the smallest number of horizontal and vertical lines as possible. Each horizontal line must go through the line and each vertical line across the column. Find the smallest number that is not covered by a line on the cost matrix. Subtract the value of this number to each item covered by a line and add it to each item covered by two lines.
4. Repeat step 2.
EXAMPLE:
A race of 400-meter relay includes four different swimmers who swim 100 meters on back, breast, butterfly and freestyle. A coach has 6 very fast swimmers whose times expected in second in individual events are given in Table How should the coach assigned to the relay swimmers to minimize the amount of his time?
APPLICATIONS (where is the problem): When there is a dilemma, on the assignment of a person or service to a response or work, so the settlement of the first approach, and be effective and useful for those in need.
IN TO USE THIS ALGORITHM: This algorithm is used to solve minimization problems, since it is more effective than used to solve the transport problem of the high degree of degeneration that may occur in allocation problems.
* SOME DEFINITIONS number of examples. * These are some of the licks I did my research * http://www.itlalaguna.edu.mx/Academico/Carreras/industrial/invoperaciones1/u5.HTML http: / / www.scribd.com/doc/62765/memmetpp http://www.monografias.com/trabajos27/complejidad-algoritmica/complejidad-algoritmica.shtml
http://www.scribd.com/doc/7046323/EL-METODO-HUNGARO ...
