Есть ли какая-нибудь программа или метод, с помощью которого можно распределить N людей на M групп (каждая группа известной длины. Есть матрица, в которой прописано какой человек не может попасть в какие группы. Есть матрица значения веса признака совместимости людей (полностью несовместим 0 совместим 1 и частично совместим -число)если в группу помещен человек несовместимый с каким-то уже выбранным человеком, то вес несовместимости увеличивается. Все люди должны быть распределены и как можно меньше несовместимых в группе. С уважением, Rita_Mur.
20.04.12 00:42: Перенесено модератором из 'Этюды для программистов' — Кодт
Re: разделение группы людей на подгруппы с учетом признака
Здравствуйте, rita_mur, Вы писали:
_>Есть ли какая-нибудь программа или метод, с помощью которого можно распределить N людей на M групп (каждая группа известной длины. Есть матрица, в которой прописано какой человек не может попасть в какие группы. Есть матрица значения веса признака совместимости людей (полностью несовместим 0 совместим 1 и частично совместим -число)если в группу помещен человек несовместимый с каким-то уже выбранным человеком, то вес несовместимости увеличивается. Все люди должны быть распределены и как можно меньше несовместимых в группе. С уважением, Rita_Mur.
Есть такой алгоритм, прям для этой задачи. О программах не в курсе.
Жизнеспособность прямо пропорциональна простоте!
Re[2]: разделение группы людей на подгруппы с учетом признак
Здравствуйте, boot, Вы писали:
B>Здравствуйте, rita_mur, Вы писали:
_>>Есть ли какая-нибудь программа или метод, с помощью которого можно распределить N людей на M групп (каждая группа известной длины. Есть матрица, в которой прописано какой человек не может попасть в какие группы. Есть матрица значения веса признака совместимости людей (полностью несовместим 0 совместим 1 и частично совместим -число)если в группу помещен человек несовместимый с каким-то уже выбранным человеком, то вес несовместимости увеличивается. Все люди должны быть распределены и как можно меньше несовместимых в группе. С уважением, Rita_Mur.
B>Есть такой алгоритм, прям для этой задачи. О программах не в курсе.
И где можно увидеть этот алгоритм?
Re: разделение группы людей на подгруппы с учетом признака
> Есть ли какая-нибудь программа или метод, с помощью которого можно распределить > N людей на M групп (каждая группа известной длины. Есть матрица, в которой
Есть.
Posted via RSDN NNTP Server 2.1 beta
Re[3]: разделение группы людей на подгруппы с учетом признак
Здравствуйте, MasterZiv, Вы писали:
Мне непонятно Posted via RSDN NNTP Server 2.1 beta
Я попробовала, но соединение не прошло, а там еще и сообщения есть, что правила соединения поменялись и у никого не проходит соединение и как пользоваться вашим RSDN NNTP Server 2.1 beta.
>> Есть ли какая-нибудь программа или метод, с помощью которого можно распределить >> N людей на M групп (каждая группа известной длины. Есть матрица, в которой
MZ>Есть.
Re[3]: разделение группы людей на подгруппы с учетом признак
Здравствуйте, boot, Вы писали:
B>Здравствуйте, rita_mur, Вы писали:
B>>>Есть такой алгоритм, прям для этой задачи. О программах не в курсе. _>>И где можно увидеть этот алгоритм?
B>Подобный можно увидеть здесь http://www.rsdn.ru/forum/alg/4367980.1.aspx
Я не смогла совместить Ваше предложенное с моим вопросом. А если упростить мой вопрос "Есть ли какая-нибудь программа или метод, с помощью которого можно распределить N людей на M групп (каждая группа известной длины. Есть матрица, в которой прописано какой человек не может попасть в какие группы."
Re[5]: разделение группы людей на подгруппы с учетом признак
_>Я не смогла совместить Ваше предложенное с моим вопросом. А если упростить мой вопрос "Есть ли какая-нибудь программа или метод, с помощью которого можно распределить N людей на M групп (каждая группа известной длины. Есть матрица, в которой прописано какой человек не может попасть в какие группы."
Ключевым моментом в этой задаче, как и в прежней, является отсутствующее, но подразумевающееся требование -- ОПТИМАЛЬНОСТЬ. Если оптимальность не нужна, распределяйте как угодно, это удовлетворит поставленные требования. Иначе необходимо применять алгоритмы оптимизации. ГА, по ссылке, которую я дал -- один из них.
Жизнеспособность прямо пропорциональна простоте!
Re[6]: разделение группы людей на подгруппы с учетом признак
_>>Я не смогла совместить Ваше предложенное с моим вопросом. А если упростить мой вопрос "Есть ли какая-нибудь программа или метод, с помощью которого можно распределить N людей на M групп (каждая группа известной длины. Есть матрица, в которой прописано какой человек не может попасть в какие группы."
B>Ключевым моментом в этой задаче, как и в прежней, является отсутствующее, но подразумевающееся требование -- ОПТИМАЛЬНОСТЬ. Если оптимальность не нужна, распределяйте как угодно, это удовлетворит поставленные требования. Иначе необходимо применять алгоритмы оптимизации. ГА, по ссылке, которую я дал -- один из них.
Нам нужно разделить N людей на M групп разной длины и при этом учитывать совместимость людей — у нас есть матрица совместимости каждого человека с каждым, к примеру, если совместим то 1, если не совместим 0 и частично совместим какое-то число. Критерий — как можно меньше несовместимых людей в группе. Кроме того у нас есть матрица для каждого человека в какую группу он не может попасть никогда. Разве матрица по совместимости не может служить для оптимального поиска. Может быть подскажете алгоритм или программу распределения на группы и как можно поставить задачу для сведения ее к задаче линейного целочисленного программирования. Ваш предложенный алгритм ГА я честно говоря не поняла как можно прикрепить к нашему случаю. С уважением, Rita_Mur.
Re[7]: разделение группы людей на подгруппы с учетом признак
Здравствуйте, rita_mur, Вы писали:
_>Нам нужно разделить N людей на M групп разной длины и при этом учитывать совместимость людей — у нас есть матрица совместимости каждого человека с каждым, к примеру, если совместим то 1, если не совместим 0 и частично совместим какое-то число. Критерий — как можно меньше несовместимых людей в группе. Кроме того у нас есть матрица для каждого человека в какую группу он не может попасть никогда. Разве матрица по совместимости не может служить для оптимального поиска.
Нет не может, это не критерий оптимальности. А вот, например, максимальная заполненность или наиболее равномерное распределение людей по группам, может. Должно присутствовать ключевое слово.
_>Может быть подскажете алгоритм или программу распределения на группы и как можно поставить задачу для сведения ее к задаче линейного целочисленного программирования. Ваш предложенный алгритм ГА я честно говоря не поняла как можно прикрепить к нашему случаю. С уважением, Rita_Mur.
Думаю Вам нужно либо понять, что такое оптимальность, либо обратиться в раздел предложений работы.
Изначальная задача не очень сложна для специалиста по решению задач оптимизации, наличие положительного результата решения очень велико.
Жизнеспособность прямо пропорциональна простоте!
Re[7]: разделение группы людей на подгруппы с учетом признак
Нужно дополнить, а то я Вас запутаю совсем. Если число свободных мест в группах приблизительно совпадает с числом людей, или людей меньше чем число мест, И, если число свободных мест достаточно невелико чтобы уложиться в определенное для поиска решения время, эта задача может решаться полным перебором вариантов. Теперь ключевые слова: максимальное время поиска решения, максимальное число людей и групп, требуемая точность решения (для варианта не полного перебора). Эти моменты определяют метод (или алгоритм) решения.
Пока не определены ключевые моменты, число решений велико для того чтобы описывать их все. Да и мотивации не хватает.
