roboforum.ru

Технический форум по робототехнике.


Задачка

Все здесь

Re: Задачка

Сообщение Виталий » 24 дек 2009, 22:04

Код: Выделить всёРазвернуть
if A(i, j) < 0 
    B(i, j) = 1
else
    B(i, j) = 0


Если отрицаельно - включаем в сумму. Если положительно - домножаем на 0. Если я правильно понял условие.
Все новости о моих проектах http://savethebest.ru
Аватара пользователя
Виталий
 
Сообщения: 2114
Зарегистрирован: 08 окт 2004, 16:43
Откуда: St. Petersburg
Skype: quark-bot
ФИО: Клебан Виталий

Re: Задачка

Сообщение =DeaD= » 25 дек 2009, 00:11

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

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

Добавлено спустя 13 минут 7 секунд:
Вторая мысль: можно ликвидировать условие "2. В[i][i] = 0 для любого i", применив первую мысль и выставив по диагонали в матрицу А сумму всех чисел которые там уже есть.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Задачка

Сообщение Michael_K » 25 дек 2009, 00:36

Из гуглевого задачника что-ли?
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Задачка

Сообщение blindman » 25 дек 2009, 07:35

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

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

Добавлено спустя 11 секунд:
Michael_K писал(а):Из гуглевого задачника что-ли?

Нет
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Задачка

Сообщение Duhas » 25 дек 2009, 08:03

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

в принципе мона попробовать на ГА... мб набросаю седня...
«Как сердцу выразить себя? … Мысль изреченная есть ложь!»
В этом мире меня подводит доброта и порядочность...
"двое смотрят в лужу, один видит лужу, другой отраженные в ней звезды"
Аватара пользователя
Duhas
 
Сообщения: 6338
Зарегистрирован: 15 сен 2007, 13:03
Откуда: Красноярск
прог. языки: ASM(МК), C(PC)
ФИО: Гагарский Андрей Александрович

Re: Задачка

Сообщение blindman » 25 дек 2009, 08:30

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

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

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

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Задачка

Сообщение =DeaD= » 25 дек 2009, 09:00

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

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

Это типа есть N дней, в каждый из них идёт N фильмов, а билеты каждый день стоят разные деньги на каждый фильм. (т.е. цена похода на каждый фильм меняется и цены разных фильмов в каждый день могут не совпадать) - надо посмотреть все фильмы потратив минимум денег. В таком виде больше похоже на задачу коммивояжера? :)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Задачка

Сообщение blindman » 25 дек 2009, 12:17

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

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

заменить на

3. В содержит как минимум 1 единичный элемент в каждой строке и в каждом столбце
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Задачка

Сообщение =DeaD= » 25 дек 2009, 12:23

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

Упростить задачу можно наложив какие-то условия на матрицу А, наверное.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Задачка

Сообщение blindman » 25 дек 2009, 12:37

=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
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Задачка

Сообщение =DeaD= » 25 дек 2009, 12:43

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

Ну тогда для затравки очевидная жадная эвристика (пробовать прямо и транспонированно, выбирать лучшее):
1. Бежим по столбцам ищем минимумы и выбираем.
2. Бежим по строкам, если в ней ничего не выбрали, выбираем минимум.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Задачка

Сообщение blindman » 25 дек 2009, 13:34

Может оказаться, что если мы поместили 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])
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Задачка

Сообщение =DeaD= » 25 дек 2009, 13:46

Не, я же не говорю, что это правильное решение, это именно жадная эвристика, дающая не самый плохой результат, и скорее всего можно даже математически обосновать на сколько % это может быть хуже, чем оптимальный результат.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Задачка

Сообщение blindman » 25 дек 2009, 13:50

Нужно точное решение.
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Задачка

Сообщение =DeaD= » 25 дек 2009, 13:50

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

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

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

Т.е. верно ли, что если решение не оптимально, то существует операция класса Х улучшающая решение?
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Пред.След.

Вернуться в Свободное общение

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

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

Mail.ru counter