Hungarian Algorithm (Венгерский алгоритм)

Реализация венгерского алгоритма для решения задачи о назначениях на C++.

📋 Описание

Венгерский алгоритм (также известный как алгоритм Куна-Манкреса) используется для решения задачи о назначениях - нахождения оптимального способа назначения работников на задачи при минимальных затратах.

🏗️ Структура проекта

Основные классы:

• Matrix - базовый класс для работы с квадратными матрицами

  • Поддержка операций set/get/addToIndex
  • Получение строк и столбцов
  • Операторы сравнения и вывода
  • Полная валидация границ

• LineMatrix - матрица с отмеченными строками и столбцами

  • Маркировка линий для покрытия нулей
  • Подсчёт отмеченных линий
  • Массовые операции с линиями

• Analyzer - аналитические функции для матриц

  • Проверка оптимальности
  • Подсчёт нулей
  • Поиск минимумов и максимумов
  • Проверка свойств матрицы

• Reducer - редукция матрицы (первый шаг алгоритма)

  • Вычитание минимума из строк
  • Вычитание минимума из столбцов
  • Проверка редуцированности

• Liner - покрытие нулей линиями

  • Простой алгоритм покрытия
  • Жадный алгоритм
  • Проверка покрытия всех нулей

🛠️ Требования

• C++17 или выше
• CMake 3.14+
• MinGW (для Windows) или GCC/Clang (для Linux/macOS)
• Google Test (подгружается автоматически через CMake)

📦 Сборка проекта

Windows (MinGW):

# Создание build директории
cmake -S . -B build -G "MinGW Makefiles"

# Сборка
cmake --build build

# Запуск тестов
.\build\tests\HungarianTests.exe

Linux/macOS:

# Создание build директории
cmake -S . -B build

# Сборка
cmake --build build

# Запуск тестов
./build/tests/HungarianTests

✅ Тестирование

Проект включает 147 unit-тестов с использованием Google Test:

• Matrix: 32 теста
• LineMatrix: 39 тестов
• Analyzer: 31 тест
• Liner: 25 тестов
• Reducer: 20 тестов

Запуск тестов:

# Все тесты
.\build\tests\HungarianTests.exe

# Конкретный набор тестов
.\build\tests\HungarianTests.exe --gtest_filter=Matrix.*

# С подробным выводом
.\build\tests\HungarianTests.exe --gtest_verbose

📊 Примеры использования

Создание и редукция матрицы:

#include "Matrix.h"
#include "Reducer.h"

// Создание матрицы из данных
std::vector<std::vector<int>> data = {
    {9, 2, 7, 8},
    {6, 4, 3, 7},
    {5, 8, 1, 8},
    {7, 6, 9, 4}
};
Matrix matrix(data);

// Редукция матрицы
Reducer::reduce(matrix);

// Вывод результата
std::cout << matrix << std::endl;

Работа с LineMatrix:

#include "LineMatrix.h"
#include "Liner.h"

Matrix matrix(data);
LineMatrix lineMatrix(matrix);

// Покрытие нулей линиями
Liner::fillMatrixGreedy(lineMatrix);

// Проверка покрытия
if (Liner::areAllZerosCovered(lineMatrix)) {
    std::cout << "Все нули покрыты!" << std::endl;
    std::cout << "Использовано линий: " 
              << lineMatrix.countTotalMarkedLines() << std::endl;
}

Анализ матрицы:

#include "Analyzer.h"

Matrix matrix(data);

// Проверки
if (Analyzer::isOptimal(matrix)) {
    std::cout << "Матрица оптимальна" << std::endl;
}

std::cout << "Минимум: " << Analyzer::findMinInMatrix(matrix) << std::endl;
std::cout << "Максимум: " << Analyzer::findMaxInMatrix(matrix) << std::endl;
std::cout << "Нулей: " << Analyzer::countTotalZeros(matrix) << std::endl;

🎯 Архитектура

Проект использует модульную архитектуру с чёткими зависимостями:

Matrix (базовый)
  ↓ PUBLIC
  ├─→ Analyzer
  ├─→ LineMatrix ─→ Liner
  └─→ Reducer

• PUBLIC линковка используется когда класс виден в публичном API
• PRIVATE линковка используется для внутренних зависимостей

📝 Стиль кода

• Современный C++17
• RAII принципы
• Константная корректность
• Явная валидация входных данных
• Осмысленные имена переменных и функций

🐛 Исправленные баги

В процессе разработки были найдены и исправлены:

1. Analyzer::isOptimal() - неправильная инициализация переменной
2. Liner::fillMatrix() - бесконечный цикл из-за опечатки в условии
3. Liner::fillMatrix() - изменения не применялись к объекту

🚀 Дальнейшее развитие

• Реализация полного венгерского алгоритма
• Поддержка прямоугольных матриц
• Оптимизация производительности
• Параллельная обработка больших матриц
• Визуализация шагов алгоритма

📄 Лицензия

Этот проект создан в образовательных целях.

👤 Автор

Nikolay

🙏 Благодарности

• Google Test framework
• CMake build system