?

Log in

No account? Create an account

Previous Entry | Next Entry

Господа негуманитарии!
А есть же какой-то алгоритм, помогающий в следующей ситуации.
Есть список неких объектов, каждый из которых обладает некими бинарными характеристиками. Задача - расставить эти объекты в списке так, чтобы последовательность была максимально разнообразной, то есть, чтоб эти характеристики в списке распределялись равномерно по длине.
Например, есть список из тридцати блюд на завтрак.
Каждому блюду присвоена характеристика по следующим параметрам: сладкое-несладкое, жесткое-мягкое, мясное-не мясное, яичное-не яичное, сытное-несытное, полезное-неполезное, овощное-неовощное.
Задача - распределить завтраки на месяц, чтобы питание было как можно более разнообразным. Чтоб, допустим, не есть яичные блюда два дня подряд, или не съесть все сладкое в начале месяца и так далее.
Ну есть же, есть же такой алгоритм? Задача-то довольно часто в жизни встречается.
promo fridka may 2, 2014 16:20 2
Buy for 40 tokens
Если вы любите порошки и пирожки, но при этом не читаете журнал taffy729, то вы пропускаете очень много прекрасного!

Comments

( 36 comments — Leave a comment )
ive_kendall
May. 8th, 2014 08:24 am (UTC)
Долго и старательно можно через эксель...
fridka
May. 8th, 2014 08:26 am (UTC)
Долго и старательно можно и просто из общих соображений. Но хотелось бы как-то оптимизировать процесс.
emherzen
May. 8th, 2014 08:52 am (UTC)
Если бы несколько сотен, то можно было бы прогу написать. Если 30 - быстрее руками.
fridka
May. 8th, 2014 08:54 am (UTC)
Руками можно какой-то параметр пропустить, или вообще сделать неоптимально.
emherzen
May. 8th, 2014 08:58 am (UTC)
Тогда попросить кого-то близкого и не ленивого программиста :) Но это время, пара часов, я думаю, чтобы прямо идеально все распределялось.
fridka
May. 8th, 2014 09:03 am (UTC)
Ну должен же УЖЕ быть алгоритм. Не программа, а именно алгоритм. Ведь ситуация - часто встречающаяся.
emherzen
May. 8th, 2014 09:06 am (UTC)
Нет, может быть готовая программа, которая позволяет заводить наборы условий и получать результат, но это нужно искать и не вам, а тому же программисту, который знает, где такое берут. Эксель - тоже такая программа :) Просто ей нужно уметь пользоваться. Есть спецы, которые там способны траекторию Земли на сто лет вперед просчитать.
rovena
May. 8th, 2014 08:54 am (UTC)
Датчик псевдослучайных чисел?
fridka
May. 8th, 2014 08:56 am (UTC)
Ты это... не с умным говоришь! Если псевдослучайных - могут быть повторы. А тут нужно - разнообразие.
rovena
May. 8th, 2014 09:04 am (UTC)
Блин, абстрактно не могу рассуждать. Но алгоритм примерно следующий. Берется первый объект. Случайным образом выбирается следующий. Проверяется на максимальное совпадение количества признаков. Если максимум не превышен, то объект переносится из первой выборки в искомую. Если превышен - выбирается другой. Если ни одного объекта не подошло, то максимальное количество признаков уменьшается на один. Повторяется подбор.
Если объект найден, то он берется за текущий. Максимальное количество признаков инициализируется исходным и пул объектов перебирается заново, в сравнении с этим объектом.
При желании в оценочную функцию можно добавить не только текущий объект, но и предыдущий.
pesec
May. 8th, 2014 08:06 pm (UTC)
Если есть ГПСЧ (рандомайзер), то я формализую предложение rovena.
Берём все наши продукты, в любой последовательности (случайной, поимённой, по калорийности -- не важно).
Изначально их число N.
Каждый день номер I выбираем новое случайное целое число R (между 1 и N), и в этот день будем есть блюдо R.
И уменьшаем значение N на единицу.


В результате получим рандомизированную последовательность. Но - жёсткую на весь месяц. Так что сладкое мы в начале месяца не съедим.

В терминах языка C (rand() возврашает псевдорандомальное целое от 0 до MAX_RAND (= 32767)), если нумеруем блюда от 1 до N:

#include <stdio.h>
#include <stdlib.h>
int main()
{
int N;
for(N=30;N>0;N--)
printf("today we eat dish #%d from the rest\n",rand()%N+1);
return 0;
}


Edited at 2014-05-08 08:06 pm (UTC)
andrzejn
May. 8th, 2014 09:10 am (UTC)
Сопоставить каждому блюду двоичное число по его признакам. 1 в том или ином разряде - соответствующий признак есть, 0 - признака нет. Отсортировать по возрастанию этих чисел.

Делим все блюда на два списка. Чётные блюда из общего списка в первый список, нечётные - во второй.
Теперь у нас есть два списка (1, 2), каждый отсортирован по возрастанию. Снова делим каждый список на два по тому же принципу (чётные-нечётные).
Теперь у нас есть четыре списка. (1.1, 1.2; 2.1, 2.2; половинки списков между собой не переставляем - сначала идут половинки первого списка, потом половинки второго). Делим каждый ещё на два по тому же принципу.
Получаем четыре списка (1.1.1, 1.1.2; 1.2.1, 1.2.2; 2.1.1, 2.1.2; 2.2.1, 2.2.2).
Повторяем до тех пор, пока в каждом из списков не остаётся по одному-два блюда.
fridka
May. 8th, 2014 09:12 am (UTC)
И что дальше делать с этими списками?
andrzejn
May. 8th, 2014 09:15 am (UTC)
Общий список, составленный из этих коротеньких кусочков в указанном порядке, и будет тем, чем надо. Не строго оптимально, но достаточно хорошо для практического применения.

Этот алгоритм применяют, когда нужно группу испытуемых разделить на примерно равноценные подгруппы по набору параметров.
fridka
May. 8th, 2014 09:17 am (UTC)
Спасибо!
arno1251
May. 8th, 2014 09:49 am (UTC)
к сожалению, если первый признак, скажем, берется "сладкое-несладкое" - первую половину месяца будут есть только несладкое, вторую половину только сладкое
поэтому при практическом применении такого алгоритма, возможно, стоит ранжировать признаки от самого несущественного к самому существенному

Edited at 2014-05-08 09:49 am (UTC)
andrzejn
May. 8th, 2014 09:52 am (UTC)
Это только до первого деления отсортированного списка. С каждым делением признак примерно равномерно "размазывается" на половины списка.

Но да, проранжировать признаки по существенности имеет смысл.
arno1251
May. 8th, 2014 10:26 am (UTC)
ну как "до первого деления"
+++ Получаем четыре списка (1.1.1, 1.1.2; 1.2.1, 1.2.2; 2.1.1, 2.1.2; 2.2.1, 2.2.2). +++
все списки, начинающиеся на "1" - несладкие, на "2" - сладкие
то есть я не говорю, что сам подход плох или хорош, он просто не всегда сработает именно для заданной целевой функции

Edited at 2014-05-08 10:26 am (UTC)
arno1251
May. 8th, 2014 12:42 pm (UTC)
сорри, понял свою ошибку
снимаю предыдущее возражение
sudzume
May. 8th, 2014 10:16 am (UTC)
Как обойтись без всяких подсчётов,
и характеристики блюд строго задавать не обязательно.
1. Составляем нумерованный список всех возможных блюд.
2. На шариках или других предметах пишем номера.
Число шариков N = количеству блюд.
3. Вслепую выбираем шарик и по номеру определяем блюдо.
4. Хочется это есть? Да - приготовляем и едим,
Нет - откладываем шарик в сторонку и повторяем попытку (3.)
5. Возвращаем шарики в общую кучу.
(Возможны варианты - не возвращать шарики,
пока общая куча не будет исчерпана).
fridka
May. 8th, 2014 04:31 pm (UTC)
Вот потому и говорю - вопрос не для гуманитариев. Предложенным вами способом решается только очень частная задача про завтраки,да и то решается так себе: в конце месяца остаются самые невкусные варианты. А общая задача так и останется не решена. Например, задача распределения номеров в концерте (веселые-грустные, исполнитель женщина - исполнитель мужчина, старые-новые, и т.д.), или задача одеваться на работу каждый раз как можно более непохоже на предыдущий, или распределить по моделям телефонов новшества так, чтобы каждый раз люди покупали новую модель.
sudzume
May. 8th, 2014 07:24 pm (UTC)
"В конце месяца остаются самые невкусные варианты".
Отнюдь. Если вариант не устраивает (невкусный),
шарик откладываем в сторону и выбираем следующий.
кончились шарики - возвращаем все в общую кучу
и начинаем отсчёт заново.
fridka
May. 8th, 2014 07:31 pm (UTC)
Ну вот в начале месяца шариков тридцать. Я вынимаю невкусный - и откладываю. Потом шариков остается пятнадцать. Из них по-прежнему один невкусный (а скорее не один, а пяток), я их продолжаю откладывать. И вот в какой-то момент все вкусные шарики я уже выбрала. И остаются - невкусные, среди которых я выбираю наименее невкусный, и так далее, пока на тридцатый день не съедаю самый невкусный завтрак. Или не ставлю последним в концерте провальный номер. Или не иду на работу в последний день в самой скучной блузке.
sudzume
May. 9th, 2014 03:11 pm (UTC)
не обязательно доедать невкусные шарики,
(так же как слушать скучные номера в концерте).
Одно дело, если завтрак вкусный, просто находится на неудобном месте,
возвращаем шарик в общую кучу, он имеет равные шансы быть выбранным снова.
И другое дело - если он менее вкусный в принципе.
Кстати, генератор случайных чисел онлайн:
http://randstuff.ru/number/
fridka
May. 9th, 2014 03:18 pm (UTC)
Ну, завтраков всего тридцать, и съесть их надо все (голодать в планы не входит). Номеров в концерте тоже тридцать, и качество их не должно капитально ухудшиться к финалу. Генератор случайных чисел проблему не решает никак. Очень долгий и скучный выходит перебор. Мягко говоря, неоптимальное решение.
sudzume
May. 10th, 2014 07:05 pm (UTC)
Кстати, есть засада,
которую не учитывают многие алгоритмы:
Есть пудинг после селёдки или селёдку после пудинга -
очень разное удовольствие, хотя блюда совершенно непохожие,
алгоритм оба случая пропустит, но нужно учитывать ещё и порядок.
gostrov
May. 8th, 2014 11:29 am (UTC)
Взять в динабанке Excel табличку для индивидуального ЧГК (Оно же "Юрьев день") и вбить вместо фамилий игроков названия блюд.
murmele
May. 8th, 2014 04:25 pm (UTC)
И что?
Генератор случайных чисел можно достать проще, наверное?
arno1251
May. 8th, 2014 11:58 am (UTC)
Ниже следует алгоритм полусумасшедшего перфекциониста, не принимайте его всерьёз.

1. Итак, у нас есть N объектов, у каждого M бинарных признаков.
Располагаем признаки в виде кортежа attr1, attr2… attrM
2. Каждый признак может иметь вес (значимость), располагаем веса в том же порядке (w1, w2,….wM). Если признаки равнозначны, полагаем все веса равными единице.
3. Все бинарные характеристики конкатенируем в общую строку S = B(attr1) U B(attr2) U … U B(attrM), получаем кортеж длиной M из нулей и единиц
4. Для каждой пары объектов (i, j) определяем степень расхождения как скалярную величину
- считаем D(I,j) = Si XOR Sj (операция "исключающее ИЛИ") - тоже строка из нулей и единиц, единица показывает различающиеся признаки
- cчитаем общий вес расхождения (скалярное произведение D(I,j) на вес W из пункта 2),
полученный результат определяет степень расхождений пары объектов прямо «в граммах» с учетом значимости признака
5. Далее для каждой различающейся последовательности (их всего таких N! штук) определяем два скалярных критерия (максиминный и минимаксный)
- Da = Сумма всех (N-1) расхождений, деленная на (N-1) – среднее расхождение
- Dg = Минимум из всех (N-1) расхождений - гарантированное расхождение
Далее определяется целевая функция F = k1*Da + k2*Dg, где k1 + k2 = 1
Сразу отбрасываем последовательности с малым значением F.
Остальные "хорошие" последовательности сортируются по убыванию целевой функции F, и прямо с верхушки и берем наши неунылые завтраки.
Как получать неповторяющиеся последовательности – см. напр. вариант отсюда http://www.fvn2009.narod.ru/Olympiads/Tasks_Olimp1/T_olimp3.htm

Сразу оговорюсь, что это nP алгоритм, и считать, к примеру, 15 блюд он будет несколько часов, а сортировать последовательности объектов можно только на хорошей БД. Если на PHP+mySQL - это примерно 500 строк кода и 2 человеко-недели на разработку и тестирование.
Выше тут предложили несколько вполне приличных вариантов, совет - выбрать какой-нибудь один из них ))
firben
May. 8th, 2014 01:20 pm (UTC)
Главное — не жрать полезное более одного дня подряд!
olenusha
May. 8th, 2014 01:31 pm (UTC)
У меня такая же проблема с одеждой - что надеть.
Только матрицу - что после чего можно, и искать длинные цепочки.
mitiay
May. 8th, 2014 06:18 pm (UTC)
Принять, что есть несколько видов зарядов, так что один вид заряда соответствует одной характеристике, и задать отталкивание одноименных зарядов одного вида по аналогии с электрическими. Плюс циклические граничные условия (нечто, выпрыгивающее за левый край интервала, впрыгивает с правого края), случайное начальное распределение, постепенно уменьшающаяся случайная тряска и какая-нибудь сила трения, чтобы все это в итоге устаканивалось.

Ну, или задать целевую функцию как потенциал такой системы из нескольких типов зарядов и использовать любой приглянувшийся метод оптимизации. Понимаю, что звучит не очень человечно, но иначе слов станет совсем много.
pesec
May. 8th, 2014 07:16 pm (UTC)
Взять последовательность кодов Грея (http://en.wikipedia.org/wiki/Gray_code).

Другой вариант такой: в первый день выбираем какую-то комбинацию. В каждый следующий день выбираем комбинацию, которая (1) ещё не была, (2) максимально отличается от вчерашней. Таких комбинаций может быть несколько, и мы выбираем из них произвольную/вкуснейшую.
fridka
May. 8th, 2014 07:18 pm (UTC)
Тогда получится вариант, что в конце нашего условного месяца наши условные завтраки будут довольно однообразны.
pesec
May. 8th, 2014 07:26 pm (UTC)
Это если код Грея; он всегда одинаково однообразен. Можно попробовать код Джонсона: http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%B4_%D0%94%D0%B6%D0%BE%D0%BD%D1%81%D0%BE%D0%BD%D0%B0

Второсй способ, видимо, к концу месяца снижает разнообразие, но я интуитивно не чувствую, насколько.
pesec
May. 8th, 2014 07:39 pm (UTC)
Очшущение, что andrzejn сверху дал код Грея или Джонсона...
( 36 comments — Leave a comment )

Profile

пудель
fridka
Счастливая женщина

Latest Month

August 2017
S M T W T F S
  12345
6789101112
13141516171819
20212223242526
2728293031  

Tags

Powered by LiveJournal.com