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

@Nevors · Регистрация: 13.11.2016

Студворк — интернет-сервис помощи студентам

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

@Shamil1 · 10.01.2017, 09:53

Граф неориентированный?

Не по теме:

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

Добавлено через 3 минуты
Алгоритм:
Берём все возможные комбинации вершин (выбор без перестановок) и для каждой определяем (поиском в глубину), существует ли путь, проходящий через все эти вершины и только через них (гамильтонов путь на подграфе).

@Nevors · 10.01.2017, 15:02 **[ТС]**

Сообщение от Shamil1

Граф неориентированный?

Граф неориентированный.

Добавлено через 7 минут

Сообщение от Shamil1

Берём все возможные комбинации вершин (выбор без перестановок)

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

@Shamil1 · 11.01.2017, 08:38

Сообщение от Nevors

найти все комбинации вершин

Если у нас есть есть n вершин, то каждой комбинации вершин можно поставить в соответствие n-битное число, в котором установленные биты будут соответствовать выбранным вершинам.

@Nevors · 11.01.2017, 13:08 **[ТС]**

Сообщение от Shamil1

Если у нас есть есть n вершин, то каждой комбинации вершин можно поставить в соответствие n-битное число, в котором установленные биты будут соответствовать выбранным вершинам.

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

@Shamil1 · 11.01.2017, 13:49

Сообщение от Nevors

но она очень трудоемкая

Что значит "трудоемкая"?

Сообщение от Nevors

Поэтому я решил построить граф

Вероятно, лишний шаг.

@Nevors · 11.01.2017, 13:59 **[ТС]**

Сообщение от Shamil1

Что значит "трудоемкая"?

ЭМ...не правильно прочитал ваше сообщение извиняюсь.

Добавлено через 5 минут

Сообщение от Shamil1

n-битное число

Не очень понимаю как это хранить если большое количество узлов.

@Shamil1 · 11.01.2017, 14:00

Сообщение от Nevors

Предложите свой вариант

Вариант чего? Перечисления подходящих комбинаций? Запросто. Предлагаю брать первые 10, а остальные - не подходят.

@Nevors · 11.01.2017, 14:00 **[ТС]**

Сообщение от Shamil1

Вероятно, лишний шаг.

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

@Shamil1 · 11.01.2017, 14:29

Сообщение от Nevors

с теми условиями что я описал

Из Вашего описания непонятно, что Вы хотите сделать.

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

@Nevors · 11.01.2017, 15:10 **[ТС]**

Сообщение от Shamil1

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

Список комбинаций узлов, среди которых нет комбинаций с одинаковым множеством узлов.

@Shamil1 · 11.01.2017, 16:06

Сообщение от Nevors

Список комбинаций узлов, среди которых нет комбинаций с одинаковым множеством узлов.

Элементарная задача из комбинаторики. Для решения граф не нужен. Ответ будет содержать 2ⁿ комбинаций.

@Nevors · 11.01.2017, 17:19 **[ТС]**

Сообщение от Shamil1

Элементарная задача из комбинаторики. Для решения граф не нужен. Ответ будет содержать 2n комбинаций.

Так я и говорю что мне все комбинации не нужны, а только те в которых есть смысл для меня. Поэтому я и построил граф чтобы определить связи между узлами где связь означает что эти две вершины есть смысл объединять.

@Shamil1 · 11.01.2017, 22:43

Сообщение от Nevors

мне все комбинации не нужны, а только те в которых есть смысл для меня

Не зная, какие комбинации имеют для Вас смысл, я не могу предложить алгоритм для их перечисления. Но, исходя из своего опыта, я могу предположить, что, вероятно, граф не нужен.

@Nevors · 12.01.2017, 12:50 **[ТС]**

Сообщение от Shamil1

Не зная, какие комбинации имеют для Вас смысл,

Ок. Вот например пусть каждый узел это селектор(CSS). Данные в узле это свойства селекторов. Комбинация узлов - это объединение селекторов. Видно сразу что не все селекторы имеют одинаковые свойства. А смысл объединять те селектора где нет одинаковых свойств.

@Shamil1 · 12.01.2017, 14:44

Что такое свойства селекторов? У css селекторов нет свойств.
Не понятно, что Вы называете "объединением селекторов". Не похоже, что речь идёт о применении комбинаторов.
Одинаковые свойства - это свойства с одинаковыми именами или свойства с одинаковыми именами и значениями?

Сообщение от Nevors

А смысл объединять те селектора где нет одинаковых свойств.

В русском языке словосочетание "а смысл делать" обычно означает, что делать это не надо. Но применяется оно в вопросительных предложениях, а у Вас предложение утвердительное. Поэтому мне не понятно, означает это, что нужно объединить селекторы, у которых нет одинаковых свойств или что-нибудь другое?

@Nevors · 12.01.2017, 15:13 **[ТС]**

Свойства селектора - набор свойств применяемых к селектору.
Одинаковый свойства - свойства, где имя и значение свойства совпадают.
Объединение селекторов - новый селектор который содержит одинаковые свойства у объединяемых селекторов.

Сообщение от Shamil1

Поэтому мне не понятно, означает это

А смысл объединять те селектора, где нет одинаковых свойств???

@Shamil1 · 12.01.2017, 15:32

Сообщение от Nevors

. Так, чтобы не было таких путей, в которых множество вершин одинаковы.

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

Добавлено через 17 минут

Сообщение от Nevors

набор свойств применяемых к селектору.

Селектор - это критерий выбора элементов. У селектора нет свойств.
Примеры css селекторов:
h3
#someid

Правило css состоит из селектора и блока объявления стилей. Может, Вы имеете ввиду правила css?

@Nevors · 12.01.2017, 19:27 **[ТС]**

Сообщение от Shamil1

от вершин с меньшими номерами к вершинам с большими номерами

А слона я не заметил.Спасибо

Новые блоги и статьи Все статьи Все блоги /
Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .

@Nevors 0 / 0 / 0 Регистрация: 13.11.2016 Сообщений: 13

	Поиск путей в графе 10.01.2017, 03:49. Показов 2203. Ответов 18 Метки нет (Все метки) Стоит задача найти все пути на графе. Так, чтобы не было таких путей, в которых множество вершин одинаковы. Жду любые предложения. Желательно с описанием алгоритма. 0

@Shamil1 Модератор 3134 / 2281 / 469 Регистрация: 26.03.2015 Сообщений: 8,877
	10.01.2017, 09:53
	Граф неориентированный? Не по теме: Теперь понятно, для чего понадобилось хэширование массива. Добавлено через 3 минуты Алгоритм: Берём все возможные комбинации вершин (выбор без перестановок) и для каждой определяем (поиском в глубину), существует ли путь, проходящий через все эти вершины и только через них (гамильтонов путь на подграфе). 0

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

Решение