Образное описание:
1. Представьте себе
трафарет.
2. Теперь, представте что у вас кучка самых разных трафаретов из N штук (N >= 1).
3. Вы складываете их в шляпу, подкидываете ввверх, они удараряются об потолок и падают на пол.
4. Трафаеты раскадало по полу, но многие из них лежат внахлёст один на другой.
5. Суммарная площадь пола накрытая трафаретами — S. Из-за лежащих внахлёст трафаретов S значительно меньше суммарной площади всех трафаретов.
Задача: найти такую минимальную (по количеству штук) комбинацию трафаретов, что они будут покрывать 80% от S.
Исходные данные этой же задачи, но вместо рисунков трафаретов — числа из диапазона [1-10000]:
var maxValue = 10000;
var rnd = new Random();
int trafaretsNum = rnd.Next(1, 100); // количество трафаретов
int[][] trafarets = new int[trafaretsNum][]; // первый уровень - непосредственно трафарет, второй уровень - точки трафарета
for (int i = 0; i < trafarets.Length; i++)
{
int trafaretSize = rnd.Next(1, 1000); // размер (количество точек) трафарета
trafarets[i] = new int[trafaretSize];
for (int j = 0; j < trafarets[i].Length; j++)
{
int min = rnd.Next(1, maxValue);
int max = rnd.Next(min, maxValue) + 1;
int val = rnd.Next(min, max);
trafarets[i][j] = val;
}
trafarets[i] = trafarets[i].OrderBy(a => a).ToArray(); // сортируем просто для красоты
}
Dictionary<int, object> dict = new Dictionary<int, object>();
foreach (int[] trafaret in trafarets)
{
foreach (int val in trafaret)
{
if (!dict.ContainsKey(val))
{
dict.Add(val, null);
}
}
}
int[] S = dict.Keys.OrderBy(a => a).ToArray(); // накрытый трафаретами набор чисел. Отсортированы просто для красоты.
Необходимо найти такой минимальный набор трафаретов (trafarets[i]), что бы накрыть 80% чисел из массива S.
Задача, на самом деле сугубо практическая и бизнесовая, просто я её максимально выхолостил для простоты понимания.
По возможности нужно максимально производительное решение, т.к. выбор оптимального набора "трафаретов" выполняется на потоке тысячи раз.
Печально
А вы не могли бы привести решение для моей трактовки задачи, потому как количество высшей математики в
документах по запросу partial set cover очень пугает
Здравствуйте, Айкон, Вы писали:
А>Печально
А>А вы не могли бы привести решение для моей трактовки задачи, потому как количество высшей математики в документах по запросу partial set cover очень пугает
Там несложная математика. Почитайте поверхностно про теорию множеств, логарифмы, числовые последовательности и схождение, мат. функции с множеством переменных, функцию max и min, комбинации в комбинаторике, условную вероятность, математическое ожидание, дисперсию, сигма-нотацию (
http://www.mathsisfun.com/algebra/sigma-notation.html), вроде, еще графы, и потом еще раз статью.
Здравствуйте, Айкон, Вы писали:
А>привести решение для моей трактовки задачи
:)
Ну разве что классический жадный алгоритм могу привести. Но в нём-то как раз всё просто — на каждой итерации нужно брать трафарет с самым большим числом ещё не покрытых значений и добавлять его в решение. И останавливаться как только накопили нужное число покрытых точек.
А>потому как количество высшей математики в документах по запросу partial set cover очень пугает
Так надо сначала выяснить, хорошо подходит твоя задача под условия алгоритма. Вот в этой конкретной статье используются либо ограничения на максимальный размер множества, либо на максимальную частоту вхождения элемента. Ну то есть целесообразность применения зависит грубо-говоря от соотношений между maxValue, trafaretsNum и trafaretSize. В любом случае, стоит сначала начать с жадного, и посмотреть на примеры, где качество его решений не устраивает, — а потом с ними и бороться.
