Система управление движением городского транспорта.

[SkorKNURE]

Доброго времени суток всем форумчанам!
На протяжении нескольких лет я увлекаюсь олимпиадной информатикой: ACM-контесты, TopCoder и т.д., думаю многим знакомо что это такое. Был на полуфиналах ACM в Румынии, написал много разных контестов, решал архивы, сборы и т.п. Вобщем, имею определенный опыт и интерес к решению комбинаторных задач, задач на графах, ДП, оптимизации и пр. И сейчас я стою на пороге решения большой и абстрактной задачи: разработки системы анализа и управления городским транспортом. Эта тема моего бакалаврского диплома.

Проблема в том, что у меня нет конкретных задач, но есть полная свобода действий в их выборе: оптимизация движения, работы сфетофорной сигнализации, борьба с пробками, анализ, прогнозирование, управление с помощью ИИ и т.д. Очевидно, что в основе всего лежит большой граф городских дорог, анализ движения машин на котором производится. Возможно еще, расписание работы светофоров и некоторая статистика по движению машин. И я могу выбрать совершенно произвольные задачи, которые мне будут интересны, и которые хоть как-то, каким-нибудь боком можно "приплести" к данной тематике. Конечно, я хочу написать диплом на близкую к информатике и алгоритмам тему, о которой уже имею некоторое представление. Но проблему я вижу в следующем: большинство конкретных олимпиадных тем можно назвать сложными, хитрыми, нестандартными, но никак не емкими и глубокими в научном плане. Нельзя же написать диплом на тему поиска каких-нибудь кратчайших путей, остовных деревьев или максимальных потоков на этом графе. В особенности, самыми классическими методами.

Я буду очень благодарен, если вы выскажите любые идеи, любые задачи (связанные с теорией графов, оптимизацией, ИИ, и др), которые интересно было бы решать в рамках диплома и которые хоть как-то можно связать с моей темой. Я понимаю, что подобные вещи нужно обсуждать на кафедре, с научным руководителем и т.д. - но к сожалению, по этой теме мне не с кем проконсультироваться. Я готов тратить сколько потребуется времени на освоение нового материала и изучение новых тем самостоятельно - но я не хочу решать те задачи, которые могут мне предложить на родной кафедре :) Я очень от них далек и мне они не интересны.

Буду рад любым материалам, ссылкам, советам и критике.
С уважением, SkorKNURE

[Toucan]

Тема перемещена из "Программирования".
Дубль из раздела "Математика (общие вопросы)" удалён.

[Yuri Gendelman]

SkorKNURE в сообщении #408599 писал(а):

Я буду очень благодарен, если вы выскажите любые идеи, любые задачи (связанные с теорией графов, оптимизацией, ИИ, и др), которые интересно было бы решать в рамках диплома и которые хоть как-то можно связать с моей темой.

Например, есть знаменитая Vehicle Routing Problem (все книги можно скачать):
- The Vehicle Routing Problem // ed. by Paolo Toth, Daniele Vigo // SIAM. 2001
- Vehicle Routing Problem // ed. by Tonci Caric and Hrvoje Gold // In-Tech. 2008
- The Vehicle Routing Problem: Latest Advances and New Challenges // ed. by Bruce Golden, S. Raghavan, Edward Wasil // Springer. 2008
Точное ее решение возможно только перебором. Эвристические методы активно разрабатываются и реализуются в коммерческих пакетах.

Полезно погуглить по ключам "Transportation Networks", "Public Transport", "Intelligent Transportation Systems", "Traffic Flow".

SkorKNURE в сообщении #408599 писал(а):

Я понимаю, что подобные вещи нужно обсуждать на кафедре, с научным руководителем и т.д. - но к сожалению, по этой теме мне не с кем проконсультироваться.
...я не хочу решать те задачи, которые могут мне предложить на родной кафедре :) Я очень от них далек и мне они не интересны.

Это очень серьезная проблема. На форумах можно обсудить олимпиадную задачу, но написать диплом так не получится. Если Вы собираетесь работать совершенно самостоятельно, то должны самостоятельно решать ВСЕ вопросы, в т.ч. выбрать тему. Если нет, то ищите руководителя [дополнительного?] на другой кафедре.