Круговой турнир, "от балды" |
Здравствуйте, гость ( Вход | Регистрация )
Круговой турнир, "от балды" |
24.05.07, 16:40
Сообщение
#1
|
|
BridgeClub Группа: Друзья клуба Сообщений: 24 Регистрация: 02.02.04 Из: Иерусалим Пользователь №: 38 |
Играется круговой турнир с чётным числом участников (в шашки). Туры (т.е. кто с кем играет) назначались произвольно и наступил такой момент, что очередной тур невозможно составить. Вопросы:
1. Каков критерий? (т.е. как узнать не перебором, что очередной тур запустить невозможно) 2. За тур до описываемого события была возможность по-разному составить пары для игры. Каков критерий лушего выбора, т.е. существует ли такой ход (расписание) при которм турнир сможет продолжиться до конца? |
|
|
24.05.07, 17:01
Сообщение
#2
|
|
BridgeClub Группа: Друзья клуба Сообщений: 80 Регистрация: 30.01.04 Из: St.Petersburg - Europe Пользователь №: 19 |
Имхо, тема - полный оффтоп. Этот ответ - возможно (и вполне вероятно) бред .
Квадрат количества разбиений на пары - это, если я ничего не путаю, перманент (то же, что и определитель, но без знаков) матрицы смежности соответствующего графа. Другое дело, что я не знаю, можно ли его в общем случае вычислить за полиномиальное время (для планарных графов можно еще добавить в матрицу смежности знаки так, чтобы это стал честный определитель - именно так проще всего сосчитать количество способов покрыть шахматную доску доминошками и т.п.). Соответственно, напрашивающийся алгоритм: каждый раз выбирать такой новый тур, чтобы перманент остающейся матрицы был как можно больше. Как практически реализовать (и можно ли это сделать) - не знаю. Сообщение отредактировал Delta4 - 24.05.07, 17:33 |
|
|
25.05.07, 9:15
Сообщение
#3
|
|
национальный гроссмейстер БК.ру Группа: Друзья клуба Сообщений: 472 Регистрация: 27.04.04 Из: Москва Пользователь №: 137 |
Я склонна согласиться с Димой. Всё-таки это бриджевый форум, а не математический ( смотри описание форума)
Несмотря на мою симпатию к тебе, Алексей, и любовь ко всевозможным математическим задачам, я надеюсь, что в следующий раз ты найдёшь другую площадку для обсуждения подобных проблем. Сообщение отредактировал catt - 25.05.07, 9:15 |
|
|
25.05.07, 10:19
Сообщение
#4
|
|
BridgeClub Группа: Друзья клуба Сообщений: 24 Регистрация: 02.02.04 Из: Иерусалим Пользователь №: 38 |
Ко мне обратился Авгера с вопросом по поводу проведения бриджевых швейцарок. При большом числе команд в начале турнира ещё есть возможность по разному назначать туры, но он не знает критерия оптимального тура. Именно поэтому эта тема и была вынесена на обсуждение
|
|
|
28.05.07, 22:13
Сообщение
#5
|
|
клубный мастер БK.ру Группа: Друзья клуба Сообщений: 91 Регистрация: 31.01.04 Пользователь №: 31 |
Нормальная тема.
Критерий не знаю. |
|
|
Текстовая версия | Сейчас: 29.03.24, 14:15 |