Может ли трёхмерная матрица быть представлена графом?

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

У меня есть задача, между двумя выбранными событиями (долгота, широта, время) найти самый короткий маршрут из событий, происходивших в интервале от первого ко второму событию. Мне это интуитивно напоминает граф, для которого уже разработаны алгоритмы под эту задачу. Но в силу своих слабых познаний в этой области, я не могу понять, можно ли такие данные представить в виде графа. Может нужно какое-то иное решение?
  • Вопрос задан
  • 2847 просмотров
Решения вопроса 1
Представить можно.

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

С другой стороны "на Вас работает" измерение времени, отсекая события ранее первого и позднее второго. И если во временном интервале между событиями, которые Вы пытаетесь связать, всего 10-20-50 промежуточных событий в базе, то возможно алгоритмы на графах Вас устроят.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
fornit1917
@fornit1917
Да можно в принципе. Каждому событию соответсвует вершина графа. Из вершины A идет дуга в B, если событие B наступило после A. Вес дуг - расстояние, вычисленное по координатам события. Если например в одной точке происходило несколько событий, то этому будет соответствовать несколько вершин в графе, дуги между которыми будут с нулевым весом.
При составлении графа используйте только те события, которые попадают в граничные условия по времени вашей задачи.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы