Как найти кратчайший путь между двумя узлами в массиве объектов? - PullRequest
Новая
       51

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

0 голосов
/ 03 апреля 2019

У меня есть 10000+ данных (Users), поступающих из API в формате JSON и с двумя узлами (то есть 2 Users), я хотел бы найти кратчайший путь между двумя Users.

Когда я понял, что, чтобы найти кратчайший путь, я мог бы использовать алгоритм Дейкстры, но затем, чтобы сделать это, мне нужно создать график, которого недостаточно с 10 000+ данных.

Например, я делаюзапрос API 

fetch('https://jsonplaceholder.typicode.com/users')
  .then(res => res.json())
)

Где каждый пользователь является объектом 

  {
    "name": "Leanne Graham",
    "address": {...}
    },
    "website": "hildegard.org",
    "company": [
      "Romaguera-Crona",
      "Google",
      "Facebook"
    ]
  }

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

Я просто не могу начать с этого, потому что данные такие огромные.Я просто хотел бы знать, как мы можем пойти по этому поводу?Создаем ли мы график и применяем алгоритм Дейкстры?

Все, что я сделал, - это действительно просмотр каждого пользователя и проверка массива компаний. 

Users.filter(user => user.companies.include([...]))

1 Ответ

0 голосов
/ 05 апреля 2019

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

Чтобы построить график пользователей, вы можете воспользоваться моим вторым предложением из другого поста:

  • Создание карты из названия компании для набора всех пользователей, которые работали в этой компании

  • Перебирайте названия компаний, перебирайте все пары пользователей, которые работали для каждой компании, и соединяйте их с ребром, если они еще не подключены

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

Теперь у вас есть график и вы хотите найти кратчайший путь между двумя узлами (я полагаю, неоднократно). Обратите внимание, что, поскольку ваш граф не имеет весов, алгоритм Джикстры не является необходимым. Вы можете запустить BFS, которая работает за O(N+M) время, где N - количество пользователей, а M - количество ребер. На миллион ребер он мог бы комфортно работать в течение секунды в Java, но в Javascript может занять несколько.

...