Может ли трёхмерная матрица быть представлена графом?
Коллеги, вопрос может быть наивным, но помогите разобраться. Предположим, я имею трёхмерный массив, одно измерение которого будет хранить долготу, второе широту, а третье - время. То есть я сохраняю в таком массиве события (где, когда). Таким образом, я могу выбрать две произвольные ячейки и посчитать расстояние между ними и разницу во времени между двумя событиями.
У меня есть задача, между двумя выбранными событиями (долгота, широта, время) найти самый короткий маршрут из событий, происходивших в интервале от первого ко второму событию. Мне это интуитивно напоминает граф, для которого уже разработаны алгоритмы под эту задачу. Но в силу своих слабых познаний в этой области, я не могу понять, можно ли такие данные представить в виде графа. Может нужно какое-то иное решение?
Но для того, чтобы применять алгоритмы поиска пути на графе, Вам нужно считать любые две записи связанными, то есть количество ребер будет расти квадратично от количества записей и, мне кажется, у Вас получится очень высокая вычислительная сложность.
С другой стороны "на Вас работает" измерение времени, отсекая события ранее первого и позднее второго. И если во временном интервале между событиями, которые Вы пытаетесь связать, всего 10-20-50 промежуточных событий в базе, то возможно алгоритмы на графах Вас устроят.
Я думаю, что для моей задачи между началом и концом маршрута будет не более 10 вершин (событий). Я только не могу понять, как будет выглядеть граф, который описывает расстояния и время между событиями. Может быть весом ребра будет какое-то числовое значение, которое я получаю, сравнивая расстояние и время между двумя событиями по некой формуле?
В любом случае Вам придется вводить относительные веса (коэффициенты) для метров и секунд. Например, коэффициент перевода км в у.е. будет 0.02, а часов в у.е. - 1.0. Тогда событие, произошедшее на расстоянии 100 км с разницей в час, будет стоить 3.0 у.е., а на расстоянии 10 км с разницей в 2 часа - 2.2 у.е. Эти у.е. и нужно будет разместить на ребрах графа.
Любые 2 записи должны быть связаны путём, а не ребром. Достаточно соединить каждую ячейку с её соседями (Для трёхмерной матрицы таких будет 9+9+3+3=24 если разрешены переходы по диагонали), т.е. ребёр не может быть больше 24 |V|. Если ищется самый короткий путь из событий, то обычного BFS'а вполне хватит. Итого линейная сложность.
@barmaley_exe Судя по постановке задачи, не каждая ячейка заполнена. Соответственно, не обязательно ребро, находящееся первым в кратчайшем пути, идет по неувеличению всех трех координат.
Да можно в принципе. Каждому событию соответсвует вершина графа. Из вершины A идет дуга в B, если событие B наступило после A. Вес дуг - расстояние, вычисленное по координатам события. Если например в одной точке происходило несколько событий, то этому будет соответствовать несколько вершин в графе, дуги между которыми будут с нулевым весом.
При составлении графа используйте только те события, которые попадают в граничные условия по времени вашей задачи.
Т.е. я упираюсь по сути только в моё собственное видение о том, что считать ближайшим событию A - событие в 2 км от него, но через час или событие в 3 км от него, но через 45 м.?
@trashmajor ну я исходил из того, что вас интересует именно близость по расстоянию. Логику вычисления расстояния (весов дуг) можно сделать любую, это уже зависит от бизнес-требований вашей задачи
Да я только когда сформулировал вопрос, понял что тут в первую очередь нужно понять, что решать "ближайшим" с точки зрения времени-пространства. Если это понять, то построение графа будет очевидно.
Простой
Простой
