Как называется конструкция графа

Vlad128

Вот у меня есть некоторое множество городов. И их соединяют пути (некоторое множество ребер). Но идти можно не произвольно по всем ребрам, есть определенные правила (например, ограничение на количество поворотов или какие-то другие более сложные/простые ограничения). И я свожу задачу поиска пути к обычной задаче пути в графе расширяя граф: добавляя дополнительные вершины, которые хранят информацию о том, как я туда попал. Эта конструкция как-то называется по-особенному? Есть ли стандартная терминология, теория?
Что-то ассоциации со всем лезут, в том числе машины тьюринга и конечные автоматы. Но походу не знаю я такого.

seregaohota

не сети Петри?

dunkel68

нельзя просто рёбрам придавать дополнительный вес и искать кратчайший взвешенный путь?

Vlad128

спасибо, что интересуетесь :) вроде нельзя :) тем более, не факт, что это будет эффективнее :)

Vlad128

да не, Петри оно вроде для моделирования вычислений каких-то. А у меня все статично: реально есть обычные города и дороги, просто усложнены правила, как можно ходить: например если шел на север, то на запад поворачивать уже нельзя.

stat3032681

может просто копировать каждую вершину? грубо говоря, один город будет представляться не одной вершиной, а двумя, из одной вершины ты можешь идти только на запад, из другой - только на север

Vlad128

в первом сообщении так и написано.
добавляя дополнительные вершины, которые хранят информацию о том, как я туда попал.

stat3032681

Тогда ты не совсем корректно выразился: не совсем понятно, как вершины могут хранить какую-то информацию. Вершины графа - это множество элементов. Если ты раздваиваешь каждую вершину, ты просто создаешь новый граф, при этом ребра, которые раньше шли от города, делятся между раздвоенными вершинами согласно твоим правилам. Я думаю, самая простая интерпретация: старый граф описывает пути между городами, новый граф описывает пути между городскими районами.

Vlad128

Информацию хранит легко. Новая вершина — это пара "город, по какому направлению в него пришли". Вот и информация.
Районы — это вообще не в тему.

Vlad128

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

Xephon

Эта конструкция по-английски называется "blow up", а по-русски я бы её перевёл как "раздутие" графа.

Vlad128

да, что-то гуглится, спасибо.

jurec67

И я свожу задачу поиска пути к обычной задаче пути в графе расширяя граф: добавляя дополнительные вершины, которые хранят информацию о том, как я туда попал. Эта конструкция как-то называется по-особенному? Есть ли стандартная терминология, теория?
Что-то ассоциации со всем лезут, в том числе машины тьюринга и конечные автоматы.
Может быть, Pushdown automata? Например, в них ты можешь хранить историю всех пройденных вершин на стеке, и от верхнего элемента стека будет зависеть функция переходов.
Оставить комментарий
Имя или ник:
Комментарий: