Модификация алгоритма Беллмана-Форда для поддержания упорядоченного списка на основе стоимости - PullRequest
Новая
       12

Модификация алгоритма Беллмана-Форда для поддержания упорядоченного списка на основе стоимости

3 голосов
/ 23 апреля 2019

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

Это проблема, которая у меня есть. Я думаю, что лучший способ решить эту проблему - это изменить алгоритм Беллмана-Форда.

Это то, что я имею до сих пор: 

  // A struct to represent an Edge in graph
   struct Edge
   {
     int source, dest, cost, duration;
   };

   // A struct to reporesented a connected, directed 
   //and wieghted graph
   struct Graph
   {
     int V, E;
     struct Edge* edge;
   };

   // Creates Graph with V vertices and E edges
   struct Graph* createGraph(int V, int E)
   {
      struct Graph* graph = new (struct Graph);
      graph -> V = V;
      graph -> E = E;
      graph -> edge = new Edge[E];
      return graph;
    }

Я уже заполнил структуры всей необходимой информацией. Теперь мне просто нужно «организовать» данные по стоимости. Итак, я понимаю, что для каждой вершины мне нужно хранить список путей, которые ведут к ней. Для каждого ребра я считаю нужным скопировать пути из первого списка вершин во второй список вершин (добавив стоимость и расстояние). Но как мне на самом деле идти о кодировании этого, той части, на которой я застрял.

Ответы [ 2 ]

2 голосов
/ 23 апреля 2019

Эта проблема хорошо изучена: проблема Планирование поездки в сетях общественного транспорта .
Ваш подход, основанный на Беллмане-Форде, может стать проблематичным и слишком дорогим в зависимости от сети, поскольку вы не можете считать, что вершина «посещена», или что кратчайший путь к вершине был вычислен уже во время выполнения алгоритма.
Эти понятия («посещенные» или «кратчайшие») могут применяться только к одной объективной проблеме кратчайших путей. Это потому, что при u, v паре вершин существует потенциально экспоненциальное количество интересных путей, потому что вы не можете рассмотреть только более быстрый или более дешевый вариант. Вы должны хранить в памяти любой путь, чтобы не было другого, более дешевого и быстрого пути, и это число путей может быстро выйти из-под контроля, если вы начнете работать в реалистичных сетях (которые могут быть довольно большими, ~ 100 тыс. Остановок, и миллионы поездок).

Я предлагаю вам прочитать о многоцелевой проблеме кратчайшего пути , с дополнительным фактом, что обычно граф, представляющий сеть, является графиком, зависящим от времени.
Я думаю, что вам стоит почитать эту страницу на многоцелевом кратчайшем пути, чтобы иметь представление об основных методах, используемых в данной области (понятие Pareto-set или Pareto-frontier очень важно понять, что касается этой проблемы), и даже более того, разделы 2 и 4 этой статьи , которые описывают современное состояние техники в отношении таких методов.

Несмотря на кажущийся сложным, большинство из них могут работать невероятно быстро (в сотни тысяч раз быстрее, чем Dijkstra, и все же намного быстрее, чем любой подход на основе A *), и для некоторых из них не слишком сложно реализовать (для Например, CSA не слишком сложен и работает довольно быстро, он может вычислить простой запрос за несколько миллисекунд в сети размером с страну).

1 голос
/ 23 апреля 2019

Типичным способом организации данных по стоимости является использование std::priority_queue для хранения ваших путей. Вы ставите пути в очередь, когда узнаете о них, а затем они сначала выходят из очереди самыми дешевыми.

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

...