2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 3, 4, 5, 6, 7  След.
 
 Re: Особый алгоритм перебора всех подмножеств мультимножества
Сообщение03.02.2018, 17:27 
Заслуженный участник
Аватара пользователя


09/09/14
6328
B@R5uk в сообщении #1289787 писал(а):
отсечение неудачных решений может происходить на самой последней сумме. Здесь выход, на мой взгляд, только один: угадать с какой суммы начать перебор, чтобы решение попалось в на самых первых попытках.
Ну, здесь должна сработать Ваша идея начинать с тех чисел, для которых меньше вариантов разбиений. Она не сработает только в том случае, если условие подобрано так, что для всех чисел вариантов разбиений примерно поровну. В этой ситуации есть смысл проделать то же на втором шаге -- заново посчитать число разбиений на оставшихся числах -- там уже вряд ли будет поровну.

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

 Профиль  
                  
 
 Re: Особый алгоритм перебора всех подмножеств мультимножества
Сообщение03.02.2018, 17:53 
Аватара пользователя


26/05/12
1534
приходит весна?
grizzly в сообщении #1289797 писал(а):
здесь должна сработать Ваша идея начинать с тех чисел, для которых меньше вариантов разбиений
Нет пути! Кроме прямого перебора посчитать число вариантов невозможно (если я ошибаюсь — поправьте), с другой стороны, этот самый прямой подсчёт может занять вечность.

Мой простейший алгоритм (брать суммы по очереди и отщеплять подмножества элементов, образующих эти суммы с возвратом в случае неудачи к предыдущей сумме и выбором нового решения) работал только до теста 15. Чтобы добраться до теста 61 я использовал принудительную остановку перебора и возврат на предыдущий уровень, если число попыток превысило определённый порог (он может быть константой, а может быть и функцией текущей глубины и других параметров). Я, правда, использовал только один порядок выделения сумм. В этом, думаю, главная проблема.

 Профиль  
                  
 
 Re: Особый алгоритм перебора всех подмножеств мультимножества
Сообщение03.02.2018, 21:34 
Аватара пользователя


26/05/12
1534
приходит весна?
arseniiv, я ещё раз внимательно проанализировал ваш алгоритм. Он практически идентичен моему последнему алгоритму. Отличие в мелочах: у вас каждый новый элемент сначала устанавливается в максимум, потом в процессе работы уменьшается по одному, а так же у вас некоторые действия, которые у меня делаются за одну итерацию, разбиты на две. Плюс у вас явное деление на оценивание состояний и итерирование состояний. У меня эти две вещи максимально интегрированы в попытке достичь максимального быстродействия (не факт, кстати, что удачной). В тех моих итерациях, что у вас разбиваются на несколько, у меня происходит зануление последнего элемента, декремент предыдущего ненулевого и инкремент следующего за ним (если большие к меньшим расположить слева на право). У вас выполняется в принципе то же самое число действий, но не за одну, а за несколько итераций. Это если говорить про порядок итерирования без учёта получающейся суммы. В полном алгоритме различия ещё более трудноуловимы. На счёт порядка итерирования, вот две последовательности для сравнения. Слева — вашего алгоритма, справа — моего. Я попытался максимально близко расположить похожие элементы последовательности.

(ДВЕ ПОСЛЕДОВАТЕЛЬНОСТИ)

2113

**** | 0000
***3 | 0001
**13 | 0002
*113 | 0003
2113 | 0013
1113 | 0113
0113 | 1113
*013 | 2113
2013 | 1013
1013 | 2013
0013 |
**03 |
*103 | 0103
2103 | 1103
1103 | 2103
0103 |
*003 |
2003 | 1003
1003 | 2003
0003 |
***2 |
**12 | 0012
*112 | 0112
2112 | 1112
1112 | 2112
0112 |
*012 |
2012 | 1012
1012 | 2012
0012 |
**02 |
*102 | 0102
2102 | 1102
1102 | 2102
0102 |
*002 |
2002 | 1002
1002 | 2002
0002 |
***1 |
**11 | 0011
*111 | 0111
2111 | 1111
1111 | 2111
0111 |
*011 |
2011 | 1011
1011 | 2011
0011 |
**01 |
*101 | 0101
2101 | 1101
1101 | 2101
0101 |
*001 |
2001 | 1001
1001 | 2001
0001 |
***0 |
**10 | 0010
*110 | 0110
2110 | 1110
1110 | 2110
0110 |
*010 |
2010 | 1010
1010 | 2010
0010 |
**00 |
*100 | 0100
2100 | 1100
1100 | 2100
0100 |
*000 |
2000 | 1000
1000 | 2000
0000 | 0000

 Профиль  
                  
 
 Re: Особый алгоритм перебора всех подмножеств мультимножества
Сообщение03.02.2018, 22:46 
Аватара пользователя


26/05/12
1534
приходит весна?
B@R5uk в сообщении #1289813 писал(а):
роме прямого перебора посчитать число вариантов невозможно (если я ошибаюсь — поправьте)
Я ошибался. Нашёл решение.

 Профиль  
                  
 
 Re: Особый алгоритм перебора всех подмножеств мультимножества
Сообщение05.02.2018, 15:58 
Аватара пользователя


26/05/12
1534
приходит весна?
Написал код для проверки количества уникальных решений, получающихся из заданного набора элементов:

код: [ скачать ] [ спрятать ]
Используется синтаксис Java
import java.util.*;

public class StudySumsNumber3 {
       
        private static final Random rng = new Random();
        private static final int size = 7;
        private static final int sumsNumber = 10;
       
        private static final int[] entryValues = new int[size];
        private static final int[] entryLimits = new int[size];
        private static final int[] tagetSums = new int[sumsNumber];
        private static final int[] result = new int[sumsNumber];
       
        private static SubsetsCounter counter;
       
        public static void main(String[] args) {
                int n, value, limit, totalSum;
                value = 0;
                for (n = 0; size > n; ++n) {
                        value += 1 + rng.nextInt(3);
                        entryValues[n] = value;
                }
                totalSum = 0;
                for (n = 0; size > n; ++n) {
                        limit = 1 + rng.nextInt(4);
                        entryLimits[n] = limit;
                        totalSum += limit * entryValues[n];
                }
                for (n = 0; sumsNumber > n; ++n) {
                        tagetSums[n] = 1 + rng.nextInt(totalSum);
                }
                Arrays.sort(tagetSums);
               
                System.out.println(Arrays.toString(entryValues));
                System.out.println(Arrays.toString(entryLimits));
                System.out.println();
               
                counter = new SubsetsCounter(entryValues, tagetSums);
                value = counter.getResult(result, entryLimits);
                System.out.println(value);
                System.out.println();
               
                for (n = 0; sumsNumber > n; ++n) {
                        System.out.print(n);
                        System.out.print(": ");
                        System.out.print(tagetSums[n]);
                        System.out.print(" -> ");
                        System.out.println(result[n]);
                }
        }
}
 

код: [ скачать ] [ спрятать ]
Используется синтаксис Java
import java.util.*;

public class SubsetsCounter {
        private int valuesNumber, sumsNumber, maxSum;
        private int[] entryValues;
        private int[] tagetSums;
        private int[] subresult;
       
        public SubsetsCounter(int[] values, int[] sums) {
                valuesNumber = values.length;
                entryValues = Arrays.copyOf(values, valuesNumber);
                sumsNumber = sums.length;
                tagetSums = Arrays.copyOf(sums, sumsNumber);
                maxSum = 0;
                for (int n = 0; sumsNumber > n; ++n) {
                        if (maxSum < sums[n]) {
                                maxSum = sums[n];
                        }
                }
                subresult = new int[maxSum + 1];
        }
       
        public int getResult(int[] result, int[] entryLimits) {
                int n, m, l, value, sum, addend, limit, index;
                Arrays.fill(subresult, 0);
                subresult[0] = 1;
                sum = 0;
                for (n = 0; valuesNumber > n; ++n) {
                        limit = entryLimits[n];
                        value = entryValues[n];
                        for (m = Math.min(maxSum - value, sum); 0 <= m; --m) {
                                addend = subresult[m];
                                for (l = 1; limit >= l; ++l) {
                                        index = m + l * value;
                                        if (maxSum >= index) {
                                                subresult[index] += addend;
                                        }
                                }
                        }
                        sum += limit * value;
                }
                index = -1;
                value = Integer.MAX_VALUE;
                for (n = 0; sumsNumber > n; ++n) {
                        limit = subresult[tagetSums[n]];
                        result[n] = limit;
                        if (value >= limit) {
                                value = limit;
                                index = n;
                        }
                }
                return index;
        }
}
 


Результаты работы какие-то такие:

(ПРИМЕР РАЗ)

[3, 5, 8, 9, 11, 13, 14]
[4, 3, 2, 4, 3, 3, 2]

1

0: 5 -> 1
1: 6 -> 1
2: 19 -> 8
3: 44 -> 60
4: 65 -> 143
5: 70 -> 161
6: 83 -> 196
7: 83 -> 196
8: 87 -> 202
9: 122 -> 111

(ПРИМЕР ДВА)

[2, 5, 7, 10, 12, 15, 17]
[1, 2, 1, 1, 2, 2, 2]

7

0: 50 -> 2
1: 59 -> 14
2: 67 -> 2
3: 69 -> 8
4: 74 -> 5
5: 78 -> 15
6: 90 -> 8
7: 99 -> 0
8: 105 -> 4
9: 112 -> 1

(ПРИМЕР ТРИ)

[2, 5, 7, 10, 11, 13, 14]
[1, 3, 1, 3, 3, 1, 2]

1

0: 9 -> 1
1: 11 -> 1
2: 30 -> 10
3: 55 -> 26
4: 56 -> 25
5: 84 -> 18
6: 101 -> 8
7: 104 -> 6
8: 121 -> 2
9: 121 -> 2


-- 05.02.2018, 16:05 --

grizzly в сообщении #1289797 писал(а):
Ну, здесь должна сработать Ваша идея начинать с тех чисел, для которых меньше вариантов разбиений. Она не сработает только в том случае, если условие подобрано так, что для всех чисел вариантов разбиений примерно поровну. В этой ситуации есть смысл проделать то же на втором шаге -- заново посчитать число разбиений на оставшихся числах -- там уже вряд ли будет поровну.
Да вы правы. Более того, проверять количество решений для оставшихся сумм надо на любом шаге. Просто потому, что удаление элементов из множества, необходимых для образования текущей суммы может привести к тому, что для одной или нескольких оставшихся сумм решения больше не найдётся. Именно это самая главная подлянка задачи. Надо иметь возможность отсеивать такие случаи сразу, а не перебрав тьму тьмущую решений для нескольких промежуточных сумм, чтобы обнаружить, что для последней суммы решения нет ни в каком из промежуточных случаев.

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

 Профиль  
                  
 
 Re: Особый алгоритм перебора всех подмножеств мультимножества
Сообщение06.02.2018, 11:41 
Аватара пользователя


26/05/12
1534
приходит весна?
Всё-таки этого механизма отсеивания мало. Нужно что-то продвинутое, или же вообще, для многорюкзачного разделения нужен какой-то свой особый алгоритм.

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

 Профиль  
                  
 
 Re: Особый алгоритм перебора всех подмножеств мультимножества
Сообщение06.02.2018, 18:23 
Заслуженный участник


27/04/09
28128
Так вы не попробовали составить алгоритм, где все элементы распределяются по всем рюкзакам модификацией алгоритма с одним рюкзаком, чтобы числа вхождений 0 и 1 переинтерпретировались как рюкзак, в который мы распределили элемент? Вдруг это можно сделать (я не пробовал) и сохранить отсечения.

 Профиль  
                  
 
 Re: Особый алгоритм перебора всех подмножеств мультимножества
Сообщение06.02.2018, 19:16 
Аватара пользователя


26/05/12
1534
приходит весна?
arseniiv в сообщении #1290619 писал(а):
Вдруг это можно сделать и сохранить отсечения.
Я думаю, переоборудовать этот алгоритм под несколько рюкзаков не получится. В случае одного рюкзака легко придумать порядок и перенумеровать комбинации именно потому, что он один, а получающиеся суммы хоть и разбросаны, но лежат на одной прямой. С двумя рюкзаками задача становится уже двумерной и тут совсем не понятно в каком виде производить перенумеровку потенциальных решений. Хотя было бы интересно посмотреть на все возможные решения в том или ином случае задачи с несколькими рюкзаками.

Я тут всё больше склоняюсь к поиску в глубину (DFS) с отсечениями. Приём, который я описал выше (позволяющий посчитать количество представлений любого числа в виде суммы подмножества заданного множества чисел) позволяет довольно эффективно реализовать эти отсечения. Если мы будет брать элементы исходного множества и вычитать их из заданных сумм, то во-первых сами суммы будут уменьшаться, а во-вторых, количество элементов исходно множества будет уменьшаться. Разумеется надо будет периодически отматывать назад, но самое главное, мы всегда может брать элементы исходного множества в одном и том же порядке. Мы можем заранее посчитать число вариантов, которыми можно представить различные числа в виде суммы подмножеств оставшихся элементов исходного множества, и использовать эту информацию для отсева неудачных направлений погружения. Фактически надо будет проверять, что все имеющиеся остатки могут быть представлены хотя бы одним способом через оставшиеся числа.

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

-- 06.02.2018, 20:08 --

B@R5uk в сообщении #1290637 писал(а):
Мы можем заранее посчитать число вариантов, которыми можно представить различные числа в виде суммы подмножеств оставшихся элементов исходного множества, и использовать эту информацию для отсева неудачных направлений погружения.
Вот наглядная иллюстрация сказанного:
.\..-..4..4..6..6..6..6..7..7..7..(53)

.0..1..1..1..1..1..1..1..1..1..1
.1..-..-..-..-..-..-..-..-..-..-
.2..-..-..-..-..-..-..-..-..-..-
.3..-..-..-..-..-..-..-..-..-..-
.4..-..1..2..2..2..2..2..2..2..2
.5..-..-..-..-..-..-..-..-..-..-
.6..-..-..-..1..2..3..4..4..4..4
.7..-..-..-..-..-..-..-..1..2..3
.8..-..-..1..1..1..1..1..1..1..1
.9..-..-..-..-..-..-..-..-..-..-
10..-..-..-..2..4..6..8..8..8..8
11..-..-..-..-..-..-..-..2..4..6
12..-..-..-..-..1..3..6..6..6..6
13..-..-..-..-..-..-..-..4..8.12
14..-..-..-..1..2..3..4..4..5..7
15..-..-..-..-..-..-..-..1..2..3
16..-..-..-..-..2..6.12.12.12.12
17..-..-..-..-..-..-..-..8.16.24
18..-..-..-..-..-..1..4..4..6.10
19..-..-..-..-..-..-..-..6.12.18
20..-..-..-..-..1..3..6..6.10.18
21..-..-..-..-..-..-..-..4..8.13
22..-..-..-..-..-..2..8..8..9.11
23..-..-..-..-..-..-..-.12.24.36
24..-..-..-..-..-..-..1..1..9.25
25..-..-..-..-..-..-..-..4..8.14
26..-..-..-..-..-..1..4..4.10.22
27..-..-..-..-..-..-..-..6.12.22
28..-..-..-..-..-..-..2..2..6.14
29..-..-..-..-..-..-..-..8.16.25
30..-..-..-..-..-..-..-..-.12.36
31..-..-..-..-..-..-..-..1..2.11
32..-..-..-..-..-..-..1..1..5.13
33..-..-..-..-..-..-..-..4..8.18
34..-..-..-..-..-..-..-..-..6.18
35..-..-..-..-..-..-..-..2..4.10
36..-..-..-..-..-..-..-..-..8.24
37..-..-..-..-..-..-..-..-..-.12
38..-..-..-..-..-..-..-..-..1..3
39..-..-..-..-..-..-..-..1..2..7
40..-..-..-..-..-..-..-..-..4.12
41..-..-..-..-..-..-..-..-..-..6
42..-..-..-..-..-..-..-..-..2..6
43..-..-..-..-..-..-..-..-..-..8
44..-..-..-..-..-..-..-..-..-..-
45..-..-..-..-..-..-..-..-..-..1
46..-..-..-..-..-..-..-..-..1..3
47..-..-..-..-..-..-..-..-..-..4
48..-..-..-..-..-..-..-..-..-..-
49..-..-..-..-..-..-..-..-..-..2
50..-..-..-..-..-..-..-..-..-..-
51..-..-..-..-..-..-..-..-..-..-
52..-..-..-..-..-..-..-..-..-..-
53..-..-..-..-..-..-..-..-..-..1


В первой строке — элементы исходного множества. Дальше — табличка с данными для отсечения. В первом столбце — проверяемое число, представление в виде суммы для которого ищется на данном шаге. В последующих столбцах — количество таких представлений. Второй столбец соответствует отсутствию элементов исходного множества, третий — наличию первого элемента, четвёртый — наличию первых двух элементов, пятый — первых трёх и так далее до последнего столбца, в котором указано количество решений при наличии всех элементов исходного множества. Количество решений я посчитал с повторами из-за одинаковых элементов, но это не важно, важен сам факт равенства нулю элемента или неравенство. Нулевые элементы для наглядности заменены прочерками.

Теперь алгоритм. Мы берём последний оставшийся элемент исходного множества и вычитаем его из какой-нибудь целевой суммы. Это влияет не только на уменьшенную сумму, но и на нетронутые, так как с использованием этого элемента для не той суммы, может потеряться возможность представления какой-нибудь другой целевой суммы. Чтобы это отсеять мы берём соответствующий столбик и поверяем, что для всех остатков целевых сумм ещё существует хотя бы одно решение. Если это не так, то отматываем назад и пробуем вычесть текущий элемент из другой суммы. Разумеется, при этом мы не можем сделать сумму меньше нуля.

В общем, алгоритм-то я придумал, но его ещё надо реализовать. Между словом и делом — промежуток временной. Надеюсь, этого механизма отсечений будет достаточно для эффективного поиска.

 Профиль  
                  
 
 Re: Особый алгоритм перебора всех подмножеств мультимножества
Сообщение07.02.2018, 02:48 
Заслуженный участник


27/04/09
28128
B@R5uk в сообщении #1290637 писал(а):
Теперь алгоритм. Мы берём последний оставшийся элемент исходного множества и вычитаем его из какой-нибудь целевой суммы. Это влияет не только на уменьшенную сумму, но и на нетронутые, так как с использованием этого элемента для не той суммы, может потеряться возможность представления какой-нибудь другой целевой суммы. Чтобы это отсеять мы берём соответствующий столбик и поверяем, что для всех остатков целевых сумм ещё существует хотя бы одно решение. Если это не так, то отматываем назад и пробуем вычесть текущий элемент из другой суммы. Разумеется, при этом мы не можем сделать сумму меньше нуля.
Вот! Поздравляю. Это именно то обобщение, которое я имел в виду, когда узнал про вторую задачу. Видимо, с выражением мыслей у меня совсем плохо иногда. :-)

Надеюсь, что его хватит, чтобы побить время.

 Профиль  
                  
 
 Re: Особый алгоритм перебора всех подмножеств мультимножества
Сообщение07.02.2018, 10:00 
Аватара пользователя


26/05/12
1534
приходит весна?
arseniiv в сообщении #1290695 писал(а):
Видимо, с выражением мыслей у меня совсем плохо иногда.
Ну, не, вы совершенно верно сказали:
arseniiv в сообщении #1290619 писал(а):
все элементы распределяются по всем рюкзакам модификацией алгоритма с одним рюкзаком, чтобы числа вхождений 0 и 1 переинтерпретировались как рюкзак, в который мы распределили элемент
Даже поиск в глубину имеет некоторый порядок перебора (интересно, делает ли этот факт предыдущий алгоритм тоже поиском в глубину). И в практической реализации алгоритма, действительно появляется массив, где для каждого элемента исходного множества записан номер суммы, в которую этот элемент отправляется.

Я не согласился (и был прав), в том, что порядок перебора в текущем алгоритме не имеет ничего нового с порядком перебора в старом (однорюкзачном). И механизм отсечений планируется тоже совершенно иной (хотя одно из отсечений, где сумму нельзя уменьшить ниже нуля, — очень похожее отсечение). Я уже реализовал простейший алгоритм. В нём порядок перебора получился самый обыденный: позиционная запись с последовательным инкрементом индексов сумм и переносами в следующий разряд, если все суммы в текущем перебраны. Алгоритм сейчас чуть-чуть лучше лобового брутфорса с перебором $N^M$ вариантов (где $N$ — число сумм, а $M$ — число элементов, из которых их надо составить) за счёт того, что как раз производится отсечение ситуаций, где из остатка суммы запрещается вычитать слагаемое, большее остатка.

Ключевое отсечение пока не реализовывал. Но результаты кое-какие уже есть:

(ПРИМЕР РАЗ)

Values = [2, 10, 10, 11, 16, 16, 18, 21]
Taget sums = [39, 32, 33]

RESULT = [2, 2, 2, 2, 1, 1, 0, 0]
RESULT = [2, 2, 0, 0, 1, 1, 0, 2]
RESULT = [2, 0, 2, 0, 1, 1, 0, 2]

(ПРИМЕР ДВА)

Values = [1, 2, 3, 3, 3]
Taget sums = [6, 6]

RESULT = [1, 1, 1, 0, 0]
RESULT = [1, 1, 0, 1, 0]
RESULT = [0, 0, 1, 1, 0]
RESULT = [1, 1, 0, 0, 1]
RESULT = [0, 0, 1, 0, 1]
RESULT = [0, 0, 0, 1, 1]

(ПРИМЕР ТРИ)

Values = [4, 4, 6, 6, 6, 6, 7, 7, 7]
Taget sums = [16, 20, 17]

RESULT = [2, 0, 2, 1, 0, 0, 2, 1, 1]
RESULT = [0, 2, 2, 1, 0, 0, 2, 1, 1]
RESULT = [2, 0, 1, 2, 0, 0, 2, 1, 1]
RESULT = [0, 2, 1, 2, 0, 0, 2, 1, 1]
RESULT = [2, 0, 2, 0, 1, 0, 2, 1, 1]
RESULT = [0, 2, 2, 0, 1, 0, 2, 1, 1]
RESULT = [2, 0, 0, 2, 1, 0, 2, 1, 1]
RESULT = [0, 2, 0, 2, 1, 0, 2, 1, 1]
RESULT = [2, 0, 1, 0, 2, 0, 2, 1, 1]
RESULT = [0, 2, 1, 0, 2, 0, 2, 1, 1]
RESULT = [2, 0, 0, 1, 2, 0, 2, 1, 1]
RESULT = [0, 2, 0, 1, 2, 0, 2, 1, 1]
RESULT = [2, 0, 2, 0, 0, 1, 2, 1, 1]
RESULT = [0, 2, 2, 0, 0, 1, 2, 1, 1]
RESULT = [2, 0, 0, 2, 0, 1, 2, 1, 1]
RESULT = [0, 2, 0, 2, 0, 1, 2, 1, 1]
RESULT = [2, 0, 0, 0, 2, 1, 2, 1, 1]
RESULT = [0, 2, 0, 0, 2, 1, 2, 1, 1]
RESULT = [2, 0, 1, 0, 0, 2, 2, 1, 1]
RESULT = [0, 2, 1, 0, 0, 2, 2, 1, 1]
RESULT = [2, 0, 0, 1, 0, 2, 2, 1, 1]
RESULT = [0, 2, 0, 1, 0, 2, 2, 1, 1]
RESULT = [2, 0, 0, 0, 1, 2, 2, 1, 1]
RESULT = [0, 2, 0, 0, 1, 2, 2, 1, 1]
RESULT = [2, 0, 2, 1, 0, 0, 1, 2, 1]
RESULT = [0, 2, 2, 1, 0, 0, 1, 2, 1]
RESULT = [2, 0, 1, 2, 0, 0, 1, 2, 1]
RESULT = [0, 2, 1, 2, 0, 0, 1, 2, 1]
RESULT = [2, 0, 2, 0, 1, 0, 1, 2, 1]
RESULT = [0, 2, 2, 0, 1, 0, 1, 2, 1]
RESULT = [2, 0, 0, 2, 1, 0, 1, 2, 1]
RESULT = [0, 2, 0, 2, 1, 0, 1, 2, 1]
RESULT = [2, 0, 1, 0, 2, 0, 1, 2, 1]
RESULT = [0, 2, 1, 0, 2, 0, 1, 2, 1]
RESULT = [2, 0, 0, 1, 2, 0, 1, 2, 1]
RESULT = [0, 2, 0, 1, 2, 0, 1, 2, 1]
RESULT = [2, 0, 2, 0, 0, 1, 1, 2, 1]
RESULT = [0, 2, 2, 0, 0, 1, 1, 2, 1]
RESULT = [2, 0, 0, 2, 0, 1, 1, 2, 1]
RESULT = [0, 2, 0, 2, 0, 1, 1, 2, 1]
RESULT = [2, 0, 0, 0, 2, 1, 1, 2, 1]
RESULT = [0, 2, 0, 0, 2, 1, 1, 2, 1]
RESULT = [2, 0, 1, 0, 0, 2, 1, 2, 1]
RESULT = [0, 2, 1, 0, 0, 2, 1, 2, 1]
RESULT = [2, 0, 0, 1, 0, 2, 1, 2, 1]
RESULT = [0, 2, 0, 1, 0, 2, 1, 2, 1]
RESULT = [2, 0, 0, 0, 1, 2, 1, 2, 1]
RESULT = [0, 2, 0, 0, 1, 2, 1, 2, 1]
RESULT = [2, 0, 2, 1, 0, 0, 1, 1, 2]
RESULT = [0, 2, 2, 1, 0, 0, 1, 1, 2]
RESULT = [2, 0, 1, 2, 0, 0, 1, 1, 2]
RESULT = [0, 2, 1, 2, 0, 0, 1, 1, 2]
RESULT = [2, 0, 2, 0, 1, 0, 1, 1, 2]
RESULT = [0, 2, 2, 0, 1, 0, 1, 1, 2]
RESULT = [2, 0, 0, 2, 1, 0, 1, 1, 2]
RESULT = [0, 2, 0, 2, 1, 0, 1, 1, 2]
RESULT = [2, 0, 1, 0, 2, 0, 1, 1, 2]
RESULT = [0, 2, 1, 0, 2, 0, 1, 1, 2]
RESULT = [2, 0, 0, 1, 2, 0, 1, 1, 2]
RESULT = [0, 2, 0, 1, 2, 0, 1, 1, 2]
RESULT = [2, 0, 2, 0, 0, 1, 1, 1, 2]
RESULT = [0, 2, 2, 0, 0, 1, 1, 1, 2]
RESULT = [2, 0, 0, 2, 0, 1, 1, 1, 2]
RESULT = [0, 2, 0, 2, 0, 1, 1, 1, 2]
RESULT = [2, 0, 0, 0, 2, 1, 1, 1, 2]
RESULT = [0, 2, 0, 0, 2, 1, 1, 1, 2]
RESULT = [2, 0, 1, 0, 0, 2, 1, 1, 2]
RESULT = [0, 2, 1, 0, 0, 2, 1, 1, 2]
RESULT = [2, 0, 0, 1, 0, 2, 1, 1, 2]
RESULT = [0, 2, 0, 1, 0, 2, 1, 1, 2]
RESULT = [2, 0, 0, 0, 1, 2, 1, 1, 2]
RESULT = [0, 2, 0, 0, 1, 2, 1, 1, 2]

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

Код на данный момент такой:
код: [ скачать ] [ спрятать ]
Используется синтаксис Java
import java.util.*;

public class StudyKnapsackProblem {
       
        private static int[] values = new int[]
//                      {4, 4, 6, 6, 6, 6, 7, 7, 7};
//                      {2, 10, 10, 11, 16, 16, 18, 21};
//                      {6, 6, 6, 13, 13, 22, 22, 22, 22, 46, 46, 48, 48};
//                      {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
                        {1, 2, 3, 3, 3};
        private static int[] tagetSums = new int[]
//                      {16, 20, 17};
//                      {39, 32, 33};
//                      {74, 81, 89, 76};
//                      {12, 13, 14, 16};
                        {6, 6};
        public static void main(String[] args) {
                int valuesNumber, sumsNumber, index, value, sum, sumIndex;
                int[] sumIndices, sums;
                boolean isDebug;
                System.out.print("Values = ");
                System.out.println(Arrays.toString(values));
                System.out.print("Taget sums = ");
                System.out.println(Arrays.toString(tagetSums));
                System.out.println();
                valuesNumber = values.length;
                sumsNumber = tagetSums.length;
                sumIndices = new int[valuesNumber];
                sums = Arrays.copyOf(tagetSums, sumsNumber);
                index = valuesNumber - 1;
                isDebug = false;
                while (true) {
                        sumIndex = sumIndices[index];
                        if (isDebug) {
                                System.out.print("index = ");
                                System.out.println(index);
                                System.out.print("sums = ");
                                System.out.println(Arrays.toString(sums));
                                System.out.print("sumIndex = ");
                                System.out.println(sumIndex);
                        }
                        if (sumsNumber == sumIndex) {
                                ++index;
                                if (valuesNumber == index) {
                                        break;
                                }
                                sumIndex = sumIndices[index];
                                sums[sumIndex] += values[index];
                                ++sumIndex;
                                sumIndices[index] = sumIndex;
                        } else {
                                value = values[index];
                                sum = sums[sumIndex];
                                if (isDebug) {
                                        System.out.print("value = ");
                                        System.out.println(value);
                                        System.out.print("sumIndices = [");
                                        display(sumIndices, index);
                                        System.out.println("]");
                                }
                                if (sum >= value) {
                                        sums[sumIndex] = sum - value;
                                        if (0 != index) {
                                                --index;
                                                sumIndices[index] = 0;
                                        } else {
                                                if (isDebug) {
                                                        System.out.println();
                                                }
                                                System.out.print("RESULT = ");
                                                System.out.println(Arrays.toString(sumIndices));
                                                sums[sumIndex] += value;
                                                ++sumIndex;
                                                sumIndices[index] = sumIndex;
                                        }
                                } else {
                                        ++sumIndex;
                                        sumIndices[index] = sumIndex;
                                }
                        }
                        if (isDebug) {
                                System.out.println();
                        }
                }
        }
       
        private static void display(int[] data, int index) {
                int n, size;
                size = data.length;
                for (n = 0; size > n; ++n) {
                        if (0 != n) {
                                System.out.print(", ");
                        }
                        if (index >= n) {
                                System.out.print("?");
                        } else {
                                System.out.print(data[n]);
                        }
                }
        }
}
 

 Профиль  
                  
 
 Re: Особый алгоритм перебора всех подмножеств мультимножества
Сообщение07.02.2018, 12:13 
Заслуженный участник


27/04/09
28128
B@R5uk в сообщении #1290728 писал(а):
Даже поиск в глубину имеет некоторый порядок перебора (интересно, делает ли этот факт предыдущий алгоритм тоже поиском в глубину).
Все, где упоминалось дерево — точно такие.

B@R5uk в сообщении #1290728 писал(а):
И механизм отсечений планируется тоже совершенно иной (хотя одно из отсечений, где сумму нельзя уменьшить ниже нуля, — очень похожее отсечение).
А отсечение слишком большого для помещения в рюкзак элемента ведь тоже очень похожее.

B@R5uk в сообщении #1290728 писал(а):
Но из-за повторяющихся элементов есть повторы решений. Это, в частности, замедляет поиск, поскольку приходится перебирать комбинации, которые уже были перебраны. Вот, думаю: как бы это исправить?
Самый прямой видимый способ — опять перейти от двоичного «входит — не входит» к степени вхождения. Это значит, что $n$ повторяющимся элементам соответствует мультимножество мощности $n$ рюкзаков. У мультимножеств элементов линейно упорядоченного множества есть удобное представление: перечислить все элементы в порядке возрастания с учётом кратностей. Перебирать все возможные неубывающие последовательности длины $n$ не так трудно; по конкретному перечислению можно сделать какие-то выводы об алгоритме:

код: [ скачать ] [ спрятать ]
Используется синтаксис Text
0000
0001
0002
0003
0011
0012
0013
0022
0023
0033
0111
0112
0113
0122
0123
0133
0222
0223
0233
0333
1111
1112
1113
1122
1123
1133
1222
1223
1233
1333
2222
2223
2233
2333
3333

Как видите, разница с перечислением ничем не ограниченных последовательностей в том, что при увеличении старшего разряда все младшие заполняются им, а не нулями.

В целом получится перечисление наборов вот таких в общем случае «списочных» цифр вместо перечисления наборов отдельных цифр; ну и, конечно, для элементов, повторяющихся один раз, получится то же самое — список из одной цифры инкрементируется и переполняется ровно так же. (Именно, мне кажется, стоит инкапсулировать такие списки и дать им по крайней мере метод инкремента, возвращающий статус переполнения — и может даже не понадобиться метод обнуления, которое нужно будет делать только в конструкторе.)

 Профиль  
                  
 
 Re: Особый алгоритм перебора всех подмножеств мультимножества
Сообщение07.02.2018, 12:40 
Аватара пользователя


26/05/12
1534
приходит весна?
arseniiv в сообщении #1290753 писал(а):
разница с перечислением ничем не ограниченных последовательностей в том, что при увеличении старшего разряда все младшие заполняются им, а не нулями.
Да, я к такому же выводу пришёл. Вот наглядный пример того, как сейчас мой алгоритм перебирал бы (если отключить отсечения) три одинаковых элемента, размещая их по трём суммам:

(ПРИМЕР)

000
100
200
010 -> 100
110
210
020 -> 200
120 -> 210
220
001 -> 100
101 -> 110
201 -> 201
011 -> 110
111
211
021 -> 210
121 -> 211
221
002 -> 200
102 -> 210
202 -> 220
012 -> 210
112 -> 211
212 -> 221
022 -> 220
122 -> 221
222

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

-- 07.02.2018, 12:51 --

arseniiv в сообщении #1290753 писал(а):
В целом получится перечисление наборов вот таких в общем случае «списочных» цифр вместо перечисления наборов отдельных цифр
Мне кажется это слишком сложно. Лучше обойтись обычными цифрами, лишь поправив порядок их перебора соответствующим образом.

arseniiv в сообщении #1290753 писал(а):
А отсечение слишком большого для помещения в рюкзак элемента ведь тоже очень похожее.
Да, однозначно есть такое и там, и тут.

Хотел, кстати, тут составить статистику и посчитать число комбинаций, получающихся с учётом повторяющихся элементов. Но что-то туплю никак не могу понять, что это будет за величина в самом простом случае: $n$ одинаковых элементов, размещаемых по $m$ корзинам. Есть подозрение, что это должно быть что-то вроде биномиального коэффициента, но для моего примера выше, где $n=3$ и $m=3$, этот коэффициент равен 10, а в вашем примере (с $n=4$ и $m=4$) — 35. $C_m^{n+m-1}$ или $C_n^{n+m-1}$ что ли? Откуда он такой берётся и почему он меньше, чем $m^n$?

 Профиль  
                  
 
 Re: Особый алгоритм перебора всех подмножеств мультимножества
Сообщение07.02.2018, 17:20 
Заслуженный участник


27/04/09
28128
B@R5uk в сообщении #1290760 писал(а):
Лучше обойтись обычными цифрами, лишь поправив порядок их перебора соответствующим образом.
И как вы будете следить за тем, где заканчиваются разряды, которые не надо трогать? Ну, конечно, можно завести массив индексов, по которым проходят границы блоков для каждого набора одинаковых элементов, но это будет то же самое, просто записано менее прозрачно. Вряд ли накладные расходы от выделения класса для упорядоченного списка и операций с ним как-то скажутся на времени.

B@R5uk в сообщении #1290760 писал(а):
Откуда он такой берётся
Это объяснить просто: преобразуем список, превратив его в диаграмму мультимножества. Сначала возьмём (первую) конечную разность списка, потом заменим каждое число в ней на столько же палочек | и одну звёздочку *, и допишем недостающее число палок в конец. Диаграмма показывает, как элементы, изображённые *, разделены между последовательными мультимножествами, разделёнными |. Пример:

Используется синтаксис Text
000  →  000(2)  →  ***||
001  →  001(1)  →  **|*|
002  →  002     →  **||*
011  →  010(1)  →  *|**|
012  →  011     →  *|*|*
022  →  020     →  *||**
111  →  100(1)  →  |***|
112  →  101     →  |**|*
122  →  110     →  |*|**
222  →  200     →  ||***

А вот теперь вы видите сочетания.

-- Ср фев 07, 2018 19:22:05 --

Я там попутал разные мультимножества между собой, но, надеюсь, понятно, где что. Обозначения надо бы ввести нам на будущее.

 Профиль  
                  
 
 Re: Особый алгоритм перебора всех подмножеств мультимножества
Сообщение07.02.2018, 19:32 
Аватара пользователя


26/05/12
1534
приходит весна?
arseniiv в сообщении #1290847 писал(а):
А вот теперь вы видите сочетания.
Красота! То есть всё-таки формула для числа комбинаций будет $C_{n}^{n+m-1}=C_{m-1}^{n+m-1}$. $$C_{n}^{n+m-1}=\frac{\left( n+m-1 \right)!}{n!\left( m-1 \right)!}=\frac{\left( n+m-1 \right)\left( n+m-2 \right)\ldots \left( n+2 \right)\left( n+1 \right)}{\left( m-1 \right)\left( m-2 \right)\ldots 2\cdot 1}$$Не понятно, как получается, что $C_{n}^{n+m-1}\le m^n$ (причём равенство достигается при $n=1$ или $m=1$). Ну да ладно, всё равно я тут подумал: количество итераций слабо перекликается с потенциальным числом перебираемых комбинаций, так как на сборку целой комбинации уходит несколько итераций, плюс не все комбинации собираются до конца, плюс не все начинают собираться с нуля как в случае брутфорса в лоб и плюс ещё нужны итерации для деконструкции комбинации (даже если она не собрана полностью).

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

-- 07.02.2018, 19:45 --

arseniiv в сообщении #1290847 писал(а):
И как вы будете следить за тем, где заканчиваются разряды, которые не надо трогать?
Ну, я же выше уже расписал алгоритм, может и не очень понятно/подробно. При переходе к новой ячейке массива возможны два действия:
1) в ячейку копируется содержимое предыдущей;
2) в ячейку заносится ноль.
Первое действие выполняется, если соответствующий новый элемент исходного множества равен предыдущему, а в противном случае — второе. Чтобы не сравнивать каждый раз элементы множества можно завести булевый массив и заполнить его перед началом перебора. Вот наглядный пример того, как это работает (здесь все элементы одинаковы, поэтому происходит только копирование):

(ПРИМЕР)

****
***0
**00
*000
0000
1000
2000
*100
1100
2100
*200
1200
2200
*200
**10
*110
1110
2110
*210
2210
*210
**20
*220
2220
*220
**20
***1
**11
*111
1111
2111
*211
2211
*211
**21
*221
2221
*221
**21
***2
**22
*222
2222

 Профиль  
                  
 
 Re: Особый алгоритм перебора всех подмножеств мультимножества
Сообщение08.02.2018, 20:16 
Аватара пользователя


26/05/12
1534
приходит весна?
Мда. Идея с отсечениями по предварительно посчитанным решениям была обнадёживающей, и она действительно дала определённый результат, но это не тот случай, где ускорение происходит не в разы, а принципиально. Решение всё ещё даже не показалось на горизонте. Вот удачный неудачный код:

Заголовочный класс:
код: [ скачать ] [ спрятать ]
Используется синтаксис Java
import java.util.*;

public class StudyKnapsackProblem3 {
       
        private static int[] values = new int[]
//                      {4, 4, 6, 6, 6, 6, 7, 7, 7, 8};
//                      {2, 10, 10, 11, 16, 16, 18, 21};
                        {5, 6, 6, 6, 6, 13, 13, 22, 22, 22, 46, 46, 48, 48, 48, 49};
//                      {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
//                      {1, 2, 3, 3, 3, 4};
//                      {9, 9, 9, 9, 9, 14, 14, 34, 34, 34, 34, 34, 42, 42, 42, 42, 42, 47, 49, 57, 66, 68, 68, 68, 68, 71, 71, 71, 71, 71, 74, 74, 97, 97, 97, 97, 97, 97, 97, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100};
        private static int[] tagetSums = new int[]
//                      {16, 20, 25};
//                      {39, 32, 33};
                        {101, 86, 95, 124};
//                      {12, 13, 14, 16};
//                      {7, 9};
//                      {227, 235, 264, 292, 298, 322, 327, 341, 820};
        public static void main(String[] args) {
                int n, valuesNumber, sumsNumber, index, sumIndex;
                int value, lastValue, sum, maxSum;
                int iterationsCount, solutionsCount;
                int[] sumIndices, sums;
                SolutionChecker checker;
                boolean[] repetitionFlags;
                System.out.print("Values = ");
                System.out.println(Arrays.toString(values));
                System.out.print("Taget sums = ");
                System.out.println(Arrays.toString(tagetSums));
                System.out.println();
                valuesNumber = values.length;
                sumsNumber = tagetSums.length;
                sumIndices = new int[valuesNumber];
                sums = Arrays.copyOf(tagetSums, sumsNumber);
                repetitionFlags = new boolean[valuesNumber];
                value = values[valuesNumber - 1];
                for (n = valuesNumber - 2; 0 <= n; --n) {
                        lastValue = value;
                        value = values[n];
                        repetitionFlags[n] = lastValue == value;
                }
                maxSum = sums[0];
                for (n = 1; sumsNumber > n; ++n) {
                        sum = sums[n];
                        if (maxSum < sum) {
                                maxSum = sum;
                        }
                }
                checker = new SolutionChecker(values, maxSum);
                index = valuesNumber - 1;
                iterationsCount = 0;
                solutionsCount = 0;
                while (true) {
                        ++iterationsCount;
                        sumIndex = sumIndices[index];
                        if (sumsNumber == sumIndex) {
                                ++index;
                                if (valuesNumber == index) {
                                        break;
                                }
                                sumIndex = sumIndices[index];
                                sums[sumIndex] += values[index];
                                ++sumIndex;
                                sumIndices[index] = sumIndex;
                        } else {
                                value = values[index];
                                sum = sums[sumIndex];
                                if (sum >= value) {
                                        sums[sumIndex] = sum - value;
                                        if (0 != index) {
                                                if (checker.isPassable(sums, index)) {
                                                        --index;
                                                        if (repetitionFlags[index]) {
                                                                sumIndices[index] = sumIndex;
                                                        } else {
                                                                sumIndices[index] = 0;
                                                        }
                                                } else {
                                                        sums[sumIndex] = sum;
                                                        ++sumIndex;
                                                        sumIndices[index] = sumIndex;
                                                }
                                        } else {
                                                ++solutionsCount;
                                                System.out.print("RESULT = ");
                                                System.out.println(Arrays.toString(sumIndices));
                                                sums[sumIndex] += value;
                                                ++sumIndex;
                                                sumIndices[index] = sumIndex;
                                        }
                                } else {
                                        ++sumIndex;
                                        sumIndices[index] = sumIndex;
                                }
                        }
                }
                System.out.println();
                System.out.print("Solutions found: ");
                System.out.println(solutionsCount);
                System.out.print("Iterations made: ");
                System.out.println(iterationsCount);
        }
}
 


Вспомогательный класс:
код: [ скачать ] [ спрятать ]
Используется синтаксис Java
public class SolutionChecker {
        private boolean[][] flags;
       
        public SolutionChecker(int[] values, int size) {
                int n, m, number, value, count;
                int[][] counts;
                number = values.length;
                counts = new int[number + 1][size + 1];
                counts[0][0] = 1;
                for (n = 0; number > n; ++n) {
                        value = values[n];
                        for (m = 0; size >= m; ++m) {
                                count = counts[n][m];
                                if (value > m) {
                                        counts[n + 1][m] = count;
                                } else {
                                        counts[n + 1][m] = count + counts[n][m - value];
                                }
                        }
                }
                flags = new boolean[number + 1][size + 1];
                for (n = 0; number >= n; ++n) {
                        for (m = 0; size >= m; ++m) {
                                flags[n][m] = 0 == counts[n][m];
                        }
                }
        }
       
        public boolean isPassable(int[] values, int index) {
                int number = values.length;
                for (int n = 0; number > n; ++n) {
                        if (flags[index][values[n]]) {
                                return false;
                        }
                }
                return true;
        }
}
 

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

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

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


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

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