Алгоритмы для двунаправленных графов

Скажем, у меня есть граф (сеть) узлов со следующими весовыми коэффициентами: 1. путешествие в одну сторону по звену между двумя узлами. 2. Путешествие в обратном направлении по звену между двумя узлами (они могут быть разными). 3. переход с одной ссылки на другую.

Кроме того, некоторые узлы являются односторонними.

В этом случае, каковы были бы лучшие алгоритмы для: а) поиска минимального остовного дерева б) поиска кратчайшего маршрута между двумя узлами в) поиска пути «коммивояжера» (т.е. кратчайшего маршрута, который идет везде, с минимальным дублированием) ?

Кроме того, было бы лучше рассматривать двунаправленную вещь как два однонаправленных пути, а не как двунаправленный путь с разными весовыми коэффициентами в каждом направлении?

---пример---

              3
  A --<2/3>-- B --<3/2>-- C
  | 1        2|3
  |           |
  ^1/4       ^4/3
  |           |
  |3         4|
8 D --<3/5>-- E
  |2
  |
1 ^3/1
  |
  |
  F

Где ‹2/3> означает вес 2, движущихся влево и 3, движущихся вправо. ^1/4 означает, что 1 движется вверх, а 4 — вниз. Одно число между двумя ссылками — это стоимость смены ссылок — например, переход с AD на DF стоит 8, а с AB на BE — 2.

Надеюсь, это имеет смысл...

Саймон

(p.s. извините за неправильную терминологию - "ссылки", "ребра" - как хотите ;))

Чтобы лучше объяснить типы взвешивания, представьте, что ребра — это железнодорожные пути, а узлы — станции. Стоимость на границе — это время в пути на поезде между двумя станциями, а стоимость на узлах — это продолжительность времени пересадки (которое может различаться между ребрами даже в одном и том же узле, в зависимости от того, как далеко находится платформа, насколько регулярно обслуживание и т. д.).


graph algorithm shortest-path minimum-spanning-tree
person simonalexander2005    schedule 26.04.2011    source источник
comment
Меня немного смущает изменение одной ссылки (/edge) на другую. Вы имеете в виду изменение графика? Для кратчайшего пути и коммивояжера все, что имеет значение, — это вес между узлами.   -  person Kathy Van Stone    schedule 27.04.2011
comment
Здесь у меня есть вес при прохождении через каждый узел, а также вес при прохождении по ребру. Думая об этом как о дорожной системе, это эквивалент затрат на смену дорог, а также на проезд по ним (с узлами, являющимися перекрестками/перекрестками).   -  person simonalexander2005    schedule 27.04.2011

Ответы (2)


arrow_upward
4
arrow_downward

Да, рассматривайте их как два ребра вместо одного. Затем вы можете без проблем использовать традиционные алгоритмы теории графов, особенно если вы всегда гарантированно имеете веса в каждом направлении. Эти алгоритмы легко найти, если вы просто используете «обычный» график, который я только что помог вам создать.

Вы можете использовать Dijkstra's для кратчайшего пути.

Вы можете использовать Prim для минимального связующего дерева.

Вы можете поискать в Google асимметричный TSP, чтобы попытаться найти для него алгоритм, и я почти уверен, что в Introduction to Algorithms тоже есть что-то по этому поводу. Извините, я не смог найти для вас хорошую реализацию. Здесь также есть пара хороших вопросов об асимметричном TSP, теперь, когда вы знаете, что это называется асимметричным TSP.

Удачи! Я люблю теорию графов.

-Брайан Дж. Стинар-

person Brian Stinar    schedule 26.04.2011
comment
С Дейкстрой и Прим все в порядке - спасибо :) ... Что касается асимметричного TSP, я могу найти здесь только один вопрос, который был закрыт как ненастоящий вопрос ... можете ли вы связать меня с одним из хороших вопросов? Ваше здоровье :) - person simonalexander2005; 27.04.2011
comment
Я пытаюсь продумать структуру этого графа в отношении Дейкстры и Прим. Это не типичный неотрицательный взвешенный граф, потому что он имеет взвешенные вершины, а также ребра. Нужно ли сначала распределять вес по вершинам на ребра? - person ThomasMcLeod; 27.04.2011
comment
Я думаю, что распределение веса можно выполнить с помощью матрицы, где каждая строка представляет собой уравнение веса вершины, а каждый столбец — ребро. Затем используйте исключение Гаусса, чтобы найти дополнительный вес на ребрах. - person ThomasMcLeod; 27.04.2011
comment
У меня небольшие проблемы с пониманием того, что на самом деле означает вес самой вершины для этого случая. Я понимаю, что вес ребра представляет собой стоимость перехода от одной вершины к другой вершине с использованием этого ребра, но что представляет собой вес вершины? Мне также непонятно предложение использовать исключение Гаусса. Вы имеете в виду, что фактическое уравнение веса ребра представляет собой просто сумму веса ребра + вершины, и вы будете вычислять эту сумму для всех ребер в вашей матрице смежности? - person Brian Stinar; 27.04.2011
comment
Хорошо, на самом деле есть много хороших вопросов об асимметричности и о TSP... Статья в Википедии неплохая, но я на самом деле не видел реализации для вас. :-( en.wikipedia.org/wiki/ - person Brian Stinar; 27.04.2011
comment
Думайте об этом как о дорожной системе — ребро имеет стоимость проезда по дороге, а узел — стоимость смены дороги (например, может потребоваться 1 минута, чтобы повернуть налево, и две минуты, чтобы повернуть направо). Посмотрев на это и немного подумав, я решил, что может быть проще рассматривать каждый узел как несколько узлов (в зависимости от того, сколько ребер связано с ним). Например, D-‹4/1›-A(1)-‹2/3›-B можно представить как D-‹4/1›-A'-‹1/1›-A''-‹2 /3›-B ... если это имеет смысл? Это устраняет необходимость беспокоиться о взвешенных узлах, и его можно рассматривать как стандартный двунаправленный граф. - person simonalexander2005; 27.04.2011
comment
...или, если хотите, стоимость каждого узла равна стоимости перехода между ребрами. - person simonalexander2005; 27.04.2011
comment
Возьмем, к примеру, поездку на поезде — как сидение в поезде, так и пересадка с одного поезда на другой требуют времени, и оба эти фактора необходимо учитывать. Одна — это стоимость на ребре (или дорожке), а другая — это стоимость на узле (или станции). - person simonalexander2005; 27.04.2011
comment
Почему бы просто не добавить эту «стоимость узла» к каждому ребру, выходящему из узла (или всякий раз, когда возникают затраты)? Тогда вы можете не создавать для этого виртуальные узлы, что упростит задачу. Я думаю, что ваша идея с виртуальным узлом сработает, но кажется, что это усложнит ситуацию, а не просто добавление затрат на ребра. - person Brian Stinar; 28.04.2011
comment
проблема в том, что стоимость уникальна в зависимости от двух ребер - того, по которому вы входите в узел, и того, по которому вы выходите, - поэтому ее нельзя добавить к исходящим ребрам, поскольку вы не знаете, каким было предыдущее ребро ( вариантов может быть несколько)... - person simonalexander2005; 28.04.2011
comment
Да, кажется, теперь я понимаю твою точку зрения. Чтобы соответствовать вашей аналогии с реальным миром, у меня была бы вершина из одного места в место, где мне нужно сделать свой ход. Между ними была бы грань, с весом. Затем, если я решу повернуть налево, у меня будет еще одна вершина после левого поворота, а ребро между ними будет иметь время на повороте. Так же и для правого поворота. Если я решу идти прямо, у меня будет преимущество между точкой поворота и следующим пунктом назначения, а между ними будет преимущество с весом. Все алгоритмы будут ожидать что-то вроде этого, - person Brian Stinar; 28.04.2011
comment
и это поможет людям, которые раньше использовали теорию графов, помочь вам, поскольку во всех учебниках графы представлены именно так. - person Brian Stinar; 28.04.2011

arrow_upward
2
arrow_downward

Для ваших «обменных» весов вы можете сделать небольшой подграф для их кодирования. Например, у вас есть:

  |   
  |3  
8 D --
  |2
  |

Вы можете закодировать это, используя только веса на ребрах, например:

  |
  |
  D0
  | \3
  |  \
 8|   D2--
  |  /
  | /2
  D1
  |
  |

Просто следите за тем фактом, что вам не нужно использовать ребро 8, чтобы перейти от D0 к D1, так как вместо этого вы можете перейти D0-> D2-> D1 для веса 5. Я не уверен, что это разрешено в вашей первоначальной формулировке.

person Keith Randall    schedule 28.04.2011
comment
согласился - и это должно быть хорошо для того, что я делаю; хотя конечно в других примерах с похожей проблемой (например поворот на светофоре) ее бы не было. - person simonalexander2005; 29.04.2011