Login
Расписание игр
159
12.08.07 20:44
Хочу написать программу для расчета расписания игр в нашей лиге. Задача усложняется тем, что каждая команда должна получить определенное кол-во домашних игр и при этом не ездить слишком далеко. Ткните, с чего бы начать?
NEW 13.08.07 15:12
in Antwort Simple 12.08.07 20:44
Ткните, с чего бы начать?
------
С теории расписаний. Но сразу добавлю, что "минимальное" решение находится только полным перебором, а эвристики не всегда дают хороший результат. Так что ищи тоненькую книжечку - Задачи школьных олимпиад по программированию - там как раз разжеван алгоритм перебора вариантов...
------
С теории расписаний. Но сразу добавлю, что "минимальное" решение находится только полным перебором, а эвристики не всегда дают хороший результат. Так что ищи тоненькую книжечку - Задачи школьных олимпиад по программированию - там как раз разжеван алгоритм перебора вариантов...
NEW 13.08.07 15:26
in Antwort Murr 13.08.07 15:12
NEW 14.08.07 09:10
in Antwort Murr 13.08.07 15:12
> Но сразу добавлю, что "минимальное" решение находится только полным перебором, а эвристики не всегда дают хороший результат
Как я и думал, полный перебор не годится.
http://mat.tepper.cmu.edu/cgi-bin/links/jump.cgi?ID=45
Как я и думал, полный перебор не годится.
http://mat.tepper.cmu.edu/cgi-bin/links/jump.cgi?ID=45
В ответ на:
Once we extended the constraint model to include travel distance, we could use bruteforce search to try and find the optimal solution. The most obvious way is to just generate all feasible timetables, compare their travel distances and return the timetable with the lowest total travelling distance. However, the TTP is an NP-hard optimisation problem and an exhaustively search of all possibilities will have a space
requirement take will overwhelm any computer and take a longer time that the age of the universe for any but the most trivial instances. We clearly need a smarter way of searching.
Once we extended the constraint model to include travel distance, we could use bruteforce search to try and find the optimal solution. The most obvious way is to just generate all feasible timetables, compare their travel distances and return the timetable with the lowest total travelling distance. However, the TTP is an NP-hard optimisation problem and an exhaustively search of all possibilities will have a space
requirement take will overwhelm any computer and take a longer time that the age of the universe for any but the most trivial instances. We clearly need a smarter way of searching.
NEW 16.08.07 19:08
in Antwort Simple 12.08.07 20:44
я бы в таком случае сделал как в NHL.
Все команды разбиваются на регионы, в которых они могут себе позволить играть друг против друга. Т.е. региональные мини-чемпионаты. Потом победители играют между собой.
Плюсы:
1. ты упрощаешь проблему до *обычного* расписания
2. командам не надо далеко ездить.
Минусы:
1. команды *зажаты* в определенном кругу соперников :-)
Все команды разбиваются на регионы, в которых они могут себе позволить играть друг против друга. Т.е. региональные мини-чемпионаты. Потом победители играют между собой.
Плюсы:
1. ты упрощаешь проблему до *обычного* расписания
2. командам не надо далеко ездить.
Минусы:
1. команды *зажаты* в определенном кругу соперников :-)
NEW 16.08.07 21:56
in Antwort Tomasson 16.08.07 19:08
Нет, это не пойдет. Да мы и так разбиты уже, можно сказать :)
NEW 17.08.07 01:13
in Antwort Simple 16.08.07 21:56
Эээ... Есть такая штука - "волновой алгоритм". Испльзуется при трассировке печатных плат. Не знаю насколько хорошо он тут будет работать, но суть его примерно такая же - дан граф, нужно получить непересекающиеся связи на нескольких уровнях... Вообщем - формализируй задачу - там станет понятнее что и как приспособить...
NEW 17.08.07 02:01
in Antwort Simple 12.08.07 20:44, Zuletzt geändert 17.08.07 02:11 (scorpi_)
Я так понимаю, что количество команд значительно превышает количество туров, и задача состоит в нахождении таких пар (независимо от результатов/силы команд?) чтобы минимизировать расстояния поездок?
NEW 17.08.07 09:06
in Antwort scorpi_ 17.08.07 02:01
Welcome back :)
Да, 12 команд, 10 туров, double round robin.
Я еще одно ограничение "придумал": нужно учитывать и другие лиги, потому что если в клубе только 4 стола, то провести домашние игры двух команд из разных лиг в нем нельзя.
Да, 12 команд, 10 туров, double round robin.
Я еще одно ограничение "придумал": нужно учитывать и другие лиги, потому что если в клубе только 4 стола, то провести домашние игры двух команд из разных лиг в нем нельзя.
NEW 17.08.07 12:03
in Antwort Simple 17.08.07 09:06
Но вы ведь возвращаетесь каждый раз домой? И какой же это round robin? Round robin, это когда каждый играет с каждым, или попросту, на русском языке, круговой турнир .
NEW 17.08.07 12:21
in Antwort scorpi_ 17.08.07 12:03
Да, конечно. Это тоже круговой турнир, только растянутый на весь сезон.
NEW 17.08.07 12:39
in Antwort Simple 17.08.07 12:21
PS Вообще, если туров не хватает для проведения кругового турнира, то обычно проводится швейцарка - http://de.wikipedia.org/wiki/Schweizer_System
Это более справедливо. Во всяком случае в шахматах швейцарка очень распостранена.
Это более справедливо. Во всяком случае в шахматах швейцарка очень распостранена.
NEW 17.08.07 14:13
in Antwort scorpi_ 17.08.07 12:39
В одном туре играется минимум два матча. То есть, собирается где-то три (или 4) команды и играют каждая с каждой.
NEW 17.08.07 14:39
in Antwort Simple 17.08.07 14:13
Ага, стало уже яснее. Значит мы имеем 10 календарных дат, в каждую из которых в 3-4 местах собираются по 3-4 команды, и проводят круговой турнир. То бишь 3-6 матчей. До конца сезона каждая команда должна дважды сыграть с каждой, то бишь всего 132 матча. Я правильно понимаю?