| Шкатулки. Последняя попытка мозгового штурма. ID:31855 |
Вс, 12 августа 2007 13:35 [#] [») |
|
|
Идея SunnyRay, реализация Моя. Почему мы сразу зациклились на ОДНОМ К? Зачем ловить рыбу на крючек если есть сеть? Абсурд? Посмотрим...
Начнем с К1=1$ (желающие могут исследовать задачу с 1 цента, а особо придирчивые с 0,000000001 цента, кому как угодно).
На К1 мы поймаем максимальную пару 0.99-1.98. Если открытая сумма будет >=2, то мы сразу увидим что наш К1 не сработает ни прикаких условиях. Зачем нам в этом случае К1? Вводим К2=4$.
На К2 мы поймаем максимальную пару 3.99-7.98. Если открытая сумма будет >=8, то мы сразу увидим что наш К2 не сработает ни прикаких условиях. Зачем нам в этом случае К2? Вводим К3=16.
На К3 мы поймаем максимальную пару 15.99-31.98. Если открытая сумма будет >=32, то мы сразу увидим что наш К3 не сработает ни прикаких условиях Зачем нам в этом случае К3? Вводим К4=64.
и так до БЕСКОНЕЧЕНОСТИ. Такая сеть будет работать?
|
|
|
| Re: Шкатулки. Революция ID:31856 ответ на 31855 |
Вс, 12 августа 2007 14:00 («] [#] [») |
|
|
Эх, зря я тебя раньше срока разбанил 
|
|
|
| Re: Шкатулки. Революция ID:31857 ответ на 31855 |
Вс, 12 августа 2007 14:05 («] [#] [») |
|
|
| Korovin писал вс, 12 августа 2007 14:35 | | Идея SunnyRay, реализация Моя. |
Очнись, Коровин, хватит палить из пушек крейсера Аврора - зимний ещё вчера взяли
http://forum.cgm.ru/showpost?goto=203408
ЗЫ Причем гораздо более эффективным способом.
|
|
|
| Re: Шкатулки. Революция ID:31858 ответ на 31855 |
Вс, 12 августа 2007 14:06 («] [#] [») |
|
|
Эх, хочу тоже в дискуссию.. но прозевал развитие темы.. и вообще не догоняю о чем вы банкуете.. С какого поста начинать читать? 
|
|
|
| Re: Шкатулки. Революция ID:31859 ответ на 31855 |
Вс, 12 августа 2007 14:34 («] [#] [») |
|
|
| Sharky писал вс, 12 августа 2007 15:06 | | Эх, хочу тоже в дискуссию.. но прозевал развитие темы.. и вообще не догоняю о чем вы банкуете.. С какого поста начинать читать? |
С первого  . В теме "Задачка: теорвер, МО и всё такое". Потом тема "Вернемся к нашим шкатулкам", потом "Скупой платит дважды, тупой платит трижды, лох платит постоянно! – Или, снова о Шкатулках", потом эта.
Разумные мысли разбросаны по темам и завалены ошибками, заблуждениями и перебранками . Почти не существует постов, с которыми все согласны. К тому же, если прочитать сразу только то, к чему сейчас пришли, не получишь кайфа от постепенного открывания второго, третьего и так далее дна этой задачки .
|
|
|
| Re: Шкатулки. Революция ID:31860 ответ на 31855 |
Вс, 12 августа 2007 14:44 («] [#] [») |
|
|
| AVG51 писал вс, 12 августа 2007 15:05 | | Очнись, Коровин, хватит палить из пушек крейсера Аврора - зимний ещё вчера взяли ЗЫ Причем гораздо более эффективным способом. |
Ты решаеш придуманую тобой задачу с определяемым Х. Меня интересует только исходная задача в которой Х никак не определен. Перестань пожалуйста флудить в моих темах.
|
|
|
| Re: Шкатулки. Революция ID:31861 ответ на 31855 |
Вс, 12 августа 2007 14:52 («] [#] [») |
|
|
| Korovin писал вс, 12 августа 2007 14:35 | | Данная модель приводит к следующему однозначному алгоритму действий: Мы меняем свой выбор если открытая сумма S<1, 2<=S<4, 8<=S<16, 32<=S<64, 128<=S<256, ... Иначе не меняем. |
Этот алгоритм не имеет того замечательного свойства алгоритма с постоянным К. Он может оказаться хуже тупой стратегии.
Например, если устроитель использует шкатулки 1-2, 4-8, 16-32, 64-128 и т. д., он даст минимальное возможное МО=Х вместо 1.5Х тупой стратегии.
Это совсем другая стратегия игрока, имеющая очень отдалённое откошение к К-стратегии. И неясно, что вообще в этой стратегии хорошего.
|
|
|
| Re: Шкатулки. Революция ID:31862 ответ на 31855 |
Вс, 12 августа 2007 14:55 («] [#] [») |
|
|
| SunnyRay писал вс, 12 августа 2007 15:52 | | Например, если устроитель использует шкатулки 1-2, 4-8, 16-32, 64-128 и т. д., он даст минимальное возможное МО=Х вместо 1.5Х тупой стратегии. |
1-2. Открыли 1, оставили, открыли 2- оставили. Так же и для всех твоих пар. Область действия критериев не должна пересекается . Моджет я неверно привел К к интревалам?
|
|
|
| Re: Шкатулки. Революция ID:31863 ответ на 31855 |
Вс, 12 августа 2007 14:59 («] [#] [») |
|
|
| Korovin писал вс, 12 августа 2007 14:35 | | меняем свой выбор если открытая сумма S<1, 2<=S<4, 8<=S<16, 32<=S<64, 128<=S<256, ... Иначе не меняем. |
То есть 1 не меняем, 2 меняем, 4 не меняем, 8 меняем, ...
Откуда "1 оставили"?
А если переставить знаки вот так:
| Цитата: | | меняем свой выбор если открытая сумма S<=1, 2<S<=4, 8<S<=16, 32<S<=64, 128<S<=256, ... Иначе не меняем. |
то стратегия становится хуже тупой для шкатулок 2-4, 8-16, 32-64 и т. д.
Вообще, наличие любой пары "если К - стоим, если 2К - меняем", делает стратегию хуже тупой для пары К-2К. А такой стратегии с интервалами, что такой пары не найдётся, вроде бы, не существует, только обычная "<К менять, >=К не менять".
|
|
|
| Re: Шкатулки. Революция ID:31864 ответ на 31855 |
Вс, 12 августа 2007 15:06 («] [#] [») |
|
|
| Korovin писал вс, 12 августа 2007 15:44 | | AVG51 писал вс, 12 августа 2007 15:05 | | Очнись, Коровин, хватит палить из пушек крейсера Аврора - зимний ещё вчера взяли ЗЫ Причем гораздо более эффективным способом. |
Ты решаеш придуманую тобой задачу с определяемым Х. Меня интересует только исходная задача в которой Х никак не определен. |
С чего это ты взял? У меня Х не известен и находится в заданном диапазоне [0...Xmax], причем Xmax нам ТОЖЕ не известен!
Если же ты снова пытаешься натянуть свое седло на исходную задачу, в которой не только верхняя граница Х вообще не определена, но величина Х вообще не является случайной величиной - то флаг тебе в руки. Вот в этом письме http://forum.cgm.ru/showpost?goto=203272 я показал, что твоя стратегия для исходных задач (в любой из двух формулировок) является АБСУРДНОЙ.
| Korovin писал вс, 12 августа 2007 15:44 | | Перестань пожалуйста флудить в моих темах. |
Поставь копирайт в названии темы
ЗЫ А писать я больше действительно не буду - ну вас нафиг
|
|
|
| Re: Шкатулки. Революция ID:31865 ответ на 31855 |
Вс, 12 августа 2007 15:06 («] [#] [») |
|
|
|
Согласен что при К1=1 К2=16 К3=256 эта проблема снимается? Или например 1-8-64-... Какое максимальное сжатие сети не вызывает противоречий?
|
|
|
| Re: Шкатулки. Революция ID:31866 ответ на 31855 |
Вс, 12 августа 2007 15:11 («] [#] [») |
|
|
| AVG51 писал вс, 12 августа 2007 16:06 | | [С чего это ты взял? У меня Х не известен и находится в заданном диапазоне [0...Xmax], причем Xmax нам ТОЖЕ не известен! |
Ты определяеш Х как случайную величину с заданым распределением. Лучше действительно не пиши о том, чего не понимаеш.
|
|
|
| Re: Шкатулки. Революция ID:31867 ответ на 31855 |
Вс, 12 августа 2007 15:13 («] [#] [») |
|
|
| Korovin писал вс, 12 августа 2007 16:06 | | Согласен что при К1=1 К2=16 К3=256 эта проблема снимается? Или например 1-8-64-... Какое максимальное сжатие сети не вызывает противоречий? |
Не вполне понимаю, о чём речь, выше дополнил пост. Вроде, любая такая стратегия имеет проблему.
|
|
|
| Re: Шкатулки. Революция ID:31868 ответ на 31855 |
Вс, 12 августа 2007 15:17 («] [#] [») |
|
|
|
Речь о том, что открыв первую сумму мы можем получит дополнительню информацию "ситуация Х<=К<2Х исключена". В этом случае мы используем другой К, для которого эта ситуация возможна. Если область действия множества К не пересекается, все должно работать.
|
|
|
| Re: Шкатулки. Революция ID:31869 ответ на 31855 |
Вс, 12 августа 2007 15:41 («] [#] [») |
|
|
Нет. Независимо от того, насколько разреженную сеть использовать, проблема "на стыке" всё равно будет.
Если мы меняем, например, 128, то мы обязаны менять и 64, чтобы не проиграть на шкатулках 64-128. Если меняем 64, обязаны менять и 32, и т. д., обязаны менять 16, 8, 4, 2 и 1.
Аналогичто, если мы, например, стоим на 3, то обязаны стоять и на 6, 12, 24, 48 и т. д.
Любая пара "при К стоим, при 2К меняем" делает стратегию уязвимой.
Строго ничего доказать не могу (всякие дискретные ерундовины вроде "если открыли 25 центов, в другой однозначно 50" мешают"), но уверен, что проблема будет в любом случае, если мы "при К1 стоим, при К2 меняем", К1<К2.
|
|
|
| Re: Шкатулки. Революция ID:31870 ответ на 31855 |
Вс, 12 августа 2007 15:49 («] [#] [») |
|
|
|
Т.е. сеть не возможна и К=375 потому что я так хочу это предел?
|
|
|
| Re: Шкатулки. Революция ID:31871 ответ на 31855 |
Вс, 12 августа 2007 16:01 («] [#] [») |
|
|
В рамках стратегий, однозначно определяющих менять/не менять по сумме, и не использующих дискретность денег, да, это предел. Есть ли польза от вероятностного подхода, и существует ли какой-нибудь другой, никому не приходящий в голову, неясно 
|
|
|
| Re: Шкатулки. Революция ID:31872 ответ на 31855 |
Вс, 12 августа 2007 16:17 («] [#] [») |
|
|
Тогда если мы говорим о способе выбора К и приходим к тому что в рамках данной задачи такого способа не существует, т.е. мы можем выбрать абсолютно люой К>0, то оригинальный ответ задачи нисколько не противоречит нашей модели решения:
| Цитата: | | если сумма в первом конверте не настолько велика, что вы готовы рискнуть ее потерять, открывайте второй конверт. Если потярять такую сумму было бы сокрушительным ударом по вашему бюджету, забирайте первый конверт |
И теперь мы наконец-то знаем как ответить на второй вопрос задачи:<font color="red">почему</font> необходимо сравнить открытую сумму со значимой для нас суммой. Потому что субъективно определяемое нами понятие "значимой для нас суммы" по своим свойставм полностью подходит под определение критерия Значимости в рамках <font color="darkblue">модели оптимально решения данной задачи</font>.
|
|
|
| Re: Шкатулки. Революция ID:31873 ответ на 31855 |
Вс, 12 августа 2007 17:12 («] [#] [») |
|
|
Да, в целом всё так, и ты это сделал уже тогда, когда описал и обосновал свою стратегию, и сказал, что она похожа на оригинальный ответ anti_profi.
Как доказать, что это оптимальная модель и оптимальное решение, я не представляю. Невозможно, видимо. Да и оптимальная ли она?
Это лучшее, что у нас есть сейчас.
Существует ли следующий уровень задачи (например тот, который пытался найти Виталий КВИНСТАР), и вписывается ли он в рамки исходной задачи?..
Моей модификацией твоей стратегии было задать для каждой суммы S вероятность того, что мы будем открывать вторую шкатулку. Например "открыв сумму S>=1, мы будем её менять с вероятностью 1/S". Даёт ли это какое-то преимущество перед оригинальной К-стратегией, является ли наверняка неоптимальным, или даёт тот же самый результат, расширяя возможный диапазон стратегий? Есть ли некая равновесная или оптимальная в данном классе стратегия? Вопросов ещё много 
|
|
|
| Re: Шкатулки. Революция ID:31874 ответ на 31855 |
Вс, 12 августа 2007 17:23 («] [#] [») |
|
|
|
Я дальше не пойду. Меня останавливают шансы найти что-то, чего до нас никто не увидел.
|
|
|
