roboforum.ru

Дана квадратная матрица A размером n x n. Найти матрицу B размером n x n, такую, что:
1. Все элементы В - 0 или 1
2. В[i][i] = 0 для любого i
3. В содержит ровно 1 единичный элемент в каждой строке и в каждом столбце
4. SUM(i=0,n-1;j=0,n-1)(A[i,j]*B[i,j]) - минимально

какой вид решения приемлем ? )

Решения, требующие порядка n! итераций (тупой перебор) неприемлемы

ГА?

вам сюда это надо задать
http://www.sciteclibrary.ru/cgi-bin/yabb2/YaBB.pl?board=golovolomki

мммм, а если найти n наименьший элементов матрицы А, и по их номерам заполнить В...

с ГА думаю я бредил )))

Duhas писал(а):ГА?

Гугу А как оценить время нахождения решения?

Michael_K писал(а):вам сюда это надо задать

Решение-то я найду в любом случае. Здесь как-то ... поуютнее, что ли...

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

Duhas писал(а):с ГА думаю я бредил )))

Может быть и нет

дык ваиант с примерно n^3 обращений к матрице не катит?

Вполне

ну дык а в чем проблема то ?

ищем n наименьших чисел в матрице А... то займет если быть точнее (n^2 - n)*n обращений... и прям в функции поиска пишем 1-цы оп найденным номерам в B... как я понимаю условие - минимальность суммы поэлементных произведений?

в В все или 0 или 1.. то по идее такой суммы = равен сумме n меньших элементов А...

ищем n наименьших чисел в матрице А

Что, если они все оказываются в одном столбце(строке)?

Добавлено спустя 3 минуты 30 секунд:

Duhas писал(а):в В все или 0 или 1

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

blindman писал(а):Дана квадратная матрица

Для чего это применяется.

Какая разница? От этого зависит решение? Если условие неоднозначно/непонятно - пишите, уточню

Это просто вопрос вызваный любопытством.

Изначально это задача по программированию - ничего более.