Комментарии 7
Я как-то ковырял латинские квадраты, было интересно, можно ли получить по индексу латинский квадрат из множества латинских квадратов? Естественно без перебора и детерменировано. Там же моячила вторая задача, выходящая из первой, можно ли получить по индексу граф из множества всех графов? Я не особо разбираюсь, что есть интересного по этой теме?
С графами проще, если соответствующим образом поставить задачу: проиндексировать все графы на данном множестве из N вершин. Между двумя вершинами либо есть ребро, либо нет, это бит информации. Соответственно, двоичными словами из N(N-1)/2 бит можно проиндексировать все графы на N вершинах. Если же мы хотим проиндексировать не все графы, а только с какими-то дополнительными свойствами, это каждый раз новая задача, иногда простая, иногда сложная, иногда, как в случае с латинскими квадратами, ничего лучше чем перебор не придумано.
С этим действительно связана одна интересная решенная задача. Если бы мы умели эффективно индексировать латинские квадраты, мы также легко бы научились выдавать (псевдо)случайные латинские квадраты: достаточно сгенерировать (псевдо)случайным образом индекс, и выдать соответствующий ему квадрат. Хотя эффективной индексации латинских квадратов на сегодня нет и не предвидится (даже точное их число известно только до порядка 11), случайные латинские квадраты научились генерировать другим способом [ Jacobson, Matthews, Generating uniformly distributed random latin squares, 1996, https://doi.org/10.1002/(SICI)1520-6610(1996)4:6<405::AID-JCD3>3.0.CO;2-J ]. Я сам не разбирался, насколько там равномерное распределение, но вроде криптографов вполне устраивает (случайные латинские квадраты могут использоваться для определенного вида шифров).
С графами проще, если соответствующим образом поставить задачу: проиндексировать все графы на данном множестве из N вершин. Между двумя вершинами либо есть ребро, либо нет, это бит информации. Соответственно, двоичными словами из N(N-1)/2 бит можно проиндексировать все графы на N вершинах.
Функция имеет только один параметр, индекс графа в множестве графов. N вершин нет. Уточню что, графы могут быть мультиграфами (со свойством что не существует количество ребер выше количества вершин), изолированными вершинами. На N вершин решение простое, это да.
Формулы поиска количества вершин от индекса графа в множестве графов вроде не существует? Я когда ковырялся в этом, обнаружил что мы можем вычислять количество вершин, количество ребёр и вершин без ребёр, но перебором (кстати, (выводил без учета мультиграфов) количество всех построенных вариантов графов для n вершины, делённое на n-1 вершин описывает золотое сечение :) ).
В задачах нумерационного кодирования (это именно такой тип задач, где по индексу нужно найти объект) часто все сводится к тому или иному перебору, вопрос только в его сложности.
Я не совсем понял конкретную формулировку. Число ребер во всем графе не больше числа вершин? Это очень разреженный граф, средняя степень вершин не больше 2... Петли в мультиграфе разрешены или нет? Но в любом случае скорее всего да, простой формулы не существует. Даже если существует формула для числа графов числе вершин в виде многократной суммы, то для подсчета числа вершин по номеру нужно фактически вычислить эту формулу для каждого меньшего числа вершин и просуммировать.
Проверка графов на изоморфизм - это NP- полная задача. Проще проверять симметрии онносительно поворотов и отражений, коих для двумерного случая 8 штук.
Про сложностной статус задачи действительно полезно помнить, но даже NP-полнота это еще не приговор, и не всегда стоит её пугаться.
1. Если какой-то алгоритм долго работает на почти всех графах (я для примера буду алгоритмы на графах рассматривать, раз уж о них речь зашла), то это не значит, что он долго работает на графах, которые вы рассматриваете для данной конкретной задачи. Ваши графы могут быть иметь определенную структуру и быть очень непохожими на обычный случайный граф (это именно так при кодировании графами латинских квадратов). Сложностной статус рассматриваемой задачи для вашего конкретного подкласса графов может не иметь ничего общего со сложностью для всех графов. Например, задача о поиске максимальной клики NP-полна для всех графов, но для подкласса графов, являющихся объединением непересекающихся циклов, она элементарна.
2. Асимптотическое поведение сложности решения какой-то массовой задачи (например, проверка графов на изоморфность) мало говорит о том, насколько эффективно её решают известные алгоритмы. Какая-то задача может решаться на случайных графах до 1000 вершин, и иметь полиномиальный статус, а другая задача быть NP-полной, но решаться современными библиотеками для случайных графов до 10000 вершин. Да, когда компьютеры станут побыстрее, может вторая задача будет решаться всего лишь для графов до 10300, а первая "аж" до 2000 вершин, но какой нам от этого прок, если у нас похожий на случайный граф с 5000 вершинами?
Про, NP-полноту/неполноту задачи об изоморфизме графов история интересная, но к сожалению не раскрытая в русскоязычной статье Википедии https://ru.wikipedia.org/wiki/Изоморфизм_графов . Более подробно написано в англоязычной статье https://en.wikipedia.org/wiki/Graph_isomorphism - доказан превдо-полиномиальный алгоритм решения этой задачи (L.Babai, 2015-2017), но в виде отрецензированной статьи результат еще не опубликован.
Действительно, для каждого отдельного класса объектов можно пытаться придумывать что-то своё, иногда получается лучше, если удается учесть какие-то особенности (да, например какие-то симметрии). Моей целью было продемонстрировать более общий подход.
Но даже с латинскими квадратами, чтобы придумать что-то эффективное без использования изоморфизма графов, нужно разрабатывать гораздо более эффективный алгоритм. Использование симметрий, о которых вы говорите, может быть первый шаг, но одного его недостаточно. Число всех латинских квадратов 7 на 7 - 61479419904000, если мы сгруппируем их в группы по 8 (иногда меньше), получающиеся друг из друга поворотами и отражениями, таких групп будет все равно тринадцатизначное число, слишком долго перебирать. Если же в качестве "симметрий" использовать изотопии (перестановки столбцов, перестановки строк и перестановки символов), то групп всего 564. Конечно, мы можем сравнивать два квадрата на изотопность просто тупо перебирая все перестановки строк, столбцов, и символов. Но таких преобразований 7! (факториал) на 7! на 7! -- это тот самый экспоненциальный перебор, которого мы хотели избежать, говоря о NP-полноте. Поэтому и предлагается представить в виде графов и свести к задаче, над которой уже десятки лет работают лучшие умы человечества :) Про NP-полноту вы интересную тему затронули, напишу отдельный коммент.
Классификация комбинаторных объектов на примере латинских квадратов