Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
Nevors
0 / 0 / 0
Регистрация: 13.11.2016
Сообщений: 13
1

Поиск путей в графе

10.01.2017, 03:49. Просмотров 996. Ответов 18
Метки нет (Все метки)

Стоит задача найти все пути на графе. Так, чтобы не было таких путей, в которых множество вершин одинаковы. Жду любые предложения. Желательно с описанием алгоритма.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.01.2017, 03:49
Ответы с готовыми решениями:

поиск путей на графе
поиск путей на графе дан ориентированый граф из 2-50 вершин, где каждому существующему ребру...

Поиск нескольких кратчайших путей в графе
Добрый день всем! Такая казалось бы тривиальная задача для гуру программистов, но ничего толкового...

Поиск всех путей в графе, сумма значений которых меньше установленного числа
Здравствуйте. Есть граф, в вершинах которого числовые значения. Нужно найти все пути в графе, сума...

Экономное представление путей в графе
Есть приведенное бинарное дерево (изоморфные подграфы сливаются, в узла может стать несколько...

Поиск в графе
Здравствуйте, есть следующая задача: Дан массив A длины (n+1), содержащий натуральные числа от 1...

18
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,497
10.01.2017, 09:53 2
Граф неориентированный?

Не по теме:

Теперь понятно, для чего понадобилось хэширование массива.



Добавлено через 3 минуты
Алгоритм:
Берём все возможные комбинации вершин (выбор без перестановок) и для каждой определяем (поиском в глубину), существует ли путь, проходящий через все эти вершины и только через них (гамильтонов путь на подграфе).
0
Nevors
0 / 0 / 0
Регистрация: 13.11.2016
Сообщений: 13
10.01.2017, 15:02  [ТС] 3
Цитата Сообщение от Shamil1 Посмотреть сообщение
Граф неориентированный?
Граф неориентированный.

Добавлено через 7 минут
Цитата Сообщение от Shamil1 Посмотреть сообщение
Берём все возможные комбинации вершин (выбор без перестановок)
Не очень понял.Как бы вся эта затея с обходом для этого и задумана, чтобы найти все комбинации вершин.
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,497
11.01.2017, 08:38 4
Цитата Сообщение от Nevors Посмотреть сообщение
найти все комбинации вершин
Если у нас есть есть n вершин, то каждой комбинации вершин можно поставить в соответствие n-битное число, в котором установленные биты будут соответствовать выбранным вершинам.
0
Nevors
0 / 0 / 0
Регистрация: 13.11.2016
Сообщений: 13
11.01.2017, 13:08  [ТС] 5
Цитата Сообщение от Shamil1 Посмотреть сообщение
Если у нас есть есть n вершин, то каждой комбинации вершин можно поставить в соответствие n-битное число, в котором установленные биты будут соответствовать выбранным вершинам.
У меня была такая реализация, но она очень трудоемкая. В моей задаче производятся действия над значениями хранимыми в узлах,и каждый набор узлов в пути это объединение данных в узлах по определенным правилам. В таком случае, есть моменты при которых объединение узлов не даст заведомо результатов. Поэтому я решил построить граф и объединить только те узлы над которыми есть смысл проводить действия. Далее для того что бы не было повторяющихся наборов узлов я решил сохранять отсортированный путь как строку и пихать все в множество,чтобы при встрече пути который содержит такой же набор вершин я прекращал дальнейший проход по данному пути. Да это все работает но не так быстро как хотелось бы. Поэтому я написал сюда в надежде, что мне предложат наиболее эффективный способ.
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,497
11.01.2017, 13:49 6
Цитата Сообщение от Nevors Посмотреть сообщение
но она очень трудоемкая
Что значит "трудоемкая"?

Цитата Сообщение от Nevors Посмотреть сообщение
Поэтому я решил построить граф
Вероятно, лишний шаг.
0
Nevors
0 / 0 / 0
Регистрация: 13.11.2016
Сообщений: 13
11.01.2017, 13:59  [ТС] 7
Цитата Сообщение от Shamil1 Посмотреть сообщение
Что значит "трудоемкая"?
ЭМ...не правильно прочитал ваше сообщение извиняюсь.

Добавлено через 5 минут
Цитата Сообщение от Shamil1 Посмотреть сообщение
n-битное число
Не очень понимаю как это хранить если большое количество узлов.
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,497
11.01.2017, 14:00 8
Цитата Сообщение от Nevors Посмотреть сообщение
Предложите свой вариант
Вариант чего? Перечисления подходящих комбинаций? Запросто. Предлагаю брать первые 10, а остальные - не подходят.
0
Nevors
0 / 0 / 0
Регистрация: 13.11.2016
Сообщений: 13
11.01.2017, 14:00  [ТС] 9
Цитата Сообщение от Shamil1 Посмотреть сообщение
Вероятно, лишний шаг.
Тогда как иначе реализовать алгоритм с теми условиями что я описал.
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,497
11.01.2017, 14:29 10
Цитата Сообщение от Nevors Посмотреть сообщение
с теми условиями что я описал
Из Вашего описания непонятно, что Вы хотите сделать.

з.ы. Даже непонятно, что требуется получить в итоге - одно число, список чисел,... и т.п.
0
Nevors
0 / 0 / 0
Регистрация: 13.11.2016
Сообщений: 13
11.01.2017, 15:10  [ТС] 11
Цитата Сообщение от Shamil1 Посмотреть сообщение
з.ы. Даже непонятно, что требуется получить в итоге - одно число, список чисел,... и т.п.
Список комбинаций узлов, среди которых нет комбинаций с одинаковым множеством узлов.
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,497
11.01.2017, 16:06 12
Цитата Сообщение от Nevors Посмотреть сообщение
Список комбинаций узлов, среди которых нет комбинаций с одинаковым множеством узлов.
Элементарная задача из комбинаторики. Для решения граф не нужен. Ответ будет содержать 2n комбинаций.
0
Nevors
0 / 0 / 0
Регистрация: 13.11.2016
Сообщений: 13
11.01.2017, 17:19  [ТС] 13
Цитата Сообщение от Shamil1 Посмотреть сообщение
Элементарная задача из комбинаторики. Для решения граф не нужен. Ответ будет содержать 2n комбинаций.
Так я и говорю что мне все комбинации не нужны, а только те в которых есть смысл для меня. Поэтому я и построил граф чтобы определить связи между узлами где связь означает что эти две вершины есть смысл объединять.
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,497
11.01.2017, 22:43 14
Цитата Сообщение от Nevors Посмотреть сообщение
мне все комбинации не нужны, а только те в которых есть смысл для меня
Не зная, какие комбинации имеют для Вас смысл, я не могу предложить алгоритм для их перечисления. Но, исходя из своего опыта, я могу предположить, что, вероятно, граф не нужен.
0
Nevors
0 / 0 / 0
Регистрация: 13.11.2016
Сообщений: 13
12.01.2017, 12:50  [ТС] 15
Цитата Сообщение от Shamil1 Посмотреть сообщение
Не зная, какие комбинации имеют для Вас смысл,
Ок. Вот например пусть каждый узел это селектор(CSS). Данные в узле это свойства селекторов. Комбинация узлов - это объединение селекторов. Видно сразу что не все селекторы имеют одинаковые свойства. А смысл объединять те селектора где нет одинаковых свойств.
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,497
12.01.2017, 14:44 16
Что такое свойства селекторов? У css селекторов нет свойств.
Не понятно, что Вы называете "объединением селекторов". Не похоже, что речь идёт о применении комбинаторов.
Одинаковые свойства - это свойства с одинаковыми именами или свойства с одинаковыми именами и значениями?

Цитата Сообщение от Nevors Посмотреть сообщение
А смысл объединять те селектора где нет одинаковых свойств.
В русском языке словосочетание "а смысл делать" обычно означает, что делать это не надо. Но применяется оно в вопросительных предложениях, а у Вас предложение утвердительное. Поэтому мне не понятно, означает это, что нужно объединить селекторы, у которых нет одинаковых свойств или что-нибудь другое?
0
Nevors
0 / 0 / 0
Регистрация: 13.11.2016
Сообщений: 13
12.01.2017, 15:13  [ТС] 17
Свойства селектора - набор свойств применяемых к селектору.
Одинаковый свойства - свойства, где имя и значение свойства совпадают.
Объединение селекторов - новый селектор который содержит одинаковые свойства у объединяемых селекторов.
Цитата Сообщение от Shamil1 Посмотреть сообщение
Поэтому мне не понятно, означает это
А смысл объединять те селектора, где нет одинаковых свойств???
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,497
12.01.2017, 15:32 18
Лучший ответ Сообщение было отмечено Nevors как решение

Решение

Цитата Сообщение от Nevors Посмотреть сообщение
. Так, чтобы не было таких путей, в которых множество вершин одинаковы.
Пронумеруйте вершины в произвольном порядке. (Например, если они в у Вас хранятся в массиве, то индекс может быть номером).
Сделайте свой граф направленным - чтобы рёбра шли от вершин с меньшими номерами к вершинам с большими номерами.
Тогда условие будет выполнятся автоматически.

Добавлено через 17 минут
Цитата Сообщение от Nevors Посмотреть сообщение
набор свойств применяемых к селектору.
Селектор - это критерий выбора элементов. У селектора нет свойств.
Примеры css селекторов:
h3
#someid

Правило css состоит из селектора и блока объявления стилей. Может, Вы имеете ввиду правила css?
0
Nevors
0 / 0 / 0
Регистрация: 13.11.2016
Сообщений: 13
12.01.2017, 19:27  [ТС] 19
Цитата Сообщение от Shamil1 Посмотреть сообщение
от вершин с меньшими номерами к вершинам с большими номерами
А слона я не заметил.Спасибо
0
12.01.2017, 19:27
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.01.2017, 19:27

Поиск циклов в графе
Подскажите, пожалуйста, какие идеи нужно применять к данной задаче

Поиск в ширину в графе
У меня есть небольшая база данных(обычный текстовый файл). Парсирую этот файл и полчается список...

Поиск кратчайшего пути в графе
Здравствуйте. Есть задача осуществить поиск кратчайшего пути между двумя заданными вершинами в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
19
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru