funcprot(0);
function []=display_all(arr_prices, arr_markers, arr_zeroes)
disp("Текущее состояние матрицы стоимостей:");
disp(arr_prices);
disp("Текущее состояние матрицы :");
disp(arr_markers);
disp("Current status of zeroes:");
disp(arr_zeroes);
endfunction
function [result]=minimize_rows(arr)
for i = 1:size(arr,1)
minimum = min(arr(i,:));
arr(i,:) = arr(i,:)-minimum
end
result = arr;
disp("Результат минимизации строк:");
disp(result);
endfunction
function [result]=minimize_columns(arr)
for i = 1:size(arr,2)
minimum = min(arr(:,i));
arr(:, i) = arr(:, i)-minimum
end
result = arr;
disp("Результат минимизации столбцов:");
disp(result);
endfunction
function [result]=combined_minimize(arr)
arr = minimize_rows(arr);
arr = minimize_columns(arr);
result = arr;
endfunction
//-----------------------------------
function [result_markers, result_zeroes]=scan_columns(arr_prices, arr_markers, arr_zeroes)
result_zeroes=arr_zeroes;
result_markers=arr_markers;
for row = 1:size(arr_prices, 1)
zeroes_in_row = find(arr_prices(row, :) == 0);
unmarked_zeroes_in_row = find(result_markers(row, zeroes_in_row) == 0);
if length(unmarked_zeroes_in_row) == 1 then
zero_index = zeroes_in_row(unmarked_zeroes_in_row(1));
if arr_markers(row, zero_index) == 0 then
result_zeroes(size(result_zeroes, 1) + 1, :) = [row, zero_index];
result_markers(:, zero_index) = result_markers(:, zero_index) +1;
end
end
end
endfunction
function [result_markers, result_zeroes]=scan_rows(arr_prices, arr_markers, arr_zeroes)
result_zeroes=arr_zeroes;
result_markers=arr_markers;
for column = 1:size(arr_prices, 2)
zeroes_in_column = find(arr_prices(:,column) == 0);
unmarked_zeroes_in_col = find(result_markers( zeroes_in_column, column) == 0);
if length(unmarked_zeroes_in_col) == 1 then
zero_index = zeroes_in_column( unmarked_zeroes_in_col(1));
if result_markers(zero_index, column) == 0 then
result_zeroes(size(result_zeroes, 1) + 1, :) = [zero_index, column];
result_markers(zero_index, :) = result_markers(zero_index, :) + 1;
end
end
end
endfunction
function [result_markers, result_zeroes]=combined_scan(arr_prices)
result_markers = zeros(size(arr_prices, 1), size(arr_prices,2));
result_zeroes = [];
[result_markers, result_zeroes] = scan_columns(arr_prices, result_markers, result_zeroes);
[result_markers, result_zeroes] = scan_rows(arr_prices, result_markers, result_zeroes);
for row = 1:size(arr_prices, 1)
zeroes_in_row = find(arr_prices(row, :) == 0);
unmarked_zeroes_in_row = find(result_markers(row, zeroes_in_row) == 0);
if length(unmarked_zeroes_in_row) > 0 then
zero_index = zeroes_in_row(unmarked_zeroes_in_row(1));
if result_markers(row, zero_index) == 0 then
result_zeroes(size(result_zeroes, 1) + 1, :) = [row, zero_index];
result_markers(:, zero_index) = result_markers(:, zero_index) +1;
end
end
end
disp("Результат зачеркивания строк и столбцов:");
disp(result_markers);
endfunction
//-----------------------------------
function [result_prices]=compensate(arr_markers, arr_prices)
intersections = find(arr_markers == 2);
free_spaces = find(arr_markers == 0);
minimum = min(arr_prices(free_spaces));
arr_prices(intersections) = arr_prices(intersections) + minimum;
arr_prices(free_spaces) = arr_prices(free_spaces) - minimum;
result_prices=arr_prices;
disp("Результат компенсации значений:");
disp(result_prices);
endfunction
//-----------------------------------
function [result]=check_for_solved(arr_zeroes, arr_prices)
printf("Количество вычеркнутых нулей: %d\n", size(arr_zeroes,1));
if size(arr_zeroes,1)==size(arr_prices,1) then
disp("Решение найдено.");
result = 1;
else result = 0;
disp("На данной итерации решение не найдено.");
end
endfunction
function []=display_answer(arr)
disp("Финальная матрица:");
arr = gsort(arr, 'lr', 'i');
disp(arr);
answer_string = msprintf("Работник %d идёт на работу %d\n", arr(:,1), arr(:,2));
x_dialog("Результат работы венгерского метода:",answer_string)
endfunction
//-----------------------------------
function []=solve_destinations(arr_prices, iteration)
iteration = iteration+1;
if iteration~=8 then
printf("\n\nИтерация %d\n", iteration);
markers = zeros(size(arr_prices, 1), size(arr_prices,2));
zeroes = [];
//Первый шаг - минимизация строк и столбцов
arr_prices = combined_minimize(arr_prices);
//Второй шаг - сканирование строк и столбцов
[markers, zeroes] = combined_scan(arr_prices);
//Третий шаг - проверка, решена ли задача
if check_for_solved(zeroes, arr_prices) ==1 then
//Если да, то выводим ответ и завершаем работу функции
display_answer(zeroes);
else
//Иначе компенсируем значения и запускаем новую итерацию
arr_prices = compensate(markers, arr_prices);
disp("Переход к следующей итерации...");
solve_destinations(arr_prices);
end
end
endfunction
//-----------------------------------
answer = x_matrix(['Введите условие задачи о назначениях в формате матрицы NxN'],[18 1 8 13 18 7 9; 11 5 17 1 12 14
5; 6 3 4 1 13 9 3; 1 15 14 8 8 16 2; 20 2 19 2 5 1