Где найти параллельный алгоритм нахождения максимального паросочетания в графе?

ddd329, А вот это - хорошая статья.

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

Заодно там уделяется внимание, собственно, паралелизации и в описании алгоритма указано, какие операции надо делать с локами/атомиками. Думаю, это именно то, что вы ищете.

Где найти параллельный алгоритм нахождения максимального паросочетания в графе?

Весьма странный документ. Во первых, там утверждается, что с обходом в ширину алгоритм Куна получает n*2.5 сложность, но это уже будет алгоритм Хопкрафта-Карпа.

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

Еще там какой-то бред про итоговую линейную сложность(?!).

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

Почему JS решил задачу на рекурсию гораздо быстрее Python/Lua?

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

Надо просто завести массив на миллион элементов и запоминать в нем подсчитанные значения функции.

Вроде:

function getCollatz(number, iterations=1){
  if(res[number] > 0) return res[number];
  ...
  restult = GetCollatz(...);
  ...
  res[number] = result;
  return result;
}

Какой генератор алгоритмов на основе входных и выходных данных вы сейчас используете?

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

Но, вообще, смысл может быть в криптографии. Большие простые числа там нужны, а если они близки к степени 2, то можно быстро делить/брать остатки, что тоже очень часто в криптографии делается. Так что генерировать их весьма полезно. Правда, редко надо найти именно 113355-ое простое число мерсенна. Обычно достаточно найти любое простое число примерно заданного размера. А это гораздо проще задача.

Какой генератор алгоритмов на основе входных и выходных данных вы сейчас используете?

xmoonlight, В контексте про Ваше утверждение "Если задачу может решить человек - машина это может делать 100%", то тут не до гита и "мне в руки". Создание сильного искусственного интеллекта - это такой шаг вперед для человечества, что никто это скрывать не стал бы. Хозяева такого открытия легко бы поработили весь мир и/или получили бы бессмертную славу.

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

Более того, ваша задача не может иметь алгоритмического решения. Это математический факт. Некоторые задачи вообще нельзя запрограммировать (Как, например, halting problem, уже приведенная выше). Другие - человечеству пока не поддались. Например, входные данные {1,2,3,4,5,6,7}, выходные {3,7,31,127,8191,131071,524287}. Даже если создатель программы рассмотрел частный случай "простые числа Мерсенна", Ни формулы, ни даже применимого на практике алгоритма вычисления их человечеству неизвестно. Полного перебора на всех компьютерах мира для входного числа 10000000 Вы будете ждать до тепловой смерти вселенной.

Какой генератор алгоритмов на основе входных и выходных данных вы сейчас используете?

xmoonlight, Вот когда сильный искусственный интеллект будет реализован, тогда вы будете правы. Пока же рано так категорично утверждать.

Какой генератор алгоритмов на основе входных и выходных данных вы сейчас используете?

xmoonlight, Ё-маё. Как же жалко потраченного на вас и ваше трололо время. Жаль, что тут нельзя минусы ставить. Вам же советую, наоборот, побольше умных книжек читать. Может мозги себе вправите. Прощайте.

Какой генератор алгоритмов на основе входных и выходных данных вы сейчас используете?

xmoonlight, Анализ вам вкратце: "хорошего" решения вашей задачи не существует (Если вы хотите кратчайший или имеющий практический смысл алгоритм). Хотя бы потому, что можно в виде входных данных закодировать программы, а в виде выходных хотеть ответ - завершается ли эта программа. Алгоритма реализующего это не существует. И тем более нет алгоритма, который бы его нашел.

А плохих решений вашей задачи море - можно, например, выдавать известные ответы на известные входы, а на все другие входы - выдавать 42. Даже интерполяций не надо.

Как реализовать метод принадлежности точки многоугольнику?

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

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

Правильный ли алгоритм?

Очень похоже на переполнение. Попробуйте тест, где одно устройство и миллион задач по 100 каждая.

Как найти кратчайший маршрут в графе с дополнительными требованиями к маршруту?

Mercury13, вообще не много, учитывая что алгоритм работает за линию от количества вершин+ребер в этом новом графе.

keddad, Логика построения - рассматриваем все возможные варианты. Вот вы можете как-то покататься и оказаться в вершине 42 с 1 "литра" топлива. А можете как-то по другому покататься и приехать туда с 100 литров топлива. Вот это 2 разные вершины в новом графе. Они все различные от 0 до n. У вас все состояние описывается двумя величинами: где вы и сколько у вас топлива сейчас топлива. Мы все это пространство состояний описываем с помощью этого искусственного графа. Ведь совершенно неважно, как вы раньше ездили, ведь если вы в вершине 42 с 10 литрами топлива, то вы дальше можете делать все то же самое. Поэтому и получается n * "количество вершин" вершин в новом графе. Далее мы в этом пространстве состояний ищем минимальный путь.

Как найти кратчайший маршрут в графе с дополнительными требованиями к маршруту?

Граф большой? Насколько длинные ребра и большой бак можно заправлять (насколько большое n)?

Как объединить в диаграмме воронова сайты(многоугольники) в группы?

Даниил,
Размеры областей по площади или по количеству ячеек (сайтов) заданы?

У вас ячейки (сайты) выделены уже? В смысле есть граф соседей для ячеек? Вроде вершина-область и от нее ребра к соседним областям, с которыми данная делит границу.

Как проверить список на уникальность основания степени?

А что делать с числами, которые не степени?

Допустим, [6, 2] - это true? Правильно понимаю, что надо вернуть False, только если одно число из списка в какой-то рациональной степени будет равно другому числу?

Как проверить список на уникальность основания степени?

gcd() c простым числом!? Почему бы просто не проверить делимость через num % pr == 0?

Как найти последную ненулевую цифру K!?

Алексей Тен, Зависит от всех последних ненулевых цифр в (k-1)! Потому что ...15*2 =...30, а ...25*2=50

Правильно ли я понял алгоритм быстрой сортировки?

res2001, Вы, наверно, неправильно прочитали что-то.

третью не рассматриваю, т.к. она не верна

Это школьная математика, наверно, 9 класс максимум:
L+(R-L)/2 = 2L/2+(R-L)/2 = (2L+R-L)/2 = (L+R)/2

Как раз чаще всего третью форму и используют - когда вам надо взять середину интервала, вы просто берете среднее арифметическое его концов. Это кажется очевидным.

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

Как сгенерировать множество с покрытием максимального числа результатов?

В этом же предложении: "покрывала все возможные комбинации нулов и не нулов"

Как сгенерировать множество с покрытием максимального числа результатов?

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

Как сгенерировать множество с покрытием максимального числа результатов?

Тут покрытие различных вариантов будет наихудшим - только n+1 вариантов в лучшем случае.