ОБЗОР МЕТОДОВ И АЛГОРИТМОВ ПОИСКА ХРОМАТИЧЕСКОГО ЧИСЛА ГРАФА
Journal Title: ΛΌГOΣ. МИСТЕЦТВО НАУКОВОЇ ДУМКИ - Year 2019, Vol 1, Issue 5
Abstract
Рассматривается задача поиска хроматического числа эвристическими методами. Целью работы является анализ эвристических методов и описание вычислительных экспериментов с помощью программы для эвристической оценки хроматического числа. Рассмотрены такие методы как жадный алгоритм, метод полного перебора, метод случайного перебора, а также метод перебора с ограничением в глубину. Проведены эксперименты, целью которых является оценка качества решений, формируемых различными методами. Сравнение результатов, даваемых различными методами для графов, различающихся такими свойствами как, например, число вершин и плотность связей, в зависимости от параметров поиска конкретных методик, дает данные для анализа актуальности использования этих методов для решения конкретных практических задач, таких как составление расписаний, кластерный анализ, вычисление производных, распараллеливание численных методов, распределение частот, цифровые знаки, распределение регистров процессора.
Authors and Affiliations
Алексей Денисенко
Keywords
Related Articles
- EP ID EP662155
- DOI -
- Views 205
- Downloads 0
МАТЕРИАЛЬНОЕ ПОЛОЖЕНИЕ НАСЕЛЕНИЯ УКРАИНЫ: ВЕКТОРЫ ИЗМЕНЕНИЙ И СОЦИОСТРУКТУРНАЯ ДИФФЕРЕНЦИАЦИЯ
В статье рассмотрены самооценки материального состояния респондентов и их семей, принадлежащих к разным демографическим и социальных категориям. Эмпирической базой работы послужили данные проекта Института социологии НАН...
«СЛУГА З ДОБРОМИЛЯ» ГАЛИНИ ПАГУТЯК: ІНТЕРТЕКСТУАЛЬНЕ ПІДҐРУНТЯ ТВОРУ
Виявлено тексти, з якими пов’язаний роман Галини Пагутяк «Слуга з Добромиля». Погруповано та проаналізовано способи інтертекстуальності. Простежено найміцнішу біблійну основу. Вказано на призначення міжтекстових зв’язків...
ПРО ЕФЕКТИВНІСТЬ АЛГОРИТМІВ ПОШУКУ ГЛОБАЛЬНОГО ЕКСТРЕМУМУ В СИСТЕМІ WOLFRAM MATHEMATICA
Приведено результати обчислювалього експерименту по знаходженню мінімального значення функцій декількох змінних за допомогою алгоритмів, вбудованих в систему Wolfram Mathematica. Показана неефективність метода Нелдера–Мі...
COMPLICATIONS IN THE GESTATION PERIOD IN PATIENTS WITH DYSAUTONOMIA
Vegetovascular vascular dystonia (VSD) can lead to complications of pregnancy, childbirth, the postpartum period, respectively, an increase in perinatal mortality, which adversely affects the further development of the c...
КОНДИЦІЙНІ ЗОБОВ’ЯЗАННЯ В ЦИВІЛЬНОМУ ПРАВІ
Стаття присвячена дослідженню правової природи зобов’язань, що виникають з набуття, збереження майна без достатньої правової підстави. З’ясуванню також підлягають питання підстави виникнення зазначених зобов’язань, суб’є...