8. Если в одной строке с ним есть 0*, то к шагу 9 иначе – к шагу 10
Лабораторная работа №1
Тема: «Венгерский метод решения задачи о назначениях»
Вариант 15
Выполнил: Смирнов А.В. ИУ7-81
Содержательная постановка задачи о назначениях
В распоряжении работодателя имеется n работ и n исполнителей. Стоимость выполнений i-ой работы j-ым исполнителем составляет 
денежных единиц. Требуется распределить работы между исполнителями так, чтобы:
1. Каждый исполнитель выполнял ровно одну работу
2. Общая стоимость выполнения работ была минимальная
Математическая постановка задачи о назначениях
Тогда общая стоимость выполненных работ:
Условие того, что i работу выполняет один сотрудник:
Условие того, что j сотрудник выполняет одну работу:
В результате:
Индивидуальное задание (Вариант 15)
| 10 | 12 | 7 | 11 | 10 |
| 12 | 5 | 12 | 7 | 12 |
| 8 | 6 | 7 | 8 | 13 |
| 8 | 11 | 5 | 9 | 9 |
| 10 | 8 | 9 | 11 | 11 |
Краткое описание венгерского метода
1. Подготовительный этап:
a. Найти минимальный элемент в каждом столбце, вычесть его из всех элементов столбца
b. Найти минимальный элемент в каждой строке, вычесть его из всех элементов строки
2. Отметить * нулевые элементы каждого столбца, если в строке с ними нет элементов 0*
3. К – число 0*
4. Если K < количества работ, то к шагу 5, иначе – к шагу 12
5. Выделить столбцы, в которых есть 0*
6. Если среди невыделенных элементов есть 0, то к шагу 7, иначе – к шагу 11
7. Пометить найденный 0 как 0’
8. Если в одной строке с ним есть 0*, то к шагу 9 иначе – к шагу 10
9. Снять выделение со столбца в котором находится 0* и выделить строку
10. Построить L цепочку. Заменить в ней все 0* на 0’ и наоборот. Снять все выделения. Перейти к шагу 4
11. Найти минимальный элемент среди невыделенных. Вычесть его из невыделенных столбцов и прибавить его к выделенным строкам. Перейти к шагу 6.
12. Решение найдено, вывести результат
Текст программы:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace lab1
{
public partial class Form1 : Form
{
public int [,]C;
public Form1()
{
InitializeComponent();
}
public DataGridView DGrid;
public bool by_step;
public struct Element
{
public int[,] Number;
public bool[,] Stared;
public bool[,] Hatch;
}
public struct Matrix
{
public Element El;
public bool[] MarkedColumn;
public bool[] MarkedString;
}
public class Pos
{
public int row;
public int col;
public bool empty;
public Pos()
{
row = -1;
col = -1;
empty = true;
}
public Pos(int r, int c)
{
row = r;
col = c;
empty = false;
}
public override string ToString()
{
return "Empty: " + empty.ToString() + "\nCol: " + col.ToString() + "\nRow: " + row.ToString();
}
}
public int size = 0;
Matrix TempMatr;
private void button1_Click(object sender, EventArgs e)
{
Clear();
size = int.Parse(textBox1.Text.ToString());
FirstGrd.RowCount = size;
FirstGrd.ColumnCount = size;
C = new int[size, size];
for (int i = 0; i < size; i++)
{
FirstGrd.Columns[i].Width = 30;
}
}
public void Prepearing_max()
{
int max = -1;
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if (TempMatr.El.Number[i, j] > max)
max = TempMatr.El.Number[i, j];
}
}
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
TempMatr.El.Number[i, j] = max - TempMatr.El.Number[i, j];
}
}
}
public void simpleOut()
{
for (int i = 0; i < size; i++)
{
DGrid.Columns[i].Width = 30;
for (int j = 0; j < size; j++)
{
DGrid.Rows[i].Cells[j].Value = TempMatr.El.Number[i, j].ToString();
DGrid.Rows[i].Cells[j].Style.BackColor = System.Drawing.Color.White;
if ((TempMatr.MarkedColumn[j]) || (TempMatr.MarkedString[i]))
DGrid.Rows[i].Cells[j].Style.BackColor = System.Drawing.Color.Yellow;
if (TempMatr.El.Stared[i, j])
DGrid.Rows[i].Cells[j].Value = TempMatr.El.Number[i, j].ToString() + "*";
if (TempMatr.El.Hatch[i, j])
DGrid.Rows[i].Cells[j].Value = TempMatr.El.Number[i, j].ToString() + "'";
}
}
}
public void tempOut(string action)
{
if (by_step)
{
simpleOut();
MessageBox.Show(action,"Отладочный режим");
}
}
//основа
public void Solve()
{
int k = 0;
//В каждом столбце отмечаем * нули такие, что в строке с ним больше нет 0*
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if ((TempMatr.El.Number[j, i] == 0) && (StrWithoutStarredNulls(j)))
{
k++;
TempMatr.El.Stared[j, i] = true;
break;
}
}
}
tempOut("Выбрали начальную комбинацию 0*.\nИх оказалось " + k.ToString());
bool actions = true;
Pos last = new Pos();
while (k < size)
{
if (actions)
{
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if (TempMatr.El.Stared[j, i])
TempMatr.MarkedColumn[i] = true;
}
}
actions = false;
tempOut("Отметили столбы в которых есть 0*");
}
Pos zero = CheckUnselected();
if (!zero.empty)
{
tempOut("Среди невыделенных элементов был 0");
TempMatr.El.Hatch[zero.row, zero.col] = true;
last = new Pos(zero.row, zero.col);
tempOut("Помечаем его");
int checker = CheckLine(zero.row);
if (checker != -1)
{
TempMatr.MarkedColumn[checker] = false;
TempMatr.MarkedString[zero.row] = true;
tempOut("В строке с ним есть 0*. Снимем выделение со столбца, \nв котором находится 0*, выделяем строку");
}
else
{
tempOut("В строке с ним нет 0*. Строим L-цепочку");
Pos[] LChain = new Pos[100];
int LSize = 1;
LChain[0] = new Pos(last.row, last.col);
Pos next = new Pos();
while (true)
{
next = findNext(LChain[LSize -1]);
if (!next.empty)
{
LChain[LSize] = new Pos(next.row, next.col);
LSize++;
}
else
break;
}
for (int i = 0; i < LSize; i++)
{
if (TempMatr.El.Hatch[LChain[i].row, LChain[i].col])
{
TempMatr.El.Stared[LChain[i].row, LChain[i].col] = true;
TempMatr.El.Hatch[LChain[i].row, LChain[i].col] = false;
}
else
{
TempMatr.El.Stared[LChain[i].row, LChain[i].col] = false;
TempMatr.El.Hatch[LChain[i].row, LChain[i].col] = true;
}
}
tempOut("После замены в L цепочке");
for (int i = 0; i < size; i++)
{
TempMatr.MarkedColumn[i] = false;
TempMatr.MarkedString[i] = false;
for (int j = 0; j < size; j++)
{
TempMatr.El.Hatch[i, j] = false;
}
}
if (k == size)
tempOut("Решение найдено");
else
tempOut("Сняли выделение");
k++;
actions = true;
}
}
else
{
tempOut("Среди невыделенных элементов нет 0");
int h = findMin();
for (int i = 0; i < size; i++)
{
if (!TempMatr.MarkedColumn[i])
{
for (int j = 0; j < size; j++)
{
TempMatr.El.Number[j, i] -= h;
}
}
if (TempMatr.MarkedString[i])
{
for (int j = 0; j < size; j++)
{
TempMatr.El.Number[i, j] += h;
}
}
}
tempOut("Минимальный элемент среди невыделенных: " + h.ToString() +
"\nВычли его из невыделенных столбцов и прибавили к выделеным строкам");
}
}
}
public int findMin()
{
int min = -1;
for (int i = 0; i < size; i++)
{
if (!TempMatr.MarkedString[i])
{
for (int j = 0; j < size; j++)
{
if (!TempMatr.MarkedColumn[j])
{
if (min == -1)
min = TempMatr.El.Number[i, j];
if (TempMatr.El.Number[i, j] < min)
min = TempMatr.El.Number[i, j];
}
}
}
}
return min;
}
public Pos findNext(Pos current)
{
if (TempMatr.El.Stared[current.row, current.col])
{
// find '
for (int i = 0; i < size; i++)
{
if (TempMatr.El.Hatch[current.row, i])
return new Pos(current.row, i);
}
}
else
{
// find *
for (int i = 0; i < size; i++)
{
if (TempMatr.El.Stared[i, current.col])
return new Pos(i, current.col);
}
}
return (new Pos());
}
public int CheckLine(int Line)
{
for (int i = 0; i < size; i++)
{
if (TempMatr.El.Stared[Line, i])
return i;
}
return -1;
}
public Pos CheckUnselected()
{
Pos ret = new Pos();
for (int i = 0; i < size; i++)
{
if (!TempMatr.MarkedString[i])
{
for (int j = 0; j < size; j++)
{
if (!TempMatr.MarkedColumn[j])
if (TempMatr.El.Number[i, j] == 0)
{
ret.empty = false;
ret.col = j;
ret.row = i;
return ret;
}
}
}
}
return ret;
}
public bool StrWithoutStarredNulls(int index)
{
for (int i = 0; i < size; i++)
{
if (TempMatr.El.Stared[index, i])
return false;
}
return true;
}
//1. Подготовительный этап
public void Prepearing()
{
int Min;
for (int i = 0; i < size; i++)
{//в каждом столбце вычитаем из всех минимальный
Min = TempMatr.El.Number[0, i];
for (int j = 0; j < size; j++)
{
if (TempMatr.El.Number[j, i] < Min)
Min = TempMatr.El.Number[j, i];
}
for (int j = 0; j < size; j++)
{
TempMatr.El.Number[j, i] = TempMatr.El.Number[j, i] - Min;
}
}
for (int i = 0; i < size; i++)
{//в каждой строке вычитаем из всех минимальный
Min = TempMatr.El.Number[i, 0];
for (int j = 0; j < size; j++)
{
if (TempMatr.El.Number[i, j] < Min)
Min = TempMatr.El.Number[i, j];
}
for (int j = 0; j < size; j++)
{
TempMatr.El.Number[i, j] = TempMatr.El.Number[i, j] - Min;
}
}
}
//Основная функция
private void button2_Click(object sender, EventArgs e)
{
Clear();
by_step = checkBox2.Checked;
TempMatr.El.Number = new int[size, size];
TempMatr.El.Stared = new bool[size, size];
TempMatr.El.Hatch = new bool[size, size];
TempMatr.MarkedColumn = new bool[size];
TempMatr.MarkedString = new bool[size];
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{//Переносим данные с формы во внутренюю матрицу для вычислений
TempMatr.El.Number[i, j] = int.Parse(FirstGrd.Rows[i].Cells[j].Value.ToString());
}
}
DGrid = SecondGrd;
SecondGrd.RowCount = size;
SecondGrd.ColumnCount = size;
//снимаем все выделения с матрицы
for (int i = 0; i < size; i++)
{
TempMatr.MarkedColumn[i] = false;
TempMatr.MarkedString[i] = false;
for (int j = 0; j < size; j++)
{
TempMatr.El.Stared[i, j] = false;
TempMatr.El.Hatch[i, j] = false;
SecondGrd.Rows[i].Cells[j].Style.BackColor = System.Drawing.Color.White;
}
}
//Подготовительный этап
if (IfMinimization.Checked)
Prepearing();
else
Prepearing_max();
tempOut("Подготовительный этап завершен");
Solve();
if (!by_step)
simpleOut();
int total = 0;
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if (TempMatr.El.Stared[i, j])
{
SecondGrd.Rows[i].Cells[j].Style.BackColor = System.Drawing.Color.Yellow;
FirstGrd.Rows[i].Cells[j].Style.BackColor = System.Drawing.Color.Yellow;
total += Convert.ToInt32(FirstGrd.Rows[i].Cells[j].Value);
}
}
}
SumLabel.Text = total.ToString();
FirstGrd.ClearSelection();
SecondGrd.ClearSelection();
}
private void Form1_Load(object sender, EventArgs e)
{
IfMinimization.Checked = true;
}
private void dataGridView1_CellBeginEdit(object sender, DataGridViewCellCancelEventArgs e)
{
Clear();
}
private void Clear()
{
SumLabel.Text = "";
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
FirstGrd.Rows[i].Cells[j].Style.BackColor = System.Drawing.Color.White;
}
}
}
private void fill_dg_with_var15(DataGridView DGrid)
{
DGrid.RowCount = 5;
DGrid.ColumnCount = 5;
size = 5;
C = new int[size, size];
for (int i = 0; i < 5; i++)
{
FirstGrd.Columns[i].Width = 30;
}
DGrid.Rows[0].Cells[0].Value = "10";
DGrid.Rows[0].Cells[1].Value = "12";
DGrid.Rows[0].Cells[2].Value = "7";
DGrid.Rows[0].Cells[3].Value = "11";
DGrid.Rows[0].Cells[4].Value = "10";
DGrid.Rows[1].Cells[0].Value = "12";
DGrid.Rows[1].Cells[1].Value = "5";
DGrid.Rows[1].Cells[2].Value = "12";
DGrid.Rows[1].Cells[3].Value = "7";
DGrid.Rows[1].Cells[4].Value = "12";
DGrid.Rows[2].Cells[0].Value = "8";
DGrid.Rows[2].Cells[1].Value = "6";
DGrid.Rows[2].Cells[2].Value = "7";
DGrid.Rows[2].Cells[3].Value = "8";
DGrid.Rows[2].Cells[4].Value = "13";
DGrid.Rows[3].Cells[0].Value = "8";
DGrid.Rows[3].Cells[1].Value = "11";
DGrid.Rows[3].Cells[2].Value = "5";
DGrid.Rows[3].Cells[3].Value = "9";
DGrid.Rows[3].Cells[4].Value = "9";
DGrid.Rows[4].Cells[0].Value = "10";
DGrid.Rows[4].Cells[1].Value = "8";
DGrid.Rows[4].Cells[2].Value = "9";
DGrid.Rows[4].Cells[3].Value = "11";
DGrid.Rows[4].Cells[4].Value = "11";
}
private void button3_Click(object sender, EventArgs e)
{
Clear();
fill_dg_with_var15(FirstGrd);
}
private void button4_Click(object sender, EventArgs e)
{
simpleOut();
}
}
}
Результаты выполнения программы
