VPF::оптимизация перебора - Форум программистов

Pawl

Дата 27.1.2012, 17:13 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

Уважаемые форумчане,
Долго думал, где разместить данную тему, и таки выбрал эту ветку - по 2-м причинам:
- похожий вопрос я задавал в алгоритмах, но там мне не помогли;
- код все-таки на java.
Итак, моя программа ищет рекурсивно перебором все комбинации чисел в массиве, которые бы составили заданную сумму. И она таки их находит, но ищет ДОЛГО! В массиве из 11 чисел для суммы равной 15, она подбирает значения где-то за 11 секунд. Если я не ошибаюсь, тут имеет место 2^11 = 2048 вариантов подбора, что для 3-х ядер в 2100 МГц каждое вообще не должно быть проблемой! Гляньте, пожалуйста, код, и выскажите свои соображения, можно ли в нем что-нибудь оптимизировать. Оговорюсь сразу, что надо делать именно рекурсивным перебором.
Спасибо!

Код


import java.util.*;

public class FindSumms {
    // заданная сумма
    private static final int SUM = 15;
    // заданный массив
    private static final int[] VALUES = {2, 10, 5, 3, 1, 5, 4, 8, 7, 6, 9};
    // список для хранения n-ной комбинации чисел, составляющих заданную сумму
    private static LinkedList<Integer> values = new LinkedList<Integer>();
    // список для хранения всех комбинаций чисел, составляющих заданную сумму
    private static LinkedList<LinkedList<Integer>> valuesList = new LinkedList<LinkedList<Integer>>();    
    // переменная, хранящая значение текущей суммы
    private static int sum = 0;
    
    // метод лоя поиска комбинаций чисел с заданной суммой
    public static void find(int[] v) {
        // если текущая сумма равна заданной и если такой комбинации чисел
        // еще не было, сохраняем эту комбинацию       
        if (sum == SUM && !valuesList.contains(values)) {               
            valuesList.add(new LinkedList<Integer>(values));                                     
        }
        
        // берем по очереди каждый элемент массива
        for (int i = 0; i < v.length; i++) { 
            // если s меньше SUM, увеличиваем s, в список чисел добавляется i-й элемент
            // сортируем список для последующей проверки, есть ли уже в valuesList такая комбинация
            // и вызываем рекурсию с новым массивом, из которого удаляется i-й элемент     
            if (sum < SUM) {
                sum += v[i];
                values.add(v[i]);
                Collections.sort(values);
                find(makeMas(i, v));                                         
            }
            // обнуляем сумму и очищаем список чисел                    
            sum = 0;
            values.clear();             
        }
    }

    // метод для удаления i-го элемента из массива, чтобы при рекурсивном вызове элементы не
    // суммировались сами с собой    
    private static int[] makeMas(int i, int [] m) {
        int [] nm = new int[m.length - 1];
        for (int j = 0; j < nm.length; j++) {
                nm[j] = (j < i) ? m[j] : m[j + 1];
        }
        return nm;
    }    
    
    public static void main(String[] args) {
        find(VALUES);
        // вывод всех комбинаций чисел, составляющих данную сумму
        for(LinkedList<Integer> v : valuesList) {
            System.out.println(v);
        }
    }
}

--------------------

В действительности всё совсем не так, как на самом деле

AntonSaburov

Дата 27.1.2012, 17:53 (ссылка)

(нет голосов)

Загрузка ...

Штурман

Профиль
Группа: Модератор
Сообщений: 5658
Регистрация: 2.7.2002
Где: Санкт-Петербург

Репутация: 51
Всего: 118

Я просто попробовал распечатать сколько раз вызывается метод find.
После 100 000 раз выключил задачу. Смотри в алгоритме - там явно ошибка.

--------------------

Мои проекты для Винграда

Pawl

Дата 28.1.2012, 00:00 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

Цитата(AntonSaburov @ 27.1.2012, 17:53

)

После 100 000 раз выключил задачу

Да, я подсчитал: в программе метод вызывается 96308248 раз! ПОЧЕМУ? smile

--------------------

В действительности всё совсем не так, как на самом деле

Dummy

Дата 28.1.2012, 01:46 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 263
Регистрация: 21.5.2007

Репутация: 9
Всего: 19

Странно, что алгоритмисты не помогли. Это, вроде, как раз по их части.

Помимо неправильной логики рекурсии (нет, я не знаю, где именно баг smile

), тут еще постоянно создаются новые массивы и проводится сортировка. Я накатал следующий вариант:

Код


package sum;

import java.util.ArrayList;
import java.util.Collection;

public class Sum {
    private int SUM = 10;
    private int[] VALUES = {2, 10, 5, 3, 1, 5, 4, 8, 7, 6, 9};
    private Collection<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

    public static void main(String[] args) {
        new Sum().run();
    }
    
    private void run() {     
        ArrayList<Integer> accum = new ArrayList<Integer>(VALUES.length);
        
        for (int i = 0; i < VALUES.length; i++) {
            findSummands(i, SUM, accum);
        }
        
        for (ArrayList<Integer> l : result) {
            System.out.println(l);
        }
    }
    
    private void findSummands(int startPosition, int sum, ArrayList<Integer> accum) {
        int startValue = VALUES[startPosition];
 
        if (startValue < sum) {
            sum -= startValue;

            Integer startValueObj = new Integer(startValue);
            
            accum.add(startValueObj);

            for (int i = startPosition + 1; i < VALUES.length; i++) {
                findSummands(i, sum, accum);
            }

            accum.remove(startValueObj);
        } else if (startValue == sum) {
            ArrayList<Integer> cp = new ArrayList<Integer>(accum);
            cp.add(Integer.valueOf(startValue));
            result.add(cp);
        }
    }
}

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

Это сообщение отредактировал(а) Dummy - 28.1.2012, 01:50

Mirkes

Дата 28.1.2012, 08:57 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 586
Регистрация: 18.8.2011
Где: Красноярск

Репутация: 7
Всего: 17

Прочитав логику программы я не понял, как она соотносится с поставленной задачей. Сначала пара вопросов.

Цитата(Pawl @ 27.1.2012, 17:13

)

Итак, моя программа ищет рекурсивно перебором все комбинации чисел в массиве, которые бы составили заданную сумму.

1. Если в массиве есть два числа равных 1 это разные числа?
    поясню вопрос. Пусть дан массив {1,3,1,2,2,10} нужная сумма 15
    вариант 3+2+10 может быть получен двумя способами: 1, 3, 5 элементы и 1, 4, 5 элементы
    ВНИМАНИЕ вопрос ЭТО разные решения?
    Вопрос не праздный, ответить на него можно только исходя из прикладного смысла.

2. Не взирая на ответ на первый вопрос стоит второй вопрос. Имеет ли значение порядок появления слагаемых.
    Пояснение рассмотрим решение 1+1+3+10. Его можно записать по разному (далее перечисляются индексы элементов):
    0, 1, 2, 5
    1, 0, 2, 5
    ...
    Всего 24 (6!) вариантов. Эти варианты различны с точки зрения прикладной интерпретации?

Если ответ на первый вопрос Да а на второй нет,
то следует просто иначе строить рекурсию.
Во первых параметрами будут Текущая сумма и номер последнего включенного элемента.
В самой процедуре проверяются только элементы с номерами БОЛЬШЕ текущего.

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

Если речь идет о больших массивах, то можно построить алгоритм частичного подсуммирования, но он потребует дополнительной памяти smile

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

--------------------

Mirkes

Pawl

Дата 28.1.2012, 10:15 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

Цитата(Dummy @ 28.1.2012, 01:46

)

Я накатал следующий вариант:

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

Цитата

ЭТО разные решения?

Нет, в результат должно попасть только 1 из них, но, как у меня в коде, если есть, к примеру, две пятерки, то они образуют самостоятельное решение (5, 5);
2)

Цитата

Эти варианты различны с точки зрения прикладной интерпретации?

Кажется, я понял, к чему Вы клоните. Нет, по идее они не должны быть различны, т. е., если найден один, остальные должны отсекаться. Но, похоже, у меня так не происходит...

Цитата(Dummy @ 28.1.2012, 01:46

)

Странно, что алгоритмисты не помогли.

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

--------------------

В действительности всё совсем не так, как на самом деле

Dummy

Дата 28.1.2012, 10:53 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 263
Регистрация: 21.5.2007

Репутация: 9
Всего: 19

В соответствии с уточненными условиями и рекомендациями Mirkes уточняем алгоритм:

Входной список значений сортируем
Когда найден очередной набор слагаемых, проверяем, нет ли такого же в списке

Из плюсов: не надо что-то постоянно сортировать - сортировка выполняется один раз.

Код


public class Sum {
    private int SUM = 15;
    private int[] values = {2, 10, 5, 3, 1, 5, 4, 8, 7, 6, 9};
    private int[] sortedValues;
    private Collection<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

    public static void main(String[] args) {
        new Sum().run();
    }
    
    private void run() {     
        ArrayList<Integer> accum = new ArrayList<Integer>();
        
        // Create a sorted copy of the initial array
        sortedValues = new int[values.length];
        System.arraycopy(values, 0, sortedValues, 0, values.length);
        Arrays.sort(sortedValues);
   
        // Let's rock!!!
        for (int i = 0; i < sortedValues.length; i++) {
            findSummands(i, SUM, accum);
        }
        
        // Print results
        for (ArrayList<Integer> l : result) {
            System.out.println(l);
        }
    }
    
    private void findSummands(int startPosition, int sum, ArrayList<Integer> accum) {
        int startValue = sortedValues[startPosition];
 
        if (startValue < sum) {
            sum -= startValue;

            Integer startValueObj = new Integer(startValue);
            
            accum.add(startValueObj);

            for (int i = startPosition + 1; i < sortedValues.length; i++) {
                findSummands(i, sum, accum);
            }

            accum.remove(startValueObj);
        } else if (startValue == sum) {
            ArrayList<Integer> cp = new ArrayList<Integer>(accum);
            cp.add(Integer.valueOf(startValue));
            addToResult(cp);
        }
    }

    private void addToResult(ArrayList<Integer> subresult) {
        // Check if there are existing dupes in the list
        for (ArrayList<Integer> r : result) {
            if (listsEqual(r, subresult)) {
                // A dupe found!!!
                return;
            }
        }
    
        result.add(subresult);
    }
    
    private boolean listsEqual(List<Integer> one, List<Integer> two) {
        int oneSize = one.size();
        int twoSize = two.size();

        // Different sizes mean the lists are different
        if (oneSize != twoSize) {
            return false;
        }

        // Compare lists element-wise
        for (int i = 0; i < oneSize; i++) {
            if (!one.get(i).equals(two.get(i))) {
                return false;
            }
        }

        return true;
    }
}

Это сообщение отредактировал(а) Dummy - 28.1.2012, 10:59

Pawl

Дата 28.1.2012, 11:47 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

Что же, спасибо всем за решение моей проблемы! Предложенный Dummy вариант т.ч.н. (то что надо). Ну и буду думать, что не так с моим алгоритмом! А пока тему закрываю.

--------------------

В действительности всё совсем не так, как на самом деле

Pawl

Дата 1.2.2012, 11:30 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

Согласно Вашим рекомендациям и примеру оптимизировал также свой код:

Код


import java.util.*;

public class SummFinder {
    private static final int SUM = 15;
    private static final int[] VALUES = {2, 10, 5, 3, 1, 5, 4, 15, 8, 7, 6, 9}, SORTED_VALUES  = new int[VALUES.length];
    private static List<LinkedList<Integer>> summs = new LinkedList<LinkedList<Integer>>();
    
    static {
        System.arraycopy(VALUES, 0, SORTED_VALUES, 0, VALUES.length);
        Arrays.sort(SORTED_VALUES);     
    }    

    public static void go() {     
        ArrayList<Integer> accum = new ArrayList<Integer>();
        for (int i = 0; i < SORTED_VALUES.length; i++) {
            findSumms(i, 0, accum);
        }
    }
    
    public static void findSumms(int startPos, int s, ArrayList<Integer> accum) {
     int newValue = SORTED_VALUES[startPos];
        s += newValue;
        accum.add(newValue);
               
        if (s < SUM) {
            for (int i = startPos + 1; i < SORTED_VALUES.length; i++) {
             findSumms(i, s, accum);
            }
                                                                                
        } else if (s == SUM && !summs.contains(accum)) {                    
         summs.add(new LinkedList<Integer>(accum));                                     
     }
     
     accum.remove(new Integer(newValue));                                                                             
    }
        
    public static void main(String[] args) {
        go();
        
        for(LinkedList<Integer> values : summs) {
            System.out.println(values);
        }
    }
}

даже малость покороче получилось smile

Вопрос к Dummy: почему Вы использовали ArrayList? Я читал, что

Цитата

...в ArrayList заметно быстрей (примерно на порядок)
осуществляются операции прохода по всему списку (итерации) и получения данных.
LinkedList почти на порядок быстрее осуществляет операции удаления и добавления новых
элемнтов.

И, на мой взгляд тут больше подходит LinkedList, т. к. в данном случае в accum мы постоянно добавляем и удаляем элементы.

--------------------

В действительности всё совсем не так, как на самом деле

Dummy

Дата 1.2.2012, 12:10 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 263
Регистрация: 21.5.2007

Репутация: 9
Всего: 19

Цитата(Pawl @ 1.2.2012, 11:30

)

Вопрос к Dummy: почему Вы использовали ArrayList? Я читал, что

На самом деле, машинально написал - никакого особого смысла не подразумевал smile

Возможно, LinkedList действительно здесь подойдет лучше за счет более дешевой операции добавления. Сомневаюсь, правда, что это даст большой прирост производительности. Есть такая вот ветка на Stack Overflow для общей информации: тынц

Pawl

Дата 1.2.2012, 12:14 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 649
Регистрация: 22.4.2008
Где: Витебск

Репутация: 7
Всего: 28

Спасибо, Dummy, еще раз! smile

--------------------

В действительности всё совсем не так, как на самом деле

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »