Алгоритмы неформально. Инструкция для начинающих питонистов - [44]

def feedback_shift_list(bits_this):

    bits_output = [bits_this.copy()]

    random_output = []

    bits_next = bits_this.copy()

    while(len(bits_output) < 2**len(bits_this)):

        bits_next,next = feedback_shift(bits_next)

        bits_output.append(bits_next.copy())

        random_output.append(next)

    return(bits_output,random_output)

В данном случае цикл while выполняется, пока серия битов должна генерироваться. Так как список битов имеет всего 23 = 8 возможных состояний, можно ожидать, что период не превысит 8. На самом деле РСЛС обычно не может выводить полный набор нулей, поэтому на практике период не превышает 23 – 1 = 7. Можно выполнить следующий код, чтобы найти все возможные варианты вывода и проверить период:

bitslist = feedback_shift_list([1,1,1])[0]

В bitslist будет сохранен следующий вывод:

[[1, 1, 1], [0, 1, 1], [0, 0, 1], [1, 0, 0], [0, 1, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]

Мы видим, что РСЛС выводит все семь возможных битовых строк, которые не состоят из одних нулей. РСЛС имеет полную периодичность, а также демонстрирует равномерное распределение выходных значений. Если использовать больше входных битов, то максимальный возможный период растет с экспоненциальной скоростью: с 10 битами он будет равен 210 – 1 = 1023, а с 20 битами — 220 – 1 = 1 048 575.

Для проверки списка псевдослучайных битов, генерируемых простым РСЛС, можно воспользоваться следующей командой:

pseudorandom_bits = feedback_shift_list([1,1,1])[1]

Вывод, хранящийся в pseudorandom_bits, выглядит достаточно случайным — особенно если учесть, насколько простым был РСЛС и его входные данные:

[1, 1, 1, 0, 0, 1, 0]

РСЛС используются для генерирования псевдослучайных чисел в различных областях, включая генерирование белого шума. Мы рассмотрели его здесь, чтобы вы получили представление о современных ГПСЧ. На практике чаще всего используется ГПСЧ вихрь Мерсенна, который представляет собой видоизмененный обобщенный регистр сдвига с обратной связью — фактически это намного более изощренная версия РСЛС, представленного в данном разделе. Если вы продолжите изучать ГПСЧ, то столкнетесь с большим количеством запутанных рассуждений и нетривиальной математики, но все они будут строиться на идеях, представленных здесь: детерминированных математических формулах, результаты которых достаточно близки к случайным по строгим математическим критериям.

Резюме

Математика и алгоритмы всегда были тесно связаны. Чем сильнее вы углубляетесь в одну область, тем более будете готовы к восприятию нетривиальных идей из другой. Математические обоснования могут показаться непрактичными и запутанными, но здесь идет игра с дальним прицелом: теоретические достижения в математике иногда приводят к появлению практических технологий только через несколько веков. В этой главе мы изучили непрерывные дроби и алгоритм, генерирующий представление любого числа в виде непрерывной дроби. Кроме того, обсудили квадратные корни и алгоритм, который калькуляторы используют для их вычисления. Наконец, мы обсудили тему случайности, включающую два алгоритма для генерирования псевдослучайных чисел, и математические принципы, которые могут использоваться для оценки списков, претендующих на случайность.

В следующей главе мы рассмотрим оптимизацию и эффективный метод, с помощью которого вы можете путешествовать по миру или выковать меч.

6. Расширенная оптимизация

Тема оптимизации вам уже знакома. В главе 3 рассматривался метод градиентного подъема/спуска, предназначенный для поиска максимумов и минимумов функций. Любую задачу оптимизации можно рассматривать как разновидность поиска экстремумов: мы стараемся найти лучший возможный результат из огромного диапазона возможностей. Метод градиентного подъема прост и элегантен, но имеет свою ахиллесову пяту: он может найти пик, который оптимален только локально, но не является глобальным оптимумом. Если провести аналогию с альпинизмом, то данный метод может привести вас на вершину предгорья; если вы немного спуститесь, то сможете подняться на огромную гору, на которую действительно хотите взобраться. Решение этой проблемы — самый сложный и важный аспект расширенной оптимизации.

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

Жизнь коммивояжера

Задача коммивояжера играет чрезвычайно важную роль в информатике и комбинаторике. Представьте, что коммивояжер хочет объехать несколько городов, чтобы продать свои товары. Поездки между городами обходятся дорого (потерянное время, стоимость бензина, головная боль после долгой поездки) (рис. 6.1).

Рис. 6.1. Коммивояжер в Неаполе

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