Любой метод о любых численных методах, которые вы знаете, которые могут быть релевантными, отправьте его здесь!
Фон
У меня есть массив values для каждого набора, а индекс для каждого значения соответствует набору, к которому привязано значение, поэтому я представляю набор как целое число, где элементы представляют позицию бита, например. набор с элементом один в нем представлен как ...001, где 1 - это LSB.
Таким образом, набор является только индексом и никогда не сохраняется, он генерируется "на лету", это ключ, который приводит к индексу в массиве, который представляет значения наборов.
То, что я делаю, задано набором, является суммарным значением для любого из попарно непересекающихся подмножеств, большего, чем значение для этого набора. Например. если set 0111 имеет значение 3, где два подмножества имеют значение 0100 = 2 и 0011 = 2, то это разделение выгоднее делать. Я делаю это для всех подмножеств множества.
Для трех агентов и упорядочения - это представление номеров наборов.
val[8] = {0,1,2,4,3,2,4,2} the values is not important, only how they are ordered
0 0 0 0 1 1 1 1 MSB bit representation of the index
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1 LSB
Наилучшее расщепление 111 равно 011 и 100 с суммой 7. Таким образом, чтобы получить значение набора, содержащего только первый элемент ergo 001, вы поместите val [1], для набора с элементами 1 и 3 (101) вы положите val [5].
Как упорядочивается массив val при группировке по мощности
val[8] = {0,1,2,3,4,2,4,2}
0 0 0 1 0 1 1 1 MSB bit representation of the index
0 0 1 0 1 0 1 1
0 1 0 0 1 1 0 1 LSB
Здесь вам нужно перевести индекс в правый ящик в массиве, поэтому он будет выглядеть так, как это делается для набора только с третьим элементом в нем (100), val [translate (4)]. Подумайте массивы размером > 2 ^ 25 элементов. Посмотрите Улучшение доступа к произвольной памяти, когда необходим произвольный доступ для дальнейшего уточнения.
Однако это приводит к высокому порядку произвольного доступа в памяти, даже если я группирую их после мощности. В настоящее время группировка по мощности и генерация индекса происходит медленнее, чем упорядочение их после числа, которое представляет набор.
То, как я создаю индекс с наборами, сгруппированными по мощности, - это использовать треугольник парабол в постоянной памяти, как описано в ответе Определить лексикографическое расстояние между двумя целыми числами
Если значение множества расположено, когда оно упорядочено и сгруппировано по мощности с четырьмя агентами
n index 1 2 4 8 3 5 6 9 10 12 7 11 13 14 15
-----------------------------------------------------
MSB 0 0 0 1 | 0 0 0 1 1 1 | 0 1 1 1 | 1
0 0 1 0 | 0 1 1 0 0 1 | 1 0 1 1 | 1
0 1 0 0 | 1 0 1 0 1 0 | 1 1 0 1 | 1
LSB 1 0 0 0 | 1 1 0 1 0 0 | 1 1 1 0 | 1
n представляет собой индекс, который он имел бы, если бы он не был упорядочен по мощности. Это просто, чтобы показать, где находится значение для каждого набора.
Целочисленное множество представляет собой индекс в массиве значений, либо через прямой индекс (то, что я делаю сейчас, дает произвольный доступ), либо через перевод из набора в индекс.
Идея
Вместо того, чтобы разбивать набор на подмножества, я хотел бы создать множество снизу вверх. Например. вместо разбиения 0111 на все его попарно непересекающиеся подмножества, я бы в какой-то точке сгенерировал бы, если из множеств {0100,0011},{0010,0101},{0001,0110}.
Как и почему он должен работать
Скажем, мы хотим оценить все расщепления множеств с мощностью 3, эрго-множеств 7,11,13,14. Поскольку единственный способ разбить набор мощности 3 состоит в разбиении на множества мощности 1 и 2, нам нужно оценить, является ли сумма любого из всех непересекающихся подмножеств мощности 1 и 2 больше объединения этих множеств.
Обозначение того, что требуется (может быть немного ошибочным):
|C|=n,∀ a,b : a ∪ b = C , a ∩ b ={Ø}, |a|+|b| = n
Таким образом, считывая значения, используя совлокальный доступ к памяти для каждого потока, для каждого подмножества, которые образуют набор мощности n, проверьте, превышает ли оно его значение больше, чем сформированный набор, если это так, обновите значение.
Простой пример, если n = 2, тогда вы должны прочитать все значения с мощностью 1 и выполнить все комбинации этих наборов и соответственно обновить их. Этот пример прост, так как все наборы не пересекаются:
pseudo code for 4 threads, input card1 is pointer to array of sets |s| =1
__shared__ int value[4];
tid = threadIdx.x;
value[tid] = card1[tid]; // coalesced memory access
int thvalue = value[tid]; // holds the value for the thread, to avoid bank conflict
int rvalue[blockDim.x/2]= 0; //holds the sum
int i = blockDim.x;
int x = 0;
//reduction loop that dont generate duplicate sets
for(;i>0;i>>=1) {
if(tid < i) {
x++;
rvalue[x-1] = value[(tid+x)%blockDim.x] + thvalue;
}
}
for(i = 0; i < x; i++) {
int index = getindex(tid,i,1); //gets the index for the set it generated, 1 represent the cardinality
if(output[index] < rvalue[i])
output[index] = rvalue[i];
}
Итерация цикла редукции
Thread set specific for thread first iteration second iteration
0 0001 0001 + 0010 0001 + 0100
1 0010 0010 + 0100 0010 + 1000
2 0100 0100 + 1000 none
3 1000 1000 + 0001 none
Как вы видите, он выбрал все значения для всех подмножеств, которые образуют множества мощности 2.
Однако проблема состоит в том, что порождающие множества мощности больше 2 более сложны, поскольку не все множества не пересекаются. Например. 0001 и 0011 не пересекаются.
Имейте в виду, что я не храню множество в любом месте, а только значение для наборов.
Наконец
Как бы вы это сделали, имея это в виду, создавая алгоритм, который читает в памяти, объединенный и генерирующий все множества из непересекающихся подмножеств. Не проверяя, являются ли подмножества непересекающимися, он должен быть полностью детерминированным.
Для награды
Алгоритм должен быть либо описан в тексте с выделенными шагами, либо с псевдокодом.
Это должно быть доказано с примерами, в которых оно работает. Не то чтобы этот алгоритм поднимался до n ^ 32 наборов, поэтому он должен хорошо масштабироваться.
Алгоритм разрешен для двух или более экземпляров, например. один для четного числа и один для нечетного.
Я бы с удовольствием упомянул источники о используемой вами технике.
Алгоритм должен использовать как можно меньше назначений и инструкций и избегать любых расхождений. Но если вы думаете, что у вас есть один, хотя у вас есть много этого, попробуйте и опубликуйте, я буду рад любой информации.
Если он упорядочен по-другому, но он по-прежнему работает, как я описал, я настоятельно призываю вас отправить его здесь, любая помощь действительно полезна
Пожалуйста, спросите, есть ли что-то непонятное.
TL/DR Простое объяснение
У меня есть массив Z со значениями, индекс i, как и в Z[i], представляет собой целочисленное множество, в зависимости от упорядочения Z. Значения сгруппированы по мощности и упорядочены бинарной лексикографической перестановкой → позиция, в которой находится значение множества, 1,2,4,3,5,6,7 < - поэтому я использую функцию (я реализовал эту функцию), чтобы преобразовать индекс в правильный индекс. Например. Установите 3- > индекс 4.
Имея значения для набора, сгруппированного по мощности, я хочу, чтобы увидеть, больше ли какое-либо из попарно непересекающихся множеств, чем заданное ими множество.
например. |a| = 3, |b|+|c| =3, b ∩ c ={Ø}, |b| =1 Таким образом, считывая в X количество значений типа b и X количество значений из типа c, найдите все непересекающиеся подмножества b и c, что из типа a (комплекты мощности 3) и получить их сумму. Продолжайте, пока все наборы не будут "сгенерированы"
Для справки
Индексирование на основе веса Хэмминга
Определить лексикографическое расстояние между двумя целыми числами
Улучшение доступа к произвольной памяти при необходимости произвольного доступа
