Средняя скорость для ребер в определенный час

[tilorn]

А так' date=' как я предлагаю - сравнивать средние температуры по всем больницам города за последние полчаса и решить, куда идти на диспансеризацию )

[/quote']

совершенно верно, только это не позволит принять решение о том куда идти на диспансеризацию сейчас, только стоит ли вообще сейчас куда-либо идти.

а вот если учитывать время, направления, день недели, то не только стоит ли идти, а еще как раз именно куда.

Размер карты СПб сейчас - 10 Мб, если к каждому ребру прибавить еще 5 байт, то думается получится уж никак не больше 15-20 Мб. это несущественно, имхо.

[crazydoctor]

tilorn, то что ваш алгоритм более точный - никто не спорит. Более того, вы - не первый, кто его предлагает (в том или ином виде). Я тоже уже успел его предложить

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

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

Мне кажется, этот порог уже превышен, поэтому смысла реализовывать более точный, но и более громоздкий алгоритм смысла не имеет.

[Lanj]

Мне кажется что алгоритм предложенный господином tilorn'ом должен давать более приближенную к реальности информацию, чем алгоритм Шпрота, т.к. если собирать статистику по часам и дням недели, то охватываются все промежутки времени, и дается информация о загруженности данного участка дороги в данный промежуток времени. А по алгоритму господина Шпрота выходит, что наиболее точные данные будут либо ночью, когда датчиков почти нет, либо днем, когда датчиков максимальное количество, а промежуточное время, например 7-9 утра будет оцениваться не очень эффективно, т.к. где-то в это время уже приличные пробки, а где-то еще свободно, и на свободных дорогах (при отсутствии датчиков)неверно будет понижаться индекс скорости, потому что данные собираются по городу, а не по конкретному участку дороги.

Ели я не прав, поправьте меня, может я что-то не так понял.

[Spectre]

tilorn

Это получается, как в больнице: собирать статистику температуры по сезонам, выходным и будням, ночью и днём.

 

А так, как я предлагаю - сравнивать средние температуры по всем больницам города за последние полчаса и решить, куда идти на диспансеризацию )

По статистике mail.ru в часы пик средняя СКОРОСТЬ движения по Москве возрастает. Сюрприз?

 

А еще при этом нет учета того, что дорога в центр и из центра совершенно разные вещи.

 

Да. И ключевая мысль этого топика - возможность прокладывать маршрут исключая заведомо пробочные участки.

[Шпрот]

 

Да. И ключевая мысль этого топика - возможность прокладывать маршрут исключая заведомо пробочные участки.

 

Для этого есть "пробки по рассписанию".

 

Чтобы реализовать механизм tilorn, необходимо провести огромную работу.

У нас сейчас даже скорости, зашитые в карту, выставлены "от балды", пока кто-то не сообщит в баг-форму.

Всё равно, даже если такую работу провести - гарантий, что информация будет соответствовать действительности, никаких нет.

 

И представьте себе, сколько будет тратиться на траффик при обновлении!

 

Хотя эту идею я не отвергаю, просто мне кажется, что никто тщательно этим заниматься не будет. К сожалению.

 

crazydoctor

 

+1

 

Если средняя скорость по городу - "25", то программа с радостью направит вас проехать по подтверждённым "40", считая это за антипробку, нежели кидать в объезд, где вшита "50", а будет там пробка или нет - никто не знает.

В любом случае, в час пик неизведанные рёбра будут использоваться с осторожностью.

 

И наоборот.

Если ночью средняя скорость будет "60", а на дороге кто-то поставит "40", то программа пошлёт в объезд, так как понижающего коэффициента к неподтверждённым "50" применено не будет.

[Spectre]

Для этого есть "пробки по рассписанию".

 

Пробки по расписанию только мешают. Я не могу сам определить пробка в этом месте или нет. Кроме того, они тоже не на статистике основаны.

 

 

[Semion_ilitch]

Простите, пожалуйста, а что такое ребро?

[Spectre]

Ребро дорожного графа.

Грубо говоря, отрезок дороги/улицы от перекрестка до перекрестка.

[YoGun]

Простите, пожалуйста, а что такое ребро?

 

http://forum.probki.net/forum_posts.asp?TID=4274&KW=%D0%E5%E1%F0%EE+%F7%E0%F1%F2%FC+%F3%EB%E8%F6%FB&PID=42009#42009 своими словами объяснял.

 

[shooo]

Чтобы этот индекс вносил поправляющий коэффициент в среднестатистическую скорость на ребре.

Если коэффициент будет применяться ко всем улицам, то что он даст? По сути, для проложения маршрута не важно какая скорость заявлена на ребере в абсолютной величине, главное как она соотносится с со скоростями на других ребрах!

Предложение tilornа, конечно, более логичное, хотя требует значительного расширения и серверной части и изменения клиента

[гидро]

не ко всем улицам, а ко всем индексам скорости.

а вот на улицах будут индексы+пробочная информация.

[Spectre]

Так не все ли равно? Главное, что один объезд имеет смысл, ибо улица обычно свободнее, а другой - нет, ибо улица вечно стоит в час пик.

А в выходные, например, ситуация может быть строго обратной: первая улица еле ползет, а вторая - летит.

[shooo]

не ко всем улицам' date=' а ко всем индексам скорости.а вот на улицах будут индексы+пробочная информация.[/quote']

Честно говоря, не вижу особой разницы. Ну в час пик, на всех улицах по котором нет данных по пробкам разом снизят индекс. Как это поможет выбору адекватного маршрута?

[YoGun]

Честно говоря' date=' не вижу особой разницы. Ну в час пик, на всех улицах по котором нет данных по пробкам разом снизят индекс. Как это поможет выбору адекватного маршрута? [/quote']

 

Тогда для программы "хрюшка" 30 или 40 будет уже "антихрюшкой". То есть когда стоит выбор между улицой без данных (но где по умолчанию стоит 50) и улицой на которой гарантированно 30, программа будет выбирать 30.

Но по-моему, статистикой будет более правильно делать.

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

 

[tilorn]

Еще раз: алгоритм средней температуры не дает никакого представления о свободных направлениях движения. _никакого_. Рассмотрим две ситуации, один и тот же город.

Время 9 утра и время 6 вечера, средняя скорость всех датчиков по городу 25 км.ч в первом случае и 25 км.ч во втором. Согласны? Только в первом случае все едут в центр, а во втором из центра. Зачем нам вводить такой параметр, если он бестолковый?????

Чтобы реализовать механизм необходимо провести огромную работу.

У нас сейчас даже скорости' date=' зашитые в карту, выставлены "от балды", пока кто-то не сообщит в баг-форму.

Всё равно, даже если такую работу провести - гарантий, что информация будет соответствовать действительности, никаких нет.

 

[/quote']

Чтобы реализовать этот механизм надо:

1. На сервере начать собирать статистику для ребер по времени и складывать ее в БД.

2. Зашить в карту не какие-то странные индексы, а по 5 байт на ребро этой статистики.

3. Продолжать собирать на сервере статистику, обновляя карты вместе с ней.

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

Пример описания бага:

На такой-то улице утром средняя на север 20, на юг 70, днем 40 и туда и туда, вечером на север 70, на юг 20, по выходным и ночью 80-90 без проблем

[shooo]

Тогда для программы "хрюшка" 30 или 40 будет уже "антихрюшкой". То есть когда стоит выбор между улицой без данных (но где по умолчанию стоит 50) и улицой на которой гарантированно 30' date=' программа будет выбирать 30. [/quote']

Ну и будет СГ водить по магистралям по которым ездит большинство и которым заведомо присвоенны повышенные индексы скорости. А так - СГ и так достает любовью к Московскому проспекту, Лиговскому и другим основным магистралям, которые как раз обычно в час пик и забиты

[shooo]

Только в первом случае все едут в центр' date=' а во втором из центра. Зачем нам вводить такой параметр, если он бестолковый?????[/quote']

Совершенно с вами согласен! А если боятся увеличения трафика, то в принципе можно вообще не учитывать ночной период! Вопрос и впрямь стоит о 4-5 бит на ребро. Сколько там ребер в городе тысяч 10? Это ж 5 кбайт инфы! О чем речь?

[crazydoctor]

Для разработчиков - это невелика задача' date=' алгоритм софта переписывать даже не придется. Именно нужен компонент, который соберет статистику сложит ее в базу, потом наложит на карту, небольшое изменение в клиентской части, чтобы использовались скоростные индексы, характерные для данного времени и все заработает.[/quote']

Судя по всему, вы никогда не сталкивались с задачей статистической обработки данных. К сожалению, все не так просто, как кажется. Это реально сложная и объемная задача.

Кроме того, алгоритм софта переписывать очень даже придется (хотя бы для того, чтобы выбирался нужный индекс согласно времени суток/дня недели). Формат карты тоже придется изменить.

Узкие места в алгоритме так же есть:

- нужно не забывать о праздниках и переносах рабочих дней

- нужно как-то реагировать на приезды президентов и проч.

- при существенном изменении дорожной обстановки (одностороннее движение, запрет поворота и т.д.) нужно обнулять статистику по целому ряду улиц. Причем не ясно, как эти улицы выбирать.

Итого, разработка выливается в следующие неслабые доработки:

1. поднятие сервиса статистики

2. изменение формата карты

3. доработка программы

4. постоянные мероприятия по поддержанию статистики (см. выше).

Т.е. все не так просто, как кажется.

А самое главное, попробуйте понять мысль, которую я уже высказывал в этой ветке: при числе датчиков более N оба алгоритма будут выдавать идентичный результат. Под результатом я понимаю одинаково оптимальные маршруты. Если кто не согласен с данным утверждением - могу объяснить подробнее.

Итого, если это N уже превышено - то реализовывать более сложный алгоритм особого смысла не имеет.

[shooo]

[shooo]

[tilorn]

Судя по всему' date=' вы никогда не сталкивались с задачей статистической обработки данных. К сожалению, все не так просто, как кажется. Это реально сложная и объемная задача.

[/quote']

Вообще-то сталкивался, так как работаю в сфере разработки ПО. И это действительно не так сложно. Потому как не стоит задача оценки качества выборки, кластерного анализа, регрессионного и проч. Задача действительно проста, пробочный датчик проехал по ребру делаем insert в базу данных, потом считаем среднее по любому приятному алгоритму. в чем сложность? или надо помочь - самому спроектировать БД, описать процедуры добавления данных, потом построения результирующей статистики, в принципе могу, конечно.

[shooo]

конечно нарисовать 3д объекты гораздо дешевле и полезнее' date=' главное конкурентное преимущество от этого появится просто сумасшедшее. [/quote']

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

[tilorn]

коими и является видимо 3д. который точно не станут воровать конкуренты. видимо, потому, что он им очень нужен.

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

СГ может максимально затруднить использование этой информации любой другой софтиной кроме самого СГ, уж поверьте это можно сделать и достаточно легко. плюс информация обновляема, к примеру раз в месяц, следовательно операцию по доставанию статистики конкурентам придется повторять.

[shooo]

СГ может максимально затруднить использование этой информации любой другой софтиной кроме самого СГ' date=' [/quote']

придется делать так, чтобы статистические индексы скоростей нельзя было посмотреть как нынешние прямо с экрана...

[Spectre]

Тут одна неприятность - положим СГ вложится в сервер статистики' date=' наберет статистику (это все время и деньги) - где гарантия, что потом эту информацию просто не срисуют конкуренты, хотя бы для определения начальных индексов скоростей для ребер? И хрен чего докажешь! Я думаю разработчиков (и владельцев) СГ интересуют более трудновоспроизводимые алгоритмы и технологии[/quote']

1. Ничего дополнительного покупать не надо. У СГ и Мэйла статистика собирается уже давно. Дополнительных мощностей, как я понимаю, для этого не нужно.

2. А что конкурентам сейчас мешает скачивать пробочные данные из программы и использовать ее у себя?