Помогите люди добрые... (задача о графе)

dr_dred

Точно, я ещё вчера думал про этот случай, но вчера решил не париться
Насчёт удаления - абсолютно точно. Удалять нужно те листья получившегося дерева, которые не входят в R, поскольку очевидно, что они и только они являются лишними в дереве.

В стандартной поставке Windows - библиотека для работы с графами?! Я обалдел

 

GIo
Вот, держи.
Там и прога, и проект VS2005, и примеры входных данных.

dr_dred
С удалением лишних рёбер на твоём тесте работает правильно.

[edit]че-то файл не присоединяется, щас куда-нить закачаю[/edit]
[edit]Вот тут: http://maximal.hocomua.ru/TREE.zip[/edit]

 

maxdiver
Я просто не знаю как тебя отблагодарить! Ты мне жизнь спас!
СПАСИБО БОЛЬШОЕ! хотя на спасибо не уедешь, как тебе мож чем нить помочь? Я даже не знаю как тебе чем нить помочь......СПАСИБО!

 

GIo
Я мог бы попросить по поводу алгоритма BPSW (см. соседнюю ветку). Но что-то подсказывает мне, что ты навряд ли поможешь мне
Видимо, придётся обойтись одним "спасибом"

 

А доказательство алгоритма имеется? Возьмем граф
0 4 4 4
4 0 5 5
4 5 0 5
4 5 5 0
R={2,3,4}.
Начинаем с вершины 2. По алгоритму мы возьмем ребра (2,1), (1,3), (1,4) и потом ничего не удалим. Сумма - 12. А если взять ребра (2,3) и (2,4) то сумма будет 10.
Поздравляю с очередным "бревном".

 

halyavin
Расшифруй, плз формат входных данных. Что-то не догоняю

 

Как crypto уже заметил выше, формулировку эту можно понимать двояко:
1) Алгоритмически: дать алгоритм, находящий такое поддерево. Тогда задача эквивалентна вот этой: http://www.wasm.ru/forum/viewtopic.php?id=9102

2) Не строя дерева, ответить на вопрос, существует ли оно. Плохо представляю, как такое возможно.

Не исключен и третий вариант - спрашивающий просто недопонял или переврал поставленную ему задачу.

 

dr_dred
Входные данные - матрица смежности.
halyavin всё правильно говорит, алгос наврёт.
Надо вернуться к обсуждению алгоритма.

 

Stiver
Задача в том топике точно такая же, как и в этом. И я тоже пошёл на поводу алгоритма Прима
Но чем больше я думаю, тем больше убеждаюсь, что традиционными алгоритмами она не решается.

 

maxdiver
можно попробовать для каждой вершины алгоритм Дейкстры, потом объединить одинаковые ребра. Но что-то здесь мутно...

 

не, по любому модифицировать прийдется

 

dr_dred
См. топик, указанный Stiver'ом.
Там как раз называется алгоритм, которым на самом деле решается эта задача - алгоритм Штейнера. Без него задачу можно решить только перебором всех поддеревьев. Да и сам алгоритм не быстр (в книге Кристофидеса, где алгоритм упоминается, говорится, что за разумное время он решает графы с ~10 вершинами).
Видимо, GIo нужно написать перебор всех поддеревьев.

 

пожалуй, все же можно. Опять отбросить лишние 'сучки', и среди всех построенных графов выбрать тот, у которого минимальная сумма весов ребер. Графы строить для R.

 

Перебрать все подграфы G (подмножества множества вершин V) и для каждого алгоритмом Прима найти каркас. Среди всех каркасов выбрать наименьший по весу.
Работать будет ужас как долго - O (2^n * n^3) или, при более хорошей реализации Прима - O (2^n * n^2 * logN).

 

Выложил новую версию программы, основанную на переборе:
http://maximal.hocomua.ru/TREE.zip

GIo
Скачивай новую программу - старая была неправильная!

 

Протестировал на тесте с 20 вершинами - работает 10 сек.
Не очень. Но для перебора нормально.