Занятие 8: алгоритмы в Python, виды, сложность

5 (100%) 6 vote[s]

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

Сложность алгоритмов

Для решения большинства задач можно применить не один, а несколько различных алгоритмов. Если мы имеем дело с небольшими объемами данных, оптимизация не является существенной, так как на малых размерностях задач разница во времени выполнения различных алгоритмов будет незаметной. Для больших объемов данных использование неэффективного алгоритма может привести к слишком долгого выполнения программы.

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

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

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

Поэтому на практике рассматривается асимптотическая сложность, которая обозначает уровень роста объема работы алгоритма с ростом объема входных данных. Фактически, вместо точной функции, рассматривается лишь общая тенденция ее роста: сложность этого алгоритма растет линейно, сложность другой — как квадратичная функция (y = n ** 2) и т.д.

Кроме того, некоторые алгоритмы являются достаточно сложными и по-разному ведут себя в зависимости от характера входных данных. Поэтому различают верхний предел количества операций, нижний предел и среднее значение. Верхний предел — это худший случай, который может быть для данного алгоритма (во многих алгоритмов есть слабые места и могут существовать наборы данных, которые будут обрабатываться медленнее обычного). Нижний предел — это, наоборот, лучший случай, который имеет место в случае с «удобными» данными, (случайно или специально) приспособленными для обработки данным алгоритмом. Среднее значение — это количество операций, которое потребуется в большинстве случаев для обработки некоторых абстрактных данных, и совсем не обязательно является средним арифметическим от двух предыдущих показателей.

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

Условно алгоритмы могут быть классифицированы по своей асимптотической сложностью, которая в литературе часто обозначается как O (g (n)). Запись f (n) ε O (g (n)) означает, что сложность алгоритма (которая является функцией от n, то есть зависит от n) при увеличении n растет не быстрее чем функция g (n), умноженная на какое-то число. То есть с увеличением размерности задачи число операций растет примерно с той же скоростью, что функция g (n).

Константная сложность f (n) ε O (k) — присущая алгоритмам, для которых количество операций является постоянной величиной, то есть не зависит от объема входных данных. Конечно, это значит, что эти алгоритмы не предусматривают обработки всех данных и выполняют лишь какие-то простые операции. Например, функция, которая возвращает первый элемент последовательности, умноженный на 2:

def get_max (seq):
     return seq [0] * 2

Нас не интересует вся последовательность, мы не собираемся обрабатывать все ее элементы и количество операций для любой длины последовательности в таком случае будет одинаковой.

Логарифмическая сложность f (n) ε O (logkn) в чистом виде возникает редко. На практике это алгоритмы рекурсивных задач, которые позволяют разделять последовательность на части, уменьшая таким образом размерность задачи. Как правило, такое разбиение возникает вследствие некоторой оптимизации и решение требует еще других действий, кроме собственно разбиения, поэтому возникают алгоритмы со сложностью n * logkn, n2 * logkn и другие. Наиболее типичными представителями являются бинарный поиск да «быстрое» сортировка, подробно рассмотрены в видео-лекции.

Линейная сложность f (n) ε O (n) возникает в простых задачах, для решения которых достаточно пройти последовательность 1 или несколько раз. Например, найти наибольший элемент в последовательности, или найти сумму всех элементов, или практическое задание 4.1 настоящего курса о проверке палиндрома. Даже если вы используете готовые функции языка программирования и с вашей точки зрения, как пользователя, это одна операция, внутри функции все равно находится полный проход последовательности, так или иначе потребует около n операций.

Полиномиальная сложность f (n) ε O (nk) — это алгоритмы, представляющие большой класс, внутри которого различают подклассы в зависимости от значения k: O (n ** 2), O (n ** 3), O (n ** 5), O (n ** 10) и другие. Такие алгоритмы легко различить, так как число k соответствует наибольшей вложенности циклов в программе.

На практике это уже довольно неприятный случай, так как с увеличением объема данных даже для n2 количество операций растет невероятно быстро и для больших объемов данных (n≈10000 и более) время работы программы уже заметно невооруженным глазом.

Еще хуже экспоненциальная сложность f (n) ε O (kn). Это так же можно представить в виде циклов — только представьте, что с размерностью задачи растет не количество итераций, а количество циклов. Для того, чтобы время работы такой программы вышло за пределы допустимого даже не нужны большие размерности задачи.

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

Некоторые алгоритмы в подходах к решению задач

Перебор

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

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

Например, следующая задача: пусть задана последовательность натуральных чисел от 1 до n и целое число m. Необходимо расставить знаки между числами последовательности (не меняя их порядка) таким образом, чтобы результатом полученного арифметического выражения было m.

Конечно, можно взять все возможные комбинации знаков, но, представляя задачу «в лоб», для этого нам понадобится n циклов, а значение n не зафиксировано. Этот один из случаев, когда для облегчения восприятия кода вместо циклов удобнее использовать рекурсию. Каждому уровню углубление рекурсии отвечает позиция между некоторыми двумя членами последовательности и в рекурсивной функции мы будем делать выбор между двумя вариантами знака, можно там поставить: «+» или «-». В направлении «туда» передавать номер следующей позиции и сумму чисел, которое уже набрано в текущей расстановке знаков, «назад» возвращать сгенерированную часть математического выражения, если в текущей в конце рекурсии получено значение m, и False, если это направление не достигло необходимого результата.

def signs1(m, n):
    def calc_step(level, current):
        if level > n:
            return current == m
        res = calc_step(level + 1, current + level)
        if res:
            return '+' + str(level) + str(res)
        res = calc_step(level + 1, current - level)
        if res:
            return '-' + str(level) + str(res)
 
    res = calc_step(2, 1)
    if res:
        return '1' + res[:-4]
    return False

Например, вариант рекурсии выглядит примерно так: для n = 20, m = 2 решение находится быстро, для n = 30, m = 3 — довольно долго. При этом рекурсия фактически завершает работу, найдя хоть один ответ. Но в случае, когда ответа нет, происходит полный перебор всех вариантов, и требует еще больше времени. Такой «безрезультатный перебор» для n = 30 потребовал 6.5 минут.

print signs1 (3, 5) # 1-2 + 3-4 + 5
print signs1 (2, 20) # 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13-14 + 15-16-17-18-19-20
print signs1 (2, 30) # False
print signs1 (3, 30) # 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 20-21- 22-23 + 24-25-26-27-28-29-30

Лучшим способом оптимизировать перебор является организация перебора (или поиска) с возвращением.

Почти всегда перебирается значение не одной, а нескольких переменных, следовательно решение генерируется не одномоментно, а по частям: выставляется значение одного параметра, это значение фиксируется и перебирается (с помощью рекурсии или вложенных циклов) варианты следующей переменной, на каждом из вариантов ее значение фиксируется и перебираются следующие переменные и т.д. И если на любом из промежуточных этапов мы можем предположить, что все последующие «вложенные» варианты будут проигрышными (а это возможно для большинства задач), такая проверка и своевременное прекращение генерации бессмысленных вариантов существенно ускорит работу. Это и есть «возвращение» — вместо погружения в вложенные переборы мы добавляем какое-то частичное условие и, если оно не оправдывается, сразу отсекаем целую группу решений, возвращаясь на шаг назад и испытывая группу решений, основанных на другом, более перспективном смысле.

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

def signs2(m, n):
    def calc_step(level, current):
        if level > n:
            return current == m
        sum_of_next = 1.0 * (level + n) / 2 * (n - level + 1)
        if m > current + sum_of_next or m < current - sum_of_next :
            return False
        res = calc_step(level + 1, current + level)
        if res:
            return '+' + str(level) + str(res)
        res = calc_step(level + 1, current - level)
        if res:
            return '-' + str(level) + str(res)
 
    res = calc_step(2, 1)
    if res:
        return '1' + res[:-4]
    return False

Ответы возвращаются такие же, как и в предыдущей версии функции. «Пустой» перебор по всем вариантам signs2 (2, 30) завершился почти на минуту быстрее. Это хорошо, но не достаточно.

Проблема такого промежуточного условия заключается в том, что в последними мы добавляем или вычитаем самые большие числа, которые больше всего влияют на конечную сумму, и, таким образом, «возвращение» в нашем переборе всегда будет происходить где-то на последних этапах. Повысить эффективность возврата можно очень просто: складывать числа, начиная не с начала, а с конца — тогда неудачно сложенные большие числа очень быстро приведут нас в ситуацию, когда просматривать следующие элементы уже не имеет смысла. Так и сделаем:

def signs3(m, n):
    def calc_step(level, current):
        if level < 1:
            return current == m
        sum_of_next = 1.0 * (level + 1) / 2 * (level)
        if m > current + sum_of_next or m < current - sum_of_next :
            return False
        res = calc_step(level - 1, current + level)
        if res:
            return '+' + str(level) + str(res)
        res = calc_step(level - 1, current - level)
        if res:
            return '-' + str(level) + str(res)
 
    res = calc_step(n-1, n)
    if res:
        return str(n) + res[:-4]
    return False

Конечно, порядок вывода слагаемых изменился. При необходимости строку-ответ можно было бы перевернуть назад или формировать её несколько по-другому, но для нашего примера это не принципиально. Выигрыш во времени на «пустом» переборе оказался существенным. Вызов signs3 (2, 30) завершил свою работу вместо нескольких минут уже за 20 секунд.

Для тех, кому интересно, когда на каждом этапе рекурсии перебирается немного значений, вместо нее для генерации ответов можно генерировать числа в альтернативных системах счисления. Например, в нашем случае на каждом этапе делается выбор из 2 значений «+» и «-» — значит для имитации выбора нам понадобится двоичная система счисления. Глубина рекурсии n-1 — значит необходимо сгенерировать все бинарные числа длиной n-1; в каждом номере 1 пусть будет соответствует «+», а 0 — «-«. Сам генератор несложен: начинаем с нуля и добавляем единицу на каждом шагу, пока не достигнем 11 … 111, в процессе получим все возможные комбинации 0 и 1, которые будут отвечать всем возможным комбинациям знаков:

def signs4(m, n):
    def add_1_to_binary_number(s):
        digit = n-2
        while s[digit] != '0':
            if s[digit] == '1':
                s = s[:digit] + '0' + s[digit+1:]
            digit -= 1
        s = s[:digit] + '1' + s[digit+1:]
        return s
 
    s = '0' * (n-1)
    s_final = '1' * (n-1)
    while s != s_final:
        # generate next position
        s = add_1_to_binary_number(s)
        # calculate sum
        res = n
        res_str = str(n)
        for j in range(0, n-1):
            sequence_element = n-1-j
            string_element = int(s[j])
            res = res + sequence_element * int(s[string_element]) - sequence_element * (1-string_element)
            res_str += '+'*string_element + '-'*(1-string_element) + str(sequence_element)
        if res == m:
            return res_str
    return False

Правда, реализовать «возвращение» в таком переборе будет намного сложнее, так как комбинации, которые перебираются, хуже структурированы.

А вот вариант рекурсивного решения перебором с возвратом задачи по ферзями (для произвольного размера шахматной доски):

# 1.5sec, 22740 combinations
counter = 0
n = 8
print 'v7, recursion bactracking'
 
def output_desk(p):
    if p == None:
        return
    for i in range(n):
        row = ''
        for j in range(n):
            flag = False
            for ii in range(n):
                if p[ii][0] == i and p[ii][1] == j:
                    flag = True
            row += '1'*int(flag) + '0'*(1-int(flag))
        print row
 
def is_ok(p):
    global counter
    counter += 1
    for i in range(n):
        for j in range(n):
            if i != j and \
                (p[i][0] == p[j][0] or p[i][1] == p[j][1] \
                or p[i][0]+p[i][1] == p[j][0]+p[j][1] \
                or n-p[i][0]+p[i][1] == n-p[j][0]+p[j][1]):
                return False
    return True  
 
def find_position():
    def try_queen(pos):
        if len(pos) == n:
            if is_ok(pos):
                return pos
            else:
                return False
        for i in range(len(pos)):
            for j in range(i+1, len(pos)):
                if pos[i][1] == pos[j][1]:
                    return False
        for current_queen_pos in range(0,n):
            pos_new = pos[:]
            pos_new.append((len(pos), current_queen_pos))
            res = try_queen(pos_new)
            if res:
                return res
 
    start_position = []
    return try_queen(start_position)
 
p = find_position()
print counter
print p
output_desk(p)

Эвристические алгоритмы

Эвристический алгоритм (эвристика) — это алгоритм решения задачи, который не имеет точного обоснования, но в большинстве практических случаев обеспечивает приемлемый ответ (по качеству и времени работы).

Это не значит, что решение, полученное эвристическим путем, всегда является приблизительным. Под неточностью эвристики понимают, что даже если найденные таким образом ответы являются точными, нет гарантий, что они так же будут точными для любых других входных данных.

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

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

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

Практические задачи

Задание 1

Разработать класс CombStr для представления строки символов.

Обеспечить следующие методы класса:

  • конструктор, принимающий 1 аргумент — строка string.
  • метод count_substrings (length), который принимает 1 аргумент — неотъемлемое целое число length, и возвращает целое число — количество всех различных подстрок длиной length, содержащиеся в строке string.

Тесты с некорректными данными не проводятся.

Последовательность символов substring считается подстрокой строки string, если ее можно получить из string путем отбрасывания символов с начала и/или конца строки. Например ‘asd‘ является подстрокой «asdfg«, а «fgh» — нет. Считать, что пустых подстрок не бывает, поэтому для length = 0 возвращать 0.

Пример последовательности действий для тестирования класса:

 s0 = CombStr ( 'qqqqqqweqqq%')
 print s0.count_substrings (0) # 0
 print s0.count_substrings (1) # 4
 print s0.count_substrings (2) # 5
 print s0.count_substrings (5) # 7
 print s0.count_substrings (15) # 0 

Смотреть ответ:

Задание 2

Разработать функцию find_fraction (summ), которая принимает 1 аргумент — неотъемлемое целое число summ, и возвращает тьюпл, содержащий 2 целых числа — числитель и знаменатель крупнейшей правильной несокращаемой дроби, для которой сумма числителя и знаменателя равна summ. Вернуть False, если создать такую дробь невозможно.

Пример последовательности действий для тестирования:

print find_fraction(2) # False
print find_fraction(3) # (1, 2)
print find_fraction(10) # (3, 7)
print find_fraction(62) # (29, 33)
print find_fraction(150000001) # (75000000, 75000001) 

Смотреть ответ:

Задание 3

Разработать функцию bouquets (narcissus_price, tulip_price, rose_price, summ), которая принимает 4 аргумента — положительные действительные числа (цены за один нарцисс, тюльпан и розу, и сумму денег в кармане главного героя),
и возвращает целое число — количество вариантов букетов, которые можно составить из этих видов цветов, таких, чтобы стоимость каждого букета не превышала summ.

Пример последовательности действий для тестирования:

print bouquets(1,1,1,5) # 34
print bouquets(2,3,4,10) # 12
print bouquets(2,3,4,100) # 4019
print bouquets(200,300,400,10000) # 4019
print bouquets(200,300,400,100000) # 3524556 

Смотреть ответ:

Задание 4

Разработать функцию make_sudoku (size), которая принимает 1 аргумент — положительное целое число (1 <= size <= 42),
и возвращает список списков — квадратную матрицу, представляющий судоку размерности size.

Судоку размерности X представляет собой квадратную матрицу размерностью X ** 2 на X ** 2, разбитую на X ** 2 квадратов размерностью X на X, заполненную целыми числами таким образом, чтобы каждая вертикаль, каждая горизонталь и каждый квадрат содержали все числа от 1 к X ** 2 включительно без повторов.

Например, судоку размерности 3 может выглядеть следующим образом:

Квадрат 9х9 (3 ** 2 = 9), который состоит из 9 квадратов 3х3. В каждой вертикали размещены различные числа от 1 до 9. То же касается каждой горизонтали и каждого внутреннего квадрата.

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

Пример входных и выходных данных:

print make_sudoku(1) # [[1]]
print make_sudoku(2) # [[1,2,3,4],[3,4,1,2],[2,1,4,3],[4,3,2,1]]
print make_sudoku(3) # [[3,5,8,1,2,7,6,4,9],[6,7,4,5,8,9,3,2,1],[2,1,9,3,4,6,5,7,8],[9,8,6,7,1,4,2,5,3],[4,3,1,2,6,5,8,9,7],[7,2,5,9,3,8,1,6,4],[1,6,3,4,7,2,9,8,5],[8,9,7,6,5,1,4,3,2],[5,4,2,8,9,3,7,1,6]] 

Смотреть ответ:

Финальное задание курса

Индиана Джонс и кольцо Цзунь-Си

На одном восточном рынке в руки Индианы Джонса попал интересный документ. В нем упоминался загадочный перстень, принадлежавший известному военному стратегу древности Цзунь-Си и, по словам автора, некоторым образом вобрал часть его мудрости. Вероятно, дальше кольцо передавался от одного императора Китая к другому и в конце концов был похоронен вместе с одним из них

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

Вам необходимо составить функцию maze_controller () для управления роботом. Известно, что лабиринт является квадратным, где-то в нем должно находиться кольцо Цзунь-Си и все. План лабиринта и его точные размеры, как и точное местонахождение входа и искомого артефакта, неизвестны.

К сожалению, вместо современного робота доктору Джонсу продали более дешевый, недостатком которого является очень ограниченный радиус действия сенсоров и отсутствие встроенной функции составления карт. Поэтому имеющийся робот «видит» только то, что находится только непосредственно перед ним и определяет наличие препятствий на пути только при непосредственном контакте с ними.

У робота есть объектно-ориентированный интерфейс управления со следующими методами:

    • go () — проехать на поле вперед, возвращает True или False в зависимости от того, удалось проехать (например, перед роботом может находиться стена). Если проехать невозможно, робот остается на месте.
    •  turn_left () — повернуть на 90 градусов против часовой стрелки.
    •  turn_right () — повернуть на 90 градусов по часовой стрелке.
    •  found () — проверяет, находится кольцо в зоне видимости работа.

В качестве единственного аргумента при вызове функции maze_controller () передается инициализированный объект класса MazeRunner для управления роботом. Функция maze_controller ничего не возвращает с помощью оператора return. Но в результате ее работы робот должен быть переведен в поле лабиринта, в котором находится искомый артефакт (считать, что артефакт всегда присутствует в лабиринте). То есть после вызова maze_controller (maze_runner), метод объекта maze_runner.found () должен возвращать True. Прямой доступ к изображению лабиринта запрещен.

Пример класса MazeRunner:

Итак, ваша задача:

  • Написать функцию maze_controller (mr), единственным аргументом которой является уже инициализирован (проверяющим) объект класса MazeRunner. Функция ничего не возвращает, но в результате ее выполнения работ должен быть переведен в поле лабиринта, где находится артефакт — то есть после вызова функции maze_controller (maze_runner), метод объекта maze_runner.found () должен возвращать True.
  • Прямой доступ к изображению лабиринта запрещен.
    Ваше решение должен содержать только функцию maze_controller и ничего кроме нее. Ни ввода или вывода данных, кроме взаимодействия с переданным объектом, быть не должно. Считайте, что объект управления роботом создается и инициализируется автоматическим за пределами вашей функции.
  • Код не должен содержать комментариев, кириллицы, проверок на то, является ли она главным модулем, подключений нестандартных модулей, функции exit ().

Один из вариантов решения:

Перевод с украинского языка.

Открытые бесплатные курсы.

Читайте больше по теме:

Подписаться
Уведомление о
guest
0 Комментарий
Inline Feedbacks
View all comments
Просмотры: 462

Популярные записи