Полное название проекта:
Задача Коммивояжера для дорог г. Красноярска
Статус: 
Допущен к очному туру
Год: 
2004
Автор
Фамилия, имя, отчество:
Воротынов Евгений Александрович
Проект
Номинация: 
Дебют
Сроки работы над проектом: 
2004
Описание: 

Задача Коммивояжера является классической задачей теории графов. Заключается она в том, что требуется определить оптимальный замкнутый маршрут в ориентированном графе. В проекте граф является математической моделью, представляющую схему дорог г. Красноярска. Самое лёгкое решение задачи сводится к полному рекурсивному перебору всех возможных комбинаций маршрута. Но, конечно, это решение является очень неэффективным. Методом же ветвей и границ реально организовать нахождение маршрута для 50 и более пунктов, причем это будет происходить очень быстро. Помимо метода ветвей и границ в программе реализован алгоритм Дейкстры, при помощи которого можно найти кратчайшее расстояние от пункта А до пункта Б. На практике данная программа может использоваться, например, водителями, или просто служить наглядным пособием по использованию алгоритма Дейкстры и метода ветвей и границ при решении задачи о Коммивояжере.

Занимаюсь программированием с 12 лет. В процессе обучения (в ДОЦе и самостоятельно) освоил языки программирования: Delphi, Pascal, C++, Perl, Visual Basic. Больше всего увлекаюсь Web-программированием (Perl) и также программированием на Delphi.