Описание тега hamiltonian-cycle
Гамильтонов цикл - это цикл в ориентированном или неориентированном графе, который посещает каждый узел / вершину ровно один раз.
1
ответ
GCJ - гамильтоновы циклы
Проблема с застреванием кода заключается в следующем: Вам дан полный ненаправленный граф с N узлами и K "запрещенными" ребрами. N <= 300, K <= 15. Найти число гамильтоновых циклов в графе, которые не используют ни одного из K "запрещенных" ребер. К…
17 май '11 в 23:36
2
ответа
Алгоритм гамильтонова цикла
Я искал некоторые алгоритмы гамильтоновых циклов, но не могу найти ни одной реализации, даже ни одного псевдокода! Мне даже не нужно выводить цикл, просто проверьте, есть ли на графике. Входные данные представляют собой граф с V вершинами и E ребрам…
10 ноя '13 в 18:20
0
ответов
Число гамильтоновых цепей в ориентированном графе
Я пытался искать это везде, но не смог найти ответ. По заданному графу (который не должен быть полным), как найти число гамильтоновых цепей
10 ноя '17 в 16:39
0
ответов
Алгоритм самого длинного пути с "может" имеет цикл и отрицательный фронт на определенном шаге
Я провел собственное исследование, однако не смог найти правильного решения для своего требования. Проблема в том, что у меня есть грузовик, который должен тратить груз (скажем, мусор). Существуют города (узел) и ребра (путь), которые могут быть пол…
21 дек '17 в 14:35
2
ответа
Генерация графов только с одним действительным гамильтоновым циклом
Я ищу несколько советов / указаний в правильном направлении. Мое требование состоит в том, чтобы сгенерировать график, а не решать один для решения. Я ищу реализовать алгоритм для генерации графа (сетка NxN) только с 1 гамильтоновым циклом. Обратите…
22 июн '17 в 08:08
0
ответов
Ограниченный гамильтонов цикл
Может кто-нибудь объяснить мне определение ограниченного гамильтонова цикла?Я знаю, что такое гамильтонов путь (и гамильтонов цикл), но у меня возникают проблемы с пониманием, что такое ограниченный гамильтонов цикл. Спасибо.
07 дек '15 в 08:24
2
ответа
Алгоритм Палмера для гамильтоновых циклов
В "плотном" графе я пытаюсь построить гамильтонов цикл с использованием алгоритма Палмера. Однако мне нужно больше объяснений для этого алгоритма, потому что он не работает со мной, когда я его реализую. Кажется, в объяснении Википедии есть неясная …
30 июн '12 в 11:18
0
ответов
Нахождение самой длинной сетки пути
Я работаю с сеткой равномерной стоимости, которая позволяет только движения в ортогональных направлениях. Это используется в качестве основы для игры змея, где змея должна постоянно двигаться и пытаться съесть яблоки на доске. Расположение пищи и пр…
24 июл '18 в 05:02
0
ответов
Обнаружение циклов в неориентированном графике с помощью библиотеки графов
Я застрял со вчерашнего дня с этой проблемой. К сожалению / к счастью, эта проблема составляет всего около 0,5% моего супер огромного (для меня новичка в C++), таким образом, требуется библиотека существующего кода, которую можно просто адаптировать…
08 мар '12 в 22:47
0
ответов
Алгоритм гамильтонова цикла v^2?
Существует ли алгоритм, который найдет максимально длинные гамильтоновы циклы за v^2 времени. Я запускаю программу, которая должна найти циклы на разреженном графике (максимум 4v ребер), и, согласно моим расчетам, мне нужно v^2 или лучше. Я понимаю,…
10 авг '12 в 11:24
1
ответ
Полный взвешенный график G, нахождение весов и одна машина
Я много читал о темах Complete Weighted Graph и Hamiltonian Tour на этом сайте, которые задавал один из пользователей, спрашивал много сотрудников в моем университете, но не мог найти хороший ответ, я изменяю важную часть этого вопроса как следующим…
15 мар '15 в 18:56
1
ответ
Нахождение гамильтонова пути и гамильтонова цикла
У меня есть SimpleGraph в JGraphT и хотите знать, если есть гамильтонов путь гамильтонов цикл И если он существует, я бы тоже хотел его получить. Я только нашел TwoApproxMetricTSP а также HamiltonianCycle, Но оба требуют полных графиков. Одно очевид…
13 янв '18 в 09:22
1
ответ
Стратегии Сокращения для вычисления общего количества гамильтоновых путей в двумерной сетке
Недавно я пытался найти общее количество гамильтоновых путей (в основном, начиная с начальной вершины, посещение каждого узла точно один раз и достижение конечной вершины). Грубая сила dfs идет на длинную прогулку по сетке среднего размера 7x8. Я пр…
17 июн '11 в 20:19
2
ответа
Показать полный граф с n вершинами, вес MST меньше или равен минимальному весу цикла, который проходит через все вершины
Я действительно борюсь с этим доказательством и буду очень признателен за подробное объяснение: Покажите полный граф с n вершинами, вес MST меньше или равен минимальному весу цикла, который проходит через все вершины (также называемый гамильтоновым …
28 мар '16 в 13:40
1
ответ
Тестирование реализации поиска гамильтоновых путей
Я реализую алгоритм, который находит оптимальный путь гамильтониана в ориентированном графе. Я реализовал алгоритм, который, кажется, работает достаточно хорошо, однако я не совсем уверен, есть ли небольшие ошибки или другие проблемы в определенных …
12 янв '12 в 15:35
2
ответа
Как найти число гамильтоновых циклов, в которых не используются "запрещенные" ребра?
Этот вопрос перефразирует этот вопрос. Проблема с застреванием кода заключается в следующем: Вам дан полный ненаправленный граф с N узлами и K "запрещенными" ребрами. N <= 300, K <= 15. Найти число гамильтоновых циклов в графе, которые не используют…
21 янв '11 в 14:30
1
ответ
Гамильтонов путь по преграде из сетки и Python
Я пытаюсь найти любые гамильтоновы пути в данной сетке, которая содержит препятствия в различных узлах. Моя проблема в том, что мой код работает уже несколько дней и еще не закончен. Хотя эта проблема находится в области NP-Complete, из того, что я …
07 сен '14 в 21:18
1
ответ
Есть ли гамильтонова схема в графе по ссылке ниже?
Вроде вопрос говорит на картинке в ссылке. Есть ли hamilton circuit на графике выше? я нашел немного hamilton path лайк: c - b - a -j - i - h - f - e - d - g Но нет hamilton circuit Я не могу добавить картинку сюда, так как stackru не позволяет мне
13 янв '16 в 16:49
1
ответ
Анализ гамильтоновых путей
Мне сказали, что если бы у графа был гамильтонов путь, он не был бы рассчитан за полиномиальное время. Давайте предположим, что мы МОЖЕМ решить это за полиномиальное время, как я могу это доказать? это невозможно, так как это NP трудная проблема?
28 ноя '13 в 01:41
1
ответ
Связный граф со степенью = 2 имеет гамильтонов цикл
Извините, если мой вопрос повторяется, но я не смог найти полного ответа, чтобы доказать, что связный граф, у которого все вершины имеют степень = 2, является гамильтоновым графом. Я прочитал это и это
24 дек '14 в 06:37