Оптимальное слияние триплетов
Я пытаюсь найти алгоритм для следующей проблемы:
У меня есть набор триплетов целых чисел - позвольте назвать эти целые числа A, B, C. Значение, хранящееся внутри, может быть большим, поэтому вообще невозможно создать массив размером A, B или C. Цель состоит в том, чтобы минимизировать размер коллекции. Для этого нам предоставлено простое правило, которое позволяет нам объединять триплеты:
- Для двух триплетов (A, B, C) и (A ', B', C ') удалите исходные триплеты и поместите триплет (A | A', B, C), если B == B 'и C = C ', где | побитовое ИЛИ. Аналогичные правила выполняются и для B и C.
Другими словами, если два значения двух триплетов равны, удалите эти два триплета, побитовые ИЛИ третьи значения и поместите результат в коллекцию.
Жадный подход обычно вводит в заблуждение в подобных случаях, и поэтому для этой проблемы я не могу найти простой контрпример, который привел бы к правильному решению. Для списка из 250 элементов, где правильное решение равно 14, средний размер, вычисленный жадным слиянием, составляет около 30 (варьируется от 20 до 70). Субоптимальные накладные расходы становятся больше по мере увеличения размера списка.
Я также пытался играть со множеством бит, но я не нашел значимых результатов. Только очевидный факт: если записи уникальны (что можно с уверенностью предположить), счетчик бит всегда увеличивается.
Здесь глупая жадная реализация (это просто концептуальная вещь, пожалуйста, не учитывайте стиль кода):
public class Record {
long A;
long B;
long C;
public static void main(String[] args) {
List<Record> data = new ArrayList<>();
// Fill it with some data
boolean found;
do {
found = false;
outer:
for (int i = 0; i < data.size(); ++i) {
for (int j = i+1; j < data.size(); ++j) {
try {
Record r = merge(data.get(i), data.get(j));
found = true;
data.remove(j);
data.remove(i);
data.add(r);
break outer;
} catch (IllegalArgumentException ignored) {
}
}
}
} while (found);
}
public static Record merge(Record r1, Record r2) {
if (r1.A == r2.A && r1.B == r2.B) {
Record r = new Record();
r.A = r1.A;
r.B = r1.B;
r.C = r1.C | r2.C;
return r;
}
if (r1.A == r2.A && r1.C == r2.C) {
Record r = new Record();
r.A = r1.A;
r.B = r1.B | r2.B;
r.C = r1.C;
return r;
}
if (r1.B == r2.B && r1.C == r2.C) {
Record r = new Record();
r.A = r1.A | r2.A;
r.B = r1.B;
r.C = r1.C;
return r;
}
throw new IllegalArgumentException("Unable to merge these two records!");
}
Есть ли у вас какие-либо идеи, как решить эту проблему?
Ответы
Ответ 1
Это будет очень длинный ответ, к сожалению, без оптимального решения (извините). Тем не менее, это серьезная попытка применить жадкое решение проблемы к вашей проблеме, поэтому она может быть полезна в принципе. Я не реализовал последний обсуждаемый подход, возможно, этот подход может дать оптимальное решение - я не могу этого гарантировать.
Уровень 0: Не очень жадный
По определению, жадный алгоритм имеет эвристику для выбора следующего шага таким образом, который является локально оптимальным, то есть оптимальным сейчас, надеясь достичь глобального оптимума, который может быть или не всегда возможен.
Ваш алгоритм выбирает любую сходящуюся пару и объединяет их, а затем переходит. Он не оценивает, что подразумевает это слияние, и есть ли лучшее локальное решение. Из-за этого я бы не назвал ваш подход жадным вообще. Это просто решение, подход. Я буду называть это слепым алгоритмом, чтобы я мог кратко описать его в своем ответе. Я также использую слегка измененную версию вашего алгоритма, которая вместо удаления двух триплетов и добавления объединенного триплета удаляет только второй триплет и заменяет первый с объединенным. Порядок полученных триплетов отличается и, следовательно, конечный результат. Позвольте мне запустить этот модифицированный алгоритм над репрезентативным набором данных, обозначив триплеты, которые будут объединены с *:
0: 3 2 3 3 2 3 3 2 3
1: 0 1 0* 0 1 2 0 1 2
2: 1 2 0 1 2 0* 1 2 1
3: 0 1 2*
4: 1 2 1 1 2 1*
5: 0 2 0 0 2 0 0 2 0
Result: 4
Уровень 1: Жадный
Чтобы иметь жадный алгоритм, вам нужно сформулировать решение о слиянии таким образом, чтобы можно было сравнивать параметры, когда доступно несколько. Для меня интуитивная формулировка решения о слиянии была:
Если я объединю эти два триплета, будет ли результирующий набор иметь максимально возможное количество слияющих триплетов по сравнению с результатом слияния любых двух других триплетов из текущего набора?
Повторяю, это интуитивно для меня. У меня нет доказательств того, что это приводит к глобально оптимальному решению, даже если это приведет к более правильному или равному решению, чем слепой алгоритм, - но оно соответствует определению жадного (и его очень легко реализовать). Попробуйте использовать этот набор данных, отображая между каждым шагом возможные слияния (путем указания индексов триплетных пар) и итоговое количество слияний для каждого возможного слияния:
mergables
0: 3 2 3 (1,3)->2
1: 0 1 0 (1,5)->1
2: 1 2 0 (2,4)->2
3: 0 1 2 (2,5)->2
4: 1 2 1
5: 0 2 0
Любой выбор, кроме слияния триплетов 1 и 5, хорош, если взять первую пару, мы получим тот же промежуточный набор, что и с слепым алгоритмом (я на этот раз скрою индексы, чтобы удалить пробелы):
mergables
0: 3 2 3 (2,3)->0
1: 0 1 2 (2,4)->1
2: 1 2 0
3: 1 2 1
4: 0 2 0
Вот где этот алгоритм использует его по-разному: он выбирает триплеты 2 и 4, потому что есть еще одно слияние после объединения их в отличие от выбора, сделанного слепым алгоритмом:
mergables
0: 3 2 3 (2,3)->0 3 2 3
1: 0 1 2 0 1 2
2: 1 2 0 1 2 1
3: 1 2 1
Result: 3
Уровень 2: Очень жадный
Теперь, второй шаг от этой интуитивной эвристики - это смотреть вперед, чтобы еще больше слить и спросить эвристический вопрос. Обобщенный, вы бы смотрели вперед k сливается дальше и применяет вышеупомянутую эвристику, назад и выбирает лучший вариант. Это становится очень многословным, поэтому, чтобы проиллюстрировать это, я буду выполнять только один шаг этой новой эвристики с помощью lookahead 1:
mergables
0: 3 2 3 (1,3)->(2,3)->0
1: 0 1 0 (2,4)->1*
2: 1 2 0 (1,5)->(2,4)->0
3: 0 1 2 (2,4)->(1,3)->0
4: 1 2 1 (1,4)->0
5: 0 2 0 (2,5)->(1,3)->1*
(2,4)->1*
Слияния последовательностей, отмеченные звездочкой, являются наилучшими параметрами при применении этой новой эвристики.
В случае необходимости словесного объяснения:
Вместо того, чтобы проверять, сколько слияний возможно после каждого возможного слияния для стартового набора; на этот раз мы проверяем, сколько сливаний возможно после каждого возможного слияния для каждого результирующего набора после каждого возможного слияния для стартового набора. И это для lookahead 1. Для lookahead n вы увидите очень длинное предложение, повторяющее часть после каждого возможного слияния для каждого результирующего набора n times.
Уровень 3: разрежьте жадность
Если вы посмотрите внимательно, предыдущий подход имеет катастрофическую производительность для даже умеренных входов и ожиданий (*). Для входов, выходящих за пределы 20 триплетов, все, что находится за пределами 4-merge-lookahead, занимает неоправданно долгое время. Идея здесь состоит в том, чтобы вырезать пути слияния, которые кажутся хуже, чем существующее решение. Если мы хотим выполнить lookahead 10, а конкретный путь слияния дает меньше слияний после трех слияний, чем другой путь после 5 слияний, мы можем просто сократить текущий путь слияния и попробовать другой. Это должно сэкономить много времени и позволить большие взгляды, которые сближают нас с глобально оптимальным решением. Я еще не реализовал этот тест для тестирования.
(*): если предположить, что существует большое сокращение входных множеств, число слияний пропорционально размеру ввода и lookahead приблизительно указывает, сколько вы переставляете эти слияния. Таким образом, вы выбрали lookahead из |input|, который биномиальный коэффициент, который при lookahead ≪ |input| может быть аппроксимирован как O(|input|^lookahead) - который также (по праву) написан, так как вы тщательно завинчены.Суб >
Объединяя все это
Я был настолько заинтригован этой проблемой, что сидел и закодировал это на Python. К сожалению, мне удалось доказать, что разные взгляды дают разные результаты и что даже слепой алгоритм иногда становится лучше, чем смотри 1 или 2. Это прямое доказательство того, что решение не является оптимальным (по крайней мере, для lookahead ≪ |input|), См. исходный код и вспомогательные скрипты, а также тритроны доказательства в github. Будьте осторожны, что, помимо воспоминаний о результатах слияния, я не пытался оптимизировать код по циклу.
Ответ 2
У меня нет решения, но у меня есть некоторые идеи.
Представление
Полезным визуальным представлением проблемы является рассмотрение триплетов как точек 3D-пространства. У вас есть целые числа, поэтому записи будут узлами сетки. И две записи сливаются тогда и только тогда, когда узлы, представляющие их, сидят на одной оси.
Counter-пример
Я нашел (минимальный) пример, когда жадный алгоритм может выйти из строя. Рассмотрим следующие записи:
(1, 1, 1) \
(2, 1, 1) | (3, 1, 1) \
(1, 2, 1) |==> (3, 2, 1) |==> (3, 3, 1)
(2, 2, 1) | (2, 2, 2) / (2, 2, 2)
(2, 2, 2) /
Но, выбирая неправильный путь, он может застревать в трех записях:
(1, 1, 1) \
(2, 1, 1) | (3, 1, 1)
(1, 2, 1) |==> (1, 2, 1)
(2, 2, 1) | (2, 2, 3)
(2, 2, 2) /
Интуиция
Я чувствую, что эта проблема каким-то образом похожа на поиск максимального соответствия в графе. Большинство этих алгоритмов находит оптимальное решение, начиная с произвольного субоптимального решения и делая его "более оптимальным" на каждой итерации путем поиска дополняющих путей, которые имеют следующие свойства:
- их легко найти (полиномиальное время в числе узлов),
- расширяющий путь, и текущее решение может быть создано для нового решения, которое строго лучше текущего,
- Если путь увеличения не найден, текущее решение является оптимальным.
Я думаю, что оптимальное решение в вашей проблеме можно найти в подобном духе.
Ответ 3
В зависимости от вашего описания проблемы:
Мне дается куча событий во времени, которые обычно получают некоторый шаблон. Цель состоит в том, чтобы найти шаблон. Каждый из битов в целочисленном "событие произошло в этом конкретном году/месяце/в день". Для Например, представление от 7 марта 2014 г. было бы [1 < (2014-1970), 1 < 3, 1 < 7]. Образец, описанный выше, позволяет нам сжимайте эти события, чтобы мы могли сказать: "событие произошло каждый 1-й в 2000-2010 годах". - Danstahr 7 марта в 10:56
Я хотел бы поддержать вас с ответами, на которые указал MicSim, в частности
Основываясь на описании проблемы, вы должны проверить это SO ответы (если вы этого не сделали): stackoverflow.com/a/4202095/44522 и stackoverflow.com/a/3251229/44522 - MicSim 7 марта в 15:31
Описание вашей цели намного понятнее, чем подход, который вы используете. Я боюсь, что вы никуда не пойдете с идеей слияния. Звучит страшно. Ответ, который вы получите, зависит от того, как вы управляете своими данными. Вы этого не хотите.
Кажется, вам нужно хранить данные и суммировать их. Таким образом, вы можете попробовать подсчитать эти биты, а не объединять их. Попробуйте алгоритмы кластеризации, конечно, но более конкретно попробуйте регрессионный анализ. Я должен подумать, что вы получите отличные результаты, используя корреляционный анализ, если создадите некоторые вспомогательные данные. Например, если вы создаете данные для "Понедельника", "Вторника", "первого понедельника месяца", "первого вторника месяца",... "второго понедельника месяца",... "даже лет", "каждые четыре года", "високосные годы", "годы без прыжков", "годы, заканчивающиеся на 3",...
То, что у вас есть сейчас, это "1-й день месяца", "2-й день месяца",... "1-й месяц года", "2-й месяц года", t звучит как сложное описание, чтобы найти шаблон.
Если вы считаете, что необходимо продолжить подход, который вы начали, вы можете рассматривать его скорее как поиск, чем слияние. Я имею в виду, что вам понадобится критерий/показатель успеха. Вы можете выполнить слияние исходных данных, строго требуя, чтобы A == A '. Затем повторите слияние исходных данных, требуя B == B '. Аналогично C == C '. Наконец сравните результаты (используя критерии/меру). Вы видите, где это происходит? Ваша идея подсчета бит может быть использована как мера.
Еще один момент, вы могли бы улучшить производительность. Вместо двойного цикла по всем вашим данным и сопоставлению пар, я бы посоветовал вам делать одиночные проходы через данные и сортировать их в ящики. HashMap - ваш друг. Обязательно реализуйте оба метода hashCode() и equals(). Используя карту, вы можете сортировать данные по ключу (скажем, где месяц и день совпадают), а затем накапливать годы в значении. О, мужик, это может быть много кодирования.
Наконец, если время выполнения не является проблемой, и вам не нужна производительность, то здесь что-то попробовать. Ваш алгоритм зависит от упорядочения данных. Вы получаете разные ответы на основе различной сортировки. Ваши критерии успеха - это ответ с наименьшим размером после слияния. Итак, повторяйте цикл, хотя этот алгоритм: перетасовать исходные данные, выполнить слияние, сохранить результат. Теперь каждый раз через цикл сохраняем результат, который является самым маленьким до сих пор. Всякий раз, когда вы получаете результат меньше предыдущего минимума, распечатывайте количество итераций и размер. Это очень упрощенный алгоритм, но при достаточном времени он найдет небольшие решения. Основываясь на вашем размере данных, это может занять слишком много времени.
С уважением,
-JohnStosh
