Венгерский алгоритм (задача о назначениях) - 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>>(); } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д