Artemis II
3 поста
3 поста
9 постов
16 постов
3 поста
3 поста
20 постов
4 поста
10 постов
8 постов
6 постов
4 поста
12 постов
5 постов
1 пост
dataclass — это декоратор, введенный в Python 3.7, который автоматически генерирует специальные методы (такие как __init__, __repr__, __eq__ и другие) для классов, которые в основном служат контейнерами для данных. Это избавляет от необходимости писать много шаблонного кода.
Использование dataclass в Python значительно упрощает работу с классами, предназначенными для хранения данных. Вместо того чтобы вручную определять методы __init__, __repr__, __eq__ и другие, достаточно просто объявить поля данных, а dataclass автоматически сгенерирует необходимый код. Это не только делает классы более лаконичными и понятными, но и улучшает читаемость кода, так как акцент смещается на данные, а не на техническую реализацию. Кроме того, автоматически сгенерированный код снижает вероятность ошибок, которые могут возникнуть при ручном написании.
Для начала, тебе нужно импортировать декоратор dataclass из модуля dataclasses:
Затем ты помечаешь класс декоратором @dataclass, и определяешь поля данных, как обычные переменные класса с аннотациями типов:
В этом примере, Point — это dataclass, которая имеет два поля: x и y, оба целого типа. dataclass автоматически создаст: * Конструктор __init__, позволяющий создавать экземпляры класса, например Point(1, 2). * __repr__, возвращающий строковое представление объекта, например Point(x=1, y=2). * __eq__, позволяющий сравнивать объекты, например Point(1, 2) == Point(1, 2).
Пример простого использования
Варианты dataclass
dataclass предоставляет несколько параметров для настройки поведения:
init: Если True (по умолчанию), генерируется метод __init__. Если False, метод __init__ не создается.
repr: Если True (по умолчанию), генерируется метод __repr__. Если False, метод __repr__ не создается.
eq: Если True (по умолчанию), генерируется метод __eq__. Если False, метод __eq__ не создается.
order: Если True, генерируются методы сравнения (__lt__, __le__, __gt__, __ge__). По умолчанию False.
unsafe_hash: Если False (по умолчанию), метод __hash__ не генерируется. Если True, метод __hash__ будет сгенерирован, а dataclass станет хешируемым.
frozen: Если True, экземпляры класса будут неизменяемыми (read-only). По умолчанию False.
Отключаем метод __repr__ и делаем класс неизменяемым
2. Устанавливаем порядок, добавляем метод hash и делаем класс неизменяемым
Значения по умолчанию
Ты можешь задавать значения по умолчанию для полей:
При создании экземпляра класса, если значения не переданы, будет использовано значение по умолчанию.
Использование dataclass с изменяемыми типами
Будь осторожен при использовании изменяемых типов данных (списки, словари) в качестве значений по умолчанию. Они будут созданы только один раз и будут использоваться всеми экземплярами класса:
В примере выше изменения в bad1.items также отображаются в bad2.items. Это происходит из-за того, что оба экземпляра класса используют один и тот же список по умолчанию.
Чтобы этого избежать, используй dataclasses.field и default_factory:
В этом случае default_factory=list создаст новый пустой список для каждого нового экземпляра класса.
Удачи!
👉 GIT
Другие шпаргалки
Посмотреть код можно в Google Colab
Google Colab — это облачная платформа, созданная Google, для работы с интерактивными блокнотами Jupyter Notebook. Она предоставляет мощные инструменты для написания и выполнения кода на Python, анализа данных, обучения моделей машинного обучения и совместной работы над проектами.
Colab предлагает доступ к мощным ресурсам, включая графические и тензорные процессоры. Это позволяет решать сложные задачи, такие как работа с большими объёмами данных или обучение нейросетей, без покупки дорогого оборудования. Colab работает на основе Jupyter Notebook. Использовать Colab можно сразу после открытия — ничего дополнительно устанавливать не нужно, всё уже готово к работе. Ты можешь подключить Google Диск, чтобы легко данные, сохранять проекты и получать доступ к файлам откуда угодно. Также в Colab можно работать вместе с другими пользователями.
- Jupyter запускается в браузере. Код выполняется на удаленных серверах Google, а результаты отображаются в блокноте. Данные могут загружаться из локального устройства или из облака, такого как Google Drive. Ты можете использовать Colab для работы с библиотеками для машинного обучения (например, TensorFlow, PyTorch), анализа данных с использованием Pandas или создания визуализаций через Matplotlib и Seaborn.
Интерфейс Colab состоит из нескольких основных частей:
Строки кода: Это ячейки, в которые ты будешь писать и выполнять свой код на Python.
Текстовые ячейки: Здесь ты можешь добавлять описания, пояснения и заметки к своему коду.
Меню: Сверху есть меню с различными опциями для работы с блокнотом (файл, правка, вид, инструменты и т.д.).
Файловый менеджер: Слева есть панель файлового менеджера, где ты можешь просматривать файлы и папки в своей среде Colab.
В Google Colab, ты работаешь в облачной среде, где файловая система организована как на обычном компьютере с папками и файлами. Ты можешь взаимодействовать с файловой системой с помощью магических команд Jupyter (начинаются с `%`) и команд bash (начинаются с `!`).
Список основных команд:
%pwd (print working directory):
Описание: Показывает текущую рабочую директорию (где ты сейчас "находишься" в файловой системе).
Пример: %pwd
Результат: /content (или другая текущая директория)
%ls (list):
Описание: Выводит список файлов и папок в текущей директории.
Пример: %ls
Результат: Список файлов и папок, например: sample_data/ my_file.txt
%cd <путь> (change directory):
Описание: Переходит в указанную директорию.
Пример: %cd sample_data
Результат: Текущая рабочая директория меняется на /content/sample_data
!head -<количество строк> <имя файла>:
!cat <имя файла>:
Описание: Выводит содержимое указанного текстового файла.
Пример: !cat sample_file.txt
Результат: Всё содержимое файла sample_file.txt.
!echo "<текст>" > <имя файла> * Описание: Создаёт новый файл с указанным именем и записывает в него текст. Если файл уже существует, он будет перезаписан * Пример: !echo "Это мой новый файл!" > new_file.txt * Результат: Создаёт файл new_file.txt с содержимым Это мой новый файл!.
Ключевые моменты:
Магические команды (%) - это специальные команды Jupyter для работы с окружением Colab.
Команды bash (!) - это команды, которые выполняются в командной строке Linux.
Путь к файлу: Путь к файлу указывает, где именно файл находится в файловой системе (например, /content/sample_data/my_file.txt).
Текущая директория: Твоё положение в файловой системе (изменяется командой %cd).
Посмотреть в Google colab
Есть несколько способов загрузить файлы в Colab, и мы рассмотрим наиболее распространенные из них.
Загрузка через файловый менеджер (GUI)
Описание: Самый простой способ загрузить файлы, особенно небольшие, – использовать графический интерфейс файлового менеджера Colab.
Как это сделать:
Открой панель файлового менеджера слева (значок папки).
Нажми на значок загрузки (обычно это значок с плюсом или стрелкой вверх).
В открывшемся окне выбери файлы на своем компьютере, которые ты хочешь загрузить.
Нажми "Открыть" или "Загрузить".
Плюсы: Простота, наглядность, не требует написания кода.
Минусы: Подходит для небольших файлов, нужно делать вручную.
2. Загрузка через код Python (google.colab.files.upload())
Описание: Этот способ позволяет загружать файлы с помощью кода Python, что дает больше гибкости.
Как это сделать:
Импортируй модуль files из библиотеки google.colab.
from google.colab import files
Вызови функцию files.upload()
uploaded = files.upload()
При запуске этого кода, появится диалоговое окно, где ты можешь выбрать файлы для загрузки.
После выполнения этого кода загруженные файлы будут доступны в виде словаря uploaded, где ключи – имена файлов, а значения – их содержимое в виде байтовых строк.
3. Клонирование репозитория GitHub (git clone)
Если твои файлы находятся в репозитории GitHub, ты можешь загрузить их, клонировав репозиторий в Colab.
Как это сделать:
Используй команду git clone с URL репозитория.
!git clone <URL_репозитория>
Например:
!git clone https://github.com/username/my_repository.git
После клонирования репозитория, содержимое будет доступно в папке, названной также как репозиторий.
Плюсы: Легко загрузить все файлы из репозитория, удобный способ для проектов с контролем версий.
Минусы: Подходит только для файлов в репозиториях GitHub.
4. Скачивание отдельного файла с GitHub
Если тебе нужен только один или несколько файлов из репозитория GitHub, ты можешь скачать их по прямой ссылке.
Как это сделать:
Открой нужный файл в репозитории GitHub.
Нажми на кнопку "View raw" (или "Необработанный вид").
Скопируй URL этого файла. 4. Используй wget или curl для скачивания файла.
!wget <URL_файла>
или python !curl <URL_файла> -o <имя_файла_в_colab>
Плюсы: Просто скачать только нужные файлы, без клонирования всего репозитория.
Минусы: Требуется знать прямую ссылку на файл.
Какой способ выбрать?
Для небольших файлов, которые нужно загрузить быстро и вручную, подойдет файловый менеджер.
Если нужно программно обрабатывать загруженные файлы, используй files.upload().
Для загрузки целых проектов, используй git clone.
Для скачивания отдельных файлов, используй wget или curl
Посмотреть код можно в Google Colab
ИСХОДНЫЙ КОД ПЕРЕЕХАЛ ПО ЭТОМУ АДРЕСУ
Примеры использования списков и словарей для представления данных о товарах. Я разложу абстрактный товар по характеристикам и покажу, как использовать список для представления товаров в категории.
Словарь (dict) – это идеальный способ представления характеристик одного товара, где есть пары "ключ-значение".
Список (list) – это отличный способ представления набора однотипных товаров, где каждый товар может быть представлен словарем.
Словарь для представления характеристик одного товара. В этом случае, ключами словаря будут названия характеристик, а значениями – их соответствующие значения.
Разъяснение кода:
словарь product, где ключами являются названия характеристик товара (id, name, brand, price и т.д.), а значениями — их соответствующие значения.
product.items() для итерации по всем парам "ключ-значение" и вывел их на экран.
Список для представления списка товаров в определенной категории. В этом случае, каждый элемент списка будет представлять отдельный товар, который, в свою очередь, может быть представлен словарем.
Разъяснение кода:
Список products, где каждый элемент - это словарь, представляющий отдельный товар.
Я проитерировал список и вывел на экран информацию о каждом товаре, используя ключи словаря для доступа к характеристикам товара.
Я показал, как получить доступ к первому товару в списке, используя индекс 0.
Я проитерировал список еще раз, и показал как можно выводить только названия товаров.
Оригинала статьи в GIT
Другие шпаргалки:
Структуры данных в python
Переменные в python: что, как и зачем нужны
Строки в python
Функции в python
Синглтон (Singleton) в Python
dict vs SimpleNamespace в Python
Серия 101 игра на python с разбором кода. Портирую классические игры на язык python с добавлением искусственного интеллекта.
КОД ПЕРЕЕХАЛ ПО ЭТОМУ АДРЕСУ
Оба они позволяют хранить именованные данные, но делают это по-разному, и каждый из них имеет свои особенности.
1. Словари (dict)
Словарь в Python – это структура данных, которая хранит пары "ключ-значение". Ключи должны быть неизменяемыми типами данных (например, строки, числа, кортежи), а значения могут быть любыми.
Создание: Словари создаются с помощью фигурных скобок {} или функции dict().
Доступ к значениям: Значения доступны по ключу с помощью квадратных скобок [].
Изменение: Значения можно изменять, добавлять новые пары "ключ-значение" и удалять существующие.
2. SimpleNamespace
SimpleNamespace – это простой класс из модуля types, который позволяет обращаться к значениям как к атрибутам объекта. Он хорош для хранения и передачи набора данных.
Создание: SimpleNamespace создается с помощью функции SimpleNamespace() и передачей именованных аргументов.
Доступ к значениям: Значения доступны как атрибуты объекта с помощью точечной нотации `.`
Изменение: Значения можно изменять, добавлять новые атрибуты и удалять существующие.
Преимущества dict
Гибкость ключей: Ключи словаря могут быть любыми неизменяемыми типами данных (строки, числа, кортежи). Это позволяет создавать словари со сложной структурой, где ключами могут быть, например, координаты точек или другие сложные объекты.
Множество методов: Словари предоставляют богатый набор встроенных методов для работы с данными:
keys(): Возвращает все ключи словаря.
values(): Возвращает все значения словаря.
items(): Возвращает все пары "ключ-значение" в виде кортежей.
get(): Возвращает значение по ключу или значение по умолчанию, если ключа нет.
pop(): Удаляет элемент по ключу и возвращает его значение.
и многие другие.
Динамическое создание: Словари можно легко расширять, добавляя новые пары "ключ-значение" во время выполнения программы.
Итерация: Словари можно удобно итерировать: по ключам, по значениям или по парам ключ-значение.
Удобно для JSON: Словари имеют удобное представление для работы с JSON данными
Преимущества SimpleNamespace
Доступ к атрибутам через точку: Доступ к значениям с помощью точечной нотации (my_namespace.attribute) более читаем и удобен, чем использование квадратных скобок и ключей (my_dict["key"]). Это делает код более похожим на работу с обычными объектами.
Удобство при передаче данных: SimpleNamespace удобно использовать для передачи данных в функции или модули, когда нужно передать набор связанных именованных значений. Вы можете передать один объект, вместо нескольких переменных.
Простота создания: SimpleNamespace легко создать, передав именованные аргументы: SimpleNamespace(name="Alice", age=30).
Меньше кода: Для простого доступа к значениям как к атрибутам объекта, использование SimpleNamespace может потребовать меньше кода, чем работа со словарями.
Предсказуемая структура: В отличии от словаря, SimpleNamespace создает объект с конкретными атрибутами.
Когда что использовать:
Используй dict когда:
У тебя есть динамический набор ключей, которые могут меняться во время выполнения программы.
Тебе нужно использовать методы словаря для обработки итерирования данных.
Ты работаешь с данными в формате "ключ-значение".
Тебе нужны гибкость и динамичность.
Тебе нужны ключи, которые не являются строками.
Используй SimpleNamespace когда:
У тебя есть предопределенный набор именованных значений (атрибутов).
Тебе нужно передавать набор данных в виде объекта.
Тебе нужна более читаемая точечная нотация для доступа к значениям.
Тебе нужна простота и удобство при создании объектов для хранения данных.
Когда структура данных не должна меняться динамически.
Пример:
У тебя есть функция, которая принимает данные о пользователе.
В этом примере, для dict я использую метод get, чтобы получить значения, с предустановленным значением, если ключа нет. Для SimpleNamespace я обращаюсь к атрибутам напрямую, что более читаемо.
Оригинала статьи в GIT
Другие шпаргалки:
Структуры данных в python
Переменные в python: что, как и зачем нужны
Строки в python
Функции в python
Синглтон (Singleton) в Python
Серия 101 игра на python с разбором кода. Портирую классические игры на язык python с добавлением искусственного интеллекта.
КОД ПЕРЕЕХАЛ ПО ЭТОМУ АДРЕСУ
В Python, синглтон – это шаблон проектирования, который гарантирует, что у класса будет только один экземпляр, и предоставляет глобальную точку доступа к этому экземпляру. Это значит, что при попытке создать новый объект этого класса, ты всегда будешь получать один и тот же объект.
Синглтоны полезны, когда нужно ограничить количество экземпляров класса, например:
Для управления подключением к базе данных (чтобы не открывать много подключений).
Для хранения глобальной конфигурации приложения (чтобы все части приложения использовали одну и ту же конфигурацию).
Для логгирования (чтобы все сообщения шли в один файл).
Преимущества синглтона:
Гарантия единственного экземпляра: Синглтон гарантирует, что класс будет иметь только один экземпляр. Это полезно для управления ресурсами, которые должны быть уникальными.
Глобальный доступ: Синглтон предоставляет глобальную точку доступа к экземпляру класса, что упрощает использование этого экземпляра в любой части программы.
Недостатки синглтона:
Глобальное состояние: Синглтон может привести к использованию глобального состояния, что может вызывать неожиданные побочные эффекты и усложнять тестирование.
Нарушение принципов ООП: Синглтон может нарушать принцип единственной ответственности и инкапсуляции.
Несколько способов реализации синглтона в Python.
Mетод __new__ отвечает за создание экземпляра класса. Переопределив его, я смогу контролировать этот процесс.
В этом примере я буду хранить единственный экземпляр класса в переменной _instance.
Если экземпляра еще нет, я его создам, иначе верну уже существующий экземпляр.
Декоратор – это функция, которая модифицирует класс.
В этом примере я создаю функцию-декоратор singleton, которая принимает класс и возвращает его обернутую версию.
Внутри декоратора я храню экземпляры классов в словаре instances.
Если экземпляр класса еще не создан, я его создам и сохраню в словаре, иначе верну существующий экземпляр.
Mетакласс позволяет контролировать создание классов.
В этом примере я создам метакласс SingletonMeta, который будет следить за созданием экземпляров.
Метакласс хранит экземпляры классов в словаре _instances.
При создании нового экземпляра, я проверяю, есть ли он уже в словаре, если нет – создаю, иначе возвращаю существующий экземпляр.
В Python модуль сам по себе является синглтоном.
Я могу создать объект в модуле, и он будет единственным экземпляром.
Когда использовать синглтон?
Когда тебе нужно, чтобы объект существовал в единственном экземпляре (например, конфигурация, логгер, подключение к базе данных).
Когда тебе требуется глобальный доступ к этому объекту.
Оригинала статьи в GIT
Другие шпаргалки:
Серия 101 игра на python с разбором кода. Портирую классические игры на язык python с добавлением искусственного интеллекта.
Серия информатика, с изложением терминов
КОД ПЕРЕЕХАЛ ПО ЭТОМУ АДРЕСУ
Полиномиальное время —время выполнения алгоритма, которое растёт как полином (многочлен) от размера входных данных. Если время выполнения алгоритма можно выразить как (O(n^k)), где (n) — размер входных данных, а (k) — константа, то такой алгоритм работает за полиномиальное время.
Примеры:
Сортировка списка: Алгоритмы, такие как сортировка слиянием или быстрая сортировка, работают за (O(n \log n)), что является полиномиальным временем.
Поиск кратчайшего пути в графе: Алгоритм Дейкстры работает за (O(n^2)) или (O(n \log n)) в зависимости от реализации, что также полиномиально.
Особенности:
Алгоритмы, работающие за полиномиальное время, считаются эффективными и практически применимыми.
Задачи, которые можно решить за полиномиальное время, относятся к классу P.
Экспоненциальное время — время выполнения алгоритма, которое растёт экспоненциально в зависимости от размера входных данных. Если время выполнения можно выразить как (O(k^n)), где (n) — размер входных данных, а (k) — константа, то такой алгоритм работает за экспоненциальное время.
Примеры:
Задача коммивояжёра: Решение методом полного перебора всех возможных маршрутов требует (O(n!)) времени, что хуже экспоненциального.
Перебор всех подмножеств: Алгоритм, который проверяет все возможные подмножества множества из (n) элементов, работает за (O(2^n)).
Особенности:
Алгоритмы, работающие за экспоненциальное время, считаются неэффективными для больших входных данных, так как время выполнения становится непрактично большим даже при относительно небольших (n).
Задачи, которые могут быть решены только за экспоненциальное время, часто относятся к классам NP-трудных или NP-полных.
Полиномиальное время:
Алгоритмы, работающие за полиномиальное время, считаются практически применимыми, так как они могут обрабатывать большие объёмы данных за разумное время.
Задачи класса P (решаемые за полиномиальное время) являются основой для многих приложений в компьютерных науках, таких как обработка данных, сети, криптография и искусственный интеллект.
Экспоненциальное время:
Алгоритмы, работающие за экспоненциальное время, становятся непрактичными даже для относительно небольших входных данных. Например, при (n = 100), (2^n) уже превышает количество атомов в наблюдаемой Вселенной.
Задачи, которые могут быть решены только за экспоненциальное время, часто требуют использования приближённых методов, эвристик или параллельных вычислений.
Задача её для (n = 10) и (n = 100):
Полиномиальное время ((n^2)):
При (n = 10): (10^2 = 100) операций.
При (n = 100): (100^2 = 10,000) операций.
Экспоненциальное время ((2^n)):
При (n = 10): (2^{10} = 1,024) операций.
При (n = 100): (2^{100} \approx 1.26 \times 10^{30}) операций.
При (n = 100) полиномиальный алгоритм выполнит 10 000 операций, что вполне реально, а экспоненциальный алгоритм потребует (1.26 \times 10^{30}) операций, что практически невозможно.
В теории вычислительной сложности задачи классифицируются по их сложности и ресурсам, необходимым для их решения. Классы сложности помогают понять, насколько "трудно" решить ту или иную задачу с точки зрения времени, памяти или других ресурсов. Они играют ключевую роль в теории вычислений, криптографии, искусственном интеллекте и других областях. Изучение этих классов позволяет разрабатывать эффективные алгоритмы и понимать пределы вычислимости.
- Задачи, которые можно решить за полиномиальное время на детерминированной машине Тьюринга (например, на обычном компьютере). Например: сортировка списка, поиск кратчайшего пути в графе (алгоритм Дейкстры). Считается, что задачи класса P "легко" решаемы.
- Задачи, для которых проверка правильности решения может быть выполнена за полиномиальное время, но само решение может быть найдено только за экспоненциальное время (или хуже). Например: задача о рюкзаке, задача коммивояжёра, задача выполнимости булевых формул (SAT). Вопрос о том, равны ли классы P и NP, является одной из главных нерешённых проблем в информатике.
- Задачи, которые одновременно являются NP-трудными и принадлежат классу NP. Это самые сложные задачи в классе NP. Например: задача коммивояжёра, задача о раскраске графа, задача о выполнимости булевых формул (SAT). Если для одной NP-полной задачи будет найден полиномиальный алгоритм, то все задачи в классе NP также смогут быть решены за полиномиальное время.
- Задачи, которые не менее сложны, чем самые сложные задачи в классе NP, но не обязательно принадлежат самому классу NP. Например: задача оптимизации, задача остановки, головоломка о перемещении пианино. Даже если задача не является NP-полной, она может быть NP-трудной, что делает её крайне сложной для решения.
- Задачи, которые могут быть решены за экспоненциальное время на детерминированной машине Тьюринга. Например: задача проверки выигрышной стратегии в шахматах или го. Эти задачи сложнее, чем задачи класса P или NP, так как их решение требует значительно больше времени.
- Задачи, которые могут быть решены с использованием полиномиального количества памяти, но время решения может быть экспоненциальным. Например: задача проверки истинности формул в логике, задача планирования в искусственном интеллекте. Класс PSPACE включает в себя как P, так и NP, и считается, что он может быть строго больше.
- Задачи, для которых проверка неправильности решения может быть выполнена за полиномиальное время. Например: задача проверки, что булева формула невыполнима. Co-NP является "дополнительным" классом к NP, и вопрос о равенстве NP и Co-NP также остаётся открытым.
- Задачи, которые могут быть решены за полиномиальное время с использованием вероятностного алгоритма, допускающего небольшую вероятность ошибки. Например: тестирование простоты числа (алгоритм Миллера-Рабина). BPP считается классом задач, которые могут быть эффективно решены на практике, даже если они не принадлежат P.
- Задачи, связанные с подсчётом количества решений для задач из класса NP. Например: подсчёт количества способов раскраски графа или количества выполнимых назначений для булевой формулы. Задачи класса #P считаются ещё более сложными, чем NP-полные задачи.
- Задачи, которые могут быть решены с использованием логарифмического количества памяти относительно размера входных данных. Например: проверка связности графа в ограниченных условиях. L является подклассом P и изучается в контексте задач, которые можно решить с минимальными ресурсами памяти.
- Задачи, которые могут быть решены за полилогарифмическое время с использованием полиномиального числа процессоров. Например: параллельная сортировка, быстрое преобразование Фурье. NC изучается в контексте параллельных вычислений и считается классом задач, которые могут быть эффективно решены на многопроцессорных системах.
- Задачи, для которых существует алгоритм, способный перечислить все возможные решения, но не обязательно завершающийся для неправильных входных данных. Например: задача остановки для машины Тьюринга. RE включает в себя как разрешимые, так и неразрешимые задачи.
- Задачи, для которых неправильность решения может быть перечислена алгоритмом, но не обязательно правильность. Например: задача проверки, что машина Тьюринга не останавливается на данном входе. Co-RE является "дополнительным" классом к RE.
- Задачи, которые могут быть решены за полиномиальное время с использованием вероятностных алгоритмов, но без ограничения на вероятность ошибки. Например: некоторые задачи из криптографии. R изучается в контексте задач, где случайность может быть полезной, но не обязательно гарантирует точность.
- Иерархия классов сложности, которая обобщает классы P, NP, Co-NP и другие. PH строится на основе чередования кванторов в логических формулах и включает в себя бесконечное число уровней сложности. Например: задачи, связанные с проверкой сложных логических утверждений. PH считается более широким, чем NP, но его точное соотношение с другими классами остаётся предметом исследований.
Ants and humans compete in maneuvering a T-shaped load across a maze. Credit: Weizmann Institute of Science
В Институте науки Вейцмана провели эксперимент, в котором муравьи и люди соревновались в решении групповой задачи: нужно было провести крупный груз через лабиринт. Результаты, опубликованные в Proceedings of the National Academy of Sciences, оказались неожиданными и пролили свет на преимущества и недостатки коллективного принятия решений.
Муравьи и люди — единственные существа в природе, которые регулярно сотрудничают при транспортировке объектов, значительно превышающих их собственные размеры. Профессор Офер Файнерман и его команда использовали эту общую черту, чтобы выяснить, кто справится с задачей лучше. Для этого они создали реальную версию классической задачи из области робототехники — "головоломку о перемещении пианино" *) . Участникам нужно было провести Т-образный объект через прямоугольное пространство, разделённое на три камеры с узкими проходами.
Эксперимент проводился с двумя видами лабиринтов — для муравьёв и людей, а также с группами разного размера. Люди участвовали добровольно, а муравьи (Paratrechina longicornis, также известные как "сумасшедшие муравьи") были привлечены, думая, что перемещают еду в свой муравейник.
Муравьи справлялись с задачей в трёх вариантах: в одиночку, в малой группе (около семи особей) и в большой группе (около 80). Люди также работали в трёх аналогичных комбинациях. Чтобы сравнение было максимально точным, людям в некоторых случаях запрещали общаться, а также использовали ручки с датчиками для измерения прилагаемой силы.
Credit: Weizmann Institute of Science
Результаты показали, что в индивидуальном зачёте люди, благодаря своим когнитивным способностям, легко обошли муравьёв. Однако в групповом задании всё изменилось. Муравьи действовали слаженно, демонстрируя коллективную память и избегая повторных ошибок. В то время как люди, особенно при ограниченном общении, не смогли улучшить свои результаты, часто выбирая краткосрочные, но неэффективные решения.
"Муравейник — это семья, где все особи связаны общими интересами. Это тесно сплочённое общество, где сотрудничество преобладает над конкуренцией. Именно поэтому муравейник иногда называют суперорганизмом, где каждая особь действует как часть единого целого", — объясняет Файнерман.
Исследование подтвердило, что муравьи в группе умнее, чем по отдельности, а у людей коллективная работа не всегда приводит к лучшим результатам. "Знаменитая "мудрость толпы", столь популярная в эпоху социальных сетей, в наших экспериментах не проявилась", — отметил учёный.
Несмотря на сложности человеческого сотрудничества, авторы исследования успешно объединили усилия, включая доктора Эхуда Фонио, профессора Нира Гова и доктора Амира Халуца. Их работа открывает новые горизонты в понимании группового поведения и эволюции сотрудничества.
More information: Tabea Dreyer et al, Comparing cooperative geometric puzzle solving in ants versus humans, Proceedings of the National Academy of Sciences (2024). DOI: 10.1073/pnas.2414274121
Journal information: Proceedings of the National Academy of Sciences
*) "Головоломка о перемещении пианино" (англ. **Piano Movers' Problem**) — это классическая задача из области робототехники, теории планирования движений и вычислительной геометрии. Она была впервые сформулирована в 1980-х годах и стала одной из ключевых проблем в разработке алгоритмов для перемещения объектов в сложных пространствах.
Суть задачи
Задача заключается в поиске оптимального пути для перемещения крупного объекта (например, пианино) из точки **А** в точку **Б** в ограниченном пространстве, которое может содержать препятствия. Основная сложность состоит в том, что объект имеет нестандартную форму и размеры, что требует тщательного планирования его траектории, чтобы избежать столкновений с окружающими объектами.
Математическая формулировка
С математической точки зрения задача сводится к поиску пути в **конфигурационном пространстве** (англ. **Configuration Space**), где каждая точка представляет возможное положение и ориентацию объекта. Пространство делится на допустимые и недопустимые области (например, где объект сталкивается с препятствиями). Задача заключается в нахождении непрерывного пути от начальной до конечной конфигурации, который лежит только в допустимых областях.
Пример
Представьте, что нужно провести пианино через узкий коридор с поворотами и дверными проёмами. Необходимо учитывать не только длину и ширину пианино, но и его высоту, а также возможность поворота в ограниченном пространстве. Алгоритм должен рассчитать, как именно двигать объект, чтобы он не задел стены или другие препятствия.
Сложность
Задача относится к классу **NP-трудных**, что означает, что для её решения в общем случае не существует эффективного алгоритма, работающего за полиномиальное время. Поэтому на практике используются приближённые методы, эвристики и алгоритмы, такие как:
- Алгоритмы поиска пути (например, A*, RRT — Rapidly-exploring Random Tree).
- Методы декомпозиции пространства (разбиение пространства на более простые области).
- Использование симуляций для проверки возможных траекторий.