Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 5.00
Gref
0 / 0 / 0
Регистрация: 14.05.2011
Сообщений: 5
#1

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

22.10.2013, 17:31. Просмотров 1374. Ответов 0
Метки нет (Все метки)

У меня следующая проблема. Нужно реализовать метод ветвей и границ (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 неделя (т. е. в следующий вторник нужно будет сдать программу).
Вложения
Тип файла: txt anna.col.txt (8.3 Кб, 34 просмотров)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.10.2013, 17:31
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Написание программы для решения задачи о раскраске вершин произвольного графа (C++):

Посоветуйте литературу\статьи для написание программы - C++
Нужно: Написать программу которая при виде на конкретном сайте конкретного слова (пусть будет слово "Перейти"), нажимала на это слово...

Создание оконного приложения для решения метаматической задачи - C++ WinAPI
Нужно написать программу, решающую некую математическую задачу. Среда разработки - Visual Studio. При запуске программы должно появляться...

Написание программы для решения СЛАУ методом Зейделя - C++
#include "stdafx.h" #include <stdio.h> #include <iostream> #include <cmath> #include <conio.h> using namespace std; const...

Проложить код программы для решения школьной геометрической задачи - C++
Задача: Дано: ABCA1B1C1 – прямая треугольная призма, AB = 13, CB = 14, AC = 15, O – центр описанной окружности, C1OC = 30°. Найдите V....

Для ориентированного графа определить полустепень захода и исхода для каждой из вершин - C++
Для ориентированного графа определить полустепень захода и исхода для каждой из вершин. Вывести списки вершин с нулевой полустепенью захода...

Нужны задачи для их решения - C++
Здравствуйте. Нужны задачи для закрепления изученного материала. Что интересует(с чем я могу работать(база)): "напечатать", ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.10.2013, 17:31
Привет! Вот еще темы с ответами:

Нужны задачи для решения - C++
Здравствуйте. Если здесь есть студенты-программисты, то очень попрошу их сбросить сюда задания по С++, потому что все свои уже перерешал.

Нахождение фактора графа и остова графа для некоторого произвольного графа (5-6 вершин) - Дискретная математика
Форумчане прошу помощь в выполнение задания по деск. мат. Задание: Нахождение фактора графа и остова графа для некоторого произвольного...

Написание алгоритма для решения задачи - C#
Помогите, пожалуйста, написать алгоритм словами к этой задаче: Случайным образом формируются координаты А(X,Y) и В(X,Y) ста...

Написание программы с использованием классов для решения квадратных уравнений - C#
Доброго дня суток! Пытаюсь написать программу через классы, которая бы решала квадратные уравнения. К сожалению сам разобраться не...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru