roboforum.ru

[blindman]

Дана квадратная матрица 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]) - минимально

[Duhas]

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

[blindman]

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

[Duhas]

ГА?

[Michael_K]

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

[Duhas]

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

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

[blindman]

ГА?

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

вам сюда это надо задать

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

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

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

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

[Duhas]

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

[blindman]

Вполне

[Duhas]

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

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

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

[blindman]

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

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

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

в В все или 0 или 1

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

[avr123.nm.ru]

Дана квадратная матрица

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

[blindman]

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

[avr123.nm.ru]

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

[blindman]

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