forum.uni-sofia.bg :: Виж темата - Конкурс на БГ мапс и Майкрософт

forum.uni-sofia.bg https://forum.su.schools.bg/

Конкурс на БГ мапс и Майкрософт https://forum.su.schools.bg/viewtopic.php?f=55&t=15977	Страница 1 от 1

Автор:	Бeтон [ 05 Ное 2009, 20:53 ]
Заглавие:	Конкурс на БГ мапс и Майкрософт
Някой заел ли се е? http://www.bgmaps.com/competition2009/register.aspx Такаааа... Не са ли малко утешителни наградите? Къртовски труд е това. Правя леки пояснения на задачката: Иде реч да си вкараш всичките адреси в София (числото е сериозно), отделно цялата мрежа на трЪнспорта (т.е. спирките) и връзките между тях. Като на една спирка (станция) отговаря списък от прилежащи адреси. Първи проблем: дъгите са вариативни за наземния транспорт. Т.е. в зависимост от деня, теглото на дъгата е различно. Ясно - заради трафика. Втори казус - броя прекачвания. Ако заявката е от Драгоманско шосе 11 до Клокотница 1 (Вилна Зона Герман) и не може да се мине с въведено '1' от потребителя - ясно - така или иначе се смята най-късия път, ще се сметне маршрут с най-малко прекачвания. Проблема е, ако обратното се иска. От Студентски до Дървеница - с 10 прекачвания и ползване на метро, трамвай и тролей. Нема ви казвам какво обхождане на графа ще е. Или може да се мине с по-тънкия вариант, изкарване на Message_Dialog към потребителя: "Аве ти тъп ли си, я въведи по-нормално число." GPS-а ми е 400Мхц и 64 МБ рам с навигационна програма IGO 8.3 като гледам за колко малко време смята от адрес в едното кьоше на България до адрес в другото кьоше на България (а картата на Телеатлас включваща всички пътища в БГ и улици на почти всички градове и паланки не е никак елементарна)... като гледам тая задачка... щом не е направена... значи не е толкова лесна.

Автор:	Kristo [ 06 Ное 2009, 01:25 ]
Заглавие:	Re: Конкурс на БГ мапс и Майкрософт
Има още 1 момент - хората които са слагали спирки и са правили маршрутите на град транс, не са ги слагали ей така, на принципа - на 200 метра спирка, а са гледали колко хора живеят в дадения район - за 10 души в 2 къщи, спирка не се прави. Съответно където има повече хора - и повече спирки. Спокойно хората могат да извървяват пеша доста територия за да хванат рейс. И съответно като се прави такава програма, може спокойно да "забравиш" за половината град, който не си струва да бъде отбелязван по логистични причини. А по-вълнуващо е по картите да слагат и спирки и линии на маршрутките... или къде има таксиджииски стоянки концентрирани... ей тва ше е забавно... и полезно

Автор:	Бeтон [ 06 Ное 2009, 02:59 ]
Заглавие:	Re: Конкурс на БГ мапс и Майкрософт
Колега - теглото на дъгите не е в км, а в минути (часове ). ГПС навигациите смятат по няколко критерия, пр. 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 [ 06 Ное 2009, 21:54 ]
Заглавие:	Re: Конкурс на БГ мапс и Майкрософт
С 1 такъв написан софтуер, те взимат в NDrivе на работа и с месечната си заплата ще си купиш и 3те награди от bgmaps. + Цитат: За оптимален ще се счита маршрутът с най-кратко време за пътуване от точка А до точка Б при зададен брой прекачвания, който използва рационално процесорните ресурси, позволявайки едновременна работа на много потребители в контекста на един сървър. Ти го спомена - задаването на прикачвания само може да счупи иначе работеща алчна дийкстра. По-скоро е вариант да изчислиш минималния брой прикачвания и ако не съответстват с поисканото от потребителя да му пускаш диалог бокс. ( което пък ще яде повече ресурси от сървърите им ) Като цяло доста зле поставен конкурс с малко информация. Моето мнение е, че не им се плаща много пари за подобен софтуер и са решили да пробват студентите ( което е даже и по-добро от професионални фирми ), но с маймуни не се ловят с трици За такъв алгоритъм - или работа, или по-дебели награди. п.с. Бетон до къде си стигнал с писането ?

Автор:

Бeтон [ 07 Ное 2009, 00:09 ]

Заглавие:

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

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

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

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

Прикачени файлове:

graph.png [ 4.89 KiB | Прегледано 1146 пъти ]

Автор:	RadoRado [ 07 Ное 2009, 11:57 ]
Заглавие:	Re: Конкурс на БГ мапс и Майкрософт
Е чисто алчен би бил бавен и неточен Мен ми е интересно дали потребителите освен прикачвания ще могат да задават и приоритети - "искам само с автобус", "искам път за кола", "искам повече пеша" и т.н. - Тогава самото обхождане на графа ще има нещо алчно в него. Също така, това нещо ме човърка : Цитат: Входни данни ще бъдат предоставени от ДАТЕКС и ще се базират на данните от Центъра за Градска Мобилност, София. След като се регистрираш ли ти предоставят данните, за да си тестваш алгоритъма ?

Автор:	moridinbg [ 07 Ное 2009, 12:46 ]
Заглавие:	Re: Конкурс на БГ мапс и Майкрософт
Цитат: Участниците дават съгласие, ако бъдат определени за победители на 1-во, 2-ро и 3-то място – авторските права върху изработения продукт да възникват директно и първоначално за ДАТЕКС ООД. Същите нямат право да получат наградите, ако се откажат от това условие и не подпишат договора за отстъпване на права, който ще им бъде предложен на церемонията за получаване на наградите. finger

Автор:	Бeтон [ 07 Ное 2009, 12:58 ]
Заглавие:	Re: Конкурс на БГ мапс и Майкрософт
RadoRado написа: Мен ми е интересно дали потребителите освен прикачвания ще могат да задават и приоритети - "искам само с автобус", "искам път за кола", "искам повече пеша" и т.н. - Тогава самото обхождане на графа ще има нещо алчно в него. Естествено, това си влиза в задачата. Само "път за кола" не ми ясно точно какво имаш предвид - то където движат раздрънкани автобуси и тролеи, е път за кола. Иначе "искам повече пеша" - съвсем резонен критерий за изчисляване на маршрут. Ето пример Плиска: Къде по-удобно е да слезеш от 280 примерно и да повървиш 50 метра пеш до спирката на 72, отколкото да не зададеш елемент "пеш между спирки", щото ще станат екстравагантни прекачвания Нали може на GPS-а да махнеш ферибот при изчисляване на маршрут, който има въпиюща нужда от пресичане на воден басейн. Ама нали се сещаш алтернативния маршрут какъв може да е. RadoRado написа: Също така, това нещо ме човърка : Цитат: Входни данни ще бъдат предоставени от ДАТЕКС и ще се базират на данните от Центъра за Градска Мобилност, София. След като се регистрираш ли ти предоставят данните, за да си тестваш алгоритъма ? И на мен това не ми е ясно. А тия входни данни нали са в някакъв формат? И оттова силно зависи как ще се подреди програмата. Аз обаче да взема да се регистрирам и да видя.

Автор:	Бeтон [ 07 Ное 2009, 13:19 ]
Заглавие:	Re: Конкурс на БГ мапс и Майкрософт
Ай честито. Ето ви входни данни. http://www.bgmaps.com/competition2009/d ... 31B65DE442 Ортогонална КС е вкарана даже. И смятат по Питагор разстояния.

Автор:	TheOnly [ 09 Ное 2009, 05:10 ]
Заглавие:	Re: Конкурс на БГ мапс и Майкрософт
Условията на конкурса са просто крайни А отношението между стойността на наградите (взети заедно) върху стойността на положения труд + условията клони към нула Където М$ имат пръст, нещата не вървят надобре. Иначе заданието е интересно.

Автор:	vvvv [ 29 Ное 2009, 00:07 ]
Заглавие:	Re: Конкурс на БГ мапс и Майкрософт
Влизаш в сайта и виждаш, че е фрашкано с реклами.. правиш една сметка и излиза, че взимат минимум по 4-5 хиляди на ден.. нема лошо. Седни 2-3 седмици и мисли алгоритми, пък после видиш ти можеш да вземеш некое лаптопче.. USB хардче - все полезни неща. Те хората после ще си увеличат тарифката и ще почнат да взимат по 7-8-9 хиляди лева на ден.. е кво нали са ти дали там да си играеш. Евалата.. добре са го измислили!

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

Страница 1 от 1	Часовете са според зоната UTC + 2 часа
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/