Третий раздел курса знакомит с итеративным методом.
Статьи из первых двух заметок:
- Заметки программиста по математике 1. Двоичное преобразование
- Математические заметки программиста 2 -- Остаток
03 итеративный метод
Что такое итерационный метод
Проще говоря, итеративный метод фактически использует старое значение переменной для рекурсивного вычисления нового значения переменной.
Вот история, чтобы представить, что такое итерационный метод. Эта история о короле, который хочет наградить придворного, который внес большой вклад, и просит придворного предложить награду, которую он хочет. Доска полна пшеницы, но требованияВ каждом квадрате в два раза больше пшеницы, чем в предыдущем квадрате.. Царь думал, что эту награду можно легко удовлетворить, но когда он действительно начал выращивать пшеницу, он понял, что даже если он вывезет зерно всей страны, он не сможет удовлетворить эту награду.
Здесь мы можем использоватьf(n)Указывает текущее количество пшеницы и количество пшеницы в предыдущей сетке.f(n-1), то просьба придворного может быть выражена следующим образом:
f(n) = f(n-1) * 2
f(1) = 1
Это итеративный метод, и если он реализован программно, то это фактически процесс реализации операции цикла.
Код для реализации этого расчета пшеницы в Python выглядит следующим образом:
def get_number_of_wheat(grid):
'''
\计算放到给定格子数量需要的麦子数量
:param grid: 格子数
:return:
'''
# f(1) = 1
wheat_numbers = 1
sums = wheat_numbers
for i in range(2, grid+1):
wheat_numbers *= 2
sums += wheat_numbers
print('when grid = %d, wheats numbers = %d' % (grid, sums))
return sums
Простой тестовый пример:
if __name__ == '__main__':
print('compute numbers of wheat!')
numbers_grid = 63
get_number_of_wheat(numbers_grid)
print('finish')
Учитывая, что количество сеток равно 63, вывод выглядит следующим образом:
compute numbers of wheat!
when grid = 63, wheats numbers = 9223372036854775807
finish
Итак, это астрономическое число состоит из 19 цифр — 9223372036854775807, что действительно много! Предполагая, что в 50-фунтовом мешке пшеницы примерно 1,3 миллиона зерен пшеницы, этот расчет эквивалентен 7 094,9 миллиарда мешков 50-фунтовой пшеницы!
Применение итерационного метода
Прочитав приведенные выше примеры, я считаю, что вы должны лучше понять основные понятия итерационного метода, и основные шаги итерационного метода также очень просты, разделены на три шага:
-
Определите переменную для использования для итерации. В приведенном выше примере переменная итерации равна
f(n)иf(n-1) -
Установите рекуррентную связь между переменными итерации. В приведенном выше примере рекуррентное соотношение имеет вид
f(n)=f(n-1)*2 -
контролировать итерационный процесс. Необходимо определить начальные условия и условия окончания итерации.В приведенном примере начальные условия имеют вид
f(1)=1, а условием завершения является достижение заданного числа ячеек.
Итак, каково применение итеративного метода?
Фактически, он имеет широкий спектр приложений в математике и компьютерных областях, таких как:
- Найдите точное или приближенное решение для чисел. Типичные методы включают метод деления пополам и метод Ньютона;
- Найти целевое значение в диапазоне. Типичные методы включают бинарный поиск, который на самом деле является применением бинарного поиска в поиске;
- Итерации в алгоритмах машинного обучения. Такие как алгоритм кластеризации Kmeans (непрерывная итерация к кластерным данным), цепь Маркова (Markov chain), метод градиентного спуска (Gradient descent) и так далее. Итерационные методы широко используются в машинном обучении именно потому, чтоПроцесс машинного обучения заключается в поиске локального оптимального решения на основе известных данных и определенных предположений.. Итерационные методы помогают алгоритму обучения выполнять пошаговый поиск, пока такое решение не будет найдено.
Далее мы сосредоточимся на решении численных решений и поиске совпадающих записей.Эти два приложения на самом деле используютдихотомияреализовать.
Найти точные или приближенные решения уравнений
В дополнение к вычислению огромных чисел, итерационные методы также могут помочь намприближаясь бесконечно, чтобы получить уравнениеточное или приближенное решение.
Например, мы хотим вычислить заданное положительное целое числоn（n>1)Квадратный корень из и не может использовать функцию, поставляемую с языком программирования, как его вычислить?
Прежде всего, мы можем прояснить, что для данного положительного целого числаn, его квадратный корень должен быть меньше его, но больше 1, то есть диапазон значений этого квадратного корня от 1 доn, квадрат значения в этом диапазоне равенn.
Здесь, принимая то, что только что было сказанодихотомия. Каждый раз, когда вы смотрите на среднее значение в интервале, проверяйте, соответствует ли оно критериям.
Например, если мы запрашиваем квадратный корень из 10, интервал, который мы ищем, равен[1,10], первое промежуточное значение равно(1+10)/2=11/2=5.5, а квадрат 5,5 равен 30,25, что, очевидно, больше 10, поэтому интервал поиска становится левой частью 5,5, что равно[1, 5.5], среднее значение равно 3,25, но квадрат 3,25 равен 10,5625, что все еще больше 10, и интервал поиска становится равным[1, 3.25], медиана становится равной 2,125, квадрат 2,125 равен 4,515625, что меньше 10, поэтому интервал равен[2.125, 3.25], поэтому продолжайте находить и возводить в квадрат медианное значение, пока не обнаружите, что квадрат числа равен ровно 10.
Конкретные шаги заключаются в следующем:
Это реализовано в коде, как показано на следующем рисунке:
def get_square_root(n, threshold, max_try):
'''
计算大于 1 的正整数的平方根
:param n: 给定正整数
:param threshold: 误差的阈值
:param max_try: 最大尝试次数
:return:
'''
if n <= 1:
return -1.0
# interval boundary 区间的左右边界
left = 1.0
right = float(n)
for idx in range(max_try):
# 防止溢出
middle = left + (right - left) / 2
square = middle * middle
# 误差
delta = abs(square / n - 1)
if delta <= threshold:
return middle
else:
if square > n:
right = middle
else:
left = middle
return -2.0
Простой тестовый пример:
square_root = get_square_root(10, 0.000001, 10000)
if square_root == -1.0:
print('please input a number > 1')
elif square_root == -2.0:
print('cannot find the square root')
else:
print('square root==', square_root)
Результат:
square root== 3.1622767448425293
В этом коде задаются два параметра, управляющие окончанием итерации:
-
threshold: Порог ошибки, используемый для контроля точности решения. Теоретически метод дихотомии может получить точное решение с помощью бесконечных итераций, но практическое применение также требует учета времени и вычислительных ресурсов, поэтому обычно нам нужно только приблизительное решение вместо полностью точных данных; -
max_try: управляет количеством итераций. Этот параметр также установлен, чтобы избежать использованияwhile TrueБесконечный цикл, который цикл может вызвать, конечно, теоретически установленthresholdМожно избежать бесконечных циклов, но хорошей практикой программирования является активное предотвращение возможности их возникновения.
Найдите совпадающие записи
Путем итеративной аппроксимации метод деления пополам может не только получить приближенное решение уравнения, но и помочь найти совпадающие записи.
Пример, приведенный здесь учителем, касается проблемы расширения синонимов или синонимов при обработке естественного языка. На этом этапе у вас будет словарь, в котором записаны синонимы или синонимы для каждого слова. Чтобы слово было найдено, нам нужно найти слово в словаре, а также все соответствующие синонимы и синонимы, а затем расширить, например, для слова--西红柿, его синонимы включают番茄иtomato.
Словари представлены в следующей таблице:
| Вход | синоним 1 | синоним 2 | синоним 3 |
|---|---|---|---|
| помидор | помидор | tomato | ... |
| ... | ... | ... | ... |
При обработке статьи и обнаружении слова «помидор» найдите его в словаре, верните синонимы или синонимы, такие как «помидор» и «помидор», и добавьте его в статью как расширение синонима/синонима.
Здесь нужно решить проблему, как запросить совпадающие слова в словаре. Один из способов сделать это — использовать хэш-таблицу. И если вы не используете метод хеш-таблицы, вы также можете использоватьбинарный поиск. Идея словарного запроса методом бинарного поиска заключается в следующем:
- Сначала отсортируйте весь словарь (при условии, что от малого к большому). Ключевым условием дихотомии является то, чтоИнтервал поиска должен быть заказан, так что каждый раз, когда вы складываете пополам, вы можете знать, следует ли продолжать поиск влево или вправо.
- Используйте дихотомию, чтобы найти искомое слово шаг за шагом. То же самое - каждый раз выбирать среднее значение интервала поиска и судить, соответствует ли оно искомому слову. Если соответствует, вернуть его, если не соответствует, оценить размер. Просто посмотрите влево диапазон.
- Повторяйте второй шаг, итеративный поиск, пока слово не будет найдено, а если оно не найдено, оно вернется несуществующим.
В отличие от поиска решений уравнений с использованием бинарного метода, бинарный поиск должен требоватьДанные в порядке!
Реализовано в коде следующим образом:
def search_word(dictionary, word):
'''
查找匹配单词
:param dictionary: 排序后的字典
:param word:待查找单词
:return:
'''
if dictionary is None:
return False
if len(dictionary) < 1:
return False
left = 0
right = len(dictionary) - 1
while left <= right:
middle = int(left + (right - left) / 2)
if dictionary[middle] == word:
return True
else:
if dictionary[middle] > word:
right = middle - 1
else:
left = middle + 1
return False
Простой тестовый код:
print('find word in dictionary')
dict_list = ['i', 'am', 'coder']
dict_list = sorted(dict_list)
print('sorted dict:', dict_list)
word_to_find = 'am'
found = search_word(dict_list, word_to_find)
if found:
print('word "%s" found in dictionary--%s!' % (word_to_find, dict_list))
else:
print('cannot find the word "%s"' % word_to_find)
Выходной результат:
find word in dictionary
sorted dict: ['am', 'coder', 'i']
word "am" found in dictionary--['am', 'coder', 'i']!
finish
Вот и все введение в итерационные методы! Приведенный выше адрес исходного кода:
Добро пожаловать, чтобы обратить внимание на мою общедоступную учетную запись WeChat — машинное обучение и компьютерное зрение, или отсканируйте QR-код ниже, давайте общаться, учиться и прогрессировать вместе!