Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 06.05.2008, 13:31
гость

 
Сообщений: n/a

Задача о назначениях!
Помогите! ! ! С курсовой завал! Нужно решение задачи о назначениях реализованное на Delphi (только Delphi) ! Это может быть венгерский алгоритм или какой-нибудь другой! Пожалуйста, выручите!
  #2  
Старый 06.05.2008, 15:03
гость

 
Сообщений: n/a

У меня есть реализация Венгерского алгоритма на C#, ~120 строк кода. Выложить?
  #3  
Старый 06.05.2008, 15:31
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

С++ (и ссылка на фортран)
венгерский алгоритм Help!!!

>У меня есть реализация Венгерского алгоритма на C#, ~120 строк кода. Выложить?

Думаю, не помешает.
  #4  
Старый 06.05.2008, 15:37
гость

 
Сообщений: n/a

Вот на C#
Код:
using System;

public class OptimalAssignmentSolver {
    /// <summary>
    /// Solves optimal assignment problem using the Kuhn-Munkres
    /// (aka Hungarian) algorithm. Time complexity: O(n^3).
    /// 
    /// References:
    /// http://www.math.uwo.ca/~mdawes/courses/344/kuhn-munkres.pdf
    /// http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/pdf/chapter5.pdf
    /// </summary>
    /// <param name="a">A square matrix.</param>
    /// <returns>
    /// A permutation p of integers 0, 1, ..., n-1, (where
    /// n is the size of matrix a) such that the expression
    ///   a[0, p[0]] + a[1, p[1]] + ... + a[n-1, p[n-1]]
    /// is maximum possible among all such permutations.
    /// </returns>
    public static int[] KuhnMunkres(int[,] a) {
        int N = a.GetLength(0);
        if (N == 0)
            return new int[0];

        int[] lx = new int[N], ly = new int[N];   // labelling function for vertices in first and second partitions
        int[] mx = new int[N], my = new int[N];   // mx[u]=v, my[v]=u <==> u and v are currently matched;  -1 values means 'not matched'
        int[] px = new int[N], py = new int[N];   // predecessor arrays.  used in DFS to reconstruct paths.
        int[] stack = new int[N];

        // invariant: lx[u] + ly[v] >= a[u, v]
        // (implies that any perfect matching in subgraph containing only
        // edges u, v for which lx[u]+ly[v]=a[u,v] is the optimal matching.)

        // compute initial labelling function:  lx[i] = max_j(a[i, j]), ly[j] = 0;
        for (int i = 0; i < N; i++) {
            lx[i] = a[i, 0];
            for (int j = 0; j < N; j++)
                if (a[i, j] > lx[i]) lx[i] = a[i, j];
            ly[i] = 0;

            mx[i] = my[i] = -1;
        }

        for (int size = 0; size < N;) {
            int s;
            for (s = 0; mx[s] != -1; s++);

            // s is an unmatched vertex in the first partition.
            // At the current iteration we will either find an augmenting path
            // starting at s, or we'll extend the equality subgraph so that
            // such a path will exist at the next iteration.

            for (int i = 0; i < N; i++)
                px[i] = py[i] = -1;
            px[s] = s;

            // DFS
            int t = -1;
            stack[0] = s;
            for (int top = 1; top > 0;) {
                int u = stack[--top];
                for (int v = 0; v < N; v++) {
                    if (lx[u] + ly[v] == a[u, v] && py[v] == -1) {
                        if (my[v] == -1) {
                            // we've found an augmenting path
                            t = v;
                            py[t] = u;
                            top = 0;
                            break;
                        }

                        py[v] = u;
                        px[my[v]] = v;
                        stack[top++] = my[v];
                    }
                }
            }

            if (t != -1) {
                // augment along the found path
                while (true) {
                    int u = py[t];
                    mx[u] = t;
                    my[t] = u;
                    if (u == s) break;
                    t = px[u];
                }
                ++size;
            } else {
                // No augmenting path exists from s in the current equality graph,
                // Modify labelling function a bit...

                int delta = int.MaxValue;
                for (int u = 0; u < N; u++) {
                    if (px[u] == -1) continue;
                    for (int v = 0; v < N; v++) {
                        if (py[v] != -1) continue;
                        int z = lx[u] + ly[v] - a[u, v];
                        if (z < delta)
                            delta = z;
                    }
                }

                for (int i = 0; i < N; i++) {
                    if (px[i] != -1) lx[i] -= delta;
                    if (py[i] != -1) ly[i] += delta;
                }
            }
        }

        // Verify optimality
        bool correct = true;
        for (int u = 0; u < N; u++) {
            for (int v = 0; v < N; v++) {
                correct &= (lx[u] + ly[v] >= a[u, v]);
                if (mx[u] == v)
                    correct &= (lx[u] + ly[v] == a[u, v]);

                if (!correct) {
                    throw new Exception(
                        "*** Internal error: optimality conditions are not satisfied ***\n" +
                        "Most probably an overflow occurred");
                }
            }
        }

        return mx;
    }
}
  #5  
Старый 26.03.2010, 13:44
гость

 
Сообщений: n/a

Так ни укого нет готовой реализации этого метода на Delphi?
Нормального, рабочего варианта?
  #6  
Старый 26.03.2010, 14:45
гость

 
Сообщений: n/a

а чё тебе слабо перевести с c# на свой делфи?
  #7  
Старый 09.12.2010, 16:33
гость001

 
Сообщений: n/a

слабо! закиньте кто-нить пожалста!!!
  #8  
Старый 09.12.2010, 22:42
гостъ

 
Сообщений: n/a

не закинем. сам переводи
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра