НГУ

Форумы НГУ
Текущее время: Сб ноя 18, 2017 3:22 pm

Часовой пояс: UTC + 7 часов




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 16 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Задача о парковке
СообщениеДобавлено: Чт фев 14, 2013 10:05 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Пусть у нас есть парковка на n машин, на которую машины ставятся параллельно друг другу и мордами к оградке. Пусть все машины имеют одинаковую ширину. Вплотную друг к другу ставить их, как известно, нельзя. Для простоты будем считать, что к каждой машине с боков приписано по 40 см "личного пространства", и если ставить их так, чтобы эти зоны не пересекались, то выйдет как раз нормально.

То есть математическая модель такая: есть отрезок длины n, и на нём нужно размещать отрезки длины 1. Основная задача: размещать их так, чтобы влезло как можно больше.

Рассмотрим сначала очень простой случай:
1) будем считать, что все пользователи парковки могут договориться друг с другом о том, как ставить машины
2) парковка расположена так, что сначала водитель проезжает вдоль неё и оценивает расположение машин, а потом уже заезжает внутрь и выбирает себе местечко (около ИМ есть что-то похожее).

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт фев 15, 2013 11:27 am 
Не в сети
Начинающий автор

Зарегистрирован: Пт мар 17, 2006 12:27 pm
Сообщения: 263
Правильный ответ известен: хозяин парковки делает разметку.
:)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт фев 15, 2013 1:47 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Chilik писал(а):
Правильный ответ известен: хозяин парковки делает разметку.
:)

Разметка, конечно, решает все проблемы. Если удастся договориться её соблюдать. Но у нас её как минимум 4 месяца под снежком не видно, поэтому в задаче разметки нет. В RL она тоже, мягко говоря, не везде есть.

Надо ещё оговорить ряд условий. Вариант, когда водители будут бегать по парковке с рулеткой, мы не рассматриваем. Можно с приемлемой точностью считать, что опытный водитель, посмотрев на 2 соседние машины, всегда может определить, какой из 4-х вариантов имеет место:
0) они стоят на расстоянии 0, т.е. рядом друг с другом
1) они стоят на расстоянии 1, т.е. между ними как раз влазит ещё одна
2) они стоят не рядом, но на расстоянии меньше 1, т.е. между ними ничего уже не поставишь
3) они стоят на расстоянии больше 1
На этом его измерительные возможности заканчиваются.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт фев 15, 2013 3:55 pm 
Не в сети
Частый гость

Зарегистрирован: Ср авг 18, 2010 4:22 pm
Сообщения: 25
Откуда: Панасенко Александр
А какова измерительная способность водителя во время парковки? То есть, с какой точностью водитель может подогнать машину к другой машине справа, если известно, что пространства хватает?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт фев 15, 2013 4:05 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
tom-anjelo писал(а):
А какова измерительная способность водителя во время парковки?

Будем считать, что выбрать один из этих четырёх вариантов он точно может. Т.е. он может поставить машину вплотную к соседней, на расстоянии 1, меньше или больше 1 (уже без какой-либо точности). То же самое касается края парковки.

Можно попробовать рассмотреть ещё какие-то варианты, если они вдруг понадобятся.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт фев 15, 2013 4:57 pm 
Не в сети
Частый гость

Зарегистрирован: Ср авг 18, 2010 4:22 pm
Сообщения: 25
Откуда: Панасенко Александр
Положим, что водитель так же может определить, где начинается парковка, и назовем начальный отрезок длины 1 - "первым местом", следующий отрезок "вторым местом" и т.д. Если первое место свободно, то водитель занимает его. Если нет, то он смотрит есть ли ненулевое пространство после первой машины. Если есть, ставит вплотную к первой машине, иначе едет дальше. Короче, пока не найдет свободное пространство ненулевой длины, он едет. Как найдет - занимает его. При таком правиле всегда будут между машинами расстояния 0, 1, 2,..., короче задаваемые натуральными числами и, как следствие, способ расстановки машин задан корректно


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт фев 15, 2013 5:01 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
Машину ставлю вплотную к какой-нибудь стоящей. Где проблема?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Сб фев 16, 2013 1:10 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Оk, простая задача решена. Заметим, что несколько сотен миллионов людей решают её каждый день по нескольку раз, и даже такой скромный результат в чём-то любопытен.

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

Напомним, что обычная парковка - очень динамичный объект, какие-то машины оттуда уезжают, какие-то приезжают. То есть в какой-то момент там могут собраться все k отщепенцев, в какой-то 0. Общее число претендентов на места существенно превышает размер парковки n, который тоже достаточно велик.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн фев 18, 2013 9:41 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Да: решение задачи мне не известно. Если найти несколько стратегий, то их можно было бы сравнить.

У парковки есть края.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср фев 20, 2013 10:53 pm 
Не в сети
Частый гость

Зарегистрирован: Ср авг 18, 2010 4:22 pm
Сообщения: 25
Откуда: Панасенко Александр
Хорошие водители должны стараться создавать как можно больше одиночных мест, то есть свободных кусков длины 1, то есть ставить машины относительно другой на расстоянии 1. Причем, предпочтение необходимо отдавать заниманию меньших кусков. То есть, если есть свободный кусок длины 3 и длины 10, то нужно разместить машину в куске длины 3 посередине
P.S. Это не решение, а лишь пара несвязных идей


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт фев 21, 2013 9:59 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
tom-anjelo писал(а):
То есть, если есть свободный кусок длины 3 и длины 10, то нужно разместить машину в куске длины 3 посередине

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт фев 22, 2013 7:20 pm 
Не в сети
Частый гость

Зарегистрирован: Ср авг 18, 2010 4:22 pm
Сообщения: 25
Откуда: Панасенко Александр
Я так понял, что мы считаем, что 1 метр - это кусок, который необходим и достаточен для комфортного влезания-вылезания. Зачем усложнять модель?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт фев 22, 2013 8:56 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
tom-anjelo писал(а):
Хорошие водители должны стараться создавать как можно больше одиночных мест, то есть свободных кусков длины 1, то есть ставить машины относительно другой на расстоянии 1.

Да, если немного подумать, то становится ясен парадоксальный факт: машины лучше всего ставить на расстоянии 1. Хоть плакат над парковками вешай. :)

Мне при этом кажется, что всегда нужно стараться занимать места с краёв парковки. То есть первый сознательный водитель ставит машину на место 2, второй - на место 4, и т.д. В итоге пространство для нарушителей каждый раз будет сокращаться на 2, а наносимый ими потенциальный ущерб - минимизироваться.

Напомним, что мы считаем всех водителей предварительно просмотревшими всю парковку. Тогда алгоритм такой: просматриваем машины, начиная от края парковки. Если все они стоят как надо (мы можем это увидеть), то паркуемся на расстоянии 1 от крайней. Если такой возможности нет, т.е. после ряда сознательных водителей стоит один нарушитель, то смотрим на другой край. Если и там стоит нарушитель, то вопрос, что делать.

Один из вариантов: теперь начинаем ставить машины в те дырки ширины 1 с краёв парковки, который были заготовлены заранее. Это даст возможность не портить ситуацию в центре: как только нарушитель уедет, вновь приезжающие сознательные водители тут же продолжат "зону порядка" на его место.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт фев 22, 2013 9:08 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Гост_Я писал(а):
Да, чтобы нагадить остальным, можно ставить посередине куска длины 3. В соседние метровые куски заехать можно, но вылезти из машины нельзя, т.к. двери не открываются.

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

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

Конечно, точно на расстоянии 1 машину не поставишь, но отклонения в обе стороны можно считать небольшими и случайными, в сумме они друг друга вполне способны компенсировать.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Сб фев 23, 2013 8:57 am 
Не в сети
Начинающий автор

Зарегистрирован: Пт мар 17, 2006 12:27 pm
Сообщения: 263
Если задача близка к практике, то нужно ещё один параметр: модель работы парковки. То есть это может быть, скажем, парковка офисного типа "утром приехал - вечером уехал", либо парковка гипермаркета, когда за сутки состав автомобилей обновляется несколько раз. В первом случае можно придумывать идеальные схемы, во втором - нарушители будут заполнять дырки как попало и любая стройная схема со временем рандомизируется.
Есть ещё один смежный вопрос: можно ли оценить предельную степень заполнения парковки (или потерю емкости) при наличии нарушителей? В самом плохом случае (все становятся ровно через 1.9(9) места) - это 50%. А если нарушителей разумная доля?


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 16 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: proxyagorm, Samueliks и гости: 6


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB