Публикации по теме 'shortest-path'
Назад к основам — Божественные алгоритмы Том III: Алгоритм A*
Вы здесь!
ХА! Я вижу, вы… нашли свой путь к моему блогу * BA DUM TS*. Хорошо, оглядываясь назад, эта шутка не будет иметь смысла, пока я не объясню тему сегодняшнего блога. Но, если вам удалось найти подсказку в моем предыдущем блоге , возможно, вы поняли, о чем я говорю, и шутка, вероятно,… не прошла мимо вас *BA DU … хорошо извините, последний каламбур, обещание. Если вы не читали мой последний блог, что должно быть удивительно, или не нашли подсказку, вот она:
В конце..
Вопросы по теме 'shortest-path'
Обновление матрицы расстояний по кратчайшему пути при уменьшении веса одной кромки
Нам дан взвешенный граф G и дельта матрицы его кратчайшего пути. Таким образом, delta (i, j) обозначает вес кратчайшего пути от i до j (i и j - две вершины графа). Изначально задается delta, содержащая значение кратчайших путей. Внезапно вес ребра...
3787 просмотров
schedule
21.11.2021
Язык программирования C, кратчайший путь
Я пишу код, чтобы найти кратчайшее расстояние между двумя точками. Мой код до сих пор работает идеально. Я имею в виду, что он находит расстояние и путь, который они должны пройти. Мне нужно распечатать эту информацию, но я должен сделать функцию...
1854 просмотров
schedule
12.09.2021
Алгоритм поиска путей в списке разбросанных точек
У меня есть список точек, взятых при измерении модели. Важная часть анализа, который необходимо провести, состоит в поиске «возможных путей» вдоль этих точек, которые в дальнейшем будут урезаны и уточнены.
Ниже представлены изображения,...
172 просмотров
schedule
29.09.2021
Связь базы данных графа Neo4j со свойствами
Я разрабатываю что-то для изучения графовых баз данных. Я нахожу кратчайший путь, который запрашивает в следующем сегменте:
start n=node(5),m=node(45) match p=shortestPath(n-[*..1000]->m) return p,length(p)
Но у меня проблема с этим. Этот...
527 просмотров
schedule
10.11.2021
Какой алгоритм использует networkx в своей функции shorttest_path ()?
Практически в точности то, что написано в названии. Например, я знаю, что есть возможность использовать алгоритм Джикстры для взвешенных графиков. Но нигде в документации networkx не указывает алгоритм, используемый для shorttest_path (). Если,...
67 просмотров
schedule
30.10.2021
Android, карты google, ломаная линия, кратчайший путь
Я уже читал некоторые темы о переполнении стека, но не нашел точного решения моей проблемы. Постараюсь объяснить свою проблему. Например, допустим, что у меня сетка 9x9. Координаты представлены перекрестками. Есть ли метод или кто-то уже...
5077 просмотров
schedule
01.12.2021
Вариант алгоритма кратчайшего пути Дейкстры
Я застрял в этой проблеме (мое решение слишком медленное). Я опишу проблему, а затем свое решение.
Проблема: учитывая N станцию, каждая из которых находится в позиции x_i в числовой строке, мы хотим переместить робота с первой станции на...
940 просмотров
schedule
21.10.2021
Алгоритм Флойда Уоршалла для плоского сеточного графа
У меня есть такой график:
И я реализовал массив графов следующим образом:
G[i][j][k]
K имеет всего 4 ячейки и показывает, соединена ли вершина со своими четырьмя соседними вершинами или нет. Например для:
G[1][1][0] = 0...
962 просмотров
schedule
10.09.2021
Поиск кратчайшего пути по нескольким точкам
Требования:
На графике есть несколько целей, которые вам нужно посетить (независимо от того, в каком порядке или сколько раз вы посещаете каждую точку)
Вы можете начать с начальной точки, посетить все мишени и вернуться на базу.
Вам...
2940 просмотров
schedule
10.11.2021
Самый быстрый путь между двумя городами
Мне нужно найти самый быстрый способ путешествовать из одного города в другой. У меня есть что-то вроде
way(madrid, barcelona, 4).
way(barcelona, paris, 5).
way(madrid, londres, 3).
way(londres,paris,1).
Я придумал предикат короткой...
600 просмотров
schedule
27.10.2021
Максимальное расстояние двух узлов дерева одного цвета
Дано дерево с N вершинами, каждое ребро которого имеет вес 1 . Узлы окрашены в C цвета. Мы хотим найти для каждого цвета максимальное кратчайшее расстояние между двумя узлами этого цвета.
Я могу построить разреженную таблицу, а затем найти...
459 просмотров
schedule
21.11.2021
Самый быстрый путь с ускорением в точках
Это просто то, что я придумал сам, но это кажется забавной проблемой, и это меня поставило в тупик.
У вас есть набор точек в двухмерном пространстве, одна из которых обозначена как «Начало», а другая - «Конец». Каждая точка имеет координаты (в...
730 просмотров
schedule
28.11.2021
Scala - рекурсивный алгоритм кратчайшего пути между двумя узлами
Я рекурсивно реализую алгоритм кратчайшего пути Дейкстры в Scala, но у меня возникли некоторые проблемы. Я получаю неправильный вывод для узлов с 3 по 2 , так называемых shortestPath(3, 2, x, BitSet.empty) . Это выводит 6, но правильный ответ...
1234 просмотров
schedule
19.10.2021
Взвешенная матрица кратчайшего пути
Найдите кратчайший путь от любого элемента в крайней левой части заданной матрицы размера n x n до любого элемента в крайней правой части матрицы.
Движение: движение может быть только одним квадратом за раз. Вы можете перемещаться влево, вправо,...
850 просмотров
schedule
25.11.2021
Как проверить, есть ли в графике отрицательный цикл, но он не может быть получен из источника?
Я хочу проверить, есть ли у моего взвешенного графика отрицательный цикл. Для использования алгоритма Беллмана-Форда нам нужно выбрать исходный узел, инициализировать все остальные расстояния до бесконечности и начать расслабление n-1 раз, если...
214 просмотров
schedule
20.10.2021
Кратчайший путь между столицами, проходящий через другие столицы
Я пытаюсь разработать код для работы в колледже, и у меня есть алгоритм, который дает мне кратчайший путь между двумя узлами в графе. Обратите внимание, что узлы - это страны, у которых есть столица.
Может ли кто-нибудь объяснить мне, как я могу...
96 просмотров
schedule
03.11.2021
Кратчайший путь, соединяющий несколько узлов в iGraph R
У меня есть сеть iGraph в R, и я хотел бы найти кратчайший путь, соединяющий несколько узлов в моей сети (скажем, узлы 1,3,4,7). Есть ли функция, которая может это сделать? Что-то вроде all_simple_paths , но для одного глобального решения?...
167 просмотров
schedule
29.10.2021
Кратчайший путь в невзвешенном 2D-массиве. Как показать шаги / направления, сделанные во время BFS
В этом алгоритме я пытаюсь найти кратчайший путь из заданной начальной точки (S) и заданной конечной точки (D) для заданного 2D-массива, имея в виду, что некоторые элементы в массиве (*) считаются препятствиями. Обычно я бы выполнил типичный BFS и...
227 просмотров
schedule
08.09.2021
Как справиться с ошибкой цикла отрицательной стоимости при вычислении кратчайшего пути с отрицательными весами с помощью networkx?
Я использую networkx для решения проблем кратчайшего пути. Я хотел бы иметь возможность использовать
На рисунке слева показан лучший маршрут при минимизации атрибута «длина», а на рисунке справа - тот, который я хотел бы получить при минимизации...
56 просмотров
schedule
29.11.2021
Как найти кратчайший путь из набора списков, представляющих железнодорожные линии?
Итак, у меня есть четыре линии поезда, представленные в виде списков:
line1 = ["a", "b", "f", "d", "e"]
line2 = ["c", "e", "j", "g", "i"]
line3 =...
80 просмотров
schedule
26.11.2021
