Comments 12
Что у вас там на гарфиках по оси OX нарисовано? От 0 до 100. А в тексте говорится про графы из ~10 вершин.
Спасибо за замечание.
Добавил уточнение в статью:
На графиках по оси OX отложен индекс элемента в упорядоченном списке результатов тестов, по оси OY - затраченное на соответствующий тест время в микросекундах.
В таком случае я бы посоветовал box plot или scatter plot (в 2 столбца). График, где ось OX не имеет смысла — только путает читателей. Особенно, в контексте времени работы программ: обычно запускают программу на многих случайных тестах разных размеров, считают среднее для каждого размера и рисуют график, где OY — вермя работы, а OX — размер теста.
И еще, я бы постеснялся называть статью "быстрый поиск". Все, что вы сделали — это реализовали полный перебор с минимальными отсечениями. Оно выглядит впечатляюще на фоне вашей наивной и очень неэффективной реализации, где постоянно выделяются матрицы.
Есть действительно быстрые алгоритмы: https://citeseerx.ist.psu.edu/doc/10.1.1.101.5342
Представленного мною алгоритма я в интернете не нашёл, поэтому посчитал полезным его опубликовать.
Вопрос не в том, выполняется перебор с отсечениями или нет, а в том, какая именно часть отсекается, и какова вычислительная цена этого отсечения. Например, бинарный поиск тоже отсекает часть вариантов. Но т.к. число этих вариантов значительно, то такой поиск считается быстрым. Если Вы предложите реализацию на c++ или java алгоритма, который Вы прислали, с удовольствием сравню.
Насколько я понял, он является развитием алгоритма Ульмана, с ним и сравнивается. В нём составляется функция осуществимости feasibility function для упрощения перебора. По сути, она точно так же, как и мой алгоритм, отсекает неподходящие варианты, но с помощью предсоставленных подграфов (ветвей).
Моему алгоритму не нужно составлять такие подграфы, их аналог - это строка и столбец подматрицы. Мой код использует в качестве функции осуществимости в худшем случаем 2k проверок на равенство целочисленных значений по промежуточной перестановке, где k - шаг рекуррентного метода. Возможно, алгоритмы с предварительным обходом работают быстрее, но пока что я не вижу этому объективных обоснований.
какая именно часть отсекается, и какова вычислительная цена этого отсечения.
В худшем случае — никакая. Например, если большой граф — клика, а искомый — клика из первых n-1 вершин, а последняя — изолированная. Тогда ваше отсечение сработает только на последней вершине.
какова вычислительная цена этого отсечения.
Еще интересна ментальная сложность идеи. "Не перебирать дальше, если уже нашли противоречие" — это настолько тривиальная идея, что у нее даже особого названия нет. Наверно, поэтому вы не смогли найти нигде описание вашего алгоритма. Хотя оно упоминается даже на википедии. Там, правда, нет ссылки в русской версии, но в английской — все есть. Вот она. Алгоритму почти 50 лет. Детальное описание алгоритма есть, например, вот тут (там нерекурсивная версия, как водится во всех таких старых статьях).
По сути, она точно так же, как и мой алгоритм, отсекает неподходящие варианты, но с помощью предсоставленных подграфов (ветвей).
По сути, почти все алгоритмы поиска изоморфизмов так и работают. Задача-то NP-полная (кстати, еще один минус статье — писать про алгоритм решения задачи не упоминуть даже вот этот весьма важный факт).
Вот только ваш "быстрый" алгоритм не делает ничего, кроме тривиального отсечения. Когда как вот эти вот все алгоритмы какие-то структуры данных городят, что-то там еще придумывают. Вот это вот что-то — может и потянуть на статью.
Если Вы предложите реализацию на c++ или java алгоритма, который Вы прислали, с удовольствием сравню.
Реализацию можно посмотреть, например, в boost (ссылается на статью выше).
"Вот это вот всё" тянет на статью в научном журнале, а не на хабре.
Цель статьи была не перевернуть мир, а показать, как пройти от тривиального алгоритма до более-менее быстрого.
Мне показалось, что в итоге мой алгоритм будет сравним по скорости, если Вы утверждаете, что это не так, то такое сравнение не было целью статьи. Сравнение времени работы было дано специально для того, чтобы показать, как сумма приёмов сократит время вычислений.
Вы правы. Если бы вы что-то подобное написали — с этим можно было бы и статью в журнале написать. А так статья для хабра подходит, но слишком громкий заголовок. Если бы в статье не было слова "быстрый", а в тексте было "вот такая простая идея дает заметный прирост в скорости", то она, на мой взгляд, была бы более точна.
del. ошибся веткой.
Жутко страшная тема для недостаточно разносторонне подкованного в математиках человека с коротким запасом усидчивости (я), но также жутко хорошее объяснение, как к ней (теме, бишь, освещаемой) подступиться!
Отмечу: я совсем зелёный человек в погромистике, но из любопытства захотела некоторое время назад воспроизвести работу путеводилки Яндекс.метро: хватило знания додуматься, что схема линий — в сущности граф, но дальше этого лыжи не ехали. Похоже, надо подступаться к обожематрицам…
Спасибо за вдохновение и понятную наводку к практической реализации!
Быстрый поиск изоморфных подграфов