Вопросы по теме 'graph-algorithm'
Сериализация графа
Я ищу простой алгоритм для «сериализации» ориентированного графа. В частности, у меня есть набор файлов с взаимозависимостями в порядке их выполнения, и я хочу найти правильный порядок во время компиляции. Я знаю, что это должно быть довольно...
41515 просмотров
schedule
16.06.2022
Алгоритм поиска по графу
Я ищу алгоритм графа с некоторыми необычными свойствами.
Каждое ребро в графе является либо «верхним», либо «нижним» ребром.
Действительный путь может проходить неопределенное количество «вверх», за которым следует неопределенное количество...
3465 просмотров
schedule
18.10.2022
Как найти цикл, содержащий набор узлов в графе?
Учитывая неориентированный граф G = (V, E) и набор узлов P. Мне нужно найти цикл (не цикл самой короткой длины), содержащий эти узлы? Как мне найти этот цикл?
1847 просмотров
schedule
03.07.2023
алгоритм для выбора набора победителей с использованием разных весов
Я пытаюсь разработать алгоритм, который делает следующее.
Вход:
У меня есть набор ключей (всего n), которые сопоставлены с набором свойств. Свойства содержат вес каждого свойства и значение свойства.
Выход:
Определите набор...
537 просмотров
schedule
02.04.2023
Как автоматически расположить блоки на блок-схеме?
У меня есть некоторые данные, которые представляют собой блок-схему. (Куча статусов Jira и их переходы в другие статусы.)
У меня также есть грубый способ позиционирования каждого элемента блок-схемы на страница A4 в документе OpenOffice Draw....
1917 просмотров
schedule
12.01.2023
Проблема присвоения региона
Я использую Povray для рендеринга изображений в кластере. Каждый рабочий узел будет отображать частичное изображение. Предметом этого вопроса является поиск подходящего алгоритма расщепления.
Povray визуализирует попиксельно. Но каждый пиксель...
160 просмотров
schedule
29.07.2022
Алгоритм встраивания
Кто-нибудь знает какие-либо документы, посвященные алгоритмам встраивания ? И тесно связанная с этим связь графа родитель-потомок с графом вызовов.
Предыстория: у меня есть компилятор, написанный на Ocaml , который агрессивно встраивает...
1016 просмотров
schedule
18.11.2022
укладка ящиков в теории графов
Пожалуйста, помогите мне найти хорошее решение этой проблемы.
У нас есть n ящиков с 3 измерениями. Мы можем ориентировать их, и мы хотим поставить их поверх других, чтобы иметь максимальную высоту. Мы можем поставить коробку поверх другой...
1427 просмотров
schedule
07.03.2022
Поиск хорошей эвристики для поиска A *
Я пытаюсь найти оптимальное решение для маленькой головоломки под названием Twiddle (апплет с игрой можно найти здесь ). В игре есть матрица 3x3 с числами от 1 до 9. Цель состоит в том, чтобы привести числа в правильном порядке, используя...
3628 просмотров
schedule
03.07.2022
Алгоритм обобщенного последовательного шаблона MapReduce
Я ищу пример реализации алгоритма Generalized Sequential Pattern (GSP) http://en.wikipedia.org/wiki/GSP_Algorithm
Хотя статья в Википедии содержит псевдокод, это немного сбивает с толку, и я хотел бы увидеть какой-нибудь правильный код (в идеале...
2458 просмотров
schedule
24.01.2023
Устранение симметрии из графиков
У меня есть алгоритмическая проблема, в которой я получил передаточную матрицу между множеством состояний. Следующий шаг — возвести его в степень, но он очень большой, поэтому мне нужно сделать для него некоторые сокращения. В частности, он содержит...
611 просмотров
schedule
06.01.2024
Самый дешевый обход стоимости на полном графике
Мне было интересно, есть ли алгоритм, который: учитывая полностью связанный граф из n узлов (с разными весами) ... даст мне самый дешевый цикл для перехода от узла A (начального узла) ко всем другим узлам и возврата к узлу A? Есть ли способ изменить...
2744 просмотров
schedule
18.02.2023
подробный венгерский алгоритм (задача о назначении) вопрос
Я реализовал венгерский алгоритм, решение проблемы назначения, как описано в эта статья , но она дает сбой на нескольких процентах матриц случайных затрат.
Я потратил недели на его отладку (я начал, когда спросил этот вопрос , хотя и не полный...
1114 просмотров
schedule
15.08.2022
Нахождение X деревьев с наименьшей стоимостью в графе
У меня есть график с N узлами и ребрами со стоимостью. (граф может быть полным, но также может содержать нулевые ребра).
Я хочу найти K деревьев в графе (K ‹ N), чтобы убедиться, что каждый узел посещен, а стоимость будет минимально возможной....
631 просмотров
schedule
23.01.2023
Постройте минимальное остовное дерево, покрывающее определенное подмножество вершин.
У меня есть неориентированный граф с положительным весом ребер (V, E) , для которого мне нужно минимальное остовное дерево, покрывающее подмножество k вершин V (проблема дерева Штейнера).
Я не ограничиваю размер остовного дерева k...
11017 просмотров
schedule
30.11.2022
Минимальное остовное дерево в графе с несколькими корневыми вершинами
Я хотел бы знать, есть ли алгоритм, который вычисляет минимальное остовное дерево (оптимальное ветвление) в ориентированном графе с учетом набора корневых вершин между всеми этими корневыми вершинами, но не только одной корневой вершиной и всеми...
1501 просмотров
schedule
24.05.2024
Алгоритм поиска пути с частичным знанием графа
Мне нужно запрограммировать алгоритм для навигации робота по «лабиринту» (прямоугольная сетка с отправной точкой, целью, пустыми пространствами и непреодолимыми пространствами или «стенами»). Он может двигаться в любом кардинальном направлении (С,...
831 просмотров
schedule
13.02.2023
Почему мой звездный алгоритм расширяет слишком много узлов, несмотря на правильную эвристику?
Я выполняю задание, в котором мне нужно использовать звездочку, чтобы решить 15-puzzle (на языке C).
Эвристическая функция — это Манхэттенское расстояние (также известное как расстояние такси).
Нам дан пример ввода/вывода, где доска...
2424 просмотров
schedule
07.05.2022
Определить, существует ли цикл в неориентированном графе
Мой вопрос касается ОБНАРУЖЕНИЯ существования цикла. Меня не волнует, где происходит цикл, но только если цикл существует. В частности, я работаю над реализацией (максимально) алгоритма остовного дерева. Я отсортировал ребра в порядке убывания, а...
3905 просмотров
schedule
02.10.2023
рекурсивный запрос с perl
У меня есть следующая таблица в БД, которая имеет 2 столбца:
from to
00001 00002
00001 00003
00002 00003
00002 00004
00003 00001
00003 00004
00002 00004
00004 00002
00005 00003
00005 00001
00006...
525 просмотров
schedule
10.07.2022