Помогите с алгоритмом!

[Rookie]

Наверняка задача описана в литературе, но пока не встречал. Если кто знает, напишите, пожалуйста.

Есть матрица целых неотрицательных чисел размером n x m, n <= m. Необходимо найти такую комбинацию различных n ячеек матрицы, чтобы:

1) Никакие две ячейки не находились в одной строке или одном столбце
2) Сумма чисел в ячейчках была минимальной.

Наивный алгоритм (выбираем минимальное число по матрице, вычеркиваем эту строку и столбец, повторяем) не работает. Какие есть варианты?

[venco]

Искать по ключевым словам:
Hungarian algorithm, the Munkres assignment algorithm, or the Kuhn-Munkres algorithm
Начать можно здесь: http://en.wikipedia.org/wiki/Hungarian_algorithm

[SVK]

Если в лоб (без особого анализа...)

1) Выбрать минимум в каждой строке.

2) Выбрать максимум из минимумов.

3) Убрать строку и столбец с выбранным элементом - т.е. уменьшить матрицу до (n-1)x(m-1)

4) Повторить п.п. 1-3 для уменьшенной матрицы, пока не дойдет дело до единственной последней строки; из нее просто выбрать минимум.

[venco]

Если в лоб (без особого анализа...)

2 3
0 2

Никакой greedy алгоритм здесь не работает. Обязательно должна быть возможность отката.
Смотрите Munkres/Hungarian алгоритм, ничего лучше мне неизвестно.

[IvanGrozniy]

А вот в другой лоб
Ногами не бить, код я не запускал - писал в блокноте. Написано на C#. Думаю идея будет понятна.

Code: Select all

int MinResult = int.MaxValue;

void RunMe()
{
   
   List<int> myPath;
   List<int> PrevPath = new List<int>();
   
   for (int x = 0; x < n; x++)   //Columns
   {

      myPath = new List<int>();
                                for (int y = 0; y < m; y++)   //Rows
      {
         if(x != y) 
         {
                  myPath.Add SourceMatrix[x][y];
         }
      }   
      if (myPath.Count == m)
      {
         //Got all rows
         if (CompareSumForMin(PrevPath, myPath)
            PrevPath = myPath.Clone();
                                                        
      }
      
   }
   //Here is your path in the matrix with your conditions
   //-------------PrevPath----------------------
}
boolean CompareSumForMin(List<int> left, List<int> right)
{
   if (left.Count == 0) 
                {
                     //Claculate MinValue according 'right' collection
                     return true;   //First step: prev path dosn't exist
   }

   //Check sum left and right. What has minimum sum? If right return true
                //Also assign MinResult to proper value
   ...
}

[venco]

А вот в другой лоб
Ногами не бить, код я не запускал - писал в блокноте. Написано на C#. Думаю идея будет понятна.

Чесно говоря, идея не понятна. Более того, я не вижу результата этой программы.

[IvanGrozniy]

А вот в другой лоб
Ногами не бить, код я не запускал - писал в блокноте. Написано на C#. Думаю идея будет понятна.

Чесно говоря, идея не понятна. Более того, я не вижу результата этой программы.

Хм.
Результат минимальной суммы хранится в перменной MinValue, сами числа из матрицы хранятся в PrevPath после выполнения всех циклов.
Идея заключается в том, что методом перебора выбирать очередной набор элементов сверху вниз матрицы. Затем сравнить с предыдущей выбранным набором элемнтов согласно условий задачи - минимальная сумма. И если условие выполняется запоминаем набор элементов в PrevPath. В конце остается правильный набор элементов.
Хотя нам сами элементы матрицы не нужны, здесь вы правы, нам нужны местоположения. Можно переписать решение:

Code: Select all

int MinResult = int.MaxValue; 

void RunMe() 
{ 
    
   List<Point> myPath; //x - element, y - number of the row where element is located
   List<Point> PrevPath = new List<Point>(); 
    
   for (int x = 0; x < n; x++)   //Columns 
   { 

      myPath = new List<Point>(); 
                                for (int y = 0; y < m; y++)   //Rows 
      { 
         if(x != y) 
         { 
                  myPath.Add new Point(SourceMatrix[x][y], y); 
         } 
      }    
      if (myPath.Count == m) 
      { 
         //Got all rows 
         if (CompareSumForMin(PrevPath, myPath) 
            PrevPath = myPath.Clone(); 
                                                        
      } 
       
   } 
   //Here is your path in the matrix with your conditions 
  for (int x = 0; n; x++)
  {
      System.WriteLine(string.Format("SourceMatrix[{0}, {1}] = {3}", x, PrevPath[x].y, PrevPath[x].y));
} 
boolean CompareSumForMin(List<Point> left, List<Point> right) 
{ 
   if (left.Count == 0) 
                { 
                     //Claculate MinValue according 'right' collection 
                     return true;   //First step: prev path dosn't exist 
   } 

   //Check sum left and right. What has minimum sum? If right return true 
                //Also assign MinResult to proper value 
   ... 
}

Результат выведется для каждой строки матрицы на консоль

[rvd]

тока хотел предложить самое "лобовое" решение - методом перебора всех комбинаций.
неужели опередили?

int imin=0;
int smin = sum(imin);
for(int i=1; i<fact(N); i++)
{
int s = sum(i);
if( s < smin )
{
imin = i;
smin = s;
}
}

ето для квадратной матрицы NxN. fact() понятно что делает, а sum() вычисляет сумму для i-той комбинации, лень писать. для 3x3 комбинации будут 012, 021, 102, 120, 201, 210

[venco]

Результат минимальной суммы хранится в перменной MinValue

Минимальной суммы чего? В вашем коде myPath содержит пары [value, rоw] для m элементов из одного или нескольких соседних столбцов матрицы. Это, между прочим, по условию задачи - недопустимая комбинация элементов. В финальном PrevPath номерa столбцов отсутствуют. Результат вообще не соответствует исходной матрице.

[IvanGrozniy]

Результат минимальной суммы хранится в перменной MinValue

Минимальной суммы чего? В вашем коде myPath содержит пары [value, rоw] для m элементов из одного или нескольких соседних столбцов матрицы. Это, между прочим, по условию задачи - недопустимая комбинация элементов. В финальном PrevPath номерa столбцов отсутствуют. Результат вообще не соответствует исходной матрице.

Минимальная сумма выбранных ячеек

В вашем коде myPath содержит пары [value, rоw] для m элементов из одного или нескольких соседних столбцов матрицы. Это, между прочим, по условию задачи - недопустимая комбинация элементов. В финальном PrevPath номерa столбцов отсутствуют. Результат вообще не соответствует исходной матрице.

Порядковый номер записи в коллекции myPath и в PrevPath и является порядковым номером столбца. Действительно совпадение уже выбранных номеров строк я просмотрел, а столбцы не совпадают из-за цикла по x.

[IvanGrozniy]

...

[IvanGrozniy]

тока хотел предложить самое "лобовое" решение - методом перебора всех комбинаций.
неужели опередили?

int imin=0;
int smin = sum(imin);
for(int i=1; i<fact(N); i++)
{
int s = sum(i);
if( s < smin )
{
imin = i;
smin = s;
}
}

ето для квадратной матрицы NxN. fact() понятно что делает, а sum() вычисляет сумму для i-той комбинации, лень писать. для 3x3 комбинации будут 012, 021, 102, 120, 201, 210

У вас условие не выполняется:
1) Никакие две ячейки не находились в одной строке или одном столбце

[venco]

У вас условие не выполняется:
1) Никакие две ячейки не находились в одной строке или одном столбце

Или я чего-то не понимаю, или всё-таки, в отличие от вашей программы, программа rvd работает правильно, хотя и очень долго.
Сам я, увы, разобраться в вашем коде не могу, т.к. имена переменных очень уж не очевидны. См., например, параметры CheckIntersections().
Так что, проверьте, что ваш код даст для случаев:
1 2 3
2 4 6
3 6 9

1 2
2 4

1 3
3 4

[IvanGrozniy]

1 2 3
2 4 6
3 6 9

Работает, причем очень быстро - смотри картинку. К тому же должно работать и на не квадратных матрицах.
На всех матрицах 2 на 2, тоже работает.
CheckIntersections() - это проверка условия, чтобы строки не повторялись и были уникальными.
Условие (currentRow == (int)MyPath[i].Y) значит, что мы проверяем местоположение каждого элемента в записанную коллекцию - претендента на минимальную сумму. Если столбец currentRow использовался, то мы не можем добавить текущий элемент в формируемую коллекцию.

[IvanGrozniy]

Или я чего-то не понимаю, или всё-таки, в отличие от вашей программы, программа rvd работает правильно, хотя и очень долго.

Так он же сам комбинацию привел:
012, 021, 102, 120, 201, 210
Первая и последняя имеют общий столбец.

[IvanGrozniy]

В моем алгоритме ошибка. Не используйте его!

[rvd]

Или я чего-то не понимаю, или всё-таки, в отличие от вашей программы, программа rvd работает правильно, хотя и очень долго.

Так он же сам комбинацию привел:
012, 021, 102, 120, 201, 210
Первая и последняя имеют общий столбец.

решением является лиш одна комбинация, в которой цифры не повторяются. Например, если минимальной была i = 2 (102), тогда получаем (1-based):
1-й работник выполнит 2-ю работу
2-й работник - 1-ю
3-й работник - 3-ю

[venco]

1 2 3
2 4 6
3 6 9

Работает, причем очень быстро - смотри картинку.

Для этой матрицы минимум - 10:
1 2 3
2 4 6
3 6 9

[Rookie]

Искать по ключевым словам:
Hungarian algorithm, the Munkres assignment algorithm, or the Kuhn-Munkres algorithm
Начать можно здесь: http://en.wikipedia.org/wiki/Hungarian_algorithm

Это именно то, что нужно - спасибо!