?

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)
Руками можно какой-то параметр пропустить, или вообще сделать неоптимально.
(no subject) - emherzen - May. 8th, 2014 08:58 am (UTC) - Expand
(no subject) - fridka - May. 8th, 2014 09:03 am (UTC) - Expand
(no subject) - emherzen - May. 8th, 2014 09:06 am (UTC) - Expand
rovena
May. 8th, 2014 08:54 am (UTC)
Датчик псевдослучайных чисел?
fridka
May. 8th, 2014 08:56 am (UTC)
Ты это... не с умным говоришь! Если псевдослучайных - могут быть повторы. А тут нужно - разнообразие.
(no subject) - rovena - May. 8th, 2014 09:04 am (UTC) - Expand
(no subject) - pesec - May. 8th, 2014 08:06 pm (UTC) - Expand
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)
И что дальше делать с этими списками?
(no subject) - andrzejn - May. 8th, 2014 09:15 am (UTC) - Expand
(no subject) - fridka - May. 8th, 2014 09:17 am (UTC) - Expand
(no subject) - arno1251 - May. 8th, 2014 09:49 am (UTC) - Expand
(no subject) - andrzejn - May. 8th, 2014 09:52 am (UTC) - Expand
(no subject) - arno1251 - May. 8th, 2014 10:26 am (UTC) - Expand
(no subject) - arno1251 - May. 8th, 2014 12:42 pm (UTC) - Expand
sudzume
May. 8th, 2014 10:16 am (UTC)
Как обойтись без всяких подсчётов,
и характеристики блюд строго задавать не обязательно.
1. Составляем нумерованный список всех возможных блюд.
2. На шариках или других предметах пишем номера.
Число шариков N = количеству блюд.
3. Вслепую выбираем шарик и по номеру определяем блюдо.
4. Хочется это есть? Да - приготовляем и едим,
Нет - откладываем шарик в сторонку и повторяем попытку (3.)
5. Возвращаем шарики в общую кучу.
(Возможны варианты - не возвращать шарики,
пока общая куча не будет исчерпана).
fridka
May. 8th, 2014 04:31 pm (UTC)
Вот потому и говорю - вопрос не для гуманитариев. Предложенным вами способом решается только очень частная задача про завтраки,да и то решается так себе: в конце месяца остаются самые невкусные варианты. А общая задача так и останется не решена. Например, задача распределения номеров в концерте (веселые-грустные, исполнитель женщина - исполнитель мужчина, старые-новые, и т.д.), или задача одеваться на работу каждый раз как можно более непохоже на предыдущий, или распределить по моделям телефонов новшества так, чтобы каждый раз люди покупали новую модель.
(no subject) - sudzume - May. 8th, 2014 07:24 pm (UTC) - Expand
(no subject) - fridka - May. 8th, 2014 07:31 pm (UTC) - Expand
(no subject) - sudzume - May. 9th, 2014 03:11 pm (UTC) - Expand
(no subject) - fridka - May. 9th, 2014 03:18 pm (UTC) - Expand
(no subject) - sudzume - May. 10th, 2014 07:05 pm (UTC) - Expand
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)
Тогда получится вариант, что в конце нашего условного месяца наши условные завтраки будут довольно однообразны.
(no subject) - pesec - May. 8th, 2014 07:26 pm (UTC) - Expand
(no subject) - pesec - May. 8th, 2014 07:39 pm (UTC) - Expand
( 36 comments — Leave a comment )

Profile

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

Latest Month

January 2018
S M T W T F S
 123456
78910111213
14151617181920
21222324252627
28293031   

Tags

Powered by LiveJournal.com