www>Эквивалентность. www>Матрицы в данном случае в точности эквивалентны двусвязным графам. А Вас интересует алгоритм проверки двух графов на планарность (т.е. именно то,что 2 графа эквивалентны друг другу с точностью до перестановки). www>По-моему задача планарности NP-полная. Перебор пишется довольно просто, а дальше можно придумывать разного рода отсечения и оптимизации. Например, простейшая эвристика с неэквивалентностью суммы элементов каждой из матриц. Более того, эта эвристика с успехом может быть применена для отсечения inner cases — как только вы сделали перестановку вы как бы начинаете работать с матрицей размерности меньшей на единицу, пока не вернетесь и сделаете другую перестановку для заданной вершины графа (~строки столбца матрицы).
Вероятно, вы имели в виду изоморфность? Планарность — это все таки совсем другое понятие
The Creator had a lot of remarkably good ideas when he put the world together, but making it understandable hadn't been one of them. (c) Terry Pratchett
Есть матрицы Y размерности NxN, элементы которой могут быть только двух типов, например 0 и 1.
Две или более матрицы считаются эквивалентными, если, переставляя любое количество строк и/или столбцов, их можно привести к одному и тому же виду. Например, для матрицы, в которой есть только один единичный элемент, расположенный в ячейке Y[1][1], все остальные матрицы с только одним единичным элементом, где бы он не находился, являются эквивалентными.
Интересует алгоритм получения всех не эквивалентных матриц при заданных размерности матрицы N и числе M единичных элементов, 0<= M <= (N*N).
В качестве альтернативы интересует алгоритм проверки, что 2 заданные матрицы являются эквивалентными.
Здравствуйте, Геннадий Майко, Вы писали:
ГМ>Добрый день!
ГМ>Есть матрицы Y размерности NxN, элементы которой могут быть только двух типов, например 0 и 1.
ГМ>Две или более матрицы считаются эквивалентными, если, переставляя любое количество строк и/или столбцов, их можно привести к одному и тому же виду. Например, для матрицы, в которой есть только один единичный элемент, расположенный в ячейке Y[1][1], все остальные матрицы с только одним единичным элементом, где бы он не находился, являются эквивалентными.
ГМ>Интересует алгоритм получения всех не эквивалентных матриц при заданных размерности матрицы N и числе M единичных элементов, 0<= M <= (N*N).
ГМ>В качестве альтернативы интересует алгоритм проверки, что 2 заданные матрицы являются эквивалентными.
ГМ>Спасибо.
ГМ>С уважением, ГМ>Геннадий Майко.
Эквивалентность.
Матрицы в данном случае в точности эквивалентны двусвязным графам. А Вас интересует алгоритм проверки двух графов на планарность (т.е. именно то,что 2 графа эквивалентны друг другу с точностью до перестановки).
По-моему задача планарности NP-полная. Перебор пишется довольно просто, а дальше можно придумывать разного рода отсечения и оптимизации. Например, простейшая эвристика с неэквивалентностью суммы элементов каждой из матриц. Более того, эта эвристика с успехом может быть применена для отсечения inner cases — как только вы сделали перестановку вы как бы начинаете работать с матрицей размерности меньшей на единицу, пока не вернетесь и сделаете другую перестановку для заданной вершины графа (~строки столбца матрицы).
Здравствуйте, www,
ГМ>>Есть матрицы Y размерности NxN, элементы которой могут быть только двух типов, например 0 и 1.
ГМ>>Две или более матрицы считаются эквивалентными, если, переставляя любое количество строк и/или столбцов, их можно привести к одному и тому же виду. Например, для матрицы, в которой есть только один единичный элемент, расположенный в ячейке Y[1][1], все остальные матрицы с только одним единичным элементом, где бы он не находился, являются эквивалентными.
ГМ>>Интересует алгоритм получения всех не эквивалентных матриц при заданных размерности матрицы N и числе M единичных элементов, 0<= M <= (N*N).
ГМ>>В качестве альтернативы интересует алгоритм проверки, что 2 заданные матрицы являются эквивалентными.
www>Эквивалентность. www>Матрицы в данном случае в точности эквивалентны двусвязным графам. А Вас интересует алгоритм проверки двух графов на планарность (т.е. именно то,что 2 графа эквивалентны друг другу с точностью до перестановки).
--
В принципе я понимаю, что можно использовать и графы для решения этой проблемы, но мне лично удобнее работать с матрицами и с точки зрения реализации этого алгоритма на С++, и с точки зрения представления окончательного решения.
www>По-моему задача планарности NP-полная. Перебор пишется довольно просто, а дальше можно придумывать разного рода отсечения и оптимизации. Например, простейшая эвристика с неэквивалентностью суммы элементов каждой из матриц. Более того, эта эвристика с успехом может быть применена для отсечения inner cases — как только вы сделали перестановку вы как бы начинаете работать с матрицей размерности меньшей на единицу, пока не вернетесь и сделаете другую перестановку для заданной вершины графа (~строки столбца матрицы).
--
Да, я тоже пока склоняюсь к такому варианту. Эвристик отсечения неэквивалентных схем я уже придумал не одну, да и рекурсию здесь хорошо использовать.
Хотелось бы узнать, не знает ли кто-нибудь явного описания похожих аглоритмов в каких-то литературных источниках.
www>Эквивалентность. www>Матрицы в данном случае в точности эквивалентны двусвязным графам. А Вас интересует алгоритм проверки двух графов на планарность (т.е. именно то,что 2 графа эквивалентны друг другу с точностью до перестановки). www>По-моему задача планарности NP-полная. Перебор пишется довольно просто, а дальше можно придумывать разного рода отсечения и оптимизации. Например, простейшая эвристика с неэквивалентностью суммы элементов каждой из матриц. Более того, эта эвристика с успехом может быть применена для отсечения inner cases — как только вы сделали перестановку вы как бы начинаете работать с матрицей размерности меньшей на единицу, пока не вернетесь и сделаете другую перестановку для заданной вершины графа (~строки столбца матрицы).
Во-первых, как уже отметили, наверное, вы имеете ввиду изоморфизм графов, а не планарность. Во-вторых, непонятно откуда взялась двусвязность графов. В-третьих эти задачи совсем не эквивалентны, это можно проверить на простейших случаях.