Пространная задача для размышления

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

Итак, упуская тех. детали.
Представьте что вы в своем автомобиле на вьезде в город. У вас ограниченное количество топлива, но вам нужно найти адресс некоего Джона в этом городе за минимальное время. Допустим некий Джон один единственный в городе живет и вы это знаете точно.

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

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

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

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

Ctrl + Enter

Cody Snider 23.09.2017 01:17

З умови задачі не зрозуміло в яких масштабах можна сортувати жителів.

Дано:
Джон в місті лише один.
Машина на вїзді в місто.
Обмежена кількість пального.

Завдання: Знайти Джона за мінімальний час, навіть якщо закінчилось пальне.

Рішення:
Пошук лінійний.

Для використання евристики потрібно певне знання про структуру простору (Ми, навіть, не знаємо, де центр міста).

Варіанти простору:
1. Місто з однієї вулиці
2. Місто з двох перехресних вулиць.
3. Місто з двох параллельних і однією перпендикулярної (для простоти) вулиць.
4. Місто з двох декількох паралельних і перпендикулярних вулиць — многогранник.

Виходячи з вищенаведених припущень про структуру спробувати побудувати оптимальний по часу лінійний пошук. Наприклад, для варіанту 4, я б зробив пошук від периметру міста (не потрібно буде тратити пального) до центру по спіралі.

Задача дозволяє створити власну карту?

Відповісти

Підтримати

Олексій Пєніє 22.09.2017 23:10

Представляемся Джоном и пробуем зарегистрироваться в этом городе. Если в городе Джон уже есть, значит какой-то механизм должен сработать и сообщить что не уникален, что уже где-то такой живёт.

Oleksandr Nahirniak Software Engineer в Stripe 22.09.2017 21:12

Если у нас с входных данных только уникальное имя Джон и не кто с жителей не знает где его искать, то можно начинать с того, что бы представить город как граф, дома-вершины, улицы — ребра, более того у вершин есть свой вес(приоритет), у многоэтажного дома он больше, так как шанс найти Джона там выше(потратив меньшее кол-во топлива), а у улиц свой вес(длина улицы, без учета пробок :) ), т.е у нас как минимум 2 критерия по которым стоит строить маршрут, строим маршрут по критериям, что бы максимально эффективно обойти все дома, если попадаем на много этажный дом, то по бинарному поиску ищем Джона, profit.
UPD:
В лучшем случае, то каждый жилец города окажется доброжелательным и поможет тебе искать Джона по тому же самому алгоритму, что описан выше, конечно же с минимальным количеством пересечений c другими жильцами

Дмитрий Шахов C++/C# Developer в ФОП Шахов Д.В. 22.09.2017 16:18

1. Использовать фильтр если есть какие то доп. данные.
2. Если фильтра нет, то только полный перебор.
3. Может быть можно спрашивать у каждого следующего жителя где живет джон.

Vlad Stelmahovsky Software Engineer в Verity AG 22.09.2017 14:25

определить, какую недвижимость может позволить себе Джон и начинать с этих районов

Олексій Пєніє 23.09.2017 11:52

©ком.взвода артиллерии

Vlad Stelmahovsky

Олексій Пєніє 22.09.2017 13:31

А можно встречную задачу: Я — владелец многоквартирного дома. И я хочу чтобы к моим Джонам приходили только девки горячие по заказу, а мусора, продавцы пылесосов и верителивывбога — не появлялись. Разумеется, карту где живут богатенькие Джоны, а где заводчики бультерьеров, я на входе вешать не стану. Если вы примерно знаете как выглядит Джон, у вас есть огромная вероятность его опознать позвонив в дверь.

Джон откроет. Он всем открывает, такова его природа. Заводчик бультерьеров тоже, притом автоматом по звонку.

Реальная проблема: все кому не лень не просто ходят, не просто звонят в дверь, а ещё и пробуют это всё отмычками (неэфективными в абсолютном большинстве случаев). Притом каждую ночь шастают. А самое смешное, что часть из них — сутенёры девок, типа для безопасности, убедиться что их не покусают. При том что у девки есть код доступа, сутенёры им не пользуются в силу тупости (косньерж уже 500 страниц логов нагрёб, говорит что засношался).

ВОПРОС: Каким способом можно обезопасить Джона, не имея (вернее не желая селить в своём доме) заводчика бультерьера, любителя взрывных устройств, или больного с активной формой туберкулёза. Потому что уже были прецеденты в других домах, что прошла перепись населения (не спрашивай почему непланово), сожрали агентов. В результате дома оказались деклассированы на рынке недвижимости по причине перечисленных проблем, хрен теперь докажешь что не верблюд.

Євген Лесько Competency manager в ELEKS 22.09.2017 13:13

Если массив не посортирован, я знаю один метод поиска в таком массиве :( разве что начинать поиск можно с разных концов «города».
А нельзя ли сделать так, чтобы этот Джон сам Тебя искал? вышел навстречу машине? Или как вариант повесить на него дополнительную пропитю: единственный сумасшедший на весь город , например...

Олексій Пєніє 22.09.2017 13:19

Не каждый Джон захочет — это раз. Не каждый заказчик хочет чтобы Джон знал что его ищут.

Євген Лесько

Євген Лесько Competency manager в ELEKS 22.09.2017 14:13

тогда, не каждый Джон обязан знать, что у него в попе чип и что его ищут :)

Олексій Пєніє

anonymous 22.09.2017 13:41

Євген Лесько Competency manager в ELEKS 22.09.2017 14:12

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

решение не подразумевает что мы имеем какието дополнительные структуры данных (вроде карт и тд).

А мы имеем какие-то дополнительные данные про Джона? болен СПИДом или проказой, национальность (китаец — ищем в китайском квартале), любит природу, боится высоты и живет только в одноэтажном доме? ИМХО наличие и использование таких данных — это то, о чем грит Виктор и что реально поможет сузить круг поиска.

anonymous

anonymous 22.09.2017 14:21

Євген Лесько Competency manager в ELEKS 22.09.2017 14:33

Если не пытаться искать нечто out-of-box, то О(n) как ни круть-верть :( Единственное: если «некий Джон один единственный в городе живет и вы это знаете точно», и остался последний хутор — то можно этот хутор и не проверять :) но я в курсе, что О(n) = О(n-1) :)

anonymous 22.09.2017 14:38

Alex Za 21.09.2017 23:41

Находим адрес в интернете, это быстрее, чем кататься. Следующие пункты уже можно не выполнять, ибо адрес найден и задача выполнена.
OK google как проехать *. Если бензина мало — идем пешком.

Andrey Rogovsky CoFounder в ГО АФК 21.09.2017 19:50

Просчитать максимальный путь избегая перекрестков и надеятся на удачу

anonymous 21.09.2017 18:27

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

DNA Exp 21.09.2017 18:41

del

Mikhail Boiko SE в NVIDIA 21.09.2017 17:10

Нужно построить специальный дом где буде жить Джон и по всему городу развесить указатели к его дому.

Oleksii Zazulin android dev 21.09.2017 21:15

да еще и на въезде в город построить!

Mikhail Boiko

Олексій Пєніє 21.09.2017 22:40

Классика, сэр!

Andrey Bulanov Senior Engineer 21.09.2017 16:35

Отправить Джону смс, что дальнейшее хранение посылки — платное, сам найдется:)
А вообще, можно скомбинировать. Поначалу делаем полный объезд домов, когда Джон найден, индексируем его. В дальнейшем, если нам нужен Джон, мы точно знаем где он живет, если нужен Вася, то мы точно знаем, где Васи нет, потому что там Джон.

Vasya Pupking 22.09.2017 00:15

мы с ним вместе арендуем, шарим.

Andrey Bulanov

anonymous 21.09.2017 15:58

Кажется те нужен фильтр Блума

Олексій Пєніє 21.09.2017 22:50

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

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

anonymous 22.09.2017 08:34

Да, я не дочитал до ограничения на мета информацию.

anonymous 21.09.2017 15:29

DNA Exp 21.09.2017 15:30

Но в городе можешь начинать с тех районов, где народа больше на одну площадь (ТВ в помощь).

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

anonymous 21.09.2017 15:33

DNA Exp

Олексій Пєніє 21.09.2017 15:06

Уверен, здесь теория давно уж изъезжена вдоль и впоперек. Всё упирается во владение мета-инфой, с последующим уходом от нормальных форм с оценкой стоимости предсказания.

Поскольку жителей в масштабах города сортировать (или иным способом индексировать — верно?) нельзя, равно как и делать то же самое в масштабах улицы (района, блока — нужное подчеркнуть) — тоже верно?

1) Есть ли связи между домами? То есть можно ли просто передать первому дому на улице попросить спросить дальше и так в испорченный телефон сыграть?
2) Были ли попытки кого-то ещё что-то проиндексировать? То есть можно ли сунуться в чужие реестры и таким образом сэкономить время? Пусть и не 100% вероятность, но и не 0%.
3) Возможно ли что Джон просто переехал, и никто об этом не знает?

Я так понимаю, что многоэтажные дома у тебя по дефолту индексированы. То есть они с точки зрения задачи такие же одноэтажные, просто их функция «проверить» чуть иная, и она встроена в конкретную реализацию абстрактного класса Дом.

Решение есть, но оно тебе не понравится: связаться с диспетчером такси, и когда у них наименьшее число заказов — дать халтуру низкой стоимости, чтобы кому совсем нефиг делать мог покататься. Притом им дать проверять ТОЛЬКО одноэтажные дома: их много, разбросаны у чёрта на куличках. На себя же бери всё, что уже индексировано. Неважно что при этом дольше проедешь — с точки зрения физики бензин тратится не столько на движение, сколько на разгон после остановки. Даже если у тебя не хватит бабла заплатить таксистам (а это ещё надо отмониторить), у тебя явно наивысшая вероятность поиска если ты начинаешь с индексированных. Мало того, многоэтажные и одноэтажные дома редко смешиваются в кучу, а скорее стоят отдельными кварталами — замечал такое?

DNA Exp 21.09.2017 15:28

Решение есть, но оно тебе не понравится: связаться с диспетчером такси, и когда у них наименьшее число заказов — дать халтуру низкой стоимости, чтобы кому совсем нефиг делать мог покататься.

Как не странно, об этом решение я тоже думал. Сделать некую службу (такси?) в масштабах города, которая каждый час обьезжает весь город (на нескольких машинах, многопоточно? ) с пачкой людей которых нужно найти. Это одно из решений, где подход не в лоб, а так сказать немного в сторону. Плюсы — финансово это оправдывает себя, когда заказов у нас очень много. Минусы — если заказов мало, из-за одного Джона обьезжать весь город накладно.

Олексій Пєніє 21.09.2017 15:30

Почему накладно? Вычислительный ресурс продаётся, в том числе с аукциона. Да и джона как правило ищут одного и того же — повестку вручить :)

Олексій Пєніє 21.09.2017 15:34

Есть решение ещё более наглое — индексировать для себя все многоквартирные дома и работать только по ним. Если Джон не найден — отдавать на аутсорс (вместе с полным доходом) знакомому таксисту, который город знает лучше. В каждом городе такого таксиста иметь. А себе снимать только сливки.

Онлайн-магазины именно так работают :)

Vadim Kopanev Architect 21.09.2017 14:57

Есть достаточно пространная задача, решение которой пока не могу найти, допускаю даже что красивого решения нет.

у тебя красивого решения быть и не может, инфа 100%

а по теме: изобрести индексы без индексов не получиться, решение только фулскан

DNA Exp 21.09.2017 15:29

Решение «в лоб» так примерно и выглядит. Тут скорей на можно ли извернутся. Поэтому собственно сугубо скучную техническую задачу я и перевел в другую, более привычную плоскость, чтобы удобеней было покрутить в голове.

Vadim Kopanev

Vadim Kopanev Architect 21.09.2017 15:44

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

решение может быть только: сразу знать адрес Джона или знать того кто знает его адрес. но тут уже скл — это просто хранилище, мне кажется ты не в эту сторону стремился

anonymous 21.09.2017 16:00

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

De Money 21.09.2017 20:05

Дайте краще нудну, але точну) Це ж саме цікаве) Тут здається треба шукати обхід, який максимальну кількість людей обробить максимально швидко. Тоді хоч максимум буде о(н) з великим коефіціентом, середнє може бути значно менше.

Пространная задача для размышления

39 коментарів

Підписатись на коментарі

Новини