Теоретическая информатика в Академическом Университете

[kicum]

Ух ты как интересно, ощущаю себя таким вот Шуриком, но до поступления.

[NeoNN]

А есть ли ссылка на наукообразный двухколоночный pdf Вашей работы на Springerlink или еще где-нибудь? Охота почитать поподробнее, а то в свое время в универе был курс по динамическому программированию, но задачу коммивояжера, кроме как методом ветвей и границ, не упрощали.

[AlexGl]

Да, конечно. Если Вам хочется почитать именно алгоритм динамиеского программирования, то его можно найти здесь: Bellman (1962) и здесь Held, Karp (1971). Алгоритм из статьи можно почитать здесь.

[NeoNN]

Спасибо.

[avsmal]

Есть одноколоночный.

[claymore]

А что такое О большое со звездочкой?

[AlexGl]

скрывает полиномиальные множители от длины входа, т.е. . Этим мы просто хотим сказать, что нам не очень интересно оценивать какой именно полином стоит перед .