Wataru

Готовых решений я не знаю, но есть следующие идеи.

Во-первых, научимся аппроксимировать одной кривой. Первая и четвертая точки нам известны - это первый и последний пиксель. координаты двух других опорных точек кривой Безье - это четыре неизвестных.

Составим функцию ошибки f(x1, y1, x2, y2) = (X(i/n)-x_i)^2+(Y(i/n)-y_i)^2. Тут x_i, y_i - координаты i-ого пикселя в нарисованной кривой, пронумерованные от 0 до n, X(t), Y(t) - координаты точки на кривой Безье - линейные комбинации x1, x2 и y1, y2 с известными вычисляемыми от t коэффициентами. Это фактически сумма квадратов расстояний от каждого пикселя до неизвестной кривой. Ее можно минимизировать подобно методу наименьших квадратов - считайте производную по всем переменным, приравнивайте к 0. Получите 4 неизвестные и 4 линейных уравнения. Можно вообще на бумажке руками методом Краммера решить, а можно алгоритмом Гаусса подсчитать.

Тут есть допущение, что i-ый пиксель будет аппроксимироваться t=i/n точкой на кривой. Вообще говоря, это не гарантированно, но в качестве некой грубой меры оптимальности подойдет. Может вообще отлично работать будет и так, я не знаю. Поэксперементируйте. Но еще можно потом честно искать ближайшую точку на кривой к заданному пикселю как оптимум полинома 6-ей степени от t, когда все опорные точки кривой фиксированы. Тут надо брать производную, находить ее нули и среди них брать лучшее t. Чтобы найти нули полинома 5-ой степени можно рекурсивно брать производную, находить нули полинома меньшей степени, и потом на каждом монотонном отрезке искать пересечение с OX бинарным поиском. Или использовать метод Ньютона. Это давно решенная задача - должно быть куча готовых решений.

Когда вы так научились считать расстояние от кучки пикселей до кривой Безье, можно локально градиентным спуском по 4-м координатам x1, x2, y1, y2 улучшать эту правильную метрику с оптимума полученного грубой метрикой.

Вот мы и умеем аппроксимировать кучку пикселей одной кривой. Заодно мы получаем метрику близости кривой к пикселям. Но надо сделать ее не зависящей от длины - поэтому складывайте квадраты расстояний и делите на количество пикселей.

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

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

n=5, m=1. первый шаг - поделить, осталось n=1, m=0. Второй шаг - проверить, заметить 0 и остановиться.

n=5,m=3, первый шаг - поделить. осталось n=3, m=2. Второй шаг - опять делим, остается m=2, n=1. Третий шаг - делим, остается n=1, m=0, четвернтый шаг - видим 0, остановились.

для n=m=5 ответ 1, возможно, потому что в алгоритме стоит проверка m==0 || m == n.

Это похоже на задачу set cover. Легких алгоритмов тут нет. Только полный перебор с отсечениями. Еще всякие методы отжига и эволюционные алгоритмы могут найти хорошее решение. Ну и, задачу можно переформулировать в виде integer linear programming и решать какой-то из существующих библиотек.

Если количество слов маленькое (типа 25-30), то можно решать динамическим программированием по маске покрытых слов.

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

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

Я предполагаю, что вам нужны только простые пути, без самопересечений по вершинам. Иначе путей может быть бесконечно много.

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

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

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

Что-то типа такого. Я не питонист, так что возможно с ошибками, но идея должна быть понятна.

def dfs(v, end, graph, path, visited):
  if v == end:
    print(path)
    return
  for u in graph.neighbours(v):
    if u not in visited:
      path.append(u);
      visited.add(u);
      dfs(u, end, graph, path, visited)
      path.pop();
      visited.remove(u);

// вызывать dfs(start, end, graph, [], set())

Это известная и сотню раз решенная задача. Гуглите "exponential backoff" или "Экспоненциальная выдержка".

Самое быстрое и простое - сортировка кучей.

Теоретически, можно любое search tree использовать, но оно будет медленее, потому что структуры сложнее.

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

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

Еще деревья часто используются в алгоритмах на строки. Есть такая структура - бор (trie) - позволяет эффективно хранить кучу строк и искать: есть ли такая строка в структуре. Более продвинутые алгоритмы типа Ахо-Корасика, Укконена тоже строят некоторое дерево с дополнительными фишками и позволяют делать крутые вещи, типа искать кучу шаблонов в тексте разом, или моментально находить самую часто встречающуюся подстроку задонного размера.

Куча (heap) используется для сортировки а так же реализации приоритетных очередей.

Далее, деревья в смысле графов тоже используются, например, в сети. Маршрутизаторы строят остовное дерево и раздают команды по его ребрам.

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

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

База - если l..r - пустая строка - ответ 0.
Иначе надо рассматривать варианты, что будет с последним символом. Если в конце стоит открывающая скобка, то ее надо удалить - других вариантов нет: F(l,r) = 1+F(l,r-1).

Если же там закрывающая скобка, то есть 2 варинта: или этот символ удаляем, или берем в ответ. В первом варианте ответ такой-же, как выше. Во втором - надо перебрать, а какой же символ в строке будет открывающей скобкой для данной. Пусть это символ i (там должна стоять открывающая скобка того же типа). Тогда ответ F(l,i-1)+F(i+1,r-1) - ведь части перед парой скобок и внутри их должны тоже быть правильными последовательностями.
Из всех вариантов надо выбрать минимальный - это и будет ответ для текущего состояния.

Если хотите восстанвливать саму последовательность, то надо при сохранении минимума еще и сохранять в отдельном двумерном массиве - какой именно из вариантов был выбран (дропнуть последний символ, или какой символ взять ему в пару).

Ответ к задаче - F(1,n) - для всей строки.

Это решение потребляет O(n^2) памяти и занимает O(n^3) времени.