Вход на сайт
Расписание игр
159
12.08.07 20:44
Хочу написать программу для расчета расписания игр в нашей лиге. Задача усложняется тем, что каждая команда должна получить определенное кол-во домашних игр и при этом не ездить слишком далеко. Ткните, с чего бы начать?
NEW 13.08.07 15:12
в ответ Simple 12.08.07 20:44
Ткните, с чего бы начать?
------
С теории расписаний. Но сразу добавлю, что "минимальное" решение находится только полным перебором, а эвристики не всегда дают хороший результат. Так что ищи тоненькую книжечку - Задачи школьных олимпиад по программированию - там как раз разжеван алгоритм перебора вариантов...
------
С теории расписаний. Но сразу добавлю, что "минимальное" решение находится только полным перебором, а эвристики не всегда дают хороший результат. Так что ищи тоненькую книжечку - Задачи школьных олимпиад по программированию - там как раз разжеван алгоритм перебора вариантов...
NEW 13.08.07 15:26
в ответ Murr 13.08.07 15:12
NEW 14.08.07 09:10
в ответ 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
в ответ Simple 12.08.07 20:44
я бы в таком случае сделал как в NHL.
Все команды разбиваются на регионы, в которых они могут себе позволить играть друг против друга. Т.е. региональные мини-чемпионаты. Потом победители играют между собой.
Плюсы:
1. ты упрощаешь проблему до *обычного* расписания
2. командам не надо далеко ездить.
Минусы:
1. команды *зажаты* в определенном кругу соперников :-)
Все команды разбиваются на регионы, в которых они могут себе позволить играть друг против друга. Т.е. региональные мини-чемпионаты. Потом победители играют между собой.
Плюсы:
1. ты упрощаешь проблему до *обычного* расписания
2. командам не надо далеко ездить.
Минусы:
1. команды *зажаты* в определенном кругу соперников :-)
NEW 17.08.07 01:13
в ответ Simple 16.08.07 21:56
Эээ... Есть такая штука - "волновой алгоритм". Испльзуется при трассировке печатных плат. Не знаю насколько хорошо он тут будет работать, но суть его примерно такая же - дан граф, нужно получить непересекающиеся связи на нескольких уровнях... Вообщем - формализируй задачу - там станет понятнее что и как приспособить...
NEW 17.08.07 12:39
в ответ Simple 17.08.07 12:21
PS Вообще, если туров не хватает для проведения кругового турнира, то обычно проводится швейцарка - http://de.wikipedia.org/wiki/Schweizer_System
Это более справедливо. Во всяком случае в шахматах швейцарка очень распостранена.
Это более справедливо. Во всяком случае в шахматах швейцарка очень распостранена.
NEW 17.08.07 14:39
в ответ Simple 17.08.07 14:13
Ага, стало уже яснее. Значит мы имеем 10 календарных дат, в каждую из которых в 3-4 местах собираются по 3-4 команды, и проводят круговой турнир. То бишь 3-6 матчей. До конца сезона каждая команда должна дважды сыграть с каждой, то бишь всего 132 матча. Я правильно понимаю?