Исследователи смогли преодолеть барьер в улучшении решения задачи коммивояжера

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

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

Алгоритм Укконена: от простого к сложному

Изучая курс Алгоритмы на строках столкнулся с задачей о построении суффиксного дерева. Перейдя по ссылке на дополнительные материалы наткнулся на рекомендацию "просмотреть этот замечательный комментарий на Stack Overflow". Изучив и реализовав по при ... Читать дальше »

Песочный алфавит при помощи генеративных алгоритмов

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

Это развитие идей из публикаций:

Визуализация при помощи генеративных алгоритмов: гифа, деревья, повторяющиеся и дифференциальные линии (на Python)

Визуализация при помощи генеративных алгоритмов: дифференциальная сетка (2D и 3D) и трещины

Однако вам необязательно читать их — все проекты, описанные здесь самодостаточны.
 

ПЕСОЧНЫЙ СПЛАЙН [GITHUB]

... Читать дальше »

Корни, комплексные числа и парадоксы многозначности

Возник вопрос с извлечением корней. Вообще, из школьного курса известно, что квадратный корень имеет два значения, и есть понятие "арифметический корень". Обычно полагают, что значение корня положительно, а варианты учитывают с помощью ±. Для кубических корней такое не всегда проходит, а если в формуле корень встречается два раза, возможны варианты: где-то предполагается, что все корни принимают одно и то же значение, а где-то они независимы...

... Читать дальше »

Графы: основы теории, алгоритмы поиска

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

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

Мелкая питонячая радость #10: конечные автоматы и глубокое обучение в несколько строк

Конечно, самая большая радость этих дней — python 3.9. Но кроме этой радости кто-то должен ворошить github в поисках мелких приятностей, которые несут добро и свет тем, кто пишет на python.

Transitions

Тем, кому приходилось писать реализацию какого-нибудь сложного информационного процесса, знает эту проблему.

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