​Выбираемся из лабиринта при помощи алгоритма «поиск в ширину» (BFS) на Python

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

В этой статье вы сможете изучить его работу на примере лабиринта и поиска выхода из него:

https://habr.com/ru/company/piter/blog/679020/

#алгоритмы

​Генерируем 2D-мир с помощью клеточного автомата на Python

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

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

Хорошая статья, в которой можно попрактиковаться сразу и в геймдеве, и в теории клеточных автоматов, и в принципе закодировать что-нибудь интересное на питоне, вместо очередного калькулятора или просмотрщика погоды: https://habr.com/ru/post/721956/

#алгоритмы

​Визуализируем 5 алгоритмов сортировки на Python

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

Давайте реализуем и визуализируем пять популярных алгоритмов сортировки на Python

#алгоритмы #гайды

Разбираемся в бинарном поиске на Python

Binary Search, или бинарный поиск — это эффективный способ найти элемент в отсортированном массиве. Принцип работы основан на делении массива пополам. Алгоритм постоянно уменьшает область поиска, пока не найдёт целевой элемент или не убедится, что его в массиве нет.

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

Рассмотрим пример итеративного бинарного поиска на Python:

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = arr[mid]
        
        if guess == target:
            return mid
        elif guess > target:
            high = mid - 1
        else:
            low = mid + 1
    
    return -1

# Пример использования
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 9
result = binary_search(arr, target)
print(f"Элемент найден на индексе: {result}" if result != -1 else "Элемент не найден")

Аналогичный пример можно реализовать и рекурсивным методом:

def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1
    
    mid = (low + high) // 2
    guess = arr[mid]
    
    if guess == target:
        return mid
    elif guess > target:
        return binary_search_recursive(arr, target, low, mid - 1)
    else:
        return binary_search_recursive(arr, target, mid + 1, high)

# Пример использования
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 9
result = binary_search_recursive(arr, target, 0, len(arr) - 1)
print(f"Элемент найден на индексе: {result}" if result != -1 else "Элемент не найден")

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

import bisect

def binary_search_bisect(arr, x):
    i = bisect.bisect_left(arr, x)
    if i != len(arr) and arr[i] == x:
        return i
    else:
        return -1

# Пример использования
arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search_bisect(arr, x)
print(f"Элемент найден на индексе: {result}" if result != -1 else "Элемент не найден")

Важно помнить, что бинарный поиск работает только с отсортированными массивами. В этом его главный плюс и ограничение. Зато временная сложность у него составляет всего O(log n), что значительно быстрее линейного поиска. Это делает бинарный поиск отличным выбором для работы с большими данными.

#советы #алгоритмы

Популярные алгоритмы машинного обучения на Python

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

А если вам этого мало, то в конце каждой темы указаны дополнительные источники для более глубокого ознакомления.

#ml #алгоритмы

Его величество Граф

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

Эта статья создана, чтобы вы смогли сделать это. После прочтения вы будете знать:

— основы работы с графами;
— как применяются графы в Python;
— примеры использования графов;
— как решать задачи на графах;
— о визуализации и аналие графов.

#графы #алгоритмы