Вопросы по теме 'graph-algorithm'
Как выбрать решатель целочисленного линейного программирования?
Я новичок в целочисленном линейном программировании. Я планирую использовать решатель целочисленного линейного программирования для решения моей задачи комбинаторной оптимизации. Я больше знаком с C++/объектно-ориентированным программированием в...
17622 просмотров
schedule
16.02.2022
Поиск пути в 2D: комбинации точек маршрута для перехода от curLocation к targetLocation
Пожалуйста, найдите минутку, чтобы понять мою ситуацию. Если это не понятно, пожалуйста, сообщите мне в комментарии.
У меня есть ArrayList путевых точек. Эти путевые точки не в любом порядке. Путевая точка имеет следующие свойства: {int type,...
2668 просмотров
schedule
25.10.2023
Получить путь от каждого конечного узла к корню в древовидной структуре
Как я могу превратить эту древовидную структуру
[1, [2, [3, 4]], [5, [6, [7], 8]]]
1
2
3
4
5
6
7
8
.... в эту структуру "перевернутого дерева", которая в основном содержит пути от всех листовых узлов к...
2737 просмотров
schedule
23.05.2023
поиск кратчайшего графа по параметрам
def shortestPath(digraph, start, end, maxTotalDist, maxDistOutdoors, visited=[]):
if not (digraph.hasNode(start) and digraph.hasNode(end)):
raise ValueError('Start or end not in graph.')
path = [str(start)]
if start == end:...
470 просмотров
schedule
03.02.2023
Алгоритм минимальной группировки
У меня есть набор значений, каждое значение имеет возможную группу. Значение может повторяться, но в другой группе.
Каким будет оптимальный алгоритм для получения минимального количества групп
Примерный набор: (12, группа б) (38, группа а) (12,...
155 просмотров
schedule
05.05.2023
Алгоритм упрощения валютных заявок
Это почти не зависящий от языка вопрос, а не домашнее задание. В идеале я бы использовал C # и / или SQL-сервер для решения.
Предположим, у меня есть функция GetExchangeRate(buyCurrency, sellCurrency) . Итак, если 1 фунт стерлингов стоит 1,6...
1255 просмотров
schedule
06.04.2022
Выведите узлы в цикле, существующем в ориентированном графе
Хотя я понимаю, что мы можем обнаруживать циклы с помощью алгоритма DFS, обнаруживая обратные края http://cs.wellesley.edu/~cs231/fall01/dfs.pdf . Я не могу понять, как эффективно и «чисто» выводить узлы в цикле, следуя указанному выше методу....
259 просмотров
schedule
12.10.2023
Циклы в ориентированном графе
Интересно, сможем ли мы доказать следующее, или если оно уже доказано, где я могу получить доказательство.
Пусть v1, v2, v3 ... vn и t - n + 1 вершина в ориентированном графе. v1, v2, v3 ... vn образуют ориентированный ациклический граф. t...
589 просмотров
schedule
30.03.2024
Почему нельзя ослабить все ребра в первой итерации алгоритма Беллмана Форда?
Пожалуйста, обратитесь к следующей странице для алгоритма Беллмана Форда (он показывает, например). http://compprog.wordpress.com/2007/11/29/one-source-shortest-path-the-bellman-ford-algorithm
Я все еще не понимаю. В первой итерации внешнего...
843 просмотров
schedule
22.07.2022
Выберите головной узел после алгоритма связующего дерева с минимальным весом
Я реализовал алгоритм Прима , чтобы найти остовное дерево минимального веса моего графа, и это работает нормально.
Теперь я хотел бы выбрать «лучшую» голову в связующем дереве. Под «лучшим» я подразумеваю более сбалансированный заголовок,...
206 просмотров
schedule
01.02.2023
Построение графа с заданными ограничениями
Дано:
Список узлов
Список узлов, к которым эти узлы могут подключаться
Ограничения, что каждый узел должен подключаться к одному и только одному другому узлу (одностороннее соединение)
Все узлы должны быть доступны, начиная с любого узла...
1031 просмотров
schedule
24.03.2024
Как найти лучший путь в графе со взвешенными узлами и вершинами
Допустим, у меня есть этот график
всегда полный график
один начальный узел - также финишный узел
взвешенные узлы и вершины
Я хочу найти путь как можно короче, но с лучшим результатом (сумма очков узлов) - другими словами, путь,...
1996 просмотров
schedule
29.08.2022
Поиск пути в реальных трехмерных средах (например, зданиях)
Существует ли алгоритм поиска пути, который также подходит для реальных 3D-сред, например. реальные здания с несколькими лестницами и т. д. Библиотека C++ или открытая реализация были бы великолепны ;-) Одним из решений, которое я видел, была...
1988 просмотров
schedule
04.08.2023
Алгоритм аппроксимации для варианта TSP, фиксированные начало и конец где угодно, кроме начальной точки + несколько посещений в каждой вершине РАЗРЕШЕНО
ПРИМЕЧАНИЕ: из-за того, что поездка не заканчивается в том же месте, в котором она началась, а также из-за того, что каждую точку можно посетить более одного раза, если я все еще посещаю их все, это на самом деле не вариант TSP, но Ставлю из-за...
1709 просмотров
schedule
16.10.2023
Маршруты между двумя точками в сетке
Учитывая сетку точек, я пытаюсь найти путь между двумя из них.
Как на этой картинке: мне нужно найти точки для желтой линии:
Какие лучшие методы / алгоритмы я могу использовать?
Спасибо
1395 просмотров
schedule
02.05.2022
Рассчитать площадь ячейки Вороного
Я пытаюсь рассчитать площадь каждой ячейки Вороного в Matlab, но я застрял. Я нашел этот код в Интернете:
[v , c] = voronoin(sdata);
for i = 1 : size(c ,1)
ind = c{i}';
tess_area(i,1) = polyarea( v(ind,1) , v(ind,2) );
end
Этот код не...
7032 просмотров
schedule
14.06.2022
Преимущество поиска в глубину перед поиском в ширину или наоборот
Я изучил два алгоритма обхода графа, поиск в глубину и поиск в ширину. Поскольку оба алгоритма используются для решения одной и той же проблемы обхода графа, я хотел бы знать, как выбирать между ними. Я имею в виду, что один более эффективен, чем...
22715 просмотров
schedule
27.07.2022
Алгоритмы графов
Пусть G — граф с n вершинами, ни одна из которых не является изолированной, и n−1 ребрами, где n ≥ 2. Покажите, что G содержит по крайней мере две вершины степени 1.
Я пробовал эту проблему, используя свойство summation degree = 2|E| . Можно ли...
109 просмотров
schedule
08.01.2024
Модификация алгоритма Дейкстры для реализации A*
Я нахожусь в процессе создания имитации лабиринта мыши, бегущей по лабиринту. Алгоритм Дейкстры великолепен и все такое, но он не особенно влияет, когда участвуют кошки, поэтому я пытаюсь изменить мою существующую реализацию Дейкстры на поиск A * с...
540 просмотров
schedule
08.03.2023
Как быстро получить всех родителей для всех листьев в дереве?
У меня есть, возможно, большая корневая древовидная структура, которую я хочу преобразовать в матрицу X * Y , где X — количество листьев в дереве, а Y — количество узлов в дереве со степенью больше 1, т. е. корневой узел и внутренний узлы....
1732 просмотров
schedule
10.04.2022
