Написание программы для решения задачи о раскраске вершин произвольного графа - C++ - Ответ 5219286

@Gref · Регистрация: 14.05.2011

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

У меня следующая проблема. Нужно реализовать метод ветвей и границ (Branch-and-Bound algorithm) для решения проблемы раскраски вершин (Vertex Coloring Problem) произвольного графа 2 способами: 1 способ – использовать жадный алгоритм для перебора цветов и нахождения оптимальной раскраски вершин графа (нет начального решения, нет оценки на число цветов снизу), 2 способ – использовать определенную эвристику, на основании нее находим начальное решение: это будет Upper Bound для нашей задачи, далее загоняем это решение в 1 способ и находим оптимального решение. На вход подаются несколько различных файлов, каждый из которых имеет один и тот же формат представления графов DIMACS. Теперь подробнее о том, что представляет собой формат представления графов DIMACS. Основные элементы формата DIMACS:
1. Комментарий. Каждая линия комментария начинается с буквы «c» в нижнем регистре. Например: c This is an example of a comment line.
2. Строка, описывающая проблему. Эта строка появляется прежде, чем строки-описатели узлов или же дуг графа. Она имеет следующий формат:
p FORMAT NODES EDGES
Символ «p» означает то, что дальше идет описание проблемы. Поле FORMAT содержит слово «edge». Поле NODES представляет собой целое число, означающее число узлов в графе (нумерация идет от 1 до NODES). Соответственно, поле EDGES представляет собой также целое число и определяет количество ребер в этом же графе.
3. Описатели ребер. Существует одна строка-описатель ребер для каждого ребра графа, которая имеет следующий формат: каждое ребро (v, w) появляется точно один раз во входном файле, оно может и повторяться в виде (w, v). Например:
e W V
Символ c означает то, что это строка-описатель ребер. Для ребра (w, v) поля W и V означают его оконечные точки, которые представляют собой целочисленные значения начала и конца ребра.
Пример DIMACS-файла прикреплен к этому сообщению.
На выходе программа должна вывести дерево ветвления, по которому можно было бы определить, сколько оптимально цветов (наименьшее их количество) необходимо для раскраски графа и время (в данной задачи – количество секунд или же миллисекунд, которое было потрачено на нахождение оптимальной раскраски графа; причем время, необходимое на чтение данных из файла не учитываем).
Программа должна быть написана на языке C/C+ с использованием объектно-ориентированной парадигмы программирования, и чтобы мне смогли объяснить то, каким образом она работает. Срок сдачи: 1 неделя (т. е. в следующий вторник нужно будет сдать программу).

Вернуться к обсуждению:
Написание программы для решения задачи о раскраске вершин произвольного графа C++

Другие темы раздела
C++ Подскажите пожалуйста движок для создания игр с пониманием основ языка Cи и С++. https://www.cyberforum.ru/ cpp/ thread984433.html Подскажите пожалуйста движок для создания игр с пониманием основ языка Cи и С++. Для начала, с чего то то нужно начинать... Просто кроме Unity3D который для C# и Java и CryEngine не знаю...	C++ Системный таймер Как присвоить переменной значение системного таймера?
C++ С++ Direct3D Intro3dGame https://www.cyberforum.ru/ cpp/ thread982197.html Изучаю книгу Intro 3D Game остановилься на теме 11.4.3 Пример приложения: ограничивающие объемы. В VS 2010 выдает ошибку: error LNK2019: ссылка на неразрешенный внешний символ "public: __thiscall d3d::BoundingBox::BoundingBox(void)" (??0BoundingBox@d3d@@QAE@XZ) в функции "bool __cdecl Setup(void)" (?Setup@@YA_NXZ) и error LNK2019: ссылка на неразрешенный внешний символ "public: __thiscall...	C++ Есть ли решение Привет всем. Есть вопрос, есть макет документа в visio нужно в указанны места вставлять данные программно и потом отправлять на печать. Можно ли это как-нибудь реализовать. Или же на с++ можно вовсе взаимодействовать с документами visio https://www.cyberforum.ru/ cpp/ thread979730.html
Почему С++ так востребован? C++ Подскажите, почему С++ так востребован? Я думаю синтаксис удобнее у СШарп чем у С++. Да и С++ вроде бы как уже устаревший язык...	C++ Точка входа должна быть определена https://www.cyberforum.ru/ cpp/ thread978225.html Вообщем начал изучать SDL.Во время выполнение первой же программы случилась как я раньше считал глупая ошибка.Вот код CApp.cpp: #include "CApp.h" CApp::CApp() { Running = true; } int CApp::OnExecute() {
C++ Планирование процессов Реализовать программу-диспетчер управления процессами (потоками). На вход системы поступает К задач. Каждая из задач состоит из 3-х процессов. Первый заполняет текстовый файл Х случайными числами типа int (a1.exe size fname), числа хранятся по одному в строке. Второй - сортирует файл заданным методом (a2.exe fname). Третий - подсчитывает контрольную сумму всех чисел файла и дописывает ее... https://www.cyberforum.ru/ cpp/ thread978180.html	C++ Разработать и получить на экране рисунок обложки учебника Очень нужна ваша помощь. Разработать и получить на экране рисунок обложки какого-либо учебника вместе с названием, фамилиями авторов, рисунками, отражающими суть предмета. Буду очень благодарен за любую помощь
C++ Как сделать, чтобы консоль не мигала Всем доброго времени суток. У меня в программе WinAPI такой фрагмент: f=popen(<обращение к консольной программе>,"r"); <ввод с потока f> pclose(f); Все работает, но пока этот фрагмент выполняется, заметное время открывается и закрывается окно консоли. Нельзя ли как-нибудь устранить это мигание консольного окна ? https://www.cyberforum.ru/ cpp/ thread968488.html	C++ Совет https://www.cyberforum.ru/ cpp/ thread967767.html Помогите решить языке программирования мне начать учить ООП + Delphi + C / / / каким именно?? + Java + PHP + Ваш совет. Я знаю Паскаль и С++ только без использования ООП.Буду писать программы 1 раз. P.S.Знаю раздел "Мимо".:)
Функции для клавишей в OpenGL C++ Нашел в OpenGL 2 функции одна для клавиш движения...вторая использует ASCII...непойму почему разработчкики не обединили функции...вообще нашел другую API функцию GetAsyncKeyState, глядя в гугл нашел примеры использования if(GetAsyncKeyState(VK_ESCAPE)) exit(0); if(GetAsyncKeyState('w')) exit(0); ни первый ни второй не работает, использую Win7, пишу игру на OpenGL...что не так с функцией API???	C++ Описать процесс чтения и записи для АЦП Описать процесс чтения и записи для АЦП нужно на С по временным диаграммам программно описать процессы записи/чтения АЦП AD7718 сигналы описать. вот тут ниже есть диаграмма чтения и программа для нее (то, что обведенно, это прога для чтения по нижней диаграмме). надо написать программу на С для ЗАПИСИ только уже по верхней диаграмме, сможете помочь помочь с этим? помогите пожалуйста, не... https://www.cyberforum.ru/ cpp/ thread965096.html

	22.10.2013, 17:31