SHARE
TWEET

Untitled

a guest Dec 9th, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. C = [1, 1, 1, 1, 1
  2. 1, 5, 5, 6, 3
  3. 1, 4, 5, 7, 2
  4. 1, 7, 4, 2, 3
  5. 1, 9, 2, 9, 5];
  6.  
  7. clc;
  8. ncols = size(C,1);
  9. nrows = size(C,2);
  10.  
  11. if ncols ~= nrows
  12.     fprintf("Матрица должна быть квадратной\n");
  13.     return;
  14. end
  15.  
  16. find_max = false;
  17. cost = C;
  18. stars = [];
  19. dots = [];
  20. plus_rows = [];
  21. plus_cols = [];
  22.  
  23. iter_num = 1;
  24.  
  25.  
  26. if find_max
  27.     max_cost = max(max(cost));
  28.     temp = max_cost - cost;
  29.     cost = temp;
  30.    
  31.     fprintf(' (Max - Cij) \n');
  32.     fprintf('  Матрица стоимостей после изменения задачи на задачу максимизации:\n');
  33.     print_matrix(cost);
  34.     fprintf('________________________\n\n');
  35. else
  36.     fprintf('Заданная матрица стоимостей :\n');
  37.     print_matrix(cost);
  38.     fprintf('________________________\n\n');
  39. end
  40.  
  41.  
  42. fprintf('Минимизированная матрица: \n')
  43. cost = minimize_matrix(cost);
  44. print_matrix(cost)
  45.  
  46. for i = 1:ncols
  47.     for j = 1:nrows
  48.         if cost(i,j) == 0
  49.             if size(stars) ~= 0
  50.                 if  not(ismember(j,stars(:,2)))
  51.                     stars = [stars; [i,j]];
  52.                     break;
  53.                 end              
  54.             else
  55.                 stars = [stars; [i,j]];
  56.                 break;                
  57.             end          
  58.         end
  59.     end
  60. end
  61.  
  62. while size(stars, 1) ~= ncols
  63.    
  64.     plus_cols = stars(:,2);
  65.     if size(plus_rows,1) == 0
  66.         plus_rows = [];
  67.     else
  68.         plus_rows = dots(:,1);
  69.     end
  70.    
  71.    
  72.     fprintf(' Итерация %d.\n', iter_num);
  73.     fprintf(' Матрица стоимостей с выделенными элементами:\n');
  74.     fprintf(' k = %d\n', size(stars,1));
  75.     print_pluses(cost, plus_cols);
  76.     print_stars(cost,stars,dots,plus_rows);
  77.     fprintf('________________________\n\n');
  78.    
  79.    
  80.    
  81.     dots = [];
  82.    
  83.     [flag, i, j] = zero_in_nonpluses(cost, plus_cols, plus_rows);
  84.  
  85.     while 1 == 1
  86.         if flag
  87.             dots = [dots; [i,j]];
  88.             [retval,colnum] = two_zeros_one_line(stars, i, j);
  89.             if retval          
  90.                 plus_rows = [plus_rows;i];
  91.                 plus_cols(plus_cols == colnum) = [];
  92.                
  93.                 fprintf(' Итерация %d.\n', iter_num);
  94.                 fprintf(" Матрица стоимостей после добавления 0':\n");
  95.                 print_pluses(cost, plus_cols);
  96.                 print_stars(cost,stars, dots, plus_rows);
  97.                 fprintf('________________________\n\n');
  98.             else
  99.                 % l_chain
  100.                
  101.                 fprintf(' Итерация %d.\n', iter_num);
  102.                 fprintf(' Матрица стоимостей до построения L-цепочки:\n');
  103.                 print_pluses(cost, plus_cols);
  104.                 print_stars(cost,stars, dots, plus_rows);
  105.                 fprintf('________________________\n\n');
  106.                
  107.                
  108.                 chain = L_chain(stars, dots);
  109.                 nchain = size(chain,1);
  110.  
  111.                 for i = 1:nchain
  112.                     [la, lb] = ismember(chain(i,:),stars, 'rows');
  113.                     if la
  114.                         stars(lb,:) = [];
  115.                     else
  116.                         stars = [stars;chain(i,:)];
  117.                     end                
  118.                 end
  119.                 [flag, i, j] = zero_in_nonpluses(cost, plus_cols, plus_rows);
  120.                 dots = [];
  121.                 plus_cols = [];
  122.                 plus_rows = [];
  123.                
  124.                 fprintf(' Итерация %d.\n', iter_num);
  125.                 fprintf(' L-цепочка:\n');
  126.                 print_l_chain(chain);
  127.                 fprintf('\n Матрица стоимостей после построения L-цепочки:\n');
  128.                 print_pluses(cost, plus_cols);
  129.                 print_stars(cost,stars, dots, plus_rows);
  130.                 fprintf('________________________\n\n');
  131.                 break;
  132.             end
  133.            
  134.             [flag, i, j] = zero_in_nonpluses(cost, plus_cols, plus_rows);                
  135.         else
  136.             cost = manipulate(cost, plus_cols, plus_rows);
  137.            
  138.             fprintf(' Итерация %d.\n', iter_num);
  139.             fprintf('\n После преобразований:\n');
  140.             print_pluses(cost, plus_cols);
  141.             print_stars(cost,stars, dots, plus_rows);
  142.             fprintf('________________________\n\n');
  143.            
  144.             [flag, i, j] = zero_in_nonpluses(cost, plus_cols, plus_rows);
  145.         end
  146.     end
  147.     iter_num = iter_num + 1;
  148. end
  149.  
  150. fprintf(' Матрица стоимостей с выделеннымми элементами:\n');
  151. fprintf(' k = %d\n', size(stars,1));
  152. print_pluses(cost, plus_cols);
  153. print_stars(cost,stars,dots,plus_rows);
  154. fprintf('________________________\n\n');
  155.  
  156. print_opt(cost, C, stars);
  157.  
  158.  
  159. function [new_mat] = minimize_matrix(mat)
  160.     new_mat = minimize_columns(minimize_columns(mat).').';
  161. end
  162.  
  163. function [new_mat] = minimize_columns(mat)
  164.     new_mat = mat;
  165.     [rows_count, columns_count] = size(new_mat);
  166.     min_column_elements = min(new_mat);
  167.    
  168.     for column_index = 1:columns_count
  169.         el = min_column_elements(column_index);
  170.         for row_index = 1:rows_count
  171.             new_mat(row_index, column_index) = new_mat(row_index, column_index) - el;
  172.         end
  173.     end
  174. end
  175.  
  176. function print_matrix(mat)
  177.       for i = 1:size(mat,1)
  178.         for j = 1:size(mat,2)
  179.             fprintf('%d  ',mat(i,j));                
  180.         end
  181.         fprintf('\n');
  182.       end
  183.      
  184. end
  185.        
  186. function print_stars(cost, stars, dots, plus_rows)    
  187.     for i = 1:size(cost,1)
  188.         for j = 1:size(cost,2)
  189.             if size(dots,2) > 0
  190.                 if ismember([i,j],dots, 'rows')
  191.                     fprintf("%d' ", cost(i,j))
  192.                     continue
  193.                 end
  194.             end
  195.             if ismember([i,j],stars, 'rows')
  196.                 fprintf('%d* ', cost(i,j))
  197.             else
  198.                 fprintf('%d  ',cost(i,j));                
  199.             end
  200.         end
  201.         if ismember(i,plus_rows)
  202.             fprintf(' +\n');
  203.         else
  204.             fprintf('\n');
  205.         end        
  206.     end    
  207. end
  208.  
  209. function print_opt(cost, C, stars)
  210.    
  211.     fprintf('\n X_opt = \n');
  212.     y = 0;  
  213.    
  214.     for i = 1:size(cost,1)
  215.         for j = 1:size(cost,2)            
  216.             if cost(i,j) == 0
  217.                 if ismember([i,j],stars, 'rows')
  218.                     y = y + C(i,j);                
  219.                     fprintf("%d  ", 1)
  220.                 else
  221.                     fprintf("%d  ", 0)
  222.                 end
  223.             else
  224.                 fprintf("%d  ", 0)
  225.             end
  226.         end
  227.         fprintf('\n');
  228.        
  229.     end
  230.     fprintf("\n f_opt = %d\n", y)
  231. end
  232.  
  233. function print_pluses(cost, plus_cols)
  234.     for j = 1:size(cost,2)
  235.         if ismember(j, plus_cols)
  236.             fprintf("+  ");
  237.         else
  238.             fprintf("   ");            
  239.         end
  240.     end
  241.     fprintf("\n");
  242. end
  243.  
  244. function chain = L_chain(stars, dots)
  245.     chain = [];
  246.     ndots = size(dots,1);
  247.     nstars = size(stars,1);
  248.  
  249.     cur_point = dots(size(dots,1),:);
  250.     chain = [chain;cur_point];
  251.     flag = 0; % 0 - search nearest by col, 1 - search nearest by row
  252.     end_flag = 1;
  253.     while end_flag
  254.         if flag == 0
  255.             for i = 1:nstars
  256.                 point = stars(i,:);
  257.                 if cur_point(2) == point(2)
  258.                     chain = [chain;point];
  259.                     cur_point = point;
  260.                     flag = 1;
  261.                 end
  262.             end
  263.             if flag == 0
  264.                 end_flag = 0;
  265.             end
  266.         else
  267.             for i = 1:ndots
  268.                 point = dots(i,:);
  269.                 if cur_point(1) == point(1)
  270.                     chain = [chain;point];
  271.                     cur_point = point;
  272.                     flag = 0;
  273.                 end
  274.             end            
  275.         end        
  276.     end
  277.  
  278.     return;
  279. end
  280.  
  281. function [flag,row,col] = zero_in_nonpluses(cost, plus_cols, plus_rows)
  282.     flag = 0;
  283.     for i = 1:size(cost,1)
  284.         for j = 1:size(cost,2)
  285.             if cost(i,j) == 0 && ~ismember(j, plus_cols) && ~ismember(i, plus_rows)
  286.                 flag = 1;
  287.                 row = i;
  288.                 col = j;
  289.                 return;
  290.             end
  291.         end
  292.     end
  293.     row = -1;
  294.     col = -1;
  295.     return;
  296. end
  297.  
  298. function cost_matrix = manipulate(cost, plus_cols, plus_rows)
  299.     %find min in unemphasized...
  300.     temp = cost;
  301.     min_elem = min_nonplus(cost, plus_cols, plus_rows);
  302.     fprintf('Матрица стоимостей после вычитания минимального остаточного элемента из каждого не вычеркнутого столбца\n');
  303.    
  304.     for i = 1:size(cost,1)
  305.         for j = 1:size(cost,2)
  306.             if ~ismember(j,plus_cols)
  307.                 temp(i,j) = temp(i,j) - min_elem;
  308.             end
  309.             fprintf('%3d ', temp(i,j));
  310.         end
  311.         fprintf('\n');
  312.     end
  313.    
  314.     fprintf('\n');
  315.     fprintf('Матрица стоимостей после добавления минимального элемента к каждой вычеркнутой строке\n');
  316.    
  317.     for i = 1:size(cost,1)
  318.         for j = 1:size(cost,2)
  319.             if ismember(i,plus_rows)
  320.                 temp(i,j) = temp(i,j) + min_elem;
  321.             end
  322.             fprintf('%3d ', temp(i,j));
  323.         end
  324.         fprintf('\n');
  325.     end
  326.     fprintf('\n');
  327.    
  328.     cost_matrix = temp;
  329. end
  330.  
  331. function min_value = min_nonplus(cost, plus_cols, plus_rows)
  332.     min_elem = max(max(cost));
  333.     for i = 1:size(cost,1)
  334.         for j = 1:size(cost,2)
  335.             if cost(i,j) < min_elem && ~ismember(i,plus_rows) && ~ismember(j, plus_cols)
  336.                 min_elem = cost(i,j);
  337.             end
  338.         end
  339.     end
  340.     min_value = min_elem;
  341.     return;
  342. end
  343.  
  344. function [retval,colnum] = two_zeros_one_line(stars, i, j)
  345.     retval = 0;
  346.     rownum = -1;
  347.     colnum = -1;
  348.    
  349.     for k = 1:size(stars,1)
  350.         if stars(k) == i
  351.             star = stars(k,:);
  352.             retval = 1;
  353.             rownum = star(1);
  354.             colnum = star(2);
  355.             return;
  356.         end
  357.     end
  358.    
  359. end
  360.  
  361. function print_l_chain(chain)
  362.     fprintf(" (%d,%d)", chain(1,1), chain(1,2));
  363.     for i = 2:size(chain,1)
  364.         fprintf("->(%d,%d)", chain(i,1), chain(i,2));        
  365.     end
  366. end
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top