"Каменный цветок - 2005" (Екатеринбург). ЧГК. 3 тур. Вопрос 11

Вопрос 11:


    Говорят, что в мире примерно 1.900.000 ИХ, в Греции — 9882, в Германии — 15113, в Швеции — 24978. Поэтому неудивительно, что такая проблема для Греции и Германии была решена в 2001 году, для Швеции — около года назад, сейчас некоторые ученые мечтают, как решить эту задачу в рамках всего мира. Картинки, иллюстрирующие решение проблемы для Швеции и Греции, перед вами. Догадайтесь, чего в Швеции 24978, и ответьте, с какой профессией принято связывать эту проблему.

Ответ: Коммивояжер.

Комментарий: В вопросе идет речь о самой известной задаче оптимизации — задаче коммивояжера: найти проходящий через все города путь минимальной длины.

Источник(и):
    1. http://www.tsp.gatech.edu/sweden/tours/maze.htm
    2. http://www.tsp.gatech.edu/world/grtour.html
    3. http://gtresearchnews.gatech.edu/reshor/rh-f04/tsp.html

Автор: Дмитрий Хлопин