Алгоритм для поиска кратчайшей гамильтоновой цепи

@0xC00000FD · Регистрация: 24.08.2021

Author24 — интернет-сервис помощи студентам

Добрый день, форумчане!
Попалась задачка, в которой необходимо найти кратчайший путь, проходящий через каждую вершину в полном неориентированном графе (или же гамильтонова цепь).
Пролистал множество страниц, везде сказано, как находить гамильтонов цикл, а не гамильтонову цепь.
Пожалуйста, скиньте подробное письменное описание алгоритма для поиска, а если не трудно, то желательно в коде.
Заранее спасибо!

@SmallEvil · 24.08.2021, 18:53

0xC00000FD,

Сообщение от Материал из Википедии

Гамильтонов граф — граф, содержащий гамильтонов цикл[1]. При этом гамильтоновым циклом является такой цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу[2]; то есть простой цикл, в который входят все вершины графа.

Алгоритм поиска гамильтонова пути

Задача о гамильтоновом пути

Найти из всех существующих, кратчайший, хм, еще та задачка.
Перебором что ли ...
А нет никаких данных о самом графе ?

ну и недолго поискав, варианты :
Задача о коммивояжере

Я еще только знакомлюсь с графами, задачка хорошая.

Новые блоги и статьи
Как написать микросервис на Go/Golang с Kafka и GitHub CI/CD InfoMaster 14.01.2025 Определение микросервиса, преимущества использования Go/ Golang Микросервис – это архитектурный подход к разработке программного обеспечения, при котором приложение состоит из небольших, независимо. . .	Как написать микросервис с нуля на C# с RabbitMQ, CQRS и CI/CD InfoMaster 14.01.2025 В современном мире разработки программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот архитектурный подход предполагает. . .	Как создать интернет-магазин на PHP и JavaScript InfoMaster 14.01.2025 В современном мире электронная коммерция стала неотъемлемой частью бизнеса. Создание собственного интернет-магазина открывает широкие возможности для предпринимателей, позволяя достичь большей. . .	Как написать Тетрис на Ассемблере InfoMaster 14.01.2025 Тетрис – одна из самых узнаваемых и популярных компьютерных игр, созданная в 1984 году советским программистом Алексеем Пажитновым. За прошедшие десятилетия она завоевала симпатии миллионы людей по. . .	Как создать игру "Танчики" на Unity3d и C# InfoMaster 14.01.2025 Разработка игр – это увлекательный процесс, сочетающий в себе творчество и технические навыки. В этой статье мы рассмотрим создание классической игры "Танчики" с использованием Unity3D и языка. . .	Организую платный онлайн микро-курс по доработке Android-клиента Telegram _Ivana 14.01.2025 Официальная версия и распространенные форки не полностью устраивают? Сделай свою кастомную версию клиента! 4 занятия по 2 часа (2 недели пн, ср 19:00-21:00 по Москве). Первое вводное занятие. . .
Как создать приложение для фитнеса для iOS/iPhone на Kotlin InfoMaster 14.01.2025 Создание собственного фитнес-приложения — это не только захватывающий, но и полезный процесс, ведь оно может стать вашим верным помощником на пути к здоровому и активному образу жизни. В современных. . .	Как создать приложение магазина для iOS/iPhone на Swift InfoMaster 14.01.2025 Введение в разработку iOS-приложений Разработка приложений для iPhone и других устройств на базе iOS открывает огромные возможности для создания инновационных мобильных решений. В данной статье мы. . .	Это работает. Скорость асинхронной логики велика. Вопрос видимо останется в стабильности. Плата - огонь! Hrethgir 13.01.2025 По прошлому проекту в Logisim Evolution https:/ / www. cyberforum. ru/ blogs/ 223907/ blog8781. html прилагаю файл архива проекта в Gowin Eda. Восьмибитный счётчик из сумматора+ генератор сигнала. . .	UserScript для подсветки кнопок языков программирования в зависимости от текущего раздела volvo 13.01.2025 В результате работы этого скрипта подсвечиваются нужные кнопки не только в форме быстрого ответа, но и при редактировании сообщения: / / ==UserScript== / / @name CF_DefaultLangSelect / / . . .	Введение в модели и алгоритмы машинного обучения InfoMaster 12.01.2025 Машинное обучение представляет собой одну из наиболее динамично развивающихся областей искусственного интеллекта, которая фокусируется на разработке алгоритмов и методов, позволяющих компьютерам. . .	Как на Python создать нейросеть для решения задач InfoMaster 12.01.2025 В контексте стремительного развития современных технологий особое внимание уделяется таким инструментам, как нейросети. Эти структуры, вдохновленные биологическими нейронными сетями, используются для. . .

@0xC00000FD 0 / 0 / 0 Регистрация: 24.08.2021 Сообщений: 1
		1
	Алгоритм для поиска кратчайшей гамильтоновой цепи 24.08.2021, 16:21. Показов 2591. Ответов 1 Метки c++, алгоритмы, графы (Все метки) Добрый день, форумчане! Попалась задачка, в которой необходимо найти кратчайший путь, проходящий через каждую вершину в полном неориентированном графе (или же гамильтонова цепь). Пролистал множество страниц, везде сказано, как находить гамильтонов цикл, а не гамильтонову цепь. Пожалуйста, скиньте подробное письменное описание алгоритма для поиска, а если не трудно, то желательно в коде. Заранее спасибо! 0

@SmallEvil 3719 / 2648 / 761 Регистрация: 29.06.2020 Сообщений: 9,800
	24.08.2021, 18:53	2
	0xC00000FD, Сообщение от Материал из Википедии Гамильтонов граф — граф, содержащий гамильтонов цикл[1]. При этом гамильтоновым циклом является такой цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу[2]; то есть простой цикл, в который входят все вершины графа. Алгоритм поиска гамильтонова пути Задача о гамильтоновом пути Найти из всех существующих, кратчайший, хм, еще та задачка. Перебором что ли ... А нет никаких данных о самом графе ? ну и недолго поискав, варианты : Задача о коммивояжере Я еще только знакомлюсь с графами, задачка хорошая. 0