Задачка

Виталий

Код:

if A(i, j) < 0 
    B(i, j) = 1 
else
    B(i, j) = 0

Если отрицаельно - включаем в сумму. Если положительно - домножаем на 0. Если я правильно понял условие.

=DeaD=

Ну первая мысль - можно считать что в матрице A только положительные числа, если это не так добавим минус наименьшее и еще 1.

Добавлено спустя 23 минуты 17 секунд:
Пока думается, что это NP-полная задача. Думаю дальше.

Добавлено спустя 13 минут 7 секунд:
Вторая мысль: можно ликвидировать условие "2. В[i][i] = 0 для любого i", применив первую мысль и выставив по диагонали в матрицу А сумму всех чисел которые там уже есть.

Michael_K

Из гуглевого задачника что-ли?

blindman

=DeaD= писал(а):

Вторая мысль: можно ликвидировать условие "2. В[i][i] = 0 для любого i",

С чего это можно? Если было бы можно, я бы это условие не писал. В матрице В элементы на главной диагонали должны быть нулевые

Добавлено спустя 11 секунд:

Michael_K писал(а):

Из гуглевого задачника что-ли?

Нет

Duhas

blindman, да я спал уже ) уже лег спать, дошло что про 1 условие забыл )

в принципе мона попробовать на ГА... мб набросаю седня...

blindman

=DeaD= писал(а):

Вторая мысль: можно ликвидировать условие "2. В[i][i] = 0 для любого i", применив первую мысль и выставив по диагонали в матрицу А сумму всех чисел которые там уже есть.

А, понял! Условие "В[i][i] = 0" выполнится автоматически.

Может быть, переставлять строки и столбцы в матрице А, приведя ее к какому-нибудь удобоваримому виду. Перестановки запоминать, а потом к найденному решению применить эти перестановки в обратном порядке?

=DeaD=

2blindman: Матрица B это и есть искомая матрица перестановок, такая, что tr(A*B) минимален (tr() - след матрицы), ну с точностью до транспонирования B вроде. Не думаю что вручную генеря перестановки можно сделать что-то более умное, чем просто найти B

В общем как-то очень от этой задачи NP-полнотой попахивает

Это типа есть N дней, в каждый из них идёт N фильмов, а билеты каждый день стоят разные деньги на каждый фильм. (т.е. цена похода на каждый фильм меняется и цены разных фильмов в каждый день могут не совпадать) - надо посмотреть все фильмы потратив минимум денег. В таком виде больше похоже на задачу коммивояжера?

blindman

Может будет проще если условие

3. В содержит ровно 1 единичный элемент в каждой строке и в каждом столбце

заменить на

3. В содержит как минимум 1 единичный элемент в каждой строке и в каждом столбце

=DeaD=

Ни разу не проще, если в общем виде

в случае положительных чисел в матрице А очевидно нет смысла выставлять более 1 единичного элемента.

Упростить задачу можно наложив какие-то условия на матрицу А, наверное.

blindman

=DeaD= писал(а):

в случае положительных чисел в матрице А очевидно нет смысла выставлять более 1 единичного элемента.

Неа.

А:

Код:

x   10  1
10  x   1
1   1   x

Есть 2 решения для В, где в каждой строке и каждой колонке ровно одна единица:

Код:

0   1   0         0   0   1    
0   0   1         1   0   0    
1   0   0         0   1   0    

А оптимальным будет такое:

Код:

0   0   1
0   0   1
1   1   0

=DeaD=

Опс, и правда, мы же теперь не блокируем

Ну тогда для затравки очевидная жадная эвристика (пробовать прямо и транспонированно, выбирать лучшее):
1. Бежим по столбцам ищем минимумы и выбираем.
2. Бежим по строкам, если в ней ничего не выбрали, выбираем минимум.

blindman

Может оказаться, что если мы поместили 1 в B[i1,j1] и B[i2,j2], будет выгоднее туда записать нули, а 1 только в B[i1,j2] или в B[i2,j1] (если A[i1,j1]+A[i2,j2] < A[i1,j2] или A[i1,j1]+A[i2,j2] < A[i2,j1])

=DeaD=

Не, я же не говорю, что это правильное решение, это именно жадная эвристика, дающая не самый плохой результат, и скорее всего можно даже математически обосновать на сколько % это может быть хуже, чем оптимальный результат.

blindman

Нужно точное решение.

=DeaD=

У меня другая мысль вертится:

Определим класс операций Х как смену между собой столбцов или строк матрицы B.

Интересно существуют ли локальные минимумы искомой функции по специальным операциям класса Х?

Т.е. верно ли, что если решение не оптимально, то существует операция класса Х улучшающая решение?

roboforum.ru

Задачка

Кто сейчас на конференции