2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Разбить множество на три примерно одинаковые части
Сообщение30.10.2008, 12:13 


11/11/07
80
Доброго времени суток всем!

Имеется следующая задача.
Имеется конечное множество элементов $x_i\in X$.
Вопрос: Нужно разбить данное множество на 3 подмножества с условием чтобы сумма элементов в этих подмножествах была $\approx\frac{\sum^m_i x_i}{3}$ или переводя на русский надо распределить элементы между тремя множествами так чтобы сумма элементов во всех трех множествах была приблизительно равна.

Мне пока кроме "железобетонного" перебора ничего в голову не приходит. Алгоритм может быть примерно следующим:
1. Упорядочиваем элементы множества $X$ от наименьшего к наибольшему.
2. В каждое из 3 множеств кладем самые наибольшие элементы множества $X$.
3. Берем 4-ый с конца элемент и смотрим по очереди каждое из подможеств чтобы сумма имеющегося и добавляемого элемента не превосходила $\frac{\sum^m_i x_i}{3}$. Если не превосходит кладем элемент в это множество если превосходит, то берем следующее подмножество и так далее.
4. Так продолжаем пока сумма во всех подмножествах не приблизиться к желаемой $\frac{\sum^m_i x_i}{3}$.
5. Ну а остатки (если таковые имеются) раскидываем приблизительно одинаково по всем множествам.

Пример: $X=\{1,2,3,5,7,2,4,1,1,9\}$, следовательно $\frac{\sum^m_i x_i}{3}=11.7$
1. После упорядочивания получаем: $X={1,1,1,2,2,3,4,5,7,9}$.
2. Теперь кладем наибольшие элементы в подмножества $Y_1=\{9\}, Y_2=\{7\}, Y_3=\{5\}$.
3. Далее берем $x_7=4$. Явно он не подходит для множества $Y_1$ а вот для множества $Y_2$ в самый раз ... значит определяем его туда. Так и с остальными элементами ... получаем что $Y_1=\{9,2\}, Y_2=\{7,4\}, Y_3=\{5,3,2\}$.
4. Теперь остатки. По существу уже не важно в какое множество пойдут оставшиеся две 1 но пусть в первое и второе множества.
Итак получили, что $Y_1=\{9,2,1\}, Y_2=\{7,4,1\}, Y_3=\{5,3,2\}$ и соответственно $\frac{\sum Y_1}{3}=12$, $\frac{\sum Y_2}{3}=12$, $\frac{\sum Y_13}{3}=11$.

Вот такой вариант у меня имеется ... может кто нибудь подскажет что-нибудь умнее изложенного выше ... ну или хотя бы более эффективное.

 Профиль  
                  
 
 
Сообщение31.10.2008, 13:21 


10/01/07
285
Санкт-Петербург
По-моему, это задача о разбиении или "о куче камней": известны количество и веса камней. Требуется распределить камни по $n$ ящикам так, чтобы вес самого тяжелого ящика был минимальным.
См., например, Романовский И.В. Алгоритмы решения экстремальных задач. М., 1977.

 Профиль  
                  
 
 
Сообщение01.11.2008, 13:36 


17/10/08

1313
Можно сформулировать эту задачу как проблему линейного программирования. Только, конечно, нужно сгруппировать элементы одинакового размера чтобы уменьшить количество симметричных вариантов (т.е. использовать размеры и количества элементов этих размеров). С вероятностью 99.9% можно утверждать, что пакет линейного программирования среднего уровня даст результат лучше, чем любая самописная программа.

Что касается Романовской и задачи распределения камней, то эта проблема также легко формулируется в терминах линейного программирования. И тоже, линейное программирование "побъет" самописные программы. Ну, и если рассмотрить пример <3,3,6>, то решение <<>,<3,3>,<6>> для камней будет оптимальным, а для исходной задачи - нет: <<3>,<3>,<6>>.

Со мной, конечно, можно спорить, но реальные тесты все поставят на свои места.

P.S. Где-то год назад просматривал книжки по дискретной математике/дискретной оптимизации. Ни одной современной книги, просто каменный век - материалы 60-х годов! "Пипл хавает..."

 Профиль  
                  
 
 
Сообщение02.11.2008, 20:36 


11/11/07
80
Ну во-первых спасибо всем за ответы.

mserg писал(а):
Можно сформулировать эту задачу как проблему линейного программирования.


Я и сам интуитивно догадываюсь что эту задачу можо переформулировать в терминах линейного программирования только не особо понимаю как это сделать. Если есть идеи то с удовольствием выслушаю.

 Профиль  
                  
 
 
Сообщение06.11.2008, 17:40 


17/10/08

1313
Можно, конечно, привести и линейную математическую модель, и данные, и решения. В чем тогда будет обучающий эффект, для которого создан данный раздел?

 Профиль  
                  
 
 
Сообщение06.11.2008, 20:50 


11/11/07
80
mserg писал(а):
Можно, конечно, привести и линейную математическую модель, и данные, и решения. В чем тогда будет обучающий эффект, для которого создан данный раздел?


Все дело в том что своим методом я эту задачу решил. Вы если уж взялись меня чему-либо обучать будьте любезны давать наводящие вопросы ибо я не телепат и не могу догадаться до Вашего решения.
Начнем с того как составить модель? С линейным программированием я некоторым образом знаком, но от того мне не легче для даной задачи составить модель.

 Профиль  
                  
 
 
Сообщение07.11.2008, 09:15 
Заслуженный участник
Аватара пользователя


13/08/08
14430
ув. zuj, можно немножко покритиковать Ваш метод?
11 10 7 7 7 7 7 7
В этом случае камни распределить можно с равными весами (21) ящиков. Но если вначале положить 10 и 11 в разные ящики, то такого распределения достичь нельзя будет.
Вам предусмотреть неизбежно придется возврат на шаг на любом этапе Вашего метода.
Я не знаю, если честно, как решать задачу, и это просто моё добродушное ворчание, а не злобная критика:)

 Профиль  
                  
 
 
Сообщение07.11.2008, 10:20 


11/11/07
80
gris писал(а):
ув. zuj, можно немножко покритиковать Ваш метод?


Покритиковать можно и даже нужно ибо это приводит к обнаружению ошибок. Вот как например в данной ситуации :D.

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

Ну как? Такой вариант чуть лучше?

 Профиль  
                  
 
 
Сообщение07.11.2008, 10:49 
Заслуженный участник
Аватара пользователя


13/08/08
14430
Мне кажется, что к задаче следует применять методы динамического программирования. С ним я знаком только на стандартных учебных задачах по распределению ресурсов, поэтому вряд ли могу дать хороший совет.
Но я думаю, что идея продвижения только вперёд неправильна. Должен быть механизм перераспределения даже первых трех камней. Иначе всегда можно подобрать соответствующий контрпример.
Хотя Ваш метод, наверное, будет хорошим приближением для практического использования в большинстве случаев. (Я не имею в виду камни, разумеется :) )

 Профиль  
                  
 
 
Сообщение07.11.2008, 11:22 


11/11/07
80
gris писал(а):
Мне кажется, что к задаче следует применять методы динамического программирования.

На тоже самое намекал mserg только не хочет признаваться как это сделать :).

gris писал(а):
Хотя Ваш метод, наверное, будет хорошим приближением для практического использования в большинстве случаев.


Я тоже думал над этим и пожалуй соглашусь с Вами. Но за не именеем "аналитического решения" приходится довольствоваться тем что есть :roll:.

 Профиль  
                  
 
 
Сообщение07.11.2008, 12:34 
Заслуженный участник
Аватара пользователя


13/08/08
14430
Я имел ввиду динамическое программирование, хотя в этой задаче, по ходу, нужно именно линейное. А Вам еще примерчики:
5 5 5 3 3 3 3 3 3 3 3 3 3
10 9 8 3 2(15 штук)
А к тому же определите строго, что Вы собираетесь минимизировать? Сумму отклонений от среднего? Попробуйте порешать эту задачу для двух ящиков... Только вот я согласен, что доморощенные методы работать, скорее всего, не будут :(

 Профиль  
                  
 
 
Сообщение07.11.2008, 19:52 


11/11/07
80
gris писал(а):
А к тому же определите строго, что Вы собираетесь минимизировать? Сумму отклонений от среднего?


Сложно сказать ... мне казалось что минимизировать нужно сумму элементов каждого множества одновременно, что в свою очередь и является проблемой: как разложить элементы равномерно по всем множествам :roll:.

 Профиль  
                  
 
 
Сообщение07.11.2008, 20:15 
Заслуженный участник
Аватара пользователя


13/08/08
14430
я имею в виду, если у вас есть два разных распределения по ящикам, то как вы определите, какое лучше? Что будет показателем равномерности?
Например, массы ящиков стали: 1) 20 20 20 2) 17 19 24 3) 16 20 24
Ясно, что первый вариант идеальный. А какой лучше 2 или 3?
А из 1) 22 22 16 и 2) 20 16 24 ?

 Профиль  
                  
 
 
Сообщение08.11.2008, 13:11 


11/11/07
80
Пардон не сразу понял что Вы имели ввиду под
gris писал(а):
Сумму отклонений от среднего?

Я не знаю как ее минимизировать, но то что это является критерием при определении насколько хорошо мы распределили - это да.

gris писал(а):
Например, массы ящиков стали: 1) 20 20 20 2) 17 19 24 3) 16 20 24
Ясно, что первый вариант идеальный. А какой лучше 2 или 3?

Я думаю что 2 лучше чем 3 потому что хотя их суммарное отклонение и одинаково, но максимальное отклонение во 2-ом случае равно 3, а в 3-ем 4.

gris писал(а):
А из 1) 22 22 16 и 2) 20 16 24 ?

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

 Профиль  
                  
 
 
Сообщение08.11.2008, 13:29 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
mserg в сообщении #155095 писал(а):
Что касается Романовской и задачи распределения камней, то эта проблема также легко формулируется в терминах линейного программирования.

Романовского не читал, но сомневаюсь в том, что рассматриваемая задача может быть сведена к задаче линейного программирования. В лучшем случае --- дискретного.
Дело в том, что задача ЛП полиномиально разрешима, а решение нашей задачи, помимо прочего, даст (ну хорошо, не обязательно даст, но вполне может дать :) ) ответ на вопрос: есть ли среди указанного множества чисел подмножество, сумма которого равна трети суммы всех чисел, т.е. частный случай NP-трудной задачи о сумме подмножеств.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



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

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


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group