Алгоритм, использующий метод ветвей и границ. С++

  1. Биржа фриланса
  2. Прикладное ПО
Завершен1 заявка275 просмотров
Найдите исполнителя для вашего проекта прямо сейчас!
Разместите заказ на фриланс-бирже и предложения поступят уже через несколько минут.

Нужно реализовать алгоритм, использующий метод ветвей и границ.

Язык С/С++

Точный алгоритм решения задачи аппроксимации графа 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.

Данный алгоритм является вариацией полного перебора, значит, очевидно, найденный граф будет оптимальным.

При необходимости могу разъяснить более подробно работу алгоритма, а также показать пример.

11 лет назад
LiderJob
Иван 
40 лет
17 лет в сервисе
Был
4 года назад

Выбранный исполнитель

winnie-the-p00h
Алексей 
39 лет
12 лет в сервисе
Был
4 года назад
11 лет назад
$28
3 дня
спасибо за работу. Очень все быстро и профессионально. Рекомендую
Четкая постановка задачи, быстрая оплата, сотрудничество оставило положительные впечатления, рекомендую.

Заявки фрилансеров

winnie-the-p00h
Алексей 
39 лет
12 лет в сервисе
Был
4 года назад
11 лет назад

  • Похожие заказы

  • Программа для социальной сети Одноклассники

    $250

    Функционал: Загрузка в программу множества аккаунтов, с возможностью отображения мобильной версии страницы Од. По виду должно напоминать VikingBotovod. Обязательно установка прокси к каждому аккаунту. Поддержка страницы онлайн. Есть еще несколько мелочей. Все подробности ...

    Прикладное ПО1 заявка
    Закрыт
    11 лет назад

  • Форматирование текста

    $28

    Требуется написать программу. Исходные данные. Дано целое число K и текстовый файл, содержащий текст, выровненный по левому краю. Абзацы выделяются в нем с помощью красной строки (5 начальных пробелов), а пустых строк нет. ...

    Delphi
    Прикладное ПО1 исполнитель
    Завершен
    11 лет назад

  • Разработать виджет- календарь с выводом картинок

    Добрый день, уважаемые фрилансеры! Необходим специалист способный разработать программу-агент (виджет) для ОС Windows (ХР, Vista, 7, 8) с функциями календаря-напоминалки и вывода графических изображений (иконок) поверх рабочего стола. По всем вопросам ...

    Прикладное ПО1 заявка
    Закрыт
    11 лет назад

  • Разработка ПО для автоотправления сообщений

    $500

    Бюджет по договоренности Среда применения торговая электронная площадка aliexpress_com/ Получатели сообщений продавцы В обычном режиме для общения между покупателем и продавцом у aliexpress имеется встроенный чат или можно использовать ...

    Прикладное ПО4 заявки
    Закрыт
    11 лет назад

  • Разработка онлайн-диктофона

    $500

    Сайту проекта "5775" (http://5775record.com) - запись самой длинной в мире песни - необходимо разработать онлайн-диктофон, совмещенный с караоке. Цель нашего проекта - записать голоса 5775 человек по всему миру, и диктофон ...

    Прикладное ПО1 заявка
    Закрыт
    11 лет назад

  • Простая программа для криптования/раскриптования л

    $250

    Здравствуйте, Нужно написать простую программу для криптования/раскриптования любых файлов для Windows7/8. Интересует полный аналог проги 4k-crypt - http://4k.com.ua/products/others/4k-crypt только с другим дизайном! Нужна сама прога и все исходники. ...

    Прикладное ПО1 исполнитель
    Завершен
    11 лет назад

  • Требуется закончить сложный проект на C# NET4

    $2500

    Требуется доделать выполненный приблизительно на 40-50% проект в сжатые сроки. Нужен специалист хорошо разбирающийся в чужом коде. Работа на нашей площадке. Безответственных просьба не беспокоить не отнимать время. Срок исполнения 5-7 дней. Работа только через ...

    Прикладное ПО1 исполнитель
    Завершен
    11 лет назад