| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > алгоритм перебора графа |
| Автор: Kubus 27.6.2007, 16:52 |
| Здравствуйте! Подскажите, пожалуйста, по поводу алгоритма для решения вот такой задачи: Составить программу для нахождения произвольного разбиения 20 человек на 2 команды, численность которых отличается не более, чем в 2 раза, если известно, что в любой команде должны быть люди, обязательно знакомые друг с другом. Круг знакомств определяется матрицей (20,20) |
| Автор: Sartorius 27.6.2007, 17:29 |
| Выбираем состав первой команды (от 7 до 13 человек): и того меньше чем 13 * С(по 13 из 20 ( 77200 )) (примерно 10^6 вариантов) и проверяем два получившихся подграфа на полную связность . |
| Автор: Kubus 1.7.2007, 15:14 |
| не могли бы вы попродробнее объяснить? как запрограммить я разберусь, но сначала нужно в алгоритме разобраться, а теория графив у меня закончилась год назад и я уже мало что помню оттуда |
| Автор: Kubus 12.7.2007, 13:42 |
| уважаемые мемберы данного ресурса! помогите, пожалуйста, с пониманием алгоритма решения задачи этой, ваша карма поднимится до небывалых высот!) сперва разделить на команды требуется. команды могут быть соответственно 7 и 13, 8 и 12, 9 и 11, 10 и 10, но как организовать цикл перебора вариантов внутри команды? а как проверить связность? берем элемент строки, просматриваем столбец на наличие "1", сравниваем с номером элементов (человек другой команды)? |
| Автор: JackYF 12.7.2007, 13:59 | ||
проверки на связность и т.д. - стандартные алгоритмы над графами, мануалы в любом учебнике по графам. Если есть возможность и желание, посмотри boost::graph - там немало алгоритмов уже реализовано. |
| Автор: Lactarius 12.7.2007, 15:09 |
| Потрібно зробити обхід графа методом DFS або BFS |
| Автор: Kubus 13.7.2007, 14:10 |
| как реализовать обход графа - разобрался, спасибо но как оформить перебор всех возможных вариантов? я так понимаю, что до 13 идти не надо - до 12. Перебирать всех 13 - это тоже самое, что перебирать группу из 7. Да и до 12 и 11. Перебор всего по 7, 8 и 9? |
