Алгоритм для размещения групп людей?

Я заинтересован в написании приложения, которое может определить, как устанавливать группы из 2-10 человек за столами, на которых могут находиться 10 человек. Там, вероятно, будет около 15 столов и 140 человек. Я не хочу разрушать ни одну из групп людей.Алгоритм для размещения групп людей?

Кажется, что это может быть распространенной проблемой, и мне было интересно, есть ли у кого-нибудь какие-либо предложения о том, где я должен искать решение для этого. Любые ссылки или предложения оценены.

источник

2010-07-07 Abe Miessler

Определите лучший пожалуйста. – IVlad

Лучшее: операция принимает O (0) для решения. Нет выполненных вычислений! – mcandre

Группы не работают. Каждая группа сидит. –

Это bin packing problem.

источник

2010-07-07 14:29:50 Svante

@Abe Miessler, посмотрите эту ссылку и прочитайте о алгоритме _First-fit. Общая проблема сложна, но ваши ограничения по размеру облегчают работу с наивным и жадным подходом. – grossvogel

Ограничение по размеру облегчает работу, если оно указано ниже - это означает, что существует множество решений. Тем не менее, в другом крайнем случае, когда невозможно сгруппировать все группы за десять столов (но едва ли), вы должны исчерпать все возможности, чтобы определить, что это невозможно. –

AFAIK, подход первого подхода - это то, что используют большинство файловых систем и диспетчеров памяти при распределении пространства, и это работает очень хорошо. – rmeador

Пусть группы решат, где сидеть. Все в порядке, если группы сами решат разбить, объединиться с другими группами или переместить таблицы вместе?

источник

2010-07-07 14:26:00 mcandre

Не, если это свадьба, где жених и невеста платят за каждый стол, и люди заранее спрашивали, какую еду они хотят. –

Нет, это слишком велико для этого, если я позволяю им решать, что группы обычно разбиваются. –

Сначала распределите самые большие группы, а затем добавьте небольшие группы, где можете. – mcandre

Это просто вариация на стандарт «Knapsack problem»

источник

2010-07-07 14:26:18

Нет, это не так! Рюкзак имеет псевдополиномиальные решения, а бин-упаковка - нет. – 2010-07-07 14:53:16

Когда мы эту проблему в школе мы решили ее как проблему TSP.

источник

2010-07-07 14:28:54

Это означает, что проблема NP-hard. Таким образом, Abe, вероятно, не найдет оптимальный алгоритм ... – YuppieNetworking

@Yuppie: Нет, это означает, что это NP, который на самом деле ничего не говорит нам * (хотя факт, что вы моделировали проблему как TSP в классе, а не используя многочлен -time алгоритм подсказывает, что инструктор знал, что проблема NP-complete:) * –

Это bin packing problem, который является NP-Hard (найти лучший ответ непросто, и нелегко проверить, является ли ответ лучшим).

Группы людей - это отдельные объекты, при этом объем = количество людей в группе. Таблицы - это бункеры размером 10.

Есть несколько алгоритмов аппроксимации, которые должны быть легко найти, зная, что вы должны Google для упаковки в бункер.

Однако ваша проблема в том, что у вас есть 10 столов - т. Если 10 таблиц - это решение OPTIMAL, вам будет сложно найти решение (если оно даже существует), но если оптимальным является действительно 7 или 8, найти решение будет легко. Все зависит от групповых распределений.

источник

2010-07-07 14:33:49

Оптимальным не может быть 7 или 8, так как есть ~ 140 человек, а размер стола - 10. – 2010-07-07 15:05:19

Алгоритм для размещения групп людей?

ответ

Смежные вопросы