2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Перебор графов
Сообщение05.10.2011, 19:39 
Какие существуют алгоритмы перебора графов заданной структуры? Например, графов с заданным числом вершин (хотя тут вроде понятно) или ребер. Где можно про них почитать? Какие есть параллельные алгоритмы?
Подскажите.

 
 
 
 Re: Перебор графов
Сообщение05.10.2011, 20:12 
cyb12 в сообщении #489821 писал(а):
Какие существуют алгоритмы перебора графов заданной структуры? Например, графов с заданным числом вершин (хотя тут вроде понятно) или ребер. Где можно про них почитать? Какие есть параллельные алгоритмы?
Подскажите.

Генетические алгоритмы. Тут http://is.ifmo.ru/download/ant_ga_min_number_of_state.pdf есть пример построения графа переходов. Посмотрите другие источники тоже http://is.ifmo.ru/genalg/. Такой способ можно сделать параллельным.

А так сложно еще что-то предложить. Для чего вам нужно перебирать все возможные графы? Граф должен решать какую-то задачу? Или нужно выдать все виды структур? Например, с помощью ГА можно решить задачу коммивояжёра.

 
 
 
 Re: Перебор графов
Сообщение06.10.2011, 00:49 
rederblack в сообщении #489846 писал(а):
Какие существуют алгоритмы перебора графов заданной структуры? Например, графов с заданным числом вершин (хотя тут вроде понятно) или ребер. Где можно про них почитать?
Погуглите "перечисление графов" -- может быть, найдете что-нибудь полезное.

(Оффтоп)

rederblack в сообщении #489846 писал(а):
Например, с помощью ГА можно решить задачу коммивояжёра.
Все зависит от того, какой смысл Вы вкладываете в слово "решить". ГА не позволяют в общем случае найти оптимальный маршрут, но довольно часто с их помощью можно за разумное время найти маршрут со стоимостью, близкой к минимальной.

 
 
 
 Re: Перебор графов
Сообщение06.10.2011, 15:52 
Аватара пользователя
Генерация графов широко применяется во многих прикладных областях, например, в математической (компьютерной) химии. Сошлюсь на свою статью: М.Трофимов, Е.Смоленский, Изв.РАН, Сер.хим., 2005, N 9, 2166-2176. Там в приложениях приведен ряд алгоритмов для генерации и даны ссылки на их источники (например, много полезных алгоритмов было предложено Фараджевым). В принципе, сгенерировать все возможные графы, казалось бы, не трудно: взять очень большое число, уменьшать его на единицу, представлять результат в двоичном коде, цифрами из которого заполнять матрицу смежности соответствующего размера. Однако при такой генерации будут повторятся изоморфные графы. В статье была цель испытать новый алгоритм изоморфизма, поэтому повторы удалялись с помощью этого алгоритма, но бывают генераторы, которые генерируют поток графов с заданными свойствами. Кроме того, для некоторых задач совсем не нужно генерировать графы, а нужно только сосчитать, сколько будет каких-то определенных графов. Тут также есть полезные подходы.

Hope it helps!

 
 
 
 Re: Перебор графов
Сообщение06.10.2011, 23:48 
rederblack в сообщении #489846 писал(а):
Граф должен решать какую-то задачу?

Нужна именно структура графа. Тут немного странно.

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

(Оффтоп)

Там, кстати, столько всего найдено, вплоть до перечисления кактусов



Меня интересуют именно параллельные алгоритмы. Организация параллельного перебора каких-либо объектов сама по себе может оказаться весьма сложной. Но что происходит в случае графов?

Например, мне нужно перебрать все графы (не обязательно исключать все изоморфные) на $n$ вершинах. Конечно, их много. Даже очень. Пусть у меня есть $p$ процессоров. Если делать совсем "в лоб", то приходится фиксировать некоторые подграфы (не более чем $p$ способами) и давать каждому процессору перебирать графы со своим подграфом.
Можно ли проще?

 
 
 
 Re: Перебор графов
Сообщение07.10.2011, 00:52 
cyb12 в сообщении #490262 писал(а):
Если делать совсем "в лоб", то приходится фиксировать некоторые подграфы (не более чем $p$ способами) и давать каждому процессору перебирать графы со своим подграфом.
Можно ли проще?
Не надо привязываться к числу физических ядер. Даже в случае, когда количество параллельных веток алгоритма на два порядка больше количества процессоров, автоматическая диспетчеризация параллельных задач выполняется достаточно эффективно (в теме Язык программирования для математика проверяли на Erlang/C++/C#).

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group