Дана квадратная матрица 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]) - минимально
roboforum.ru
Технический форум по робототехнике.
Задачка
Re: Задачка
какой вид решения приемлем ? )
Re: Задачка
Решения, требующие порядка n! итераций (тупой перебор) неприемлемы
Re: Задачка
ГА?
Re: Задачка
вам сюда это надо задать
http://www.sciteclibrary.ru/cgi-bin/yabb2/YaBB.pl?board=golovolomki
http://www.sciteclibrary.ru/cgi-bin/yabb2/YaBB.pl?board=golovolomki
Re: Задачка
мммм, а если найти n наименьший элементов матрицы А, и по их номерам заполнить В...
с ГА думаю я бредил )))
с ГА думаю я бредил )))
Re: Задачка
ГугуDuhas писал(а):ГА?
А как оценить время нахождения решения?Michael_K писал(а):вам сюда это надо задать
Решение-то я найду в любом случае. Здесь как-то ... поуютнее, что ли...
Добавлено спустя 53 секунды:
Duhas писал(а):с ГА думаю я бредил )))
Может быть и нет
Re: Задачка
дык ваиант с примерно n^3 обращений к матрице не катит?
Re: Задачка
Вполне
Re: Задачка
ну дык а в чем проблема то ?
ищем n наименьших чисел в матрице А... то займет если быть точнее (n^2 - n)*n обращений... и прям в функции поиска пишем 1-цы оп найденным номерам в B... как я понимаю условие - минимальность суммы поэлементных произведений?
в В все или 0 или 1.. то по идее такой суммы = равен сумме n меньших элементов А...
ищем n наименьших чисел в матрице А... то займет если быть точнее (n^2 - n)*n обращений... и прям в функции поиска пишем 1-цы оп найденным номерам в B... как я понимаю условие - минимальность суммы поэлементных произведений?
в В все или 0 или 1.. то по идее такой суммы = равен сумме n меньших элементов А...
Re: Задачка
ищем n наименьших чисел в матрице А
Что, если они все оказываются в одном столбце(строке)?
Добавлено спустя 3 минуты 30 секунд:
Duhas писал(а):в В все или 0 или 1
Это не единственное условие!
3. В содержит ровно 1 единичный элемент в каждой строке и в каждом столбце
Re: Задачка
blindman писал(а):Дана квадратная матрица
Для чего это применяется.
Re: Задачка
Какая разница? От этого зависит решение? Если условие неоднозначно/непонятно - пишите, уточню
Re: Задачка
Это просто вопрос вызваный любопытством.
Re: Задачка
Изначально это задача по программированию - ничего более.