Представьте, что у вас есть бухгалтерский отчет, состоящий из нескольких сотен строк со следующей структурой:
Общая сумма в правильном отчете должна быть равна нулю, даже на цент.
Ошибка всегда возникает из-за того, что некоторые строки имеют неправильные знаки, поэтому нам нужно найти их и перевернуть знак.
Для заданного массива ненулевых сумм задача состоит в том, чтобы найти, в каких строках нужно поменять местами знаки, чтобы сумма стала равной 0. Правильный ответ — это массив значений, которые нужно поменять местами.
Особенности:
Я решил попросить совета здесь, так как чувствую себя немного потерянным в направлении своего исследования.
Я пробовал решение sort + bruteforce:
Это работает во многих случаях, но не работает, когда есть 2 острова или 1 остров и 1-2 ряда выбросов далеко от исходного острова.
В общем, я нашел SSP и много разных алгоритмов, но, очевидно, O(2^(n/2)) на 500 строк — непосильная задача. Я обнаружил, что, учитывая, что это фрагмент JS, который нужно запустить в браузере клиента — чтобы время вычисления составляло менее 1 секунды, алгоритм может попробовать ~ 2 ^ 22 комбинации, прежде чем он должен остановиться.
Я еще не пробовал использовать методы динамического программирования для достижения псевдополиномиального времени здесь.
У меня такое ощущение, что с учетом этих очень специфических ограничений на задачу выше — должно быть что-то попроще.
Правильные ответы всегда 1-2 острова + 1-2 выброса, никогда ничего сложного. 99% случаев — 5-6 подбрасываний решают сумму. Таким образом, «10 бросков» — это наихудший случай, на самом деле в среднем это ~ 5.
Как будто должен быть какой-то конкретный подход, который мне не хватает, который мог бы резко снизить среднюю сложность случая, используя эти ограничения.
Может быть, я ошибаюсь.
О да, вы абсолютно правы. В моем текущем и любом будущем алгоритме я сначала конвертирую все в центы и оперирую целыми числами.
Насколько большим может быть остров?
Обычный остров ~3-4 ряда. До, скажем, 10 макс. Иногда встречаются островки «с дырками», напр. [1,2,3,4,500,502,503] — два острова [1,4], [500,503], но 501 не хватает.
Мы можем упростить такие задачи, говоря, что это два острова [1,4] и [502,503] с [500] в качестве единственного выброса. Но вообще под «островами» я подразумеваю не то, что они обязательно строго соприкасаются, а то, что ошибки концентрируются вокруг конкретных точек притяжения.
Как вы правильно заметили, общий случай вашей проблемы эквивалентен сумме подмножеств, которая является NP-полной. Преобразование простое, мы знаем, как далеко мы находимся от 0, поэтому нам нужно найти подмножество строк со значением, равным ровно половине этой разницы. Если их перевернуть, сумма всех данных будет равна нулю.
Однако, учитывая общий (ограничения на) вид решения, мы можем найти решение, которое обычно позволяет найти решение за разумное время.
Во-первых, вы должны использовать целые числа, представляющие центы (путем умножения на 100), чтобы нам не приходилось иметь дело с плавающей запятой.
Теперь мы можем вычислить и сохранить каждое значение, которое мы можем получить, используя не более двух значений. Это всего 500^2 комбинаций, что достаточно быстро. Мы храним их в структуре данных, которая позволяет выполнять поиск O(1), например, в хэш-карте, а также храним используемые нами индексы.
Затем мы перебираем все смежные «острова» не более, скажем, размера 10. Их около 10 * 500, что все еще не проблема. Вы можете даже полностью ослабить это ограничение и просто просмотреть все ~500*500/2 островов. Мы вычитаем сумму этих островов из целевого числа, чтобы найти количество, которое нам еще нужно перевернуть, и проверяем хэш-карту, возможно ли получить это значение не более чем с двумя строками. Если это так, нам, наконец, нужно проверить, включены ли последние строки в остров, и в этом случае отклонить решение.
Эта стратегия позволяет эффективно искать все возможные комбинации островка и одного или двух случайных переворотов.
Поскольку нет необходимости делать определенное количество переворотов, мы можем хранить только минимальное количество переворотов, необходимое для создания суммы до i
-го элемента,
for each element:
for each sum stored in the previous round:
if the number of its flips is less than 10:
make a new record of sum with flipped value
if this sum can now be associated with
less flips, update that
make a new record of sum with given value
if this sum can now be associated with
less flips, update that
Не забывайте, что мы хотим найти решение, а не просто знать, что оно существует.
@btilly, конечно, просто добавьте элемент в единый список, который отслеживает, какой именно путь привел к минимальным переворотам для суммы.
Я пробовал динамическое программирование. Производительность... не такая, как хотелось бы. Проблема в том, что комбинаторный взрыв возможностей происходит слишком быстро.
Но если у вас всего 2-3 группы флипов, может быть достаточно следующего?
function findFlips (accounts) {
for (let i = 0; i < accounts.length; i++) {
accounts[i]['cents'] = Math.round(accounts[i].value * 100);
}
let sum = accounts.reduce((a, b) => a+b.cents, 0);
// -2 is a hack to make the start of the next group be 0.
const start = {"sum": sum, "flips": 0, "i": -2, "decisions": 0, "prev": null};
let best = {}
best[start.sum] = [start];
let todo = [start];
let d = new Date;
let startTime = d.getTime();
let count = 0;
while (0 < todo.length) {
let current = todo.shift();
if (current.sum == 0) {
let answer = [];
while (current.prev != null) {
answer.unshift(current.i);
current = current.prev;
}
return answer;
}
// Did we take too long?
count++;
if (0 == count%10000) {
d = new Date;
if (999 < d.getTime() - startTime) {
return null;
}
}
for (let i = current.i+2; i < accounts.length; i++) {
let next = {
"sum": current.sum - 2*accounts[i].cents,
"flips": current.flips + 1,
"i": i,
"decisions": current.decisions+1,
"prev": current};
let j = i;
while (j < accounts.length && next.flips < 11 && next.decisions < 5) {
let existing = (best[next.sum] || [])
let k = 0;
while (k < existing.length) {
if (existing[k].i <= next.i && existing[k].flips <= next.flips) {
break;
}
k++;
}
if (k == existing.length) {
existing.push(next);
best[next.sum] = existing;
todo.push(next);
}
j++;
if (j < accounts.length && j < i + 4) {
let next2 = next;
next = {
"sum": next2.sum - 2*accounts[j].cents,
"flips": next2.flips + 1,
"i": j,
"decisions": next2.decisions,
"prev": next2};
}
}
}
}
return null;
}
let accounts = [
{'accountId': 1, 'value': 24.12},
{'accountId': 2, 'value': 128.16},
{'accountId': 3, 'value': -545.43},
{'accountId': 4, 'value': 191.92},
{'accountId': 5, 'value': 238.01},
{'accountId': 6, 'value': -500.36},
{'accountId': 7, 'value': -81.22},
{'accountId': 8, 'value': 132.50},
{'accountId': 9, 'value': 246.80},
{'accountId': 10, 'value': 93.80},
{'accountId': 11, 'value': 389.00},
{'accountId': 12, 'value': -331.00},
{'accountId': 13, 'value': -332.00},
{'accountId': 14, 'value': 321.00},
{'accountId': 15, 'value': 321.06},
{'accountId': 16, 'value': -336.04},
{'accountId': 17, 'value': -491.02},
{'accountId': 18, 'value': -119.06},
{'accountId': 19, 'value': 245.69},
{'accountId': 20, 'value': 404.07},
];
console.info(findFlips(accounts));
// Do some flips.
[2, 3, 11, 18].forEach((i) => accounts[i].value = - accounts[i].value);
console.info(findFlips(accounts));
accounts[2].value += 0.03;
console.info(findFlips(accounts));
Я думаю, что подход с растровым изображением хорош, в том смысле, что в ограниченной области вы бы посмотрели все комбинации включения-выключения для перелистывания.
Чтобы поддерживать два таких острова, сохраните эффект каждой конфигурации острова в карте с ключом этой разницы сумм и, связанный с этим ключом, сохраните крайний левый индекс этого острова вместе с флип-битмап.
Конечно, если какой-либо из этих островов решит проблему, верните это решение.
Если нет, то повторите эти острова и определите, с какой суммой вам нужно их объединить, чтобы получить нулевую сумму. Найдите на карте эту недостающую сумму (которая должна быть ключом на этой карте). Если найдено, вы объединяете два местоположения и возвращаете этот результат.
Следует проявлять некоторую осторожность, чтобы не объединять два перекрывающихся острова, поскольку вы всегда найдете эквивалентную комбинацию, где острова не пересекаются.
Чтобы продемонстрировать эту идею, я создал функцию, которая создает случайный массив из 500 значений в диапазоне (-100 000,...,100 000) и применяет максимальное количество подбрасываний не более чем к 2 островам. Я определил «остров» как набор флипов, где два крайних индекса отстоят друг от друга не более чем на 12. Так, например, остров может состоять из 12 последовательных бросков, или может быть 2 бросков с индексами 3 и 15, или любым промежуточным вариантом.
Приведенная ниже демонстрация будет продолжать создавать новые данные и вычислять для них решение. Если решение не может быть найдено в течение 1 секунды (чего никогда не случалось на моем ПК), или решение не может быть найдено не более чем с двумя островками, вывод «не найден». В противном случае это массив с индексами, где должны применяться флипы.
Каждый раз решение проверяется путем фактического суммирования сумм с учетом переворотов и утверждения, что эта сумма равна нулю.
Вот фрагмент, который продолжает запускать случайные тесты:
const randint = (end) => Math.floor(Math.random() * end);
function randomInput(size, maxFlips, maxIslands) {
let amounts = [];
let sum = 0;
while (size-- > 1) {
let amount = (Math.floor(Math.random() * 2e7) - 1e7) / 100;
amounts.push(amount);
sum += amount;
}
// Make sum zero
while (Math.abs(sum) >= 100000) {
let i = randint(amounts.length);
if (amounts[i] * sum > 0) {
sum -= amounts[i] * 2;
amounts[i] = -amounts[i];
}
}
amounts.push(-Math.round(sum * 100) / 100);
// Prepare islands
let islands = Array(maxIslands).fill(0);
// Determine size of each island (could remain 0)
while (maxFlips-- > 0) {
islands[randint(maxIslands)]++;
}
// Apply the flips (could occasionally overlap, making the problem simpler)
for (let count of islands) {
let i = randint(amounts.length - count + 1);
while (count-- > 0) {
// 80% probability that amount is flipped; so we may get holes in islands
if (randint(100) < 80) {
amounts[i + count] = -amounts[i + count]; // Flip!
}
}
}
return amounts;
}
function solve(amounts) {
let deadline = performance.now() + 900;
const map = new Map;
function memo(sum, loc) {
if (map.has(sum)) map.get(sum).push(loc);
else map.set(sum, [loc]);
}
function recur(i, j, bits, width, sum) {
if (width == 0) return memo(sum, [i, bits]);
recur(i, j + 1, bits * 2, width - 1, sum);
recur(i, j + 1, bits * 2 + 1, width - 1, sum + amounts[j]*2);
}
function expand([i, bits]) {
return Array.from(bits.toString(2), (bit, j) => +bit ? i + j : -1)
.filter(i => i >= 0);
}
// Convert to cents
amounts = amounts.map(val => Math.round(val * 100));
let sum = amounts.reduce((a, b) => a + b);
if (sum == 0) return []; // No flips
const WIDTH = 12;
// Collect islands with at least one flip (at i)
for (let i = 0; i < amounts.length; i++) {
recur(i, i + 1, 1, WIDTH - 1, amounts[i]*2);
}
// Solution with one island?
if (map.has(sum)) return expand(map.get(sum)[0]);
// Look for solutions with two islands...
for (let [sum1, islands] of map) {
if (map.has(sum - sum1)) {
for (let [i, bits1] of map.get(sum - sum1)) {
for (let [j, bits2] of islands) {
if (i >= j + WIDTH) return expand([j, bits2]).concat(expand([i, bits1]));
else if (j >= i + WIDTH) return expand([i, bits1]).concat(expand([j, bits2]));
}
}
}
if (performance.now() >= deadline) break;
}
return "not found";
}
function verify(amounts, flips) {
let sum = Math.round(amounts.reduce((acc, val, i) => acc + Math.round(100*val) * (flips.includes(i) ? -1 : 1), 0));
if (sum != 0) {
console.info("amounts", JSON.stringify(amounts));
console.info("flips", JSON.stringify(flips));
throw "Wrong solution detected! sum = " + sum;
}
}
// I/O handling
const input = document.querySelector("textarea");
const [output, time] = document.querySelectorAll("span");
const pause = document.querySelector("input");
let pausing = false;
setInterval(function repeat() {
if (pausing) return;
const amounts = randomInput(500, 12, 2);
const start = performance.now();
const flips = solve(amounts);
time.textContent = Math.ceil(performance.now() - start);
verify(amounts, flips);
input.value = amounts;
output.textContent = flips;
}, 1000);
pause.onchange = () => pausing = pause.checked;
textarea { width: 100%; height: 6em }
500 amounts: <textarea readonly></textarea><br>
Flips found: <span></span><br>
Time elapsed: <span></span> ms<br>
<input type = "checkbox">Pausing
Обратите внимание, что новый тест выполняется каждую секунду. Это не то время, которое требуется для получения результата. Время, необходимое для обработки, отображается в выходных данных.
Во-вторых, решений часто много. Этот алгоритм не ищет решение, требующее наименьшего количества переворотов, хотя он отдает предпочтение решениям с одним островком. Но поскольку часто бывает много решений, решение часто будет включать самый первый индекс, так как этот индекс включен в первые островки, которые сначала объединяются со всеми остальными островками.
Это оказалось лучшим решением для моего случая, и у него очень приличная частота предположений на реальных примерах, которые у нас есть.
Хотя я не знаю, какой алгоритм может быть лучшим, я могу сказать вам, что первый «конкретный» означает, что вы не можете использовать арифметику с плавающей запятой. Хоть есть над чем подумать для реализации.