roboforum.ru

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


Задачка

Все здесь

Re: Задачка

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

Улучшит - вполне возможно. Но в общем случае такие операции не гарантируют нахождение оптимального решения. Оптимальное может быть найдено только если перед тем как применять эти операции матрица B будет содержать ровно столько единиц, сколько их в оптимальном решении.
Проект [[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: Задачка

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

А разве число единиц в матрице B не всегдаа будет равно n?
Грубо коворя, располагаем единицы в B по второй диагонали (для четного n)
и перставляем...
Только вот в общем случае сложность все равно дикая, а оптимальность... не уверен.
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Задачка

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

blindman писал(а):Улучшит - вполне возможно. Но в общем случае такие операции не гарантируют нахождение оптимального решения. Оптимальное может быть найдено только если перед тем как применять эти операции матрица B будет содержать ровно столько единиц, сколько их в оптимальном решении.

Ну я писал про исходную задачу.

Добавлено спустя 58 секунд:
Переставляем - это решение "в лоб", сложность n!

Его можно так же "в лоб" оптимизировать, сделав оценку сначала жадным алгоритмом и потом применив метод ветвей и границ.

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

Re: Задачка

Сообщение Michael_K » 25 дек 2009, 14:20

Типа, находим пару, у которой a(x1y1)+a(x2y2)-a(x1y2)-a(x2y1) минимально
и переставляем, проверив условие про главную диагональ.
поиск пропорционален n2... Скорость схождения не могу оценить.
Или нет?
Последний раз редактировалось Michael_K 25 дек 2009, 15:01, всего редактировалось 1 раз.
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Задачка

Сообщение blindman » 25 дек 2009, 14:22

Michael_K писал(а):А разве число единиц в матрице B не всегдаа будет равно n?

Нет, не всегда. Я уточнил условие - не "ровно 1 единичный элемент в каждой строке/столбце", а "как минимум 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, 14:31

2Michael_K: Да, именно это. Скорость схождения пока тоже не берусь оценивать, но всё равно Андрей уже поменял уже условия задачи :)

Добавлено спустя 5 минут 30 секунд:
Я думаю можно в текущей формулировке попробовать дин-прог применить и чуть обобщив задачу.

Убрать только надо моим методом условие про главную диагональ (поставив в неё в матрице А числа равные сумме 1 и всех положительных значений исходной матрицы А).

И попытаться перейти от матрицы A'[n, i] к матрице A''[n,i+1], где i от 1 до n-1.

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

Re: Задачка

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

Может так: расставляем единицы так, чтобы было по одной в каждой строке и колонке. Потом меняем матрицу с помощью 3 операций:

1. берем единичный элемент, и рассматриваем возможность его "деления" - вместо него единица будет в той же строке, но в другой колонке, другая единица в той же колонке, но в другой строке
2. берем единичный элемент, и рассматриваем возможность его слияния с другим - вместо двух будет один на пересечении их строки и колонки (2 варианта)
3. берем единичный элемент, и рассматриваем возможность его перемещения по строке или колонке

Разумеется, операция может быть выполнена только если в ее результате не нарушатся условия задачи, и операция улучшит решение. Итерации прекращаем, когда нет возможности выполнить ни одну из 3 операций
Проект [[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: Задачка

Сообщение Michael_K » 25 дек 2009, 15:03

Что-то мне кажется сильно сложнее... не считал - просто Ащущенье

Добавлено спустя 1 минуту 4 секунды:
Как это вы сможете двигать одну единицу, не двигая другие...
Это ж дерево сильно разрастающееся!

Добавлено спустя 3 минуты 14 секунд:
Ой, блин, все забываю, вы ж условия поменяли :))
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Задачка

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

После "деления" это будет возможно
Проект [[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: Задачка

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

Еще мысль. Преобразуем матрицу А в направленный граф с n узлами. Элемент (i,j) матрицы преобразуется в ребро с весом А(i,j) и направлением от i к j. Применяем алгоритм поиска кратчайших путей, например [[ru:Алгоритм Флойда — Уоршелла]]. Для всех ребер, входящих в найденные пути, пишем 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: Задачка

Сообщение Michael_K » 25 дек 2009, 19:31

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

Re: Задачка

Сообщение Duhas » 25 дек 2009, 20:34

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

Re: Задачка

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

Андрей, погоди, что-то я сразу не вкурил. То что ты сначала рассказал - это же почти классическая переведенная в матрицы задача коммивояжера на ориентированном графе? A[i,j] - время в пути из i в j. B[i,j] - используем это ребро в выбранном кольцевом пути по всем городам или нет. Как раз получается B[i,j] или 0 или 1.

Сумма B[i,j] по j от 0 до n-1 при любом i равна 1, сумма B[i,j] по i от 0 до n-1 при любом j равна 1 - это типа в каждый город должны ровно 1 раз войти и ровно 1 раз выйти.

Тут же понятно, почему B[i,i]=0 при любом i :) нечего из i в i ходить :)

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

Re: Задачка

Сообщение Michael_K » 25 дек 2009, 20:47

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

Re: Задачка

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

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

Пред.След.

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

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

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

Mail.ru counter