powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Гуру, подскажите алгоритм решения задачи с множествами!
28 сообщений из 28, показаны все 2 страниц
Гуру, подскажите алгоритм решения задачи с множествами!
    #32929440
Ken_new
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Задача:
Имеется набор чисел. Необходимо распределить их по заданному количеству множеств таким образом, чтобы сумма чисел во множестве, имеющим самую большую сумму из всех остальных множеств в данном варианте распределения, была минимальной по сравнению со всеми остальными возможными вариантами распределения чисел по множествам.

Пример 1:

Имеется следующий набор чисел: 4; 5; 3; 4; 3.
Необходимо распределить их на 2 множества.
Ожидаемый ответ:
множество 1: 5; 4 (сумма равна 9).
множество 2: 4; 3; 3 (сумма равна 10)

Пример 2:

Имеется следующий набор чисел: 4; 5; 3; 4; 3.
Необходимо распределить их на 3 множества.
Ожидаемый ответ:
множество 1: 5 (сумма равна 5).
множество 2: 4; 3 (сумма равна 7)
множество 3: 4; 3 (сумма равна 7)

Я знаю один вариант алгоритма перестановки чисел, но не могу сформулировать условие его завершения. Я специально не стал его здесь писать, чтобы вам мозги лишним не забивать.
Я уверен на 100 процентов что эта задача имеет давным-давно разработанное решение и математическое описание, но, увы, я его не знаю - сказывается отсутствие профильного образования :-(
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32929447
Гаджимурадов Рустам
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Инет есть? Есть. Полазай, посмотри. Ты думаешь тебе сейчас с ъходу готовый алгоритм выдадут? Задача похожу на "медвежонковскую".
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32929559
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ken_new
Я уверен на 100 процентов что эта задача имеет давным-давно разработанное решение и математическое описание

Однозначно. Поищи в сети.
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32929577
Ken_new
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Да понимаете, я пытался порыться в Интернете, но не нашёл ни фига. Проблема в том, что я не очень представляю как правильно сформулировать название задачи. Это явно не задача оптимизации, не задача поиска экстремумов и т.п. Подозреваю что она имеет какое-то конкретное наименование, но вот какое...

Вообще, раз уж пошла дискуссия, расскажу какой алгоритм мне пришел в голову.

Имеем набор чисел 4; 5; 3; 4; 3.

Шаг 1:
сортируем числа по убыванию: 5; 4; 4; 3; 3.

Шаг 2:
последовательно (то есть первое число - в первое множество, второе - во второе, третье - снова в первое и так далее) раскидываем числа на два множества:
Множество 1: 5; 4; 3 (сумма 12).
Множество 2: 4; 3 (сумма 7).

Шаг 3.
Перебрасываем из множества, имеющего максимальную сумму элементов, минимальное число в другое множество:
Множество 1: 5; 4 (сумма 9).
Множество 2: 4; 3; 3 (сумма 10).

Ответ: минимальная сумма равна 10

Проблема в том, что я не могу сформулировать критерий, по которому алгоритм должен завершаться. Анализ сумм множеств не даёт результата, так как в общем случае не каждом шаге они могут меняться изменяются как в сторону увеличения, так и в сторону уменьшения.
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32929580
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это из области комбинаторных алгоритмов, дискретной математики ИМХО. Поищи по вышеуказанным ключевым словам. Задача явно популярная на производстве.
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32929738
Тузик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Может это поможет?
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32930185
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Идея для полного перебора. Неэффективно, но хоть что- то.
Количество шагов = (кол-во множеств) в степени (кол-во чисел)
Представляем себе множества в виде столбиков одинаковой высоты, так чтобы все числа умещались в одно множество (столбик). Ставим столбики рядом.Начальная позиция- все числа в самый левый столбик. Перемещать числа будем только по горизонтали, т.е. числа не падают вниз и не поднимаются; суммы считаются по вертикали.

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

Или можно рекурсивно.
1.Перебор всех состояний первого (самого нижнего) числа - это переход этого числа последовательно из самого левого в самый правый столбец. Здесь для каждого перехода считаются суммы и все что необходимо для запоминания "минимальной конфигурации"
2.Перебор всех состояний 2-го числа - это переход этого числа последовательно из самого левого в самый правый столбец, и для каждого такого перехода вызывается 1.
3.Перебор всех состояний N-го числа, это переход этого числа последовательно из самого левого в самый правый столбец, и для каждого такого перехода вызывается "Перебор всех состояний N-1 го числа".
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32930758
Valer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Извините , я немного не понял условия,
что все таки надо минимизировать
может надо просто получить несколько примерно равных
по сумме групп чисел ?
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32930946
Ken_new
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
ValerИзвините , я немного не понял условия,
что все таки надо минимизировать
может надо просто получить несколько примерно равных
по сумме групп чисел ?

Да нет.
Аналогичная "жизненная" задача может звучать так: передача данных идет по нескольким каналам (аналог множест). Каждый передатчик требует себе определённое количество временных интервалов в канале для передачи данных (аналог чисел). Как распределить передатчики по каналам, чтобы в итоге занимать наименьшее количество временных интервалов с целью экономии ресурсов.
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32931017
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
2 Ken new

1) Ты привел реальный пример из своего производства (то есть я хотел спросить примников-передатчиков действительно 3-5)?

В этом случае я бы мог предложить алгоритм полного перебора. ИМХО можно вполне сгенерировать перестановки и сочетания 5 элементов по 3 группам и для КАЖДОГО случая посчитать оптимальность. Если из будет ОООЧЕНЬ много то лучше ограничить такой алгоритм по времени. То есть дать ему лимит (скажем 1 сек) и взять локально оптимальный план который ему удалось сформировать.

2) Какое минимальное время отклика требуется для выдачи плана распределения?

Есть системы в которых это время меряется микросекундами. Есть менее критичные (сети передачи данных). Есть вообще некритичные электронная почта, новости, телеграф.

3) Может быть стоит подумать не над построением очередного плана а над ОПТИМИЗАЦИЕЙ существующего?

То есть к примеру, нам удалось вычислить оптимальный план, и если передатчик № 1 выключается а через некоторое время включается передатчик № 2 то можно вносить кратковременные корректировки в план без полного перерасчета.

4) Какими библиотеками и технологиями пользуешся в разработке (некоторые элементы комбинаторных алгоритмов уже реализованы в STL).

C уважениме
Mayton
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32931095
Kenneth
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
mayton2 Ken new

1) Ты привел реальный пример из своего производства (то есть я хотел спросить примников-передатчиков действительно 3-5)?

В этом случае я бы мог предложить алгоритм полного перебора. ИМХО можно вполне сгенерировать перестановки и сочетания 5 элементов по 3 группам и для КАЖДОГО случая посчитать оптимальность. Если из будет ОООЧЕНЬ много то лучше ограничить такой алгоритм по времени. То есть дать ему лимит (скажем 1 сек) и взять локально оптимальный план который ему удалось сформировать.


Не совсем из моего, но суть похожа. Реально элементов (ну, пусть будут "передатчики") может быть до ста. Мнеожеств ("каналов"), по которым они будут распределены - от одного до шести.

mayton2 Ken new
2) Какое минимальное время отклика требуется для выдачи плана распределения?

Есть системы в которых это время меряется микросекундами. Есть менее критичные (сети передачи данных). Есть вообще некритичные электронная почта, новости, телеграф.

3) Может быть стоит подумать не над построением очередного плана а над ОПТИМИЗАЦИЕЙ существующего?

То есть к примеру, нам удалось вычислить оптимальный план, и если передатчик № 1 выключается а через некоторое время включается передатчик № 2 то можно вносить кратковременные корректировки в план без полного перерасчета.


Система не рилтаймовая, поэтому время не очень критично. Другое дело что эту задачу, возможно, необходимо будет решить 500 или даже 1000 раз подряд.

mayton2 Ken new
4) Какими библиотеками и технологиями пользуешся в разработке (некоторые элементы комбинаторных алгоритмов уже реализованы в STL).

C уважениме
Mayton

Самое смешное и самое грустное, что эту задачу, возможно, необходимо будет решить средствами MS SQL'а, в хранимой процедуре, скорее всего :-(
Вообще, я думаю что, возможно, тут следует соблюдать компромисс между быстродействием и точностью. Возможно следует применять алгоритм, работающий быстрее и возвращающий избыточное решение, вместо 100% точного алгоритма, но работающего очень долго.
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32931100
Kenneth
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Kenneth = Ken_new. Я зарегистрировался...
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32931923
Valer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ken_new ValerИзвините , я немного не понял условия,
что все таки надо минимизировать
может надо просто получить несколько примерно равных
по сумме групп чисел ?

Да нет.
Аналогичная "жизненная" задача может звучать так: передача данных идет по нескольким каналам (аналог множест). Каждый передатчик требует себе определённое количество временных интервалов в канале для передачи данных (аналог чисел). Как распределить передатчики по каналам, чтобы в итоге занимать наименьшее количество временных интервалов с целью экономии ресурсов.


насколько я понял в общей куче лежит несколько чисел ( до сотни)
- времена передачи сигналов от разл передатчиков
есть несколько каналов по которым их надо распихать
число каналов может менятся
что надо минимизировать ?
общее время передачи или число каналов
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32932142
Kenneth
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Valer
насколько я понял в общей куче лежит несколько чисел ( до сотни)
- времена передачи сигналов от разл передатчиков
есть несколько каналов по которым их надо распихать
число каналов может менятся
что надо минимизировать ?
общее время передачи или число каналов

Общее время передачи.
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32932256
b
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
b
Гость
"минимизировать максимальную сумму"
=
"распределить числа по наборам как можно равномернее"

Чипуха, короче говоря. Тем более, что есть готовое решение на t-sql от акуза:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
set nocount on
declare @q_korzin int, @ves float, @n int, @k int, @avg_k float

create table #kamni (
	n int identity( 1 , 1 ) primary key,
	ves float,
	korzina int null
)

create table #korziny (
	k int identity( 1 , 1 ) primary key
)

-- подготовочка
declare @s int, @e int, @str varchar( 8000 )

set @str = -- это веса камней, которые нужны раскидать по корзинам
'1 1 2 3 3 3 3 3 5 5 5 6 7 7 8 8 9 9 9 9 9 9 22 33 43 44 46 50 53 53 53 ' +
'73 73 73 83 91 97 97 104 109 223 223 223 223 233 333 333 401 407 407'

set @s =  0 
while charindex(' ',@str,@s) <>  0 
begin
	set @e = charindex(' ',@str,@s)
	insert #kamni (ves) values (convert(int,substring(@str,@s,@e - @s)))
	set @s = @e +  1 
end
insert #kamni (ves) values (convert(int,substring(@str,@s, 8000 )))

select @q_korzin =  7 , @k =  1    --------- число корзин = 7

while @k <= @q_korzin
begin
	insert #korziny default values
	set @k = @k +  1 
end

-- вычисляем среднюю массу
select @avg_k = sum(ves) / @q_korzin
from #kamni

-- закидываем в корзинки по очереди, берём камешек покрупнее, кидаем в корзинку,
-- если есть место, кидаем ещё камушек побольше, покуда есть место :)
while @k <= @q_korzin
begin
	select @ves = sum(ves)
	from #kamni
	where korzina = @k

	set @n = null
	select top  1  @n = n
	from #kamni
	where korzina is null
		and ves <= @avg_k - isnull(@ves, 0 )
	order by ves desc

/*	select @k, ves, @ves
	from #kamni
	where n = @n
*/
	if @n is null
		set @k = @k +  1 
	else
		update #kamni set
			korzina = @k
		where n = @n
end

-- а теперь докидываем остатки:
while exists(select  1  from #kamni where korzina is null)
begin
	select top  1  @n = n
	from #kamni
	where korzina is null
	order by ves desc

	select top  1  @k=k
	from #korziny
		left join #kamni on korzina = k
	group by k
	order by sum(ves), k

	update #kamni set
		korzina = @k
	where n = @n

/*	select @k, ves, @ves
	from #kamni
	where n = @n
*/
end

-- вуаля!
select * from #kamni order by korzina, n

select k, sum(ves)
from #korziny
	left join #kamni on korzina = k
group by k

drop table #kamni
drop table #korziny
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32932541
Valer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Абсолютно согласен с пред тов арищем B,
надо просто равномерно разложить
числа по заданному числу множеств.
Если задача не динамическая т е в процессе
раскладывания не появляются новые числа,
то не вижу проблем в ее решении.
Непонятно почему это надо делать на TSQL,
а не на VB или Ci
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32933505
Kenneth
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
b"минимизировать максимальную сумму"
=
"распределить числа по наборам как можно равномернее"

Чипуха, короче говоря. Тем более, что есть готовое решение на t-sql от акуза:


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

Вот такой набор чисел:

5 2 6 7 5 4 3 3 8 6 3

пример, который ты привёл, распределяет их так:

3 3 8 = 14
7 4 3 = 14
5 2 6 = 13
5 6 = 11

Максимальная сумма тут 14.

А мне необходимо чтобы они были распределены следующим образом:

8 5 = 13
6 5 2 = 13
6 4 3 = 13
7 3 3 = 13

Максимальная сумма тут 13.

Теперь понятно что мне нужно?

Вообще, я написал алгоритм, который решает данную задачу так, как мне нужно. Сейчас я его тестирую и выложу как только буду уверен что он работает как надо.
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32933531
Kenneth
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
ValerНепонятно почему это надо делать на TSQL, а не на VB или Ci

Такая архитектура системы, заложена ещё в 2000 году, сейчас ничего уже не изменить без глобального переписывания.
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32933617
b
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
b
Гость
Да Вы, батенка, шутник, однако.
Или Вы думали, что я брошусь тестировать код акуза и ловить в нем баги?
Его код обязан был выдать (почему не выдал - это вопрос к нему):

8 5 = 13
6 5 2 = 13
6 4 3 = 13
7 3 3 = 13
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32933799
Kenneth
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
bДа Вы, батенка, шутник, однако.
Или Вы думали, что я брошусь тестировать код акуза и ловить в нем баги?
Его код обязан был выдать (почему не выдал - это вопрос к нему):

8 5 = 13
6 5 2 = 13
6 4 3 = 13
7 3 3 = 13

Да к тебе претензий нет :-)
Я просто думал что ты задачу неправильно понял.
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32935793
Valer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
1 По моему мнению критерий оптимальности
должен быть другой, если S сумма всех n чисел
m число групп (множеств ),
то минимизировать надо размер множества - S / m
пример 101 , 101,101,97 лучше чем
102,100,99,99
2 задача может решаться приближенно
раскладыванием n чисел по m группам.
Если цена отклонения от оптимального решения
не велика , то этого возможно достаточно
точное решение имеет сложность A в степени n т.е. с ростом n
катострофически растет ( возможно A > 2 )
т.к. надо генерировать все возможные комбинации элементов
3 В свое время делал задачу о рюкзаке,
при числе групп m=2
указанная задача сводится к задаче о рюкзаке емкостью S/2
4 Делать точное решени на TSQL ,бессмыслено.
Почему нельзя на клиенте прочитать таблицу,
провести расчеты и записать результаты в таблицу?
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32939248
Kenneth
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Ну вот, выкладываю алгоритм как и обещал.
Ломайте, тестируйте, критикуйте :-)

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
203.
204.
205.
206.
207.
208.
209.
210.
211.
212.
213.
214.
215.
216.
217.
218.
219.
220.
221.
222.
223.
224.
225.
226.
227.
228.
229.
230.
231.
232.
233.
234.
235.
236.
237.
238.
239.
240.
241.
242.
243.
244.
245.
246.
247.
248.
249.
250.
251.
252.
DECLARE @i_PCMs tinyint
SET @i_PCMs =  4  -- количество множеств

DECLARE @TempEdgeTable TABLE (
    numberOfJokerDS0TS tinyint
  )

-- а ниже - числа
INSERT INTO @TempEdgeTable
          SELECT  5 
UNION ALL SELECT  2 
UNION ALL SELECT  6 
UNION ALL SELECT  7 
UNION ALL SELECT  5 
UNION ALL SELECT  4 
UNION ALL SELECT  3 
UNION ALL SELECT  3 
UNION ALL SELECT  8 
UNION ALL SELECT  6 
UNION ALL SELECT  3 

DECLARE @TempEdgeMatrixTable TABLE (
    rowID              smallint identity not null,
    PCMnumber          tinyint,
    numberOfJokerDS0TS tinyint
  )

-- STEP 1
DECLARE
  @i_PCMmin  tinyint,
  @i_PCMmax  tinyint,
  @i_PCMstep smallint,
  @i_PCMcurr tinyint

DECLARE
  @i_numberOfJokerDS0 tinyint

DECLARE cursor_EdgeSites CURSOR FAST_FORWARD FOR
SELECT
  numberOfJokerDS0TS
FROM
  @TempEdgeTable
ORDER BY
  numberOfJokerDS0TS DESC

OPEN cursor_EdgeSites

SET @i_PCMmin =  1 
SET @i_PCMmax = @i_PCMs
SET @i_PCMstep =  0 
SET @i_PCMcurr = @i_PCMmin

FETCH NEXT FROM
  cursor_EdgeSites
INTO
  @i_numberOfJokerDS0

WHILE @@FETCH_STATUS =  0 
BEGIN
  INSERT INTO @TempEdgeMatrixTable (
    PCMnumber,
    numberOfJokerDS0TS
  )
  VALUES (
    @i_PCMcurr,
    @i_numberOfJokerDS0
  )
  
  SET @i_PCMstep = CASE
                     WHEN (@i_PCMs =  0 ) THEN  0 
                     WHEN (@i_PCMmax = @i_PCMmin) THEN  0 
                     WHEN (@i_PCMcurr = @i_PCMmax AND @i_PCMstep =  0 ) THEN - 1 
                     WHEN (@i_PCMcurr = @i_PCMmin AND @i_PCMstep =  0 ) THEN  1 
                     WHEN ((@i_PCMcurr = @i_PCMmax OR @i_PCMcurr = @i_PCMmin) AND @i_PCMstep <>  0 ) THEN  0 
                     ELSE @i_PCMstep
                   END

  SET @i_PCMcurr = @i_PCMcurr + @i_PCMstep
    
  FETCH NEXT FROM
    cursor_EdgeSites
  INTO
    @i_numberOfJokerDS0
END

CLOSE cursor_EdgeSites
DEALLOCATE cursor_EdgeSites

SELECT * FROM @TempEdgeMatrixTable

-- STEP 2
DECLARE @i_updated int
SET @i_updated =  1 

WHILE (@i_updated >  0 )
BEGIN
  UPDATE
    @TempEdgeMatrixTable
  SET
    PCMnumber = CRT.destPCM
  FROM
    @TempEdgeMatrixTable TBL
    INNER JOIN (
                SELECT TOP  1 
                  TBL1.minRowID AS sourceRowID,
                  TBL2.PCMnumber AS destPCM
                FROM
                  (
                   SELECT
                     TBL1.PCMnumber AS PCMnumber,
                     SUM(TBL1.numberOfJokerDS0TS) AS SumNumberOfJokerDS0TS,
                     MIN(TBL1.numberOfJokerDS0TS) AS MinNumberOfJokerDS0TS,
                     minRowID = (SELECT TOP  1  rowID FROM @TempEdgeMatrixTable SUB WHERE SUB.PCMnumber = TBL1.PCMnumber AND SUB.numberOfJokerDS0TS = MIN(TBL1.numberOfJokerDS0TS))
                   FROM
                     @TempEdgeMatrixTable TBL1
                   GROUP BY
                     TBL1.PCMnumber
                  ) TBL1
                  CROSS JOIN
                  (
                   SELECT
                     TBL1.PCMnumber AS PCMnumber,
                     SUM(TBL1.numberOfJokerDS0TS) AS SumNumberOfJokerDS0TS,
                     MIN(TBL1.numberOfJokerDS0TS) AS MinNumberOfJokerDS0TS,
                     minRowID = (SELECT TOP  1  rowID FROM @TempEdgeMatrixTable SUB WHERE SUB.PCMnumber = TBL1.PCMnumber AND SUB.numberOfJokerDS0TS = MIN(TBL1.numberOfJokerDS0TS))
                   FROM
                     @TempEdgeMatrixTable TBL1
                   GROUP BY
                     TBL1.PCMnumber
                  ) TBL2
                WHERE
                  TBL1.PCMnumber <> TBL2.PCMnumber
                  AND (CAST(TBL1.SumNumberOfJokerDS0TS AS int) - CAST(TBL2.SumNumberOfJokerDS0TS AS int)) > TBL1.MinNumberOfJokerDS0TS
               ) CRT ON CRT.sourceRowID = TBL.rowID
  
  SET @i_updated = @@ROWCOUNT
END

SELECT * FROM @TempEdgeMatrixTable

-- STEP 3
DECLARE
  @i_swpRowID1 smallint,
  @i_swpPCM1   smallint,
  @i_swpRowID2 smallint,
  @i_swpPCM2   smallint

SET @i_swpRowID1 =  0 
SET @i_swpPCM1 =  0 
SET @i_swpRowID2 =  0 
SET @i_swpPCM2 =  0 

SET @i_updated =  1 

WHILE (@i_updated >  0 )
BEGIN
  SELECT TOP  1 
    @i_swpRowID1 = TBL1.rowID,
    @i_swpPCM1 = TBL1.PCMnumber,
    @i_swpRowID2 = TBL2.rowID,
    @i_swpPCM2 = TBL2.PCMnumber
  FROM
    (
     SELECT
       TBL2.rowID AS rowID,
       TBL2.PCMnumber AS PCMnumber,
       TBL2.numberOfJokerDS0TS AS numberOfJokerDS0TS,
       TBL1.SumNumberOfJokerDS0TS AS SumNumberOfJokerDS0TS
     FROM
       @TempEdgeMatrixTable TBL2
       INNER JOIN (
                   SELECT TOP  1 
                     TBL1.PCMnumber AS PCMnumber,
                     SUM(TBL1.numberOfJokerDS0TS) AS SumNumberOfJokerDS0TS
                   FROM 
                     @TempEdgeMatrixTable TBL1
                   GROUP BY
                     TBL1.PCMnumber
                   ORDER BY
                     SUM(TBL1.numberOfJokerDS0TS) DESC
                  ) TBL1 ON TBL2.PCMnumber = TBL1.PCMnumber
     ) TBL1
     CROSS JOIN (
                 SELECT
                   TBL2.rowID AS rowID,
                   TBL2.PCMnumber AS PCMnumber,
                   TBL2.numberOfJokerDS0TS AS numberOfJokerDS0TS,
                   TBL1.SumNumberOfJokerDS0TS AS SumNumberOfJokerDS0TS
                 FROM
                   @TempEdgeMatrixTable TBL2
                 INNER JOIN (
                             SELECT TOP  1 
                               TBL1.PCMnumber AS PCMnumber,
                               SUM(TBL1.numberOfJokerDS0TS) AS SumNumberOfJokerDS0TS
                             FROM 
                               @TempEdgeMatrixTable TBL1
                             GROUP BY
                               TBL1.PCMnumber
                             ORDER BY
                               SUM(TBL1.numberOfJokerDS0TS) ASC
                            ) TBL1 ON TBL2.PCMnumber = TBL1.PCMnumber
                ) TBL2
  WHERE
    (CAST(TBL1.SumNumberOfJokerDS0TS AS float) - CAST(TBL2.SumNumberOfJokerDS0TS AS float)) >  1 
    AND (CAST(TBL1.numberOfJokerDS0TS AS int) - CAST(TBL2.numberOfJokerDS0TS AS int)) >=  1 
    AND (CAST(TBL1.numberOfJokerDS0TS AS int) - CAST(TBL2.numberOfJokerDS0TS AS int)) <= CAST(CEILING((CAST(TBL1.SumNumberOfJokerDS0TS AS float) - CAST(TBL2.SumNumberOfJokerDS0TS AS float)) /  2 ) AS int)
  ORDER BY
    (CAST(TBL1.numberOfJokerDS0TS AS int) - CAST(TBL2.numberOfJokerDS0TS AS int)) ASC

  SET @i_updated = @@ROWCOUNT

  IF @i_updated >  0 
  BEGIN
    UPDATE
      @TempEdgeMatrixTable
    SET
      PCMnumber = @i_swpPCM2
    WHERE
      rowID = @i_swpRowID1
  
    UPDATE
      @TempEdgeMatrixTable
    SET
      PCMnumber = @i_swpPCM1
    WHERE
      rowID = @i_swpRowID2
  END
END

-- final result
SELECT
  *
FROM @TempEdgeMatrixTable

-- summs
SELECT
  PCMnumber,
  sum(numberOfJokerDS0TS)
FROM
  @TempEdgeMatrixTable
GROUP BY
  PCMnumber

-- max
SELECT TOP  1 
  SUM(numberOfJokerDS0TS)
FROM
  @TempEdgeMatrixTable
GROUP BY
  PCMnumber
ORDER BY
  SUM(numberOfJokerDS0TS) DESC
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32963504
Фотография VidmakCase
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я не очень внимательно читал прошлые месаги в этом топике, но по как я понял вопрос в АЛГОРИТМЕ. Зачем T-SQL ? Дайте алгоритм а кому как надо так и напишет.
Мне например очень трудно разобратся в приведенных исходниках.
Задачка кстати мне очень понравилась. С тех пор как я на ACM был мозги так не напрягал (в плане придумывания алгортма)

Вот такие пока идеи есть:
(если я пропустил готовый алгоритм - поправте меня)
1) однозначно суммы оджны минимально отличатся, в таком случае максимальная из них и будет минимальной для всех разных наборов.
2) Кто то там вспоминал о рюкзаке (или о двух). ИМХО это здесь не подходит. Хотя некорые аналогии можно провсти. И то и то по идее
А вообще мне пахнет здесь жадными алгоритмами... По дороге с работы в метро обязательно подумаю. Хотя можно и в поисовиках поискть - но это не сравнится с тем удовольствием когда сам решаешь :)
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32963531
Фотография VidmakCase
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
По поводу Жадных алгоритмов - пока не уверен.
У задач, которые решаются с помощью жадных алгоритмов должно быть свойство оптимальности для подзадач.
Как я помню задачу оптимизации можно решать при помощи жадного выбора, если последовательность локально оптимальных выборов дает глобально оптимальное решение. А вот в динамическом программирования просчитываются сразу последствия всех вариантов.

Оптимальность для подзадач: оптимальное решение всей задачи содержит в себе оптимальные решения подзадач.

Так по поводу алгоритма больше никто не выскажется??? Придется читать T-SQL
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32963577
Фотография VidmakCase
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Kenneth
Нифига не так. Не "распределить числа по наборам как можно равномернее", а распределить так, чтобы "минимизировать максимальную сумму".


А по моиму моему как раз наборы сума которых буде равномернее и будут решением задачи.
Вопрост только в том, чт опонимать под словом равномернее.

И кто то там говорил, что это задача не оптимизации... ИМХО как рах оптимизации.

И еще то что надо числа отсортировать - факт! Какой бы алгоритм потом не применялся ему это понадобится
Сегодня вечером обязательно что то придумаю :) Очень хочется.
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32964269
Kenneth
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
В кратце, алгоритм следующий:

Шаг 1 : сортируем числа по убыванию и распределяем их по множествам "зейкой". То есть для набора чисел 5 2 6 7 5 4 3 3 8 6 3 и четырёх множеств это будет следующим образом:

Сортировка: 8 7 6 6 5 5 4 3 3 3 2
Распеределение:
(8 3 3) = 14
(7 4 3) = 14
(6 5 2) = 13
(6 5 ) = 11

Шаг 2 : переносим минимальный элемент из одного множества в другое при условии что разница их сумм больше чем переносимый элемент. Этот шаг повторяем до тех пор, пока приведённое выше условие выполняется.

Таким образом при распределении чисел "змейкой" на перовом шаге, этот шаг для данного набора чисел игнорируется. Для других наборов, в которых числа различаются на большие величины, этот шаг выполняется.

Шаг 3 : выбираются два множества - с максимальной и минимальной суммой элементов. Выполняем проверку что разность их сумм больше 1 (исходим из того, что работаем с целыми числами). Если это условие не выполняется, то нашли оптимальное решение, в противном случае находим разность между элементами множества (каждый элемент с каждым). Полученные разности упорядочеваем по возрастанию и находим попадающие в интервал [1, CEILING((S1 - S2)/2)] (где S1 и S2 - суммы множеств, CEILING - округление в большую сторону). Из значений, удовлетворяющих этому неравенству выбираем максимальное. Пару элементов множества, удовлетворяющих приведённому условию, меняем местами. Этот шаг повторяем до тех пор, пока можем поменять элементы местами.

Таким образом:

итерация 1:
(8 3 3) = 14
(6 5 ) = 11

S1 - S2 = 3

Пары элементов:
(8 - 6 = 2) (3 - 6 = -3) (3 - 6 = -3) (8 - 5 = 3) (3 - 5 = -2) ( 3 - 5 = -2)
1 <= Xij <= CEILING(1.5) = 2
меняем местами элементы 8 и 6. Получаем:
(6 3 3) = 12
(7 4 3) = 14
(6 5 2) = 13
(8 5 ) = 13

итерация 2:
рассуждая аналогично меняем местами элементы первого и второго множества. Тут, однако, возможны варианты. Можно поменять местами 6 и 7, либо 3 и 4. Однако, это не имеет значение что мы будем менять местами.

Если мы менем местами 7 и 6, то получаем:

(7 3 3) = 13
(6 4 3) = 13
(6 5 2) = 13
(8 5 ) = 13 - искомый результат.

Если мы меняем местами 3 и 4 то получаем:

(6 4 3) = 13
(7 3 3) = 13
(6 5 2) = 13
(8 5 ) = 13 - искомы результат.

Вот.

В принципе, основную роль в алгоритме играет шаг 3. Используя только его можно получить ответ, однако шаг 1 и шаг 2 значительно сокращают количество итераций на шаге 3.
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32964698
Фотография VidmakCase
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
О! Спасибо большое за алгоритм. Так я хоть понял.
Он по идее правльный
Однако мне что то заело (чисто с теор. точки зрения).
Часов с 6-ти голову ламаю.
Вот как-то мне он не неравится Как минимум нету доказательства, что он правильный.
Особенно действия описаные в Шаге 3. Который по сути главный.
Вопрос к теоретикам (Они же тоже должы читать этот форум:) ): что скажете?
...
Рейтинг: 0 / 0
Гуру, подскажите алгоритм решения задачи с множествами!
    #32970012
Дмитрий Валуев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Насколько помню такие алгоритмы называются обменно-итерационными. Известно, что в задаче разрезания графа (разбить множество вершин графа на 2 подмножества так, что бы сумма связей между подмножествами была минимальной) обменно-итерационный алгоритм дает лишь локально оптимальное решение. Хотя задача разрезания графа кажется более сложной, чем рассматриваемая за счет наличия связей между элементами, скорее всего аналогичная картина будет и здесь: варьируя начальное разбиение будем получать различные локальные минимумы, из который выберем наилучший. Что это будет глобальный минимум - не факт. Повторюсь еще раз, что это только мое предположение, но доказательство того, что обменно-итерационный алгоритм в этой задаче всегда сходится к глобальному минимуму действительно необходимо.
В теории локального поиска есть предположение (однако такие вещи опасно обобщать), что "хорошие" алгоритмы слабо зависят от качества начального приближения и всегда находят локальные оптимумы определенной "силы". С этой точки зрения интересно посмотреть, дают ли шаги 1 и 2 преимущество по сравнению со случайным выбором начального разбиения.
Если требуется найти точное решение, я бы поступил так. Ясно, что оптимум надо искать вблизи равномерных разбиений. В рассматриваемом примере общая сумма 52, идеальный случай 4 подмножества по 13. Находим все комбинации элементов, дающие в сумме 13 (это как раз одна из разновидностей задачи о рюкзаке). Далее смотрим существуют ли среди полученных комбинаций 4 таких, что:
1.Каждый элемент в них встречается ровно 1 раз.
2.Не существует элемента, который не встретился ни разу.
В данном примере такое разбиение существует, но в общем случае его может и не быть. Тогда отступаем на шаг - 13,13,14,12 и повторяем процесс. Сколько итераций придется сделать в общем случае неясно, однако есть предположение, что конечное число :^) Способ хотя и не самый быстрый, но теоретически обоснованный: "правильность" конечного результата следует из "правильности" алгоритма решения задачи о рюкзаке, которую мы решаем на каждом шаге и которая известна.
Кроме того, имея все комбинации элементов, дающие в сумме 13, можно искать не обязательно 4 подмножества , а также 3, 5 и т.д.
...
Рейтинг: 0 / 0
28 сообщений из 28, показаны все 2 страниц
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Гуру, подскажите алгоритм решения задачи с множествами!
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]