Синтетические задачи

На всяких (полу)программистких мероприятиях иногда происходит "баттл" на непонятных задачах. Хотя само мероприятие иногда состоит из понятных задач. Под это дело часто есть призы/спонсоры.

Правда, я в них почти не участвую. Там все близко к магии, так как задачи непонятны и плохо формализованы (вообще плохо, начиная от постановки. Функция оценки, тесты и все остальное обычно еще хуже).

Это не дорожки TREC-a, там явно профессионалы и готовят и участвуют. Но и круг немного очерчен.

 Есть Яндекс с его интернет-математикой. Яндекс бывает и без интернет-математики, что аж тоже стыдно и непонятно. За последние 4 года я видел 2 соревнования по пробкам на дорогах.

Я, кстати, уже в голове примерно отличаю IR от ML от AI (information retrieval, machine learning, artificial insemination intelligence). В первом случае пишутся такие статьи: вот есть такие-то данные и такая-то задача, мы сделали так-то и получили такую-то погрешность. Свои данные мы вам не дадим, сделать как мы вы все равно не сможете, ибо реализация закрыта и даных нет, но все крута-а-а. Во втором случае есть задача, абстрактный набор данных и вот тут наши идеи как оно будет уменьшать погрешность. Ну, или мы взяли и сгенерили набор данных (который мы вам не дадим) на нем все зашибись. Другие данные мы не генерили (или там не все зашибись, не скажем), но с некоторой вероятностью наши идеи должны и на нем работать, мало ли (а вдруг). А в третьем варианте: а давай-те Каспарова в шахматы обыграем.

К баранам. В первой от Яндекса надо было по набору данных с пробок за несколько лет спрогнозировать где же они будут завтра. С точки зрения IR - нормальная задача. С точки зрения жизни - задача бесполезная. Ну нельзя в большой системе, где превышен порог ее понимания, что-то предсказывать. Система вообще не устойчивая и не сходится, любое малое изменение приводит к неконтролируемым последствиям.

Вторая задача была такова: по данным движения выбрать популярный маршрут у водителей. Типа, водители не дураки, ездят по правильным и быстрым путям. Опять же с точки зрения IR - нормальная задача, с точки зрения жизни - большинство водителей стоят в пробках. Это и будет популярным маршрутом. 

Яндекс для той же Москвы сделал хорошую штуку, они показали узкие места. Даже в интернет-новостях это было года 2 назад. Но их городские власти, похоже, уже в маразме. Разумно как раз в больше системе ликвидировать бутылочные горлышки и оно должно стать лучше. Я, например, за последние несколько лет вынужден был около универа привести суммарно недели 2. Там по данным все того же Яндекса и есть узкое место, вечером с центра по Вернадского(?) пробочка, после Ломоносовского(? или как оно там, около метро универа, которая горизонтальная) уже пусто. Так бага и решение видно невооруженным глазом. Там остановка общественного транспорта прямо на углу, в квадранте где сам универ. По горизонтальной улице по светофору кое-как успевают выехать длинные автобусы и троллейбусы. И они все не вмещаются на остановку, а последние вообще перекрывают 2-3 полосы по Вернадского(?). Вечарками там пробочка до горизонтика из машиночек. Банальщина, но если остановку перенести в глубь метров на 100, то проблемы не будет. Им вообще похоже это нравится. Ладно, это их проблемы. На конец мая 2012 там все так же.

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

В этом году от Интела видел такую классику, найти lcs (longest common substring) для длинных строк. Там типа идея должна быть в параллельности, контест на это. Посидели с Денисом и покурили пол-дня, пришли к линейному(!) решению, которое должно почти полностью влезть в память. Почти полностью - это потому что ограничения не четко даны. Многопоточить там можно вообще малую часть, если это имеет смысл. На форумах там люди обсуждали SSE, оказывается есть конвейерный поиск подстроки.

Пару лет (а может быть и 3) назад на ЧУ в качестве игровой стратегии была стандартная задача на минимакс. Лидеры сделали даже альфу-бету (первая тройка), Паша тоже реализовал альфа-бету (они были в тройке). За 5 часов. Разница между первым и вторым местом была в глубине расчета, у первых стояло 9, у вторых - 8. Там все на грани ТЛ было. В итоге распределение мест по крутизне, кто знает что такое минимакс и альфа-бета и способен это реализовать. Опять же это немного скучно.

А во всех других контестах получается по формуле, как повезет. Очень часто выигрывает наиболее тупое решение. В других случаях - слабина тестов, точнее ты угадал в тесты. Что-то из IR...

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