Что быстрее?Ищете кратчайший путь в матрице или списке? - PullRequest
Новая
       39

Что быстрее?Ищете кратчайший путь в матрице или списке?

2 голосов
/ 18 марта 2011

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

Так, например, у меня есть этот файл:

Афины Стокгольм 34
Стокгольм Прага 23

, который, когда я читаю, сохраняется в массиве следующим образом: 

          _____0______ ______1______
point1   | Athens     | Stockholm   |
point2   | Stockholm  | Prague      |
distance | 34         | 23          |
          ------------ -------------

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

Ответы [ 4 ]

2 голосов
/ 18 марта 2011

Отделите имена от расстояний.Создайте список, который содержит только названия городов. 

          _____0______ ______1______ ______2______ 
city     | Athens     | Stockholm   | Prague      |
          ------------ ------------- -------------

Затем создайте матрицу отдельно 

     __0__ __1__ __2__ 
 0  | 0   | 34  | 0   |
     ----- ----- -----
 1  | 34  | 0   | 23  |
     ----- ----- -----
 2  | 0   | 23  | 0   |
     ----- ----- -----

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

  • Прага: 2
  • Афины: 0

Затем вы ищите в матрицеваш путь.

  • (2,1,23) -> (1,0,34)

Наконец, вы переводите в города, используя свой список

  • (Прага, Стокгольм, 23) -> (Стокгольм, Афины, 34)
2 голосов
/ 18 марта 2011

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

Надеюсь, его помощь!

1 голос
/ 23 марта 2011

Я думаю, что списки приличия здесь, безусловно, лучший вариант здесь. Позже они очень полезны, когда дело доходит до таких алгоритмов, как D / BFS или Dijkstra.

Если вы не знаете, как сохранить города и расстояния, просто используйте некоторую структуру, чтобы объединить их. Если бы вы могли использовать пронумерованные индексированные города, вы бы использовали простую структуру пары (также самой простой реализацией было бы n векторов STL пары.

Конечно, если вы не хотите использовать STL, попробуйте реализовать собственные списки структур с указателями, которые вы хотели бы использовать.

0 голосов
/ 24 июня 2013

Ваш подход выглядит просто отлично.

Чтобы расслабиться, помните, что синтаксический анализ одного списка / массива всегда будет быстрее и более дружественным к ресурсам, чем работа с двумя (или более) списками, когда вам практически просто нужно искать одну строку / запись предопределенных данных. ,

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

Упрощенно сказал: выполнить простой переход к списку / массиву, который у вас есть в данный момент, трудно, если говорить о скорости.

...