информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Портрет посетителяSpanning Tree Protocol: недокументированное применениеАтака на Internet
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Крупный взлом GoDaddy 
 Просроченный сертификат ломает... 
 Phrack #70/0x46 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Что-то я не совсем понял, как код Грея тут прикручивается,... 04.09.06 18:08  Число просмотров: 2212
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 04.09.06 18:11  Количество правок: 1
<"чистая" ссылка>
> Сегодня придумал способ скомбинировать два алгоритма,
> классический на списках и мой на коде Грея. Ускорение более
> чем в 100 раз :). На текущем тестовом примере из 32 чисел:
> - классический алгоритм на списках = в глубоком отпаде, не
> хватает памяти;
> - алгоритм на коде Грея = 39 сек + ~1 кбайт памяти;
> - новый алгоритм = 0.2 сек + ~1 мбайт памяти;
> Всё это для поиска ближайшей суммы (по модулю разности).

Что-то я не совсем понял, как код Грея тут прикручивается, боюсь изобрести "велосипед", но уж точно не классический алгоритм, поскольку памяти тут не нужно.
Задачку рекомендую разбить на поиск "ближайшего снизу" и "ближайшего сверху". Потом уже из двух выбрать наиболее ближайшее.
Смысл в том, чтоб сначала упорядочить по убыванию (или возрастанию) числа. Если первое число больше требуемого, то суммы со всеми остальными не рассматриваются. Или если первое меньше, но сумма первых дву больше заданного, то к ним уже не имеет смысл добавлять последующие, продолжаем комбинировать первое с третьим и последующими, но уж точно без второго.
Помозгую на досуге как это поточнее алгоритмизировать.
<programming>
Задачка 31.08.06 11:31  
Автор: leo <Леонид Юрьев> Статус: Elderman
<"чистая" ссылка>
Если кому интересно подумать:

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

Это NP-задача, в которой для худшего случая требуется перебор 2**N вариантов. Я реализовал алгоритм, ~100 строк C вместе с тестом, требуемая память пропорциональна N, время в худшем случае 2**N, полный перебор для N==32 занимает менее минуты на P4.

Быстрее кто-нибудь сможет?
Кстати, обязательно ли оптимальное решение или можно приближенно? 02.09.06 00:02  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
> Приятель попросил помочь. Ему в бизнес-приложении
> необходимо реализовать функцию сопоставления-поиска
> платежей и услуг. Задача сводится к нахождению такого
> подмножества из заданного множества чисел, сумма элементов
> которого ближе всего к заданной величине.

А то, что то мне эта задачка уж сильно напомнила "1d bin packing problem" в народе еще именуюемую задачей оптимальной раскройки одномерного профиля.

Если изначально задача состоит в том, чтобы расфасовать числа по наборам таким образом, чтобы минимизировать количество этих наборов, то можно использовать "Best Fit Decreasing" или "First Fit Decreasing". В случае, если набор не ограничен сверху жестко (как длины отрезаемых профилей), то можно использовать "Best Fit Decreasing", но в качестве целевой функции для определения наилучшести использовать не остаток, а модуль разности.

Время полиномиальное (насколько я понимаю O(N^2) для BFD-решения). Количество наборов не превышает 11/9 OPT + 4 (где OPT - оптимальное количество)

> Быстрее кто-нибудь сможет?

Тут http://en.wikipedia.org/wiki/Bin_packing говорят, что существуют приближенные методы, вычисляющие разбивку С ЛЮБОЙ заданной точностью (процентом от оптимального решения). В частности PTAS (http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme)
Я нашел способ сильно ускорить поиск :) 03.09.06 00:12  
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 03.09.06 00:13  Количество правок: 1
<"чистая" ссылка>
Сегодня придумал способ скомбинировать два алгоритма, классический на списках и мой на коде Грея. Ускорение более чем в 100 раз :). На текущем тестовом примере из 32 чисел:
- классический алгоритм на списках = в глубоком отпаде, не хватает памяти;
- алгоритм на коде Грея = 39 сек + ~1 кбайт памяти;
- новый алгоритм = 0.2 сек + ~1 мбайт памяти;
Всё это для поиска ближайшей суммы (по модулю разности).

> А то, что то мне эта задачка уж сильно напомнила "1d bin
> packing problem" в народе еще именуюемую задачей
> оптимальной раскройки одномерного профиля.
Да, всё это варианты задачи "укладки ранца".
Но если придерживаться реалий, то нужно максимально не приближенное решение, и желательно несколько из top-списка.

[...]
> Время полиномиальное (насколько я понимаю O(N^2) для
> BFD-решения). Количество наборов не превышает 11/9 OPT + 4
> (где OPT - оптимальное количество)
>
> Тут http://en.wikipedia.org/wiki/Bin_packing говорят, что
> существуют приближенные методы, вычисляющие разбивку С
> ЛЮБОЙ заданной точностью (процентом от оптимального
> решения). В частности PTAS
> (http://en.wikipedia.org/wiki/Polynomial-time_approximation
> _scheme)
Сейчас гляну, может еще что-нибудь придумаю :)
Что-то я не совсем понял, как код Грея тут прикручивается,... 04.09.06 18:08  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 04.09.06 18:11  Количество правок: 1
<"чистая" ссылка>
> Сегодня придумал способ скомбинировать два алгоритма,
> классический на списках и мой на коде Грея. Ускорение более
> чем в 100 раз :). На текущем тестовом примере из 32 чисел:
> - классический алгоритм на списках = в глубоком отпаде, не
> хватает памяти;
> - алгоритм на коде Грея = 39 сек + ~1 кбайт памяти;
> - новый алгоритм = 0.2 сек + ~1 мбайт памяти;
> Всё это для поиска ближайшей суммы (по модулю разности).

Что-то я не совсем понял, как код Грея тут прикручивается, боюсь изобрести "велосипед", но уж точно не классический алгоритм, поскольку памяти тут не нужно.
Задачку рекомендую разбить на поиск "ближайшего снизу" и "ближайшего сверху". Потом уже из двух выбрать наиболее ближайшее.
Смысл в том, чтоб сначала упорядочить по убыванию (или возрастанию) числа. Если первое число больше требуемого, то суммы со всеми остальными не рассматриваются. Или если первое меньше, но сумма первых дву больше заданного, то к ним уже не имеет смысл добавлять последующие, продолжаем комбинировать первое с третьим и последующими, но уж точно без второго.
Помозгую на досуге как это поточнее алгоритмизировать.
Re: как код Грея тут прикручивается 05.09.06 12:48  
Автор: leo <Леонид Юрьев> Статус: Elderman
<"чистая" ссылка>
> Что-то я не совсем понял, как код Грея тут прикручивается,
> боюсь изобрести "велосипед", но уж точно не классический
> алгоритм, поскольку памяти тут не нужно.

Итерирование кодом Грея позволяет перебрать все комбинации, делая на каждом шаге одну операцию добавления или вычитания одного слагаемого.
Другими словами это очень удобный и быстрый способ итерирования, недостатка два:
- проверяются все комбинации, включая заведомо проигрышные варианты;
- если оперировать числами с плавающей точкой, то при большой разнице в слагаемых возможно накопление ошибок округления и/или потери точности;

С ускорением на два порядка я пожалуй поторопился. В первом варианте у меня была запара, из-за чего отсекались перспективные пути поиска решения. Т.е. поиск шел очень быстро, но не всегда находилось оптимальное решение. После переделки ускорение есть, но сильно зависит от качественного состава слагаемых. Оптимальный вариант - экспоненциальное увеличение номиналов. Время поиска между 2^N и 2^(N/2), реально в 4-16 раз быстрее перебора кодом Грея на наборе из 32 чисел.

> Задачку рекомендую разбить на поиск "ближайшего снизу" и
> "ближайшего сверху". Потом уже из двух выбрать наиболее
> ближайшее.
> Смысл в том, чтоб сначала упорядочить по убыванию (или
> возрастанию) числа. Если первое число больше требуемого, то
> суммы со всеми остальными не рассматриваются. Или если
> первое меньше, но сумма первых двух больше заданного, то к
> ним уже не имеет смысл добавлять последующие, продолжаем
> комбинировать первое с третьим и последующими, но уж точно
> без второго.
Именно так работает классический алгоритм на списках. Это хорошая тактика, беда в том, что нужно очень много памяти для хранения промежуточных результатов.
Конечно интересно. 31.08.06 14:23  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 31.08.06 16:34  Количество правок: 1
<"чистая" ссылка>
> Если кому интересно подумать:

Конечно интересно.

> Это NP-задача, в которой для худшего случая требуется
> перебор 2**N вариантов. Я реализовал алгоритм, ~100 строк C
> вместе с тестом, требуемая память пропорциональна N, время
> в худшем случае 2**N, полный перебор для N==32 занимает
> менее минуты на P4.
>
> Быстрее кто-нибудь сможет?

К стати, откуда 2**N? Должно быть сумма сочетаний из 32 от 1 до 32.
И еще, возможны варианты, когда требуется получить сумму, которая меньше наименьшего или больше наибольшего. В последнем случае только наибольший однозначно подходит, а если есть ограничение "с верху", то наибольший отбрасывается из сочетаний.
Термин "Наиболее близка" не уточняется ли фразой ", но не больше"? А то иногда хочется провести наибольшее количество платежей, имея определенную сумму. В сумму надо вкладываться.
Re: К стати, откуда 2**N? 31.08.06 17:09  
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 31.08.06 17:10  Количество правок: 1
<"чистая" ссылка>
Очень просто, можно либо посчитать через комбинаторику, либо немного подумать:

Будем кодировать использование каждого элемента множества одним битом. Всего получиться N бит, каждое такое N-битное число из 2**N возможных будет отражать один из вариантов подмножества, т.е. каждый бит показывает, складываем элемент или нет. Например, 0 - пустая сумма, а 2**N-1 сумма всех элементов.
Посмотрел я не сумму сочетаний и понял, что к общему... 31.08.06 18:48  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
<"чистая" ссылка>
> Очень просто, можно либо посчитать через комбинаторику,
> либо немного подумать:

Посмотрел я не сумму сочетаний и понял, что к общему знаменателю их привести будет не просто.
Написал прогу и получил действительно 2**N-1 для каждого N.

> Будем кодировать использование каждого элемента множества
> одним битом. Всего получиться N бит, каждое такое N-битное
> число из 2**N возможных будет отражать один из вариантов
> подмножества, т.е. каждый бит показывает, складываем
> элемент или нет. Например, 0 - пустая сумма, а 2**N-1 сумма
> всех элементов.

Сдается мне, что есть какой-то подход, хотя если доказано, что задача не полименальная, то имеет ли смысл с ней биться...
Re: имеет ли смысл с ней биться 31.08.06 19:19  
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 31.08.06 19:25  Количество правок: 1
<"чистая" ссылка>
> Сдается мне, что есть какой-то подход, хотя если доказано,
> что задача не полименальная, то имеет ли смысл с ней
> биться...
Доказанная полиноминальность говорит о том, что можно посчитать за 2**N или быстрее. Но это не значить, что нельзя быстрее. Например, можно сделать перебор с "большим" перешагиванием через "плохие" варианты и показать, что время будет расти не по 2**N.

У этой задачи есть два "классических" решения. Одно для целых чисел, при этом требует построения таблицы [N, S], где S - заданная сумма.

Другое решение - это алгоритм на основе списков. Кроме времени 2**N еще требуется 2**N памяти, и если учесть время на обработку этой кучи, то в худшем случае время стремиться к 2**N*N. Но у этого алгоритма есть плюс, итерируются только не тупиковые ветви поиска решения, а не все варианты.
Я бы на вашем месте не стал сравнивать только суммы, также... 01.09.06 11:10  
Автор: Den <Denis> Статус: The Elderman
<"чистая" ссылка>
Я бы на вашем месте не стал сравнивать только суммы, также необходимо сравнивать день выставления счета и дату платежа.
Но вообще задача дурацкая и на мой взгляд, не имеет смысла, потому что в платежных поручениях указывают по какому договору и счету осуществляется платеж. Поэтому, привязку оказанной услуги к платежу осуществляет бухгалтер, вносящий информацию по платежу в истему.
Re: Я бы на вашем месте не стал сравнивать только суммы, также... 02.09.06 23:49  
Автор: leo <Леонид Юрьев> Статус: Elderman
<"чистая" ссылка>
> Я бы на вашем месте не стал сравнивать только суммы, также
> необходимо сравнивать день выставления счета и дату
> платежа.
> Но вообще задача дурацкая и на мой взгляд, не имеет смысла,
> потому что в платежных поручениях указывают по какому
> договору и счету осуществляется платеж. Поэтому, привязку
> оказанной услуги к платежу осуществляет бухгалтер, вносящий
> информацию по платежу в истему.
Всё немного не так. Нужно найти платеж, который по сумме похож на оплату за несколько различных услуг. Т.е. клиент вправе сделать один платеж за несколько услуг.

Но ситуация отчасти всё равно дурацкая. Разумней ввести другие бизнес-правила. Например, главное - итоговый баланс, а не списки оплаченных или не оплаченных услуг.

Мне же задача интересна исключительно с алгоритмической точки зрения.
Думаю нет, не выйдет. Доказано, что эта задача NPC-класса, и... 31.08.06 16:35  
Автор: leo <Леонид Юрьев> Статус: Elderman
<"чистая" ссылка>
> Сдается мне, что для худшего случая, может получиться
> 2**N/2, но это все равно не выход из положения.
Думаю нет, не выйдет. Доказано, что эта задача NPC-класса, и имеет "псевдо-полиноминальное" решение только для целых чисел.
Но хотя чем черт не шутит, тогда с него пиво (с моего приятеля через меня :)

> И еще, возможны варианты, когда требуется получить сумму,
> которая меньше наименьшего или больше наибольшего.
> Термин "Наиболее близка" не уточняется ли фразой ", но не
> больше"? А то иногда хочется провести наибольшее количество
> платежей, имея определенную сумму. В сумму надо
> вкладываться.
Совершенно верно. Допустим, что есть накая checkpoint-функция, которая оценивает применимость результата итерации и опционально сохраняет top лучших вариантов.
Мой код (для MSC) 31.08.06 12:39  
Автор: leo <Леонид Юрьев> Статус: Elderman
<"чистая" ссылка>
#include <stdio.h>
#include <math.h>

extern "C" unsigned char _BitScanForward (unsigned *, unsigned __int32); 
#pragma intrinsic (_BitScanForward)

static unsigned looking4sum_gray (unsigned length, const double array[], const double target)
{
	// минимальная проверка
	if (length < 1|target <= 0.0)
		return 0;

	double flip[32];
	unsigned pos, i, j;
	char tab[32];
	double sum;
	
	// компируем элементы, фильтруя ненужные и проверяя единичные случаи
	sum = 0.0; i = length; length = 0; do {
		i--;
		if (array[i] == target)
			return 1u << i;
		if (array[i] < target) {
			sum += array[i];
			tab[length] = i;
			flip[length] = array[i];
			if (++length > 32)
				return 0;
		}
	} while (i);

	if (length < 2)
		return 1u << tab[0];

	// проверяем парные случаи, это несравнимо быстрее полного перебора
	i = 0; do {
		j = i + 1; do {
			if (flip[i] + flip[j] == target)
				return (1u << tab[i]) + (1u << tab[j]);
		} while (++j < length);
	} while (++i < length - 1);

	// счетчик для перебора
	pos = (1ul << length) - 1;
	if (length == 32)
		pos = ~0u;

	unsigned best_gray, gray;
	if (sum <= target)
		// наилучший вариант - сумма всех слагаемых меньших target
		best_gray = pos;
	else {
		// полный перебор кодом Грея
		double best_diff = fabs (target);
		gray = best_gray = 0; sum = 0.0; do {
			j = gray;
			gray = pos ^ (pos >> 1);
			j ^= gray;
			_BitScanForward (&i, j);
			sum += flip[i];
			flip[i] = -flip[i];
			double diff = fabs (sum - target);
			if (diff < best_diff) {
				best_gray = gray;
				best_diff = diff;
				if (diff == 0.0)
					break;
			}
		} while (--pos);
	}

	// конвертируем индексы слагаемых (с учетом пропусков и обратного порядка)
	gray = i = 0; do {
		if (best_gray & 1)
			gray |= 1u << tab[i];
		i++;
	} while (best_gray >>= 1);
	return gray;
}

static unsigned looking4sum_gray_test (const unsigned length, const double array[], const double target)
{
	unsigned gray = looking4sum_gray (length, array, target);
	double test = 0.0;
	for (unsigned i = 0; gray; i++) {
		if (gray & 1)
			test += array[i];
		gray >>= 1;
	}

	printf ("target %f, result %f, error %f\n", target, test, target - test);
	return gray;
}

int main (int argc, char* argv[])
{
	static const double test_array[32] = {
		6015.8208, 9489.67893, 83.219879, 848.9457, 163.978846,
		371946.92, 741.743057, 72464.5683, 45.675712, 56.129234, 89412.3127,
		479.74316, 9874.652, 17649.589146, 6565.98146, 79.846252, 854764,
		4523.574, 43576.945, 86.9871396, 451513.3424, 52.1619388, 131624,
		464.9687, 74592.1453, 697.1834745, 637.195, 44535,
		3476.91274, 4123.1237, 3102.982, 769.8498
	};

	looking4sum_gray_test (32, test_array, 23534.9999);
	return 0;
}

---
1






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2021 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach