- Код: Выделить всё • Развернуть
if A(i, j) < 0
B(i, j) = 1
else
B(i, j) = 0
Если отрицаельно - включаем в сумму. Если положительно - домножаем на 0. Если я правильно понял условие.
roboforum.ru
Технический форум по робототехнике.
Задачка
Re: Задачка
Если отрицаельно - включаем в сумму. Если положительно - домножаем на 0. Если я правильно понял условие.
Re: Задачка
Ну первая мысль - можно считать что в матрице A только положительные числа, если это не так добавим минус наименьшее и еще 1.
Добавлено спустя 23 минуты 17 секунд:
Пока думается, что это NP-полная задача. Думаю дальше.
Добавлено спустя 13 минут 7 секунд:
Вторая мысль: можно ликвидировать условие "2. В[i][i] = 0 для любого i", применив первую мысль и выставив по диагонали в матрицу А сумму всех чисел которые там уже есть.
Добавлено спустя 23 минуты 17 секунд:
Пока думается, что это NP-полная задача. Думаю дальше.
Добавлено спустя 13 минут 7 секунд:
Вторая мысль: можно ликвидировать условие "2. В[i][i] = 0 для любого i", применив первую мысль и выставив по диагонали в матрицу А сумму всех чисел которые там уже есть.
Re: Задачка
Из гуглевого задачника что-ли?
Re: Задачка
=DeaD= писал(а):Вторая мысль: можно ликвидировать условие "2. В[i][i] = 0 для любого i",
С чего это можно? Если было бы можно, я бы это условие не писал. В матрице В элементы на главной диагонали должны быть нулевые
Добавлено спустя 11 секунд:
Michael_K писал(а):Из гуглевого задачника что-ли?
Нет
Re: Задачка
blindman, да я спал уже ) уже лег спать, дошло что про 1 условие забыл )
в принципе мона попробовать на ГА... мб набросаю седня...
в принципе мона попробовать на ГА... мб набросаю седня...
Re: Задачка
=DeaD= писал(а):Вторая мысль: можно ликвидировать условие "2. В[i][i] = 0 для любого i", применив первую мысль и выставив по диагонали в матрицу А сумму всех чисел которые там уже есть.
А, понял! Условие "В[i][i] = 0" выполнится автоматически.
Может быть, переставлять строки и столбцы в матрице А, приведя ее к какому-нибудь удобоваримому виду. Перестановки запоминать, а потом к найденному решению применить эти перестановки в обратном порядке?
Re: Задачка
2blindman: Матрица B это и есть искомая матрица перестановок, такая, что tr(A*B) минимален (tr() - след матрицы), ну с точностью до транспонирования B вроде. Не думаю что вручную генеря перестановки можно сделать что-то более умное, чем просто найти B 
В общем как-то очень от этой задачи NP-полнотой попахивает
Это типа есть N дней, в каждый из них идёт N фильмов, а билеты каждый день стоят разные деньги на каждый фильм. (т.е. цена похода на каждый фильм меняется и цены разных фильмов в каждый день могут не совпадать) - надо посмотреть все фильмы потратив минимум денег. В таком виде больше похоже на задачу коммивояжера?
В общем как-то очень от этой задачи NP-полнотой попахивает
Это типа есть N дней, в каждый из них идёт N фильмов, а билеты каждый день стоят разные деньги на каждый фильм. (т.е. цена похода на каждый фильм меняется и цены разных фильмов в каждый день могут не совпадать) - надо посмотреть все фильмы потратив минимум денег. В таком виде больше похоже на задачу коммивояжера?
Re: Задачка
Может будет проще если условие
3. В содержит ровно 1 единичный элемент в каждой строке и в каждом столбце
заменить на
3. В содержит как минимум 1 единичный элемент в каждой строке и в каждом столбце
3. В содержит ровно 1 единичный элемент в каждой строке и в каждом столбце
заменить на
3. В содержит как минимум 1 единичный элемент в каждой строке и в каждом столбце
Re: Задачка
Ни разу не проще, если в общем виде в случае положительных чисел в матрице А очевидно нет смысла выставлять более 1 единичного элемента.
Упростить задачу можно наложив какие-то условия на матрицу А, наверное.
в случае положительных чисел в матрице А очевидно нет смысла выставлять более 1 единичного элемента.Упростить задачу можно наложив какие-то условия на матрицу А, наверное.
Re: Задачка
=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
Re: Задачка
Опс, и правда, мы же теперь не блокируем
Ну тогда для затравки очевидная жадная эвристика (пробовать прямо и транспонированно, выбирать лучшее):
1. Бежим по столбцам ищем минимумы и выбираем.
2. Бежим по строкам, если в ней ничего не выбрали, выбираем минимум.
Ну тогда для затравки очевидная жадная эвристика (пробовать прямо и транспонированно, выбирать лучшее):
1. Бежим по столбцам ищем минимумы и выбираем.
2. Бежим по строкам, если в ней ничего не выбрали, выбираем минимум.
Re: Задачка
Может оказаться, что если мы поместили 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])
Re: Задачка
Не, я же не говорю, что это правильное решение, это именно жадная эвристика, дающая не самый плохой результат, и скорее всего можно даже математически обосновать на сколько % это может быть хуже, чем оптимальный результат.
Re: Задачка
Нужно точное решение.
Re: Задачка
У меня другая мысль вертится:
Определим класс операций Х как смену между собой столбцов или строк матрицы B.
Интересно существуют ли локальные минимумы искомой функции по специальным операциям класса Х?
Т.е. верно ли, что если решение не оптимально, то существует операция класса Х улучшающая решение?
Определим класс операций Х как смену между собой столбцов или строк матрицы B.
Интересно существуют ли локальные минимумы искомой функции по специальным операциям класса Х?
Т.е. верно ли, что если решение не оптимально, то существует операция класса Х улучшающая решение?