Конкурс на БГ мапс и Майкрософт

[Бeтон]

Някой заел ли се е?

http://www.bgmaps.com/competition2009/register.aspx

Такаааа...

Не са ли малко утешителни наградите?

Къртовски труд е това. Правя леки пояснения на задачката:
Иде реч да си вкараш всичките адреси в София (числото е сериозно), отделно цялата мрежа на трЪнспорта (т.е. спирките) и връзките между тях. Като на една спирка (станция) отговаря списък от прилежащи адреси.
Първи проблем: дъгите са вариативни за наземния транспорт. Т.е. в зависимост от деня, теглото на дъгата е различно. Ясно - заради трафика.
Втори казус - броя прекачвания. Ако заявката е от Драгоманско шосе 11 до Клокотница 1 (Вилна Зона Герман) и не може да се мине с въведено '1' от потребителя - ясно - така или иначе се смята най-късия път, ще се сметне маршрут с най-малко прекачвания.
Проблема е, ако обратното се иска. От Студентски до Дървеница - с 10 прекачвания и ползване на метро, трамвай и тролей. Нема ви казвам какво обхождане на графа ще е.
Или може да се мине с по-тънкия вариант, изкарване на Message_Dialog към потребителя:
"Аве ти тъп ли си, я въведи по-нормално число."

GPS-а ми е 400Мхц и 64 МБ рам с навигационна програма IGO 8.3 като гледам за колко малко време смята от адрес в едното кьоше на България до адрес в другото кьоше на България (а картата на Телеатлас включваща всички пътища в БГ и улици на почти всички градове и паланки не е никак елементарна)... като гледам тая задачка... щом не е направена... значи не е толкова лесна.

[Kristo]

Има още 1 момент - хората които са слагали спирки и са правили маршрутите на град транс, не са ги слагали ей така, на принципа - на 200 метра спирка, а са гледали колко хора живеят в дадения район - за 10 души в 2 къщи, спирка не се прави. Съответно където има повече хора - и повече спирки. Спокойно хората могат да извървяват пеша доста територия за да хванат рейс.

И съответно като се прави такава програма, може спокойно да "забравиш" за половината град, който не си струва да бъде отбелязван по логистични причини.

А по-вълнуващо е по картите да слагат и спирки и линии на маршрутките... или къде има таксиджииски стоянки концентрирани... ей тва ше е забавно... и полезно

[Бeтон]

Колега - теглото на дъгите не е в км, а в минути (часове ).

ГПС навигациите смятат по няколко критерия, пр. IGO, че с нея най-много съм работил. Да ме извиняват Гармините. Та:
Бърз: според разстоянието, дели на макс. допустимата скорост според участъка и получава времето. Ако пропускателната способност е по-голяма (магистрала/2,3 лентов булевард, взема това предвид пред двупосочен път/еднолентова улица)
Къс: просто пътя, който е най-малко км
Лесен: къс или нещо подобно на него
Икономичен: бърз или нещо подобно на бързия
Последните 2 практиката ми е показала, че са идентични на базовите 2.
При мен практика не липсва, така че нещата съм ги усетил live на пътя, което е много важно.

Следващото нещо, за което спомена са спирките+адресите. От изключително значение е, как ще се свържат.

Да вземем за пример спирката на баба Яга за 94 и 280. Прилежащите адреси към нея са: 40 блок, 41, 50... и тн.
Същите блокове обаче могат да бъдат прилежащи адреси на спирката до посолствата за 67 и 102. Да, съвсем логично и правилно.

Т.е. ако искаш да пътуваш от 41 блок към Руски паметник, примерно... трябва да тръгнеш от 2 изходни позиции - баба Яга и посолствата.
Ако сложим и условия за прекачвания...

Нарочно казах Руски паметник, защото 102 примерно не отива до там. Ако зададеш 41 блок - Гоце Делчев, неминуемо алгоритъма трябва да сметне само и единствено 102, щото е директна линия.
А времето между прекачванията също е от значение. Идеалния вариант е, да е 0. Ако го вземеш 0, т.е. просто събираш времената на единия + другия рейс, то ще се получат определено обърквации и ще те дънят по главата с оптималния ти маршрут
Естествено със статични данни трафика е вън от предвиждане, но едно е да изчислиш еди колко си минути, примерно 10 на прекачване, които примерно те хвърлят в адски задръствания, друго е без 10-те минути, които ще бъдат в диапазона на аха олекотен трафик.
Има разлика. 10 минути съм закъснявал, попадал съм в адски задръствания, карал съм по трамвайни линии, наваксвал съм извънредно много.

Така че тая изродщина струва повече от лаптоп с Windows 7 или XBox, да не говоря преносим хард (почти всеки може да си го позволи) кой каквото ще да ми говори...

[RadoRado]

С 1 такъв написан софтуер, те взимат в NDrivе на работа и с месечната си заплата ще си купиш и 3те награди от bgmaps.
+

За оптимален ще се счита маршрутът с най-кратко време за пътуване от точка А до точка Б при зададен брой прекачвания, който използва рационално процесорните ресурси, позволявайки едновременна работа на много потребители в контекста на един сървър.

Ти го спомена - задаването на прикачвания само може да счупи иначе работеща алчна дийкстра.
По-скоро е вариант да изчислиш минималния брой прикачвания и ако не съответстват с поисканото от потребителя да му пускаш диалог бокс. ( което пък ще яде повече ресурси от сървърите им )
Като цяло доста зле поставен конкурс с малко информация.
Моето мнение е, че не им се плаща много пари за подобен софтуер и са решили да пробват студентите ( което е даже и по-добро от професионални фирми ), но с маймуни не се ловят с трици
За такъв алгоритъм - или работа, или по-дебели награди.

п.с. Бетон до къде си стигнал с писането ?

[Бeтон]

Прав си: с трици лОвят маймуни.

Като каза алчен алгоритъм... повечето задачки от вида: сумата m с най-малко банкноти как може да бъде платена или политическа карта да се оцвети с най-малко цветове (2 съседни държави не могат да бъдат с еднакви цветове) ги решават с алчен алгоритъм.
Ама той не дава реалността в общия случай, а нещо близко.

В контекста на графите няма да получиш най-късия път.

Аз обичам да намирам реално най-късия път.
Измислих един граф, търсим от А до В

Как ще изглеждат нещата
A-T 2
A-G 3

A-T-F 7
A-T-S 5
A-G-S 5
A-G-E 10
Изтриваме реда A-T-F 7, защото F вече няма необходени съседи.
Изтриваме реда A-G-S 5, защото A-T-S = 5 (кой от двата в случая е равностойно)

Продължаваме:
A-T-S-Е 8
A-T-S-G 7
A-G-E-B 20
A-G-E-S 13
Изтриваме реда A-T-S-G 7, защото A-G 3
От същите съображения и другия

A-T-S-E-B 18
A-T-S-E-G 15

Окончателно:
A-T-S-E-B 18

Готово! Със сигурност е най-късия път.

Алчния алгоритъм би дал решение:
A-T-S-G-E-B 24

Представям си от Владая до Ботунец какво ще става.

[RadoRado]

Е чисто алчен би бил бавен и неточен
Мен ми е интересно дали потребителите освен прикачвания ще могат да задават и приоритети - "искам само с автобус", "искам път за кола", "искам повече пеша" и т.н. - Тогава самото обхождане на графа ще има нещо алчно в него.

Също така, това нещо ме човърка :

Входни данни ще бъдат предоставени от ДАТЕКС и ще се базират на данните от Центъра за Градска Мобилност, София.

След като се регистрираш ли ти предоставят данните, за да си тестваш алгоритъма ?

[moridinbg]

Участниците дават съгласие, ако бъдат определени за победители на 1-во, 2-ро и 3-то място – авторските права върху изработения продукт да възникват директно и първоначално за ДАТЕКС ООД. Същите нямат право да получат наградите, ако се откажат от това условие и не подпишат договора за отстъпване на права, който ще им бъде предложен на церемонията за получаване на наградите.

*finger*

[Бeтон]

Мен ми е интересно дали потребителите освен прикачвания ще могат да задават и приоритети - "искам само с автобус", "искам път за кола", "искам повече пеша" и т.н. - Тогава самото обхождане на графа ще има нещо алчно в него.

Естествено, това си влиза в задачата.
Само "път за кола" не ми ясно точно какво имаш предвид - то където движат раздрънкани автобуси и тролеи, е път за кола.
Иначе "искам повече пеша" - съвсем резонен критерий за изчисляване на маршрут. Ето пример Плиска:
Къде по-удобно е да слезеш от 280 примерно и да повървиш 50 метра пеш до спирката на 72, отколкото да не зададеш елемент "пеш между спирки", щото ще станат екстравагантни прекачвания

Нали може на GPS-а да махнеш ферибот при изчисляване на маршрут, който има въпиюща нужда от пресичане на воден басейн. Ама нали се сещаш алтернативния маршрут какъв може да е.

Също така, това нещо ме човърка :

Входни данни ще бъдат предоставени от ДАТЕКС и ще се базират на данните от Центъра за Градска Мобилност, София.

След като се регистрираш ли ти предоставят данните, за да си тестваш алгоритъма ?

И на мен това не ми е ясно.
А тия входни данни нали са в някакъв формат? И оттова силно зависи как ще се подреди програмата.
Аз обаче да взема да се регистрирам и да видя.

[Бeтон]

Ай честито.
Ето ви входни данни.
http://www.bgmaps.com/competition2009/d ... 31B65DE442

Ортогонална КС е вкарана даже. И смятат по Питагор разстояния.

[TheOnly]

Условията на конкурса са просто крайни

А отношението между стойността на наградите (взети заедно) върху стойността на положения труд + условията клони към нула Където М$ имат пръст, нещата не вървят надобре.

Иначе заданието е интересно.

[vvvv]

Влизаш в сайта и виждаш, че е фрашкано с реклами.. правиш една сметка и излиза, че взимат минимум по 4-5 хиляди на ден.. нема лошо. Седни 2-3 седмици и мисли алгоритми, пък после видиш ти можеш да вземеш некое лаптопче.. USB хардче - все полезни неща. Те хората после ще си увеличат тарифката и ще почнат да взимат по 7-8-9 хиляди лева на ден.. е кво нали са ти дали там да си играеш. Евалата.. добре са го измислили!

[Бeтон]

Човек, то е ясно от самото начало, че добре са го измислили В ТЯХНА ПОЛЗА.
Ние като прости хора можем да си направим следната сметка. Сумата за наградите им е не повече от 2 хиляди лева, от мен да мине - малко повече. Като сложим организация по конкурса ала-бала... събрано повече от 3-4 едва ли ще хвърли.
А някой сигурно им е поискал за това 10 К. Проекта е специфичен - не може да вземеш Нюйоркския или Парижкия и да чакаш да тръгне за София
И решили да се направят на цигани.