Вісники НТУ "ХПІ"
Постійне посилання на розділhttps://repository.kpi.kharkov.ua/handle/KhPI-Press/2494
З 1961 р. у ХПІ видається збірник наукових праць "Вісник Харківського політехнічного інституту".
Згідно до наказу ректора № 158-1 від 07.05.2001 року "Про упорядкування видання вісника НТУ "ХПІ", збірник був перейменований у Вісник Національного Технічного Університету "ХПІ".
Вісник Національного технічного університету "Харківський політехнічний інститут" включено до переліку спеціалізованих видань ВАК України і виходить по серіях, що відображають наукові напрямки діяльності вчених університету та потенційних здобувачів вчених ступенів та звань.
Зараз налічується 30 діючих тематичних редколегій. Вісник друкує статті як співробітників НТУ "ХПІ", так і статті авторів інших наукових закладів України та зарубіжжя, які представлені у даному розділі.
Переглянути
3 результатів
Результати пошуку
Документ Аналіз методу відкладених рішень для пошуку гамільтонового циклу на графі(Національний технічний університет "Харківський політехнічний інститут", 2023) Прокопенков, Володимир ПилиповичПредмет досліджень є рішення задачі пошуку гамільтонова циклу на графі, яка відноситься до NP класу складності. Мета роботи – розробка ефективного поліноміального алгоритму її оптимального вирішення. Дана робота є продовженням попередньої роботи автора, де запропоновано метод відкладених рішень, який використовує перебірну схему допустимих рішень задачі, що пояснюється неможливістю n сформулювати умови для прямого знаходження оптимального рішення. Для графа з вершин розмір простору перебору становить ( 1)!.n n − Для великих значень витрати часу неприпустимо великі і потрібно їх скорочення. У процесі роботи методу відкладених рішень, поки формоване рішення задачі не стане гамільтоновим циклом, воно називається частковим рішенням. Схема, покладена в основу методу відкладених рішень, забезпечує: відмову від повної побудови усіх рішень; одночасне формування множини часткових рішень; відкидання неперспективних рішень; можливість повернення до відкладених часткових рішень при необхідності; виключення втрати оптимального рішення при відкиданні часткових рішень, але, як показано, тільки при виборі правильної оцінки часткових рішень. Спочатку у якості оцінки була використана реальна довжина шляху часткового рішення. Для неповного графа з 20 вершин оптимальне рішення було знайдено за 0,005 хвилини, але на повному графі з 20 вершин час пошуку було порівняно з перебором усіх допустимих рішень задачі. У статті виконано аналіз і показано, що реальна довжина шляху як оцінка логічно обґрунтована і гарантує знаходження оптимального рішення, але не завжди гарантує мінімальні витрати часу на його пошук, оскільки при переборі простору допустимих рішень відпрацьовується схема пошуку в ширину, що тягне побудову практично всіх допустимих рішень. Цим пояснюються різні витрати часу на пошук оптимального рішення для тестових неповного і повного графів – множини допустимих рішень істотно відрізняються. У роботі як альтернатива запропонована інша оцінка – довжина шляху часткового рішення, що вимірюється в дугах графа. Показано, що використання цієї оцінки призводить до перебору рішень в глибину. Ця оцінка скорочує час на пошук рішення, але не гарантує оптимальний результат. Для успішного застосування методу потрібна розробка нової оцінки часткових рішень, яка б поєднувала якості розглянутих оцінок.Документ Полиномиальный алгоритм поиска гамильтонова цикла на графе(Національний технічний університет "Харківський політехнічний інститут", 2021) Прокопенков, Владимир ФилипповичПредметом исследований является решение задачи поиска гамильтонова цикла на графе, которая в дискретной математике относится к NP классу сложности и по-прежнему сохраняет к себе интерес. Целью работы является разработка нового алгоритма решения этой задачи, гарантирующего нахождение оптимального решения с полиномиальными затратами времени. В работе [1] был выполнен анализ современного состояния проблемы, отмечены недостатки существующих методов решения, изложены новые принципы и метод нахождения решения. Известные методы решения задачи основаны на реализации перебора возможных вариантов решений или на интуитивных эвристиках. Методы с перебором решений неприемлемы по затратам так как характеризуются неполиномиальными затратами времени. Эвристические методы удовлетворительны по времени, но не гарантируют нахождение оптимального решения. Популярность методов перебора объясняется простотой линейного поиска в заранее известном множестве допустимых решений задачи. Но факториальная зависимость мощности множества решений (n-1)! от числа вершин графа n делает невозможным применение таких методов для задач большого размера на практике. Желание существенно снизить временные затраты приводит к попыткам обоснованного редуцирования множества перебора либо к разработке различных эвристик, что фактически свидетельствует о невозможности сформулировать условия нахождения оптимального решения задачи в целом. В данной статье представлены описание условий, определяющих нахождение оптимального решения задачи и полиномиальный алгоритм решения задачи, воплощающий описанный метод. Поиск оптимального решения задачи сводится к поиску замкнутого пути в новом графе кратчайших путей. Граф кратчайших путей строится на основе исходного графа задачи, для чего используется алгоритм Дейкстры. Множество перебора для определения оптимального решения задачи состоит из решений, которые строятся из каждой вершины графа в графе кратчайших путей. Размер этого множества оценивается как n(n -1). Разработанный параллельный алгоритм гарантирует отыскание оптимального решения, значительно сокращает исходное пространство поиска, позволяет находить решение с полиномиальной сложностью. Тестирование программы показало работоспособность разработанного метода и алгоритма решения задачи.Документ Новый метод поиска гамильтонова цикла на графе(Національний технічний університет "Харківський політехнічний інститут", 2020) Прокопенков, Владимир ФилипповичВ дискретной математике существует много задач, которые относятся к NP классу сложности. Решение этих задач имеет как теоретическую, так и практическую ценность. Одной из них является задача поиска гамильтонова цикла на графе. Целью работы является разработка нового метода и алгоритма решения этой задачи предпочтительного имеющимся по затратам времени и качеству получаемого решения. В работе выполнен анализ проблемы и существующих методов её решения, определены недостатки этих методов. Показано, что все известные методы решения этой задачи строятся на реализации перебора вариантов решений либо на интуитивных эвристиках. Первые из них характеризуются неполиномиальными затратами времени, а вторые – не обеспечивают получение оптимального решения. Причиной такого состояния является невозможность сформулировать условия, определяющие оптимальное решение задачи. В таком случае единственно возможным способом решения задачи по-прежнему остаётся перебор вариантов, а для снижения затрат нахождения решения необходимо прибегать к сокращению пространства перебора вариантов. В работе изложены новые принципы нахождения решения и предложен новый метод решения задачи. На основе нового метода разработан полиномиальный алгоритм решения задачи. Поиск гамильтонова цикла в графе сводится к поиску замкнутого пути в новом графе кратчайших путей. Для построения графа кратчайших путей используется алгоритм Дейкстры. Пространство перебора вариантов решения задачи состоит из решений, которые строятся из каждой вершины графа в графе кратчайших путей. Тестирование разработанной программы показало работоспособность разработанного метода и алгоритма решения задачи. Предложенный метод решения существенно сокращает пространство перебора и позволяет находить оптимальное решение с полиномиальной сложностью, как в полном, так и неполном графах. Рассмотренный метод пригоден для параллельной реализации, что даёт дополнительный выигрыш во времени и позволяет на всю мощь использовать параллельные возможности современных многоядерных процессоров.