|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
22.10.2013, 19:50 | #1 |
Новичок
Джуниор
Регистрация: 11.06.2010
Сообщений: 2
|
Написание программы для решения задачи о раскраске вершин произвольного графа
У меня следующая проблема. Нужно реализовать метод ветвей и границ (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 означают его оконечные точки, которые представляют собой целочисленные значения начала и конца ребра. Пример 1 такого DIMACS-файла прикреплен к этому сообщению. На выходе программа должна вывести дерево ветвления, по которому можно было бы определить, сколько оптимально цветов (наименьшее их количество) необходимо для раскраски графа и время (в данной задачи – количество секунд или же миллисекунд, которое было потрачено на нахождение оптимальной раскраски графа; причем время, необходимое на чтение данных из файла не учитываем). Программа должна быть написана на языке C/C+ с использованием объектно-ориентированной парадигмы программирования, и чтобы мне смогли объяснить то, каким образом она работает. Может ли кто-нибудь мне помочь в этом, поскольку срок сдачи программы: 1 неделя (т. е. в следующий вторник нужно будет сдать программу) и нужно делать быстрее? |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Решения задачи,написание программы.(Паскаль) | Dr.Carlyxa | Помощь студентам | 1 | 25.12.2012 08:07 |
Для двух выделенных вершин графа построить соединяющий их просто путь. | Lombard | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 05.04.2012 21:03 |
Реализовать алгоритм Ершова для раскраски произвольного графа | Nordbank | Фриланс | 1 | 14.12.2011 19:12 |
Обход заданных вершин графа | Badrvic | Помощь студентам | 1 | 22.11.2011 12:54 |
Задание с курсовой.программа для решения дифференциальных уравнений произвольного порядка. | saydmc | Помощь студентам | 5 | 29.12.2010 23:10 |