ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Тяпничный изоморфизм на 600 ядрах
17 сообщений из 17, страница 1 из 1
Тяпничный изоморфизм на 600 ядрах
    #39195889
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Коллеги доброй ночи!

В продолжение темы 18943562 .

Меня заинтересовал вопрос принципиального решения задачи изоморфизма на 600 ядрах.
Но для начала его неплохо-бы решить на 2х или 4х ядрах основного CPU.

Краткий ликбез.

 
Напомню суть. Граф это такая штука в которой есть вершины (V), vertices, и ребра (E), edges.
Вершины - сами по себе. А рёбра их связывают. (Ребра бывают ориентированные (стрелочка)
которые смотрят в одну сторону но мы такие трогать не будем. Нас будут интересовать
только неориентированные).

Пример:


У графов есть характеристики мощностей вершин. Есть остов . Клика и многое другое.
Есть формулы, связывающие предельные объемы вершин и ребер. Есть понятие смежность
когда одна вершина смежна к другой. И инцедентность - это связь вершина - со списком ребер.

Считается что граф обобщает достижения дискретной математики и позволяет решать (почти) любые
задачки связанные с топологиями. Задачки коммивояжера. Поиск путей в лабиринтах. Разрезы. Потоки.
Кратчайшие пути. Системотехника. Медицина. Раскрска гео-карты, моделирование
сети TCP/IP и многое и многое другое полезное для народного хозяйства.

Деревья и связные списки также - суть частные случаи графов.

Один граф изоморфен по отношению к другому если их можно наложить
один на другой с сохранением топологии (вершина к вершие, ребро
к ребру) без учёта нумераций или меток вершин и ребер.

На этом пожалуй все. Я слил то что знал и помнил из курса дискретки.
Остальное читайте в вики.

Собственно постановка

Дано. Два неориентированных графа в следующем виде (матрица смежностей).
Первый из них - соответствует картинке.

Input:
 
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
8
00001110
00001101
00001011
00000111
11100000
11010000
10110000
01110000

8
01010011
10100100
01010000
10101010
00010100
00001010
01000101
10010000
10000100



Необходимо установить, являются ли они изоморфными.

Output:
Код: sql
1.
false



Несмотря ка кажущуюся простоту - задачка имеет фейерический оверхед по вычислениям.
Про асимпт. сложность я пока не буду говорить. Это вопрос неоднозначный. Лучше читайте сами.

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

Ограничения.

В данном топике нас с вами не интересует копи-паста готового решения.
Нас интересует проверка принципиальной возможности
ускорить расчёт изоморфизма в 600 раз используя железо (CPU/GPU)
Будут или не будут блокировки. Можно или не можно сделать
shared nothing e.t.c. Нужно или нет диспетчеризировать процессы.

Приветствуется:

С/C++/Assembler/Rust/D
Особый респект поцанам которые осилят: CUDA, OpenNP или построят вычислительную
сетку из 600 рабочих станций

Не ждите от меня моего решения. У меня его на данный момент к сожалению нет.

Слуга ваш покорный
mayton

Go!Go!
...
Рейтинг: 0 / 0
19.03.2016, 02:51
| Ответить | Цитировать | Написать  
Тяпничный изоморфизм на 600 ядрах
    #39195940
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Граф это матрица - нужно всего лишь перебрать все перестановки строчек и столбцов в ней.

Вычислительная сложность - n!^2.

Поскольку основная матрица только для чтения - параллелится легко. Каждая перестановка в отдельном потоке генерится своим потоком в свою матрицу.

Все. Задача имеет решение, дальше неинтересно =)
...
Рейтинг: 0 / 0
19.03.2016, 10:30
| Ответить | Цитировать | Написать  
Тяпничный изоморфизм на 600 ядрах
    #39195979
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Ну и способ сократить количество перестановок - нам же известно количество связей каждой точки.

Соответственно, перебирать надо точки с одинаковым числом связей.
...
Рейтинг: 0 / 0
19.03.2016, 12:53
| Ответить | Цитировать | Написать  
Тяпничный изоморфизм на 600 ядрах
    #39195985
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SiemarglПоскольку основная матрица только для чтения - параллелится легко. Каждая перестановка в отдельном потоке генерится своим потоком в свою матрицу.
Давай я внесу еще одну поправку. Граф будет не с 8 вершинами как я нарисовал а с большим количеством.

И непонятно также с какой перестановки начнёт каждый поток. И непонятно какое явление или процесс
ему эту перестановку выдаст так чтобы была уникальность.
...
Рейтинг: 0 / 0
19.03.2016, 13:11
| Ответить | Цитировать | Написать  
Тяпничный изоморфизм на 600 ядрах
    #39195989
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
mayton,

Ну факториальные алгоритмы очень легко параллелить.

Пусть n-й проц занимается перестановками, в который n-й элемент на 1м месте. Это - идея, а дальше разбивайте сами )
...
Рейтинг: 0 / 0
19.03.2016, 13:20
| Ответить | Цитировать | Написать  
Тяпничный изоморфизм на 600 ядрах
    #39195992
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Siemarglmayton,

Ну факториальные алгоритмы очень легко параллелить.

Пусть n-й проц занимается перестановками, в который n-й элемент на 1м месте. Это - идея, а дальше разбивайте сами )
Не... Зяма. Стоп. Ты набижал. Вбросил дескыть тут нефиг делать.
А я вот не понимаю кто (какой процесс) будет генерить
или диспетчеризировать работы для наших процессов
workers и как.
...
Рейтинг: 0 / 0
19.03.2016, 13:35
| Ответить | Цитировать | Написать  
Тяпничный изоморфизм на 600 ядрах
    #39195998
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
Кто-то сомневается, что задача NP-полная?
...
Рейтинг: 0 / 0
19.03.2016, 13:51
| Ответить | Цитировать | Написать  
Тяпничный изоморфизм на 600 ядрах
    #39195999
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
mayton,

Так тут действительно нефиг делать.

На старте поделил на куски - и стартовал 600 процессов.
Если какой либо процесс выставил 1 в глобальном флаге найден_изоморфизм - все, приехали.

Никакой конкуренции, никакой диспетчеризации.
...
Рейтинг: 0 / 0
19.03.2016, 13:51
| Ответить | Цитировать | Написать  
Тяпничный изоморфизм на 600 ядрах
    #39196088
Иммануил Кант
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иммануил Кант
Участник
ИзопропилКто-то сомневается, что задача NP-полная?

у этой задачи могут быть весьма частные и сильно отличные по эффективности случаи. матрица, например, может иметь какие-то внутренние симметрии
...
Рейтинг: 0 / 0
19.03.2016, 17:15
| Ответить | Цитировать | Написать  
Тяпничный изоморфизм на 600 ядрах
    #39196246
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SiemarglНу и способ сократить количество перестановок - нам же известно количество связей каждой точки.

Соответственно, перебирать надо точки с одинаковым числом связей.
Отлично давайте перебирать точки с одинаковым числом связей.

Для графа с N вершинами мы не будем использовать permutations всех вершин т.к. уже для 21 вершины
(21 факториал) мы получаем число перестановок больше чем максимальное целое для int64.

Скорее всего нам придется заведомо отбрасывать ветви поиска которые не совпадают. И сразу
переходить к поискам.

Грубо говоря.

1. Если количество вершин (N1) графа G1 не равно количеству вершин N2 то ответ - не изоморфны.
2. Если мощности вершин G1 не совпадают с G2 (их надо отсортировать для сравнения) то - не изоморфны.
3. Самое интересное. Гистограммы мощностей вершин совпали. Надо доказать изоморфизм, переставляя
вершины в группах. (Это возможно грубо и тоже похоже на брутфорс).
...
Рейтинг: 0 / 0
19.03.2016, 23:39
| Ответить | Цитировать | Написать  
Тяпничный изоморфизм на 600 ядрах
    #39196690
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Марк, ну я тут-же вспомнил Кнута, где в одном из упражнений он предлагает доказать теорему Ферма, ни слова не говоря о том что это и есть та самая теорема. При это сложность задачи ставит равно 45, а не максимально возможную 50.
Задача ваша, если не ошибаюсь, принадлежит NP полному классу задач. Тут бы алгоритм приличный найти, а уже потом об оптимизации думать. А вы тут так интересно пишите

maytonПро асимпт. сложность я пока не буду говорить. Это вопрос неоднозначный. Лучше читайте сами.

Конечно не будете :D Ну вы весельчак :D


А вообще, 600 ядер, в общем случае и как всем известно, не даст ускорение в 600 раз (не помню как выглядит формула расчёта скорости, но там точно не линейная зависимость, даже если все функции входящие в состав программы реентерабельны).
...
Рейтинг: 0 / 0
21.03.2016, 01:59
| Ответить | Цитировать | Написать  
Тяпничный изоморфизм на 600 ядрах
    #39196698
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
В смежном топике Кудрявцев пишет
Да где там рекурсия?

IMHO Большинство задач сводится к многократному поиску кратчайшего пути. Зачем вешать блокировки на вершинах и ребрах - мне вообще не понятно. Если граф в процессе расчета не меняет свою топологию, отдельные "ветки" можно запускать на каком угодно кол-ве процессоров .
Я сходу согласился. Но не представляю себе каким образом мы будем вычислять "те самые отдельные ветки".
Причем не просто вычислять а вычислять эффективно.

Мне это непонятно.

А по поводу алгоритма.... ну это имеет значение, но мне нужна была симуляция нагрузки.

А если кто готов принять математический challenge - то welcome. Я не буду возражать против
параллельных копаний в дискретную математику.
...
Рейтинг: 0 / 0
21.03.2016, 02:41
| Ответить | Цитировать | Написать  
Тяпничный изоморфизм на 600 ядрах
    #39197566
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
математический challenge это хорошо, но дело в том что некоторые учёные бьются над данной проблемой 10 лет.
Если нам интересно проверить утверждение Кудрявцева ( а кто это такой кстати ?), то вероятно лучше использовать другие алгоритмы на графах, асимптотика которых заранее известна. Не так давно читал про формирование некой непрерывной последовательности всех возможных комбинаций алгоритма, при это постфикс текущего элемента последовательности, является префиксом следующего. Вроде бы асимптотика построения такого графа известна, но не могу вспомнить как называется алгоритм. Может быть кто-нибудь подскажет, или предложит другой алгоритм для тестирования
...
Рейтинг: 0 / 0
22.03.2016, 01:50
| Ответить | Цитировать | Написать  
Тяпничный изоморфизм на 600 ядрах
    #39197567
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
не комбинаций алгоритма, а правильно будет "всех возможных перестановок алфавита"
...
Рейтинг: 0 / 0
22.03.2016, 01:51
| Ответить | Цитировать | Написать  
Тяпничный изоморфизм на 600 ядрах
    #39197572
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ты имеешь в виде Генератор перестановок ?
...
Рейтинг: 0 / 0
22.03.2016, 02:34
| Ответить | Цитировать | Написать  
Тяпничный изоморфизм на 600 ядрах
    #39197575
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Не просто генератор перестановок, и их формирование в таком порядке, чтобы постфикс текущего, был префиксом следующего. Это используется, например, для ускорения полного перебора в том случае когда начало ввода ключа не фиксируется
...
Рейтинг: 0 / 0
22.03.2016, 03:22
| Ответить | Цитировать | Написать  
Тяпничный изоморфизм на 600 ядрах
    #39197576
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Граф де Брёйна, если не ошибаюсь
...
Рейтинг: 0 / 0
22.03.2016, 03:24
| Ответить | Цитировать | Написать  
17 сообщений из 17, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Тяпничный изоморфизм на 600 ядрах
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&fpage=30&tid=1340766]:
 0ms
get settings:
 4ms
get forum list:
 10ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 31ms
get topic data:
 6ms
get forum data:
 1ms
get page messages:
 31ms
get tp. blocked users:
 1ms
others: 209ms
total:  297ms
созд. / загр.: 297ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]