Сообщение от WooD
Извините зануд.
Ответ на вопрос:
http://ru.wikipedia.org/wiki/%D0%A2%...84%D0%BE%D0%B2
Идея применения для системы дорог проста. Строим сетку. В узлах - перекрестки. Ребра - дороги их соединяющие. Любой маршрут (участок дороги соединяющий два соседних узла) имеет цену или, как иногда говорят вес. В данном случае цена - время прохождения участка.
Задача: минимизировать время в пути из точки А в точку Б (обычно точки не смежные). Можно еще добавлять цену прохождения перекрестка (например в зависимости от направления или добавлять разные веса дороги при движении в разном направлении в данное время суток). При определении веса (цены) участка не забываем про время суток - всем, надеюсь, очевидна зависимость от времени.
Задача и в простом, теоретическом варианте не сахар по требуемой вычислительной мощности, а уж с динамическими весами- ну может быть в следующем столетии решат.
Задача в нашем понимании звучит еще краше:
Оптимизировать сеть дорог таким способом, чтобы вне зависимости от времени суток время прохождения из множества узлов А (множество узлов берем в центре города) до множества узлов Б (берем на окраинах города) не превышало (хотя бы) 1 час.
Думаю, в такой постановке (она еще сильно упрощена!!) задача не решаема. Имеют ли смысл другие постановки задачи - не думаю.
Вообщем, мне кажется, для моделирования движения на наших дорогах больше подходит термодинамика, чем теория графов.
Можно попробовать решить набор частных задач - с оптимизировать время маршрута из кремля до рублевки - вот это у нас с успехом умеют делать, правда не математическими методами.
Короче, не забивайте себе головы![]()