Описание тега hamiltonian-path
1
ответ
Нахождение гамильтонова пути и гамильтонова цикла
У меня есть SimpleGraph в JGraphT и хотите знать, если есть гамильтонов путь гамильтонов цикл И если он существует, я бы тоже хотел его получить. Я только нашел TwoApproxMetricTSP а также HamiltonianCycle, Но оба требуют полных графиков. Одно очевид…
13 янв '18 в 09:22
0
ответов
Гамильтоновы схемы / графики
Может кто-нибудь сказать мне, правильно ли я делаю эти графики для гамильтоновых цепей? Я знаю, что вы начинаете с корневого узла и показывает путь "назад" в дереве. Но что, если он пересекается и тому подобное. Я просто запутался в том, как на само…
28 фев '18 в 06:32
8
ответов
Разница между гамильтоновым и эйлеровым путями
Может кто-нибудь сказать мне разницу между гамильтоновым путем и путем Эйлера. Они кажутся похожими!
16 июл '10 в 21:33
1
ответ
Гамильтонов путь - могу ли я покрыть ребро дважды, если каждая вершина может быть покрыта только один раз?
Из этого вопроса - Разница между гамильтоновым путем и эйлеровым путем, каждый гамильтонов путь не является эйлеровым путем. Как я могу покрыть каждую вершину ровно один раз и пересечь ребро дважды?
23 сен '18 в 20:04
0
ответов
Гамильтониан путь функциональный путь
Я пытаюсь работать над проблемой, которая дает мне гамильтонову путь в графе. Я знаю об алгоритмах, используемых для этого, но они все подходят для императивного стиля. Моя путаница заключается в том, что если я должен использовать динамическое прог…
27 июн '18 в 18:28
0
ответов
Преобразование кода C++ в C# для гамильтонова алгоритма пути
Я пытаюсь дублировать часть 2 учебника по этой ссылке в C#. Я написал код, и он компилируется, но функция всегда возвращает false. Для этой задачи я заполнил четыре узла, расположенных в виде сетки с размерами 2x2. Узлы связаны с узлами справа, слев…
06 фев '19 в 19:46
1
ответ
Какие из следующих задач могут быть сведены к задаче о гамильтоновом пути?
Я беру класс " Алгоритмы: дизайн и анализ II ", один из вопросов: Предположим, что P ≠ NP. Рассмотрим неориентированные графы с неотрицательными длинами ребер. Какие из следующих проблем могут быть решены за полиномиальное время? Подсказка: задача о…
08 янв '19 в 00:57
0
ответов
Коммивояжер, не возвращаясь к исходной точке
Мой вопрос: если мы рассмотрим задачу коммивояжера без возврата к начальной точке, правильно ли алгоритм жадного алгоритма (ближайшего соседа) решает эту проблему? В предыдущем потоке кто-то заявил, что эта проблема эквивалентна кратчайшему гамильто…
11 фев '18 в 14:53
0
ответов
Рекомендовать хорошую эвристику для самого длинного гамильтонова пути за полиномиальное время
У меня есть полный взвешенный граф с 1000 узлами, и мне нужно найти максимально длинный гамильтонов путь в графе (точнее, последовательность узлов). Я должен уместиться в 5 секунд (для Java), ограничение памяти достаточно велико. Поиск самого длинно…
11 июн '19 в 23:34
0
ответов
Я не могу понять состояние гамильтонова пути?
Путь к Гамильтону завершен, я знаю, и для начала кода необходимо знать, могу ли я найти этот путь или нет, но я нашел это условие, которое не могу понять. я хочу понять эти слова: "достаточное условие, которое гласит, что для графа G,если сумма степ…
17 июн '19 в 22:07
0
ответов
Алгоритм гамильтонова пути на направленном невзвешенном графе использует несуществующие ребра
Я пытаюсь реализовать алгоритм Хелда-Карпа для нахождения гамильтонова пути на невзвешенном ориентированном графе. Для этого я создал внутренний класс Combination, в котором хранится стек, представляющий порядок выбранного пути, и набор, в котором х…
28 май '19 в 11:44
1
ответ
Показать np-полноту непересекающегося гамильтонова пути
Рассмотрим проблему непересекающегося гамильтонова пути: Вход: график, который может быть направленным или ненаправленным Вывод: существует ли в этом графе хотя бы 2 гамильтоновых пути, которые не пересекаются по ребрам? Непересекающиеся края означа…
07 авг '19 в 22:16
0
ответов
Гамильтонов путь в простом DAG
Я пытаюсь реализовать рекурсивный поиск гамильтонова пути в простом DAG. Вот данные и код моей игрушки: DAG в формате Edge-List 4 5 1 2 3 1 3 2 4 3 4 2 DAG в формате словаря после преобразования {1: [2], 3: [1, 2], 4: [3, 2]} Код: G - это граф, разм…
13 дек '19 в 11:23
0
ответов
Как эффективно найти все гамильтоновы пути в неориентированном графе, не используя только DFS?
У меня проблема, когда мне нужно отображать все узлы, которые включены в путь (от источника к месту назначения), но таким образом, чтобы мы посещали каждый узел на пути только один раз. Решение только с DFS (и маркировкой посещенных элементов) недос…
22 апр '20 в 21:01
0
ответов
генерировать все таблицы непредвиденных обстоятельств с заданными полями по гамильтоновому пути
Таблица записей на случай непредвиденных обстоятельств n[t,s] с участием t=1,...,k а также s=1,...,q. Вот,k>1, q>1 и n[t,s] неотрицательные целые числа. Предположить, что sum_s n[t,s] = a_t >= 0 sum_t n[t,s] = b_s >= 0 фиксированные марж…
20 ноя '19 в 22:07
0
ответов
Какой алгоритм я могу использовать, чтобы найти кратчайший путь к Пути Гамильтона
Изображение графа, которое мне нужно, чтобы найти короткий путь Итак, в основном название говорит само за себя: мне нужно найти кратчайший путь и создать Путь Гамильтона. Итак, какой алгоритм мне следует использовать. Я пробовал алгоритм Джикстры, …
31 май '20 в 12:03
2
ответа
Problem in R studio while solving Traveling Salesman Problem (TSP) using Concorde
I am working with Concorde to solve TSP problems. Here is my code library(TSP) concordePath = "E:/Concorde_Code/" concorde_path(concordePath) concorde_help() dataset_path = "E:/RA/" name = "graph1.txt" dataset = read.table(paste(dataset_path,name,se…
11 апр '20 в 22:46
0
ответов
Количество гамильтоновых путей в графах
Я пытаюсь найти быстрый алгоритм, который может вычислить количество гамильтоновых путей в неориентированном графе. Я видел это в сети, но похоже, что все гамильтоновы пути начинаются с одной конкретной вершины. (например, вершина 0 в этом коде) Одн…
05 дек '20 в 18:00
0
ответов
Подход гамильтонова пути для сборки генома с примерами, показывающими его проблемы и возможные решения
Я хотел бы больше узнать о том, где используется гамильтонов путь и его использование при сборке генома, а также о проблемах, с которыми здесь сталкиваются.
28 ноя '20 в 22:12
1
ответ
Ультрагамильтонов цикл
Ультрагамильтонов цикл определяется как закрытый обход, который посещает каждую вершину ровно один раз, за исключением не более одной вершины, которая посещает более одного раза. Вопрос: - Докажите, что NP-сложно определить, содержит ли данный гра…
28 мар '21 в 21:04