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

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

Такаааа...

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

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

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

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

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

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

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

ГПС навигациите смятат по няколко критерия, пр. 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, да не говоря преносим хард (почти всеки може да си го позволи) кой каквото ще да ми говори...

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

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

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

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

Като каза алчен алгоритъм... повечето задачки от вида: сумата 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

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

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

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

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

*finger*

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

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


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

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

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

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

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

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

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

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