Венгерский алгоритм (задача о назначениях) - C#

Узнай цену своей работы

Формулировка задачи:

Здравствуйте. Необходимо реализовать венгерский алгоритм. Поиски в интернете ни к чему не привели. Наткнулась на псевдокод Лопатина. Но с векторами никогда не сталкивалась и боюсь, что не освою. Может у кого-то есть более простая реализация этого алгоритма? Буду крайне признательна.

Решение задачи: «Венгерский алгоритм (задача о назначениях)»

textual
Листинг программы
    public partial class Form1 : Form
    {
        List<int> PInt = new List<int>();
        List<int> VInt = new List<int>();
        List<List<int>> VVInt = new List<List<int>>();
        List<List<int>> VPInt = new List<List<int>>();
 
 
        public Form1()
        {
            InitializeComponent();
        }
 
        private void Form1_Load(object sender, EventArgs e)
        {
            int taskCount = 4;
            int emplCount = 4;
 
            VVInt = new List<List<int>>(){new List<int>() {6,15,3,12,4,2},
                                          new List<int>() {14,3,3,7,2,1},
                                          new List<int>() {3,2,8,15,8,12},
                                          new List<int>() {3,14,3,15,11,10},
                                          new List<int>() {3,13,1,9,6,6},
                                          new List<int>() {15,10,3,4,5,10}
            };
 
 
            #region Если на максимум
             List<int> maxStrVals = VVInt.Select(str => str.Max()).ToList();
             for (int i = 0; i < VVInt.Count; i++)
                 for (int j = 0; j < (VVInt.Sum(x => x.Count) / VVInt.Count); j++)
                     VVInt[i][j] = maxStrVals[i] - VVInt[i][j];
            #endregion
 
 
            VVInt = hungarian(VVInt); 
 
 
            foreach (List<int> i in VVInt)
            {
                foreach (int j in i)
                    richTextBox1.Text+=j.ToString() + " \t ";
 
                richTextBox1.Text += "\r\n";
            }
            //MessageBox.Show("");
        }
 
        
        List<List<int>> hungarian(List<List<int>> matrix) {
            try
            {
                // Размеры матрицы
                int height = matrix.Count, width = matrix.Sum(x => x.Count) / height;
 
                // Значения, вычитаемые из строк (u) и столбцов (v)
                // VInt u(height, 0), v(width, 0);
                List<int> u = new List<int>(height);
                List<int> v = new List<int>(width);
 
                for (int a = 0; a < height; a++)
                    u.Add(0);
                for (int a = 0; a < width; a++)
                    v.Add(0);
                
 
                // Индекс помеченной клетки в каждом столбце
                List<int> markIndices = new List<int>(width);
                for (int a = 0; a < width; a++)
                    markIndices.Add(-1);
 
                // Будем добавлять строки матрицы одну за другой
                    int count = 0;
                for (int i = 0; i < height; i++)
                {
                    List<int> links = new List<int>(width)   ;
                    List<int> mins = new List<int>(width)    ;
                    List<int> visited = new List<int>(width) ;
 
                    for (int a = 0; a < width; a++)
                    {
                        links.Add(-1);
                        mins.Add(int.MaxValue);
                        visited.Add(0);
                    }
 
                    // Разрешение коллизий (создание "чередующейся цепочки" из нулевых элементов)
                    int markedI = i, markedJ = -1, j = 0;
                    while (markedI != -1)
                    {
                        // Обновим информацию о минимумах в посещенных строках непосещенных столбцов
                        // Заодно поместим в j индекс непосещенного столбца с самым маленьким из них
                        j = -1;
                        for (int j1 = 0; j1 < width; j1++)
                            if (visited[j1] != 1)
                            {
                                if (matrix[markedI][j1] - u[markedI] - v[j1] < mins[j1])
                                {
                                    mins[j1] = matrix[markedI][j1] - u[markedI] - v[j1];
                                    links[j1] = markedJ;
                                }
                                if (j == -1 || mins[j1] < mins[j])
                                    j = j1;
                            }
 
                        // Теперь нас интересует элемент с индексами (markIndices[links[j]], j)
                        // Произведем манипуляции со строками и столбцами так, чтобы он обнулился
                        int delta = mins[j];
                        for (int j1 = 0; j1 < width; j1++)
                            if (visited[j1] == 1)
                            {
                                u[markIndices[j1]] += delta;
                                v[j1] -= delta;
                            }
                            else
                            {
                                mins[j1] -= delta;
                            }
                        u[i] += delta;
 
                        // Если коллизия не разрешена - перейдем к следующей итерации
                        visited[j] = 1;
                        markedJ = j;
                        markedI = markIndices[j];
                        count++;
                    }
 
                    // Пройдем по найденной чередующейся цепочке клеток, снимем отметки с
                    // отмеченных клеток и поставим отметки на неотмеченные
                    for (; links[j] != -1; j = links[j])
                        markIndices[j] = markIndices[links[j]];
                    markIndices[j] = i;
                }
 
                // Вернем результат в естественной форме
                List<List<int>> result = new List<List<int>>();
                for (int j = 0; j < width; j++)
                    if (markIndices[j] != -1)
                        result.Add(new List<int>() { markIndices[j], j });
                return result;
            }
            catch (Exception ex)
            {
                MessageBox.Show(ex.Message);
                return new List<List<int>>();
            }
           
        }
    }

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

14   голосов , оценка 4.214 из 5
Похожие ответы