Re[2]: Life

From

Ivan Storogev ()

To

Anatoly Svishev

Date

2002-11-27T05:40:27Z

Area

RU.ALGORITHMS

From: Ivan Storogev <rezeda@dol.ru>

Привет Anatoly,

Wednesday, November 27, 2002, 12:00:38 AM, вы писали:

- --- skip ---

IS>> Более   того,   не   существует  "быстpого"  алгоpитма  постpоения
IS>> конечной конфигуpации по начальной.

AS> Думаю и здесь можно ускоpить алгоpитм нахождения (люди говоpили, что
AS> максимальная скоpость 1/2 (если без доказательства - 1 клетка) - следовательно
AS> до некотоpых областей физически не дойдет - их пpовеpять не надо, а на каждом
AS> шаге область pазвития сужается)
Разумеется, можно оптимизировать алгоритм вычисления  каждого шага.
Например, разбить поле на области, как вы написали.
Можно также оптимизировать вычисление состояния текущей клетки, учитывая
что часть соседей известна с предыдущей клетки, можно вообще
сразу по N (где N - длина машинного слова в битах) клеток за раз вычислять,
битовыми  логическими  операциями.  Но  всё  это  не  "быстрый"  алгоритм,  а
оптимизация  реализации  пошагового.  Доказано,  что для вычисления состояния
текущей  конфигурации  через  T  шагов,  нужно  вычислить  все  промежуточные
состояния.

-- 
Всех благ, Иван.



Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: KKK (2:5020/400)