Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/2: Рейтинг темы: голосов - 2, средняя оценка - 5.00
cancrushem
0 / 0 / 0
Регистрация: 03.07.2014
Сообщений: 2
1

Алогоритм поиска поиска покрывающего дерева (Minimal Ratio Spanning Tree)

04.07.2014, 17:10. Просмотров 438. Ответов 3
Метки нет (Все метки)

Задача которую мне необходимо решить сводится к нахождению Minimal Ratio Spanning Tree.
Условие вкратце - дан граф (связный и обыкновенный). Каждое ребро графа имеет 2 веса (допустим Ai и Bi для i-го ребра). Надо найти покрывающее дерево у которого минимально отношение (сумма(Ai)/сумма(Bi)) ребер, входящих в такое дерево. Так и не удалось найти алгоритм, который находит оптимальное поддерево при любых входных данных . Изначально я пытался модифицировать алгоритм Прима, но там не совсем понятно, как реализовать нахождение оптимального ребра на каждом шаге. Прошу помочь мне с данной проблемой.

Добавлено через 22 часа 49 минут
Я так и не смог найти нормальное описание алгоритма поиска такого дерева в литературе - только намеки. Могу запостить описание того алгоритма, который на данный момент написан. Имеются подозрения, что он некорректно обработает определенные графы, хотя неплохо работает на примитивных примерах.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.07.2014, 17:10
Ответы с готовыми решениями:

Spanning-Tree protocol
Подскажите мне пожалуста админы как мне настроить топологию STP - на порте fa0/2 Switch2 настроить...

Spanning-tree protocol портами на коммутаторе
Доброго времени суток! Господа помогите - есть cisco 3560G (24 порта) 1-7 порт находяться в...

Защита сети от колец, или как настроить грамотный spanning tree на Cisco
Добрый день. Имеется такой вопрос: Появилась необходимость защитить сеть от вероятности...

Алгоритм покрывающего дерева; третий этап; поиск назначенных коммутаторов и портов
То есть, ребята с первыми двумя этапами я более или менее разобрался. А со вторым не могу. Итак,...

Реализация дерева поиска
Мне крайне срочно необходимо реализовать дерево поиска на с++(чтобы пользователь сам вводил...

3
salam
187 / 168 / 29
Регистрация: 10.07.2012
Сообщений: 782
04.07.2014, 18:00 2
Задача NP-трудная. Пишите перебор. Если есть интерес, попробуйте придумать какие-то оптимизации.

Добавлено через 2 минуты
задача NP-трудная. пишите перебор. если есть интерес, попридумывайте какие-то оптимизации.
0
cancrushem
0 / 0 / 0
Регистрация: 03.07.2014
Сообщений: 2
05.07.2014, 09:01  [ТС] 3
То есть кроме перебора всех покрывающих деревьев других вариантов нет ?
0
salam
187 / 168 / 29
Регистрация: 10.07.2012
Сообщений: 782
05.07.2014, 09:30 4
Если вы хотите получить наилучшее решение - изучайте литературу.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.07.2014, 09:30

Удаление вершины дерева поиска
Здравствуйте. Не получается написать удаление вершины из дерева поиска, что бы после удаления,...

Высота бинарного дерева поиска
Что неправильно в программе? Полное условие #include <iostream> #include <cstdio> #pragma...

Реализация бинарного дерева поиска
Задача: Реализация бинарного дерева поиска Компилируется нормально, а при запуске выбивает ошибку...


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

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

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