докажите, что для каждого детерминированного алгоритма ALG существует сценарий, в котором общее расстояние грузовиков Джона

Есть 3 популярных пляжных курорта, A, B и C, которые расположены на одной линии:

                    A-----(1km)-----B-----(1km)------C.

Расстояния между курортами 1к. У Джона есть грузовик с мороженым, расположенный на пляжном курорте A, а другой - на пляжном курорте C. Два автобуса с детьми, жаждущими мороженого, прибудут на пляжные курорты (A, B и C) завтра, но Джон не приедет. знать, на какой курорт направляется каждый автобус и когда он прибудет (автобусы могут прибывать в разное время). Он планирует отправить грузовик с мороженым с его текущего местоположения на пляжный курорт, как только на этот курорт прибудет автобус. Каждый грузовик может обслуживать только один пляжный курорт, то есть после отправки грузовика на пляжный курорт он должен оставаться там весь день. Джон хочет разработать алгоритм, который минимизирует сумму расстояний, которые проходят его грузовики, чтобы добраться до мест расположения автобусов.

Покажите, что для каждого детерминированного алгоритма ALG существует некоторый сценарий (т. Е. Расписание и места прибытия автобусов), в котором общее расстояние, которое грузовики Джона пересекают согласно ALG, равно 3OPT, где OPT - значение оптимального решения в этом сценарии.


optimization algorithm deterministic game-theory
person Puka Puka    schedule 02.12.2012    source источник
comment
Если это какое-то домашнее задание, отметьте его как таковое. И задайте пожалуйста вопрос;)   -  person Tim    schedule 02.12.2012
comment
@ Тим, если вы знаете похожие проблемы, это будет очень полезно. Благодарность :-)   -  person Puka Puka    schedule 02.12.2012
comment
Ваш вопрос пока остается лишь описанием проблемы. Итак, какие проблемы у вас есть при решении проблемы? Описание непонятное? Что вы пробовали решить проблему? С чего начать решение проблемы? Просто дайте нам немного поработать здесь ^^   -  person Tim    schedule 02.12.2012
comment
@Tim, если вы дадите какой-либо детерминированный алгоритм ALG, который решает эту проблему, докажите, что для этого ALG существует сценарий, согласно которому общее расстояние, на которое проходят грузовики Джона (два грузовика), составляет не менее 3OPT ?? вы можете доказать это.   -  person Puka Puka    schedule 02.12.2012
comment
@PukaPuka Пожалуйста, покажите нам, что вы пробовали   -  person Haile    schedule 02.12.2012
comment
@Halie позволяет сказать, что первый автобус прибывает на пляж B, поэтому мы должны отправить один из грузовиков, расположенных в C или A, в B (как только этот грузовик отправляется в B, он не может быть перемещен до конца дня - предположим, что грузовик, расположенный в A, отправился в B), но если второй автобус прибывает в A, тогда мы должны отправить грузовик, заблокированный в C, в A. Суммарное расстояние, которое проходят грузовики, составляет 3 км, хотя мы могли бы это сделать оставив грузовик заблокированным в точке A в точке A, и отправив грузовик из точки C в точку B, и в этом случае сумма расстояния составит 1 км.   -  person Puka Puka    schedule 02.12.2012
comment
но как мне доказать это всем AlG?   -  person Puka Puka    schedule 02.12.2012
comment
@Tim: тег домашнего задания устарел.   -  person Nik Bougalis    schedule 03.12.2012

Ответы (1)


arrow_upward
0
arrow_downward

Вы уже описали одну стратегию в своих комментариях. Немного доработаю:

Стратегия заключается в том, что грузовики остаются на своих местах, пока дети не прибудут на место, а затем направляют грузовик к этому месту. Затем дети прибывают в точку B, поэтому грузовик, расположенный в точке A, отправляется в точку B. Теперь второй автобус прибывает в точку A, поэтому мы должны отправить грузовик, остановленный в точке C, в точку A. Суммарное расстояние, которое проходят грузовики, составляет 3 км.

Для этой стратегии вы уже доказали, что существует сценарий, в котором расстояние равно 3*OPT.

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

person Tim    schedule 02.12.2012