Login
Расписание игр
159 просмотров
Перейти к просмотру всей ветки
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.