Нужно реализовать алгоритм, использующий метод ветвей и границ.
Язык С/С++
Точный алгоритм решения задачи аппроксимации графа A
Вход: произвольный граф G без петель и кратных рёбер, с числом вершин 20-30.
Результат: граф M* такой, что p(G,M*) = min p(G,M) // p – расстояние.
Допустимое решение – граф M – может состоять из следующих «элементов»: вершина, ребро (на 2 вершинах, соответственно), треугольник (3 вершины, 3 ребра) и никаких других. Оптимальный граф M* – граф M с наименьшей оценкой границы, т.е. с наименьшим числом удалённых рёбер.
Шаг 0. Устанавливаем для графа G оценку границы равную нулю.
Шаг 1. Если граф G не является допустимым решением, то переходим к шагу 2. Если граф G является допустимым решением, то этот граф – искомое решение. Конец.
Шаг 2. Берём в графе G произвольное ребро. В ветвлении рассматриваем следующие варианты: граф G без этого ребра (1), граф G с фиксированным этим ребром (т.е. ребро не может быть удалено на любом последующем шаге).
Граница будет оцениваться по количеству удалённых рёбер. Для (1) она увеличится на единицу, для (2) – не изменится.
Далее, среди имеющихся вариантов выбираем вариант с наименьшей границей и переходим на шаг 1.
Данный алгоритм является вариацией полного перебора, значит, очевидно, найденный граф будет оптимальным.
При необходимости могу разъяснить более подробно работу алгоритма, а также показать пример.
Нужно сделать 9 программ задания я прикрепил: там 1, 3, 5 задания и последний вариант из методички, а из ПДФ файла нужны только задачи под номерами 1.34, 3.18, 5.13 Выполнение начать нужно с задач из ПДФ, ...
Функционал: Загрузка в программу множества аккаунтов, с возможностью отображения мобильной версии страницы Од. По виду должно напоминать VikingBotovod. Обязательно установка прокси к каждому аккаунту. Поддержка страницы онлайн. Есть еще несколько мелочей. Все подробности в л/с
Требуется написать программу. Исходные данные. Дано целое число K и текстовый файл, содержащий текст, выровненный по левому краю. Абзацы выделяются в нем с помощью красной строки (5 начальных пробелов), а пустых строк нет. Отформатировать текст так, чтобы ...
Добрый день, уважаемые фрилансеры! Необходим специалист способный разработать программу-агент (виджет) для ОС Windows (ХР, Vista, 7, 8) с функциями календаря-напоминалки и вывода графических изображений (иконок) поверх рабочего стола. По всем вопросам просьба писать на ящик ...
Бюджет по договоренности Среда применения торговая электронная площадка aliexpress_com/ Получатели сообщений продавцы В обычном режиме для общения между покупателем и продавцом у aliexpress имеется встроенный чат или можно использовать отдельное ПО (кит яз: 阿里旺旺 ...
Сайту проекта "5775" (http://5775record.com) - запись самой длинной в мире песни - необходимо разработать онлайн-диктофон, совмещенный с караоке. Цель нашего проекта - записать голоса 5775 человек по всему миру, и диктофон необходим для максимального упрощения ...
Нужно написать программу для обработки данных с ексель прайса и на выходе получить нужный файл. видео ТЗ по ссылке http://yadi.sk/d/fs66H5RpN9qsV пример входящего файла, наброски ТЗ, пример 1 строчки выходящего файла в прикрепленных файлах готов за полную и человеческую ...
Здравствуйте, Нужно написать простую программу для криптования/раскриптования любых файлов для Windows7/8. Интересует полный аналог проги 4k-crypt - http://4k.com.ua/products/others/4k-crypt только с другим дизайном! Нужна сама прога и все исходники. Спасибо, жду вами предложения. Вячеслав
Необходимо сделать программу с помощью программирования. Язык не принципиален. Срок 2-4 дня
Требуется доделать выполненный приблизительно на 40-50% проект в сжатые сроки. Нужен специалист хорошо разбирающийся в чужом коде. Работа на нашей площадке. Безответственных просьба не беспокоить не отнимать время. Срок исполнения 5-7 дней. Работа только через ...