| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > остановится ли жизнь? |
| Автор: nmn 30.4.2010, 19:17 |
| здравствуйте возможно ли узнать остановится ли игра, или будет бесконечно продолжаться? |
| Автор: _Y_ 30.4.2010, 21:08 |
| Что-то непонятно. Что за игра? Почему она может или не может остановиться? Или вопрос о том как узнать есть ли где-то в далеком будущем играемого виртуального действа обязательное завершение программы? |
| Автор: Фантом 30.4.2010, 22:29 | ||
Имеется в виду "Жизнь"? В общем случае никак; ее, вообще говоря, такой и задумывали. |
| Автор: Bitter 1.5.2010, 19:56 |
| Всё зависит от правил и начального размещения жителей. Если это класическая Жизнь, то скорее всего нет. Добавлено через 6 минут и 10 секунд Вообще тут подробно написано. http://ru.wikipedia.org/wiki/Жизнь_(игра) |
| Автор: nmn 4.5.2010, 08:59 |
| да, классическая Жизнь <2 - погибает =3 - рождается новая >3 - погибает ну ведь необязательно должны остатьтся осциляторы или другие эволюционирующие фигуры, может же так получится что популяция вымрет? |
| Автор: _Y_ 4.5.2010, 10:17 | ||
Тогда возникает вопрос к божественной философии Что есть остановка жизни? Если отсутствие "живых" обьектов на экране - да остановится. Если завершение работы программы - нет, т.к. цикл обработки продолжит крутиться даже не находя ни одного живого обьекта. |
| Автор: Bitter 4.5.2010, 20:42 |
| при стандартных правилах, остановка Жизни зависит от начального размещения популяции. И её остановка, так же, как и не остановка возможны. |
| Автор: nmn 4.5.2010, 21:00 | ||
вот вот, это меня и интересует возможно ли заранее сказать что случится с данной популяцией? |
| Автор: _Y_ 4.5.2010, 23:37 | ||
Думаю, проще всего прогнать модель без вывода промежуточных каринок. Основное время программы идет на красивости - вывод на экран с равными интервалами времени (межшаговые задержки). Убрать вывод на экран и результат посчитатеся слету. |
| Автор: Bitter 6.5.2010, 16:06 |
| Да, но тогда надо как-то принимать решение о бесконечности популяции. Например отслеживать повторяющиеся фигуры. Но они могут повториться через большое количество итераций, или же одна и та же повторяющаяся фигура бывает умирает через несколько итераций. Может как-то следить некоторое время за тенденцией развития. если популяция не растет и не уменьшается долгое время, значит она устойчивая. Если колеблется сильно, значит не устойчивая. Как-то так. |
| Автор: _Y_ 7.5.2010, 12:10 |
| 1. Если фигура умирает через несколько популяций это значит, что она повторяется не идеально. Зацикленные фигуры повторяются бесконечно. 2. Видимо придется взять на себя роль Бога и установить что же есть бесконечная жизнь. Т.е. сколько иттераций можно считать бесконечностью. Например, не ожидается, что человек (с улыбкой идиота) сидит перед экраном неделю подряд. Можно допустить, скажем, 2 часа максимум. Если одна иттерация происходит за секунду, то любое число иттераций больше, чем 2*60*60 можно принять за бесконечность. 3. Отслеживать зацикленность можно наверное только сравнивая каждую новую структуру со всеми предидущими. Понятно, что хранить их все - себе дороже. Но здесь, наверное, можно опять перейти к философским размышлениям. "Каково максимальное количество шагов, воспринимаемое человеком как цикл"? Наверное получится не так уж и много. Только их и запоминать. Кстати, число комбинаций нулей и единиц на экране, хоть и очень велико, но не бесконечно. Поэтому все все равно сведется ко пункту 2 "что есть бесконечность". |
| Автор: Abyx 7.5.2010, 13:34 |
| планерное ружье-то запускает и запускает планеры, с чего бы ему остановиться? |
| Автор: nmn 7.5.2010, 17:58 | ||
это не то, с какой стати 2 часа? тут надо точно бесконечность... это когда не будет конца ни через 2 часа ни через 1000 часов ни через любое сколь угодно большое число часов мне эта задача чем то напоминает проблему остановки из теории алгоритмов |
| Автор: Bitter 7.5.2010, 20:57 | ||||
Это не верное утверждение. Некоторые зацикленные фигуры умирают через несколько итераций. Тому пример - планер, о котором упомянул Abyx.
Что за странные допущения вообще? Бесконечность это значит, что алгоритм не имеет окончания, а не ограничен каким-то допущением. nmn, попробуйте всё таки посторить графики по количеству индивидуумов в популяции на каждом шагу, для того, чтобы выяснить устойчивость. Например то же планетарное ружье будет иметь постоянную устойчивось, следовательно оно бесконечно. |
| Автор: _Y_ 7.5.2010, 21:53 | ||||
Это как?  Я всегда думал что каждой предидущей комбинации соответствует строго определенная и легко рассчитываемая последующая. А Вы утверждаете, что по каким-то непонятным причинам алгоритм
начинает ветвиться. Вы заставите меня верить в приведения, любезнейший ...................... Что касается моего предложения о переопределении бесконечности, то оно относится исключительно к практическим применениям. Если же нужна выкладка из области чистой теории, то, понятное дело, оно не применимо. |
| Автор: Bitter 7.5.2010, 22:39 |
_Y_, например фигура "планер" зациклена, но она постепенно смещается в одну сторону, что в итоге приведет к выходу за границы, тем самым она погибнет. Кроме того, зацикленую фигуру, которая не двигается, может нарушить тот же планер, если он её пересечёт. То есть зацикленые фигуры не означают бесконечность популяции. Так что никаких приведений  |
| Автор: Bitter 7.5.2010, 23:46 |
Вот, набросал програмку, рисующую график развития популяции. Один из примеров устоявшейся жизни: А вот и прожка: |
| Автор: Bitter 7.5.2010, 23:48 |
| Да, забыл сказать: ставить точки можно только в режиме паузы. Левой кнопкой ставить точки, правой - стирать. Кнопка "стоп" всё сотрёт и поставит режим паузы. |
| Автор: _Y_ 8.5.2010, 12:33 | ||||
Эээ. Да это мы расходимся в определениях. ИМХО, то что предлагаете, это не фигура, а локальный фрагмент фигуры. Фигрура же - это расположение объектов на всем поле. Смысла рассматривать зацикленные фрагменты особого нет, т.к. они независимыми никак не являются.
В классическом варианте "жизни" то, что уползает за одну границу, выползает из-за противоположной. Т.е. матрица "зациклена" верх-низ, право-лево. А-А-А-А-А-А!!! ПРИВИДЕНИЯ!!!!!  |
| Автор: nmn 9.5.2010, 16:34 |
| все же, ведь могут быть такие конфигурации, что период цикла будет не 2 хода, а намного больше, 10000000 например. и если из одинаковых расположений будут обязательно одинаковые результаты, то ничего, вобщем, не говорит про то что из неодинаковых расположений будут неодинаковые результаты, нужно каким то образом вывести эффективное расположение данного расположения (т.е. м.б. что расп1!=расп2, но эффективное расположение(расп1)==эффективное расположение(расп2), и тогда следующее поколение что расп1 что расп2 будут одинаковыми) все таки вопрос был не в этом, а в том, что можно ли определить результат жизни произвольной популяции за гарантированно конечное количество времени? |
| Автор: Abyx 9.5.2010, 18:26 | ||
планер не умирает, если ни с чем не столкнется |
| Автор: Bitter 9.5.2010, 20:39 |
| nmn, о, а может использовать нейросеть? Случайно располагая начальную популяцию, просчитать N ходов и результат подать в нейросеть. А она пусть выдаёт результат 0 или 1. Типа умрут или выживут. И так прогнать через неё большое количество жизней и в итоге потом она должна автоматически определять живучесть популяции. |
| Автор: _Y_ 10.5.2010, 17:51 |
Bitter, а что, прикольно! Только гаринтированного ответа нейросеть не даст. Но, как юноша практичный  , я опять предлагаю сделать условия задачи более близкими к практике. Сказать "...узнать с заданной вероятностью остановится ли игра..." и радоваться нейросети  |
| Автор: Badmanmad 15.5.2010, 21:22 |
Модератор: Сообщение скрыто. |
