Улучшение результатов в заданном разделе, чем различие

Ответ 1

Для того, что бы это ни стоило, простая, неоптимизированная реализация Python процедуры "полного поиска Кармарка Карпа" (CKK) в [Korf88] - незначительно изменилась, чтобы спастись от поиска по заданному сроку (скажем, 4.95 секунд) и вернуть лучшее решение, найденное до сих пор, - достаточно, чтобы забить 14.204234 по проблеме SPOJ, обыграв счет за Кармаркар-Карп. На момент написания этой статьи это # 3 в рейтинге (см. Редактировать # 2 ниже)

Несколько более читаемое представление алгоритма KorfKKK можно найти в [Mert99].

РЕДАКТИРОВАТЬ № 2. Я реализовал гибридную эвристику Евгения Клуева, применяя Кармаркар-Карп до тех пор, пока список чисел не будет ниже некоторого порога а затем переход к точному методу перечисления подмножества Горовица-Сахни [HS74] (краткое описание можно найти в [Korf88]). Как и предполагалось, моя реализация Python потребовала снижения порога переключения в сравнении с его реализацией на С++. С некоторыми проб и ошибок я обнаружил, что порог 37 был максимальным, что позволило моей программе закончить в течение срока. Тем не менее, даже на этом нижнем пороге мне удалось достичь показателя 15.265633, достаточно хорошего для второе место,

Я также попытался включить этот гибридный метод KK/HS в поиск дерева CKK, в основном используя HS как очень агрессивную и дорогостоящую стратегию обрезки. В простой CKK мне не удалось найти порог переключения, который даже соответствовал методу KK/HS. Однако, используя стратегию поиска ILC (см. Ниже) для CKK и HS (с порогом 25), я смог добиться очень небольшого выигрыша по сравнению с предыдущим счетом, до 15.272802. Вероятно, не удивительно, что CKK + ILDS в этом контексте превосходит обычный CKK, поскольку он будет, по своему усмотрению, обеспечивать большее разнообразие входных данных для фазы HS.

РЕДАКТИРОВАТЬ № 1 - Я пробовал еще два уточнения базового алгоритма CKK:

• "Улучшен поиск с ограниченным расхождением" (ILDS) [Korf96] Это альтернатива естественному упорядочению путей DFS в дереве поиска. Он имеет тенденцию исследовать более разнообразные решения ранее, чем регулярный поиск по глубине.

• "Ускорение двухстороннего разделения номеров" [Cerq12] Это обобщает один из критериев отсечения в CKK из узлов в пределах 4 уровней листовых узлов до узлов в пределах 5, 6 и 7 уровней над листовыми узлами.

В моих тестовых случаях оба эти усовершенствования обычно обеспечивали заметные преимущества по сравнению с исходным CKK в сокращении числа исследованных узлов (в случае последнего) и в более ранних решениях (в случае первого), Однако в рамках структуры проблем SPOJ ни один из них не был достаточным для улучшения моей оценки.

Учитывая специфический характер этой проблемы SPOJ (т.е. 5-секундный временной интервал и только один конкретный и нераскрытый экземпляр проблемы), трудно дать совет относительно того, что может фактически улучшить оценку ^* Например, следует ли нам продолжать проводить альтернативные стратегии упорядочения поиска (например, многие из статей Уилера Румля перечисленные здесь)? Или мы должны попытаться включить какую-то форму эвристики локального улучшения в решения, найденные CKK, чтобы помочь обрезать? Или, может быть, нам следует отказаться от подходов на основе CKK и попытаться использовать динамический подход к программированию? Как насчет PTAS? Не зная больше о конкретной форме экземпляра, используемого в проблеме SPOJ, очень сложно догадаться, какой подход будет приносить наибольшую пользу. Каждый из них имеет свои сильные и слабые стороны, в зависимости от конкретных свойств данного экземпляра.

^* Помимо простого запуска того же самого действия быстрее, скажем, путем реализации в С++ вместо Python.

Ссылки

[Cerq12] Cerquides, Хесус и Педро Месегер. "Ускорение двухстороннего разделения номеров". ECAI. 2012, doi: 10.3233/978-1-61499-098-7-223

[HS74] Горовиц, Эллис и Сартай Сахни. " Вычисление разделов с приложениями в проблему с рюкзаком." Журнал ACM (JACM) 21.2 (1974): 277-292.

[Korf88] Korf, Richard E. (1998), " Полный алгоритм для разбиения чисел, Искусственный интеллект 106 (2 ): 181-203, doi: 10.1016/S0004-3702 (98) 00086-1,

[Korf96] Корф, Ричард Э. " Улучшен поиск ограниченного расхождения." AAAI/IAAI, Vol. 1. 1996.

[Mert99] Mertens, Stephan (1999), полный алгоритм для сбалансированного разбиения чисел, arXiv: cs/9903011

Ответ 2

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

• "Полный алгоритм для разбивки чисел" Ричардом Э. Корфом.
• "Эффективная полностью полиномиальная схема аппроксимации для проблемы подмножества сумм" от Hans Kellerer и др.

Честно говоря, я не знаю, какие из них дают более эффективное решение. Вероятно, ни один из этих передовых алгоритмов не требуется для решения этой проблемы SPOJ. Бумага Korf по-прежнему очень полезна. Алгоритмы, описанные там, очень просты (чтобы понять и реализовать). Также он рассматривает несколько еще более простых алгоритмов (в разделе 2). Поэтому, если вы хотите узнать подробности методов Горовица-Сахни или Шреппеля-Шамира (см. Ниже), вы можете найти их в бумаге Корфа. Также (в разделе 8) он пишет, что стохастические подходы не обеспечивают достаточно хороших решений. Поэтому маловероятно, что вы получите значительные улучшения с чем-то вроде восхождения на холм, симулированного отжига или поиска табу.

Я попробовал несколько простых алгоритмов и их комбинации для решения проблем секционирования с размером до 10000, максимальное значение до 10 ¹⁴ и ограничение по времени 4 сек. Они были протестированы на случайных равномерно распределенных числах. И оптимальное решение было найдено для каждого экземпляра проблемы, который я пробовал. Для некоторых задач вероятность оптимальности гарантируется алгоритмом, для других оптимальность не гарантируется на 100%, но вероятность получения субоптимального решения очень мала.

Для размеров до 4 (зеленая область слева) алгоритм Кармаркар-Карпа всегда дает оптимальный результат.

Для размеров до 54 алгоритм грубой силы достаточно быстр (красная область). Существует выбор между алгоритмами Горовица-Сахни или Шреппеля-Шамира. Я использовал Горовиц-Сахни, потому что он кажется более эффективным для заданных пределов. Schroeppel-Shamir использует гораздо меньше памяти (все вписывается в кэш L2), поэтому может быть предпочтительнее, когда другие ядра процессора выполняют некоторые задачи с интенсивной памятью или могут выполнять разделение с использованием нескольких потоков. Или решать большие проблемы не с жестким временным ограничением (где у Горовица-Сахни просто заканчивается память).

Когда размер, умноженный на сумму всех значений, меньше 5 * 10 ⁹ (синяя область), применим подход динамического программирования. Граница между грубой силой и динамическими зонами программирования на диаграмме показывает, где каждый алгоритм работает лучше.

Зеленая область справа - это место, где алгоритм Кармаркар-Карпа дает оптимальный результат с почти 100-процентной вероятностью. Здесь существует так много идеальных вариантов разбиения (с дельтами 0 или 1), что алгоритм Кармаркар-Карпа почти наверняка найдет один из них. Можно создать набор данных, где Кармаркар-Карп всегда дает субоптимальный результат. Например {17 13 10 10 10...}. Если вы умножите это на некоторое большое число, ни KK, ни DP не смогут найти оптимальное решение. К счастью, такие наборы данных на практике маловероятны. Но задатчик может добавить такой набор данных, чтобы сделать конкурс более сложным. В этом случае вы можете выбрать какой-то продвинутый алгоритм для улучшения результатов (но только для серых и зеленых зон на диаграмме).

Я попробовал два способа реализации очереди приоритетов алгоритма Кармаркар-Карпа: с максимальной кучей и с отсортированным массивом. Опция Sorted array выглядит немного быстрее при линейном поиске и значительно быстрее при двоичном поиске.

Желтая область - это место, где вы можете выбирать между гарантированным оптимальным результатом (с DP) или просто оптимальным результатом с высокой вероятностью (с Кармаркар-Карпом).

Наконец, серая область, где ни один из простых алгоритмов сам по себе не дает оптимального результата. Здесь мы можем использовать Karmarkar-Karp для предварительной обработки данных до тех пор, пока они не будут применимы ни к Horowitz-Sahni, ни к динамическому программированию. В этом месте также есть много идеальных вариантов разметки, но меньше, чем в зеленой зоне, поэтому Кармаркар-Карп сам по себе мог иногда пропустить правильное разбиение. Обновление. Как отмечено в @mhum, нет необходимости внедрять алгоритм динамического программирования, чтобы заставить все работать. Горовиц-Сахни с предварительной обработкой Кармаркар-Карпа. Но для алгоритма Горовица-Сахни важно, чтобы (до почти) гарантировать оптимальное разбиение на размеры до 54 в течение указанного времени. Поэтому предпочтительнее использовать С++ или другой язык с хорошим оптимизирующим компилятором и быстрым компьютером.

Вот как я объединил Кармаркар-Карп с другими алгоритмами:

template<bool Preprocess = false>
i64 kk(const vector<i64>& values, i64 sum, Log& log)
{
    log.name("Karmarkar-Karp");
    vector<i64> pq(values.size() * 2);
    copy(begin(values), end(values), begin(pq) + values.size());
    sort(begin(pq) + values.size(), end(pq));
    auto first = end(pq);
    auto last = begin(pq) + values.size();

    while (first - last > 1)
    {
        if (Preprocess && first - last <= kHSLimit)
        {
            hs(last, first, sum, log);
            return 0;
        }
        if (Preprocess && static_cast<double>(first - last) * sum <= kDPLimit)
        {
            dp(last, first, sum, log);
            return 0;
        }
        const auto diff = *(first - 1) - *(first - 2);
        sum -= *(first - 2) * 2;
        first -= 2;
        const auto place = lower_bound(last, first, diff);
        --last;
        copy(last + 1, place, last);
        *(place - 1) = diff;
    }

    const auto result = (first - last)? *last: 0;
    log(result);
    return result;
}

Ссылка на полную реализацию С++ 11. Эта программа определяет только разницу между суммами разделов, она не сообщает сами разделы. Предупреждение:, если вы хотите запустить его на компьютере с объемом свободной памяти менее 1 Гб, уменьшите константу kHSLimit.

Ответ 3

EDIT Здесь реализация, начинающаяся с разности Кармаркар-Карпа, затем пытается оптимизировать результирующие разделы.

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

Моя реализация Кармаркар-Карпа в начале должна быть неточной, поскольку итоговый балл с помощью только Кармаркар-Карпа 2,711483 не 11.796614 пунктов, процитированных OP. При оптимизации используются оценки 7.718049.

ПРЕДУПРЕЖДЕНИЕ SPOILER Код отправки С# следует

using System;
using System.Collections.Generic;
using System.Linq;
public class Test
{
    // some comparer to lazily avoid using a proper max-heap implementation
    public class Index0 : IComparer<long[]>
    {
        public int Compare(long[] x, long[] y)
        {
            if(x[0] == y[0]) return 0;
            return x[0] < y[0] ? -1 : 1;
        }
        public static Index0 Inst = new Index0();
    }
    public class Index1 : IComparer<long[]>
    {
        public int Compare(long[] x, long[] y)
        {
            if(x[1] == y[1]) return 0;
            return x[1] < y[1] ? -1 : 1;
        }
    }

    public static void Main()
    {
        // load the data
        var start = DateTime.Now;
        var list = new List<long[]>();
        int size = int.Parse(Console.ReadLine());
        for(int i=1; i<=size; i++) {
            var tuple = new long[]{ long.Parse(Console.ReadLine()), i };
            list.Add(tuple);
        }
        list.Sort((x, y) => { if(x[0] == y[0]) return 0; return x[0] < y[0] ? -1 : 1; });

        // Karmarkar-Karp differences
        List<long[]> diffs = new List<long[]>();
        while(list.Count > 1) {
            // get max
            var b = list[list.Count - 1];
            list.RemoveAt(list.Count - 1);
            // get max
            var a = list[list.Count - 1];
            list.RemoveAt(list.Count - 1);
            // (b - a)
            var diff = b[0] - a[0];
            var tuple = new long[]{ diff, -1 };
            diffs.Add(new long[] { a[0], b[0], diff, a[1], b[1] });
            // insert (b - a) back in
            var fnd = list.BinarySearch(tuple, new Index0());
            list.Insert(fnd < 0 ? ~fnd : fnd, tuple);
        }
        var approx = list[0];
        list.Clear();

        // setup paritions
        var listA = new List<long[]>();
        var listB = new List<long[]>();
        long sumA = 0;
        long sumB = 0;

        // Karmarkar-Karp rebuild partitions from differences
        bool toggle = false;
        for(int i=diffs.Count-1; i>=0; i--) {
            var inB = listB.BinarySearch(new long[]{diffs[i][2]}, Index0.Inst);
            var inA = listA.BinarySearch(new long[]{diffs[i][2]}, Index0.Inst);
            if(inB >= 0 && inA >= 0) {
                toggle = !toggle;
            }
            if(toggle == false) {
                if(inB >= 0) {
                    listB.RemoveAt(inB);
                }else if(inA >= 0) {
                    listA.RemoveAt(inA);
                }
                var tb = new long[]{diffs[i][1], diffs[i][4]};
                var ta = new long[]{diffs[i][0], diffs[i][3]};
                var fb = listB.BinarySearch(tb, Index0.Inst);
                var fa = listA.BinarySearch(ta, Index0.Inst);
                listB.Insert(fb < 0 ? ~fb : fb, tb);
                listA.Insert(fa < 0 ? ~fa : fa, ta);
            } else {
                if(inA >= 0) {
                    listA.RemoveAt(inA);
                }else if(inB >= 0) {
                    listB.RemoveAt(inB);
                }
                var tb = new long[]{diffs[i][1], diffs[i][4]};
                var ta = new long[]{diffs[i][0], diffs[i][3]};
                var fb = listA.BinarySearch(tb, Index0.Inst);
                var fa = listB.BinarySearch(ta, Index0.Inst);
                listA.Insert(fb < 0 ? ~fb : fb, tb);
                listB.Insert(fa < 0 ? ~fa : fa, ta);
            }
        }
        listA.ForEach(a => sumA += a[0]);
        listB.ForEach(b => sumB += b[0]);

        // optimize our partitions with give/take 1 or swap 1 for 1
        bool change = false;
        while(DateTime.Now.Subtract(start).TotalSeconds < 4.8) {
            change = false;
            // give one from A to B
            for(int i=0; i<listA.Count; i++) {
                var a = listA[i];
                if(Math.Abs(sumA - sumB) > Math.Abs((sumA - a[0]) - (sumB + a[0]))) {
                    var fb = listB.BinarySearch(a, Index0.Inst);
                    listB.Insert(fb < 0 ? ~fb : fb, a);
                    listA.RemoveAt(i);
                    i--;
                    sumA -= a[0];
                    sumB += a[0];
                    change = true;
                } else {break;}
            }
            // give one from B to A
            for(int i=0; i<listB.Count; i++) {
                var b = listB[i];
                if(Math.Abs(sumA - sumB) > Math.Abs((sumA + b[0]) - (sumB - b[0]))) {
                    var fa = listA.BinarySearch(b, Index0.Inst);
                    listA.Insert(fa < 0 ? ~fa : fa, b);
                    listB.RemoveAt(i);
                    i--;
                    sumA += b[0];
                    sumB -= b[0];
                    change = true;
                } else {break;}
            }
            // swap 1 for 1
            for(int i=0; i<listA.Count; i++) {
                var a = listA[i];
                for(int j=0; j<listB.Count; j++) {
                    var b = listB[j];
                    if(Math.Abs(sumA - sumB) > Math.Abs((sumA - a[0] + b[0]) - (sumB -b[0] + a[0]))) {
                        listA.RemoveAt(i);
                        listB.RemoveAt(j);
                        var fa = listA.BinarySearch(b, Index0.Inst);
                        var fb = listB.BinarySearch(a, Index0.Inst);
                        listA.Insert(fa < 0 ? ~fa : fa, b);
                        listB.Insert(fb < 0 ? ~fb : fb, a);
                        sumA = sumA - a[0] + b[0];
                        sumB = sumB - b[0] + a[0];
                        change = true;
                        break;
                    }
                }
            }
            //
            if(change == false) { break; }
        }

        /*
        // further optimization with 2 for 1 swaps
        while(DateTime.Now.Subtract(start).TotalSeconds < 4.8) {
            change = false;
            // trade 2 for 1
            for(int i=0; i<listA.Count >> 1; i++) {
                var a1 = listA[i];
                var a2 = listA[listA.Count - 1 - i];
                for(int j=0; j<listB.Count; j++) {
                    var b = listB[j];
                    if(Math.Abs(sumA - sumB) > Math.Abs((sumA - a1[0] - a2[0] + b[0]) - (sumB - b[0] + a1[0] + a2[0]))) {
                        listA.RemoveAt(listA.Count - 1 - i);
                        listA.RemoveAt(i);
                        listB.RemoveAt(j);
                        var fa = listA.BinarySearch(b, Index0.Inst);
                        var fb1 = listB.BinarySearch(a1, Index0.Inst);
                        var fb2 = listB.BinarySearch(a2, Index0.Inst);
                        listA.Insert(fa < 0 ? ~fa : fa, b);
                        listB.Insert(fb1 < 0 ? ~fb1 : fb1, a1);
                        listB.Insert(fb2 < 0 ? ~fb2 : fb2, a2);
                        sumA = sumA - a1[0] - a2[0] + b[0];
                        sumB = sumB - b[0] + a1[0] + a2[0];
                        change = true;
                        break;
                    }
                }
            }
            //
            if(DateTime.Now.Subtract(start).TotalSeconds > 4.8) { break; }
            // trade 2 for 1
            for(int i=0; i<listB.Count >> 1; i++) {
                var b1 = listB[i];
                var b2 = listB[listB.Count - 1 - i];
                for(int j=0; j<listA.Count; j++) {
                    var a = listA[j];
                    if(Math.Abs(sumA - sumB) > Math.Abs((sumA - a[0] + b1[0] + b2[0]) - (sumB - b1[0] - b2[0] + a[0]))) {
                        listB.RemoveAt(listB.Count - 1 - i);
                        listB.RemoveAt(i);
                        listA.RemoveAt(j);
                        var fa1 = listA.BinarySearch(b1, Index0.Inst);
                        var fa2 = listA.BinarySearch(b2, Index0.Inst);
                        var fb = listB.BinarySearch(a, Index0.Inst);
                        listA.Insert(fa1 < 0 ? ~fa1 : fa1, b1);
                        listA.Insert(fa2 < 0 ? ~fa2 : fa2, b2);
                        listB.Insert(fb < 0 ? ~fb : fb, a);
                        sumA = sumA - a[0] + b1[0] + b2[0];
                        sumB = sumB - b1[0] - b2[0] + a[0];
                        change = true;
                        break;
                    }
                }
            }
            //
            if(change == false) { break; }
        }
        */

        // output the correct ordered values
        listA.Sort(new Index1());
        foreach(var t in listA) {
            Console.WriteLine(t[1]);
        }

        // DEBUG/TESTING
        //Console.WriteLine(approx[0]);
        //foreach(var t in listA) Console.Write(": " + t[0] + "," + t[1]);
        //Console.WriteLine();
        //foreach(var t in listB) Console.Write(": " + t[0] + "," + t[1]);

    }
}