НГУ
http://forum.nsu.ru/

Задача о парковке
http://forum.nsu.ru/viewtopic.php?f=18&t=23674
Страница 2 из 2

Автор:  Pavel E. Alaev [ Сб мар 02, 2013 9:27 pm ]
Заголовок сообщения: 

Chilik писал(а):
Если задача близка к практике, то нужно ещё один параметр: модель работы парковки.

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

Chilik писал(а):
... нарушители будут заполнять дырки как попало и любая стройная схема со временем рандомизируется.

В задаче есть параметр k - число нарушителей. Если, например, k = 1, то понятно, что о скором наступлении хаоса говорить не приходится. Если просто ставить машины рядом друг с другом, как в самом первом алгоритме, то нарушитель с высокой вероятностью "загубит" одно лишнее место. Если рядом с ним кто-то встанет, то даже после его отъезда этот кто-то всё равно будет портить порядок.

Если же ставить машины через 1, начиная с краёв парковки, то после отъезда нарушителя порядок автоматически восстановится. Более того, есть шанс, что к приезду нарушителя парковка уже будет заполнена с шагом 1, и ему неизбежно придётся поставить машину правильно.

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

Страница 2 из 2 Часовой пояс: UTC + 7 часов
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/