Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Круговой турнир
Все форумы > Старое > Kошкин дом
bogach
Играется круговой турнир с чётным числом участников (в шашки). Туры (т.е. кто с кем играет) назначались произвольно и наступил такой момент, что очередной тур невозможно составить. Вопросы:

1. Каков критерий? (т.е. как узнать не перебором, что очередной тур запустить невозможно)
2. За тур до описываемого события была возможность по-разному составить пары для игры. Каков критерий лушего выбора, т.е. существует ли такой ход (расписание) при которм турнир сможет продолжиться до конца?
Delta4
Имхо, тема - полный оффтоп. Этот ответ - возможно (и вполне вероятно) бред smile.gif.

Квадрат количества разбиений на пары - это, если я ничего не путаю, перманент (то же, что и определитель, но без знаков) матрицы смежности соответствующего графа. Другое дело, что я не знаю, можно ли его в общем случае вычислить за полиномиальное время (для планарных графов можно еще добавить в матрицу смежности знаки так, чтобы это стал честный определитель - именно так проще всего сосчитать количество способов покрыть шахматную доску доминошками и т.п.).

Соответственно, напрашивающийся алгоритм: каждый раз выбирать такой новый тур, чтобы перманент остающейся матрицы был как можно больше. Как практически реализовать (и можно ли это сделать) - не знаю.
catt
Я склонна согласиться с Димой. Всё-таки это бриджевый форум, а не математический ( смотри описание форума) smile.gif

Несмотря на мою симпатию к тебе, Алексей, и любовь ко всевозможным математическим задачам, я надеюсь, что в следующий раз ты найдёшь другую площадку для обсуждения подобных проблем.
bogach
Ко мне обратился Авгера с вопросом по поводу проведения бриджевых швейцарок. При большом числе команд в начале турнира ещё есть возможность по разному назначать туры, но он не знает критерия оптимального тура. Именно поэтому эта тема и была вынесена на обсуждениеsmile.gif
IBM
Нормальная тема.
Критерий не знаю.
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Форум IP.Board © 2001-2019 IPS, Inc.