Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Алгоритмы
Перезагрузить страницу Вычислить теоретическую сложность алгоритма
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
timmy8823 timmy8823 вне форума
Новичок
 
Сообщений: 1
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.09.2011
Question Вычислить теоретическую сложность алгоритма - 23.09.2011, 16:35

Здравствуйте!
Есть алгоритм, которому на вход подаются два ордерева(ациклический связанный граф). Требуется найти максимально общий подграф ,который вкладывается в оба исходных ордерева.
Идея алгоритма заключается в рекурсивном отображении вершин одного ордерева на другое: начиная с какого-то начального отображения (запуск рекурсии), на каждом шаге анализируются новые отображения, которые опять же передаются в рекурсивную часть и т.д.
Например у нас есть два ордерева G1 = (V1,E1) (левое), G2=(V2,E2) (правое)

http://s52.radikal.ru/i136/1109/6f/b6bdbedce5dc.png

вершины G1 будем отображать на G2
Начнем, например с отображения (1-1) и запускаем рекурсию
reccur_func(1,1);
В теле этой функции определяется вершины окрестности 1 в G1: 2,3 и их отображаем на вершины окрестности 1 в G2, т.е. получаем новые отображения (2-2), (2-3) и (3-4) и отправляем их опять в рекурсивную часть
reccur_func(2,2); reccur_func(2,3); reccur_func(3,4); ... и т.д.

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

Требуется найти теоретическую сложность такого алгоритма. Я просто никогда этим не занимался, могу определить лишь для простых алгоритмов. Уже смотрел соответствующую литературу Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. Готового ответа на данный вопрос там естественно нету, но есть определенные наброски на эту тему. Но не могу это сейчас осилить, так как время поджимает. Короче, горю!

Одна надежда на ВАС, помогите пожалуйста, если вы хоть что-то знаете по этой теме! Тех кто поможет я обязательно отблагодарю
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
скорость выполнения алгоритма wm5 Вопросы начинающих программистов 3 14.09.2011 18:25
serious sam HD first encoun-сложность mental polka Компьютерные игры 0 12.02.2011 18:53
Изучение алгоритма Дейкстры 4ma Вопросы начинающих программистов 1 07.06.2007 21:53
Сложность n*log как работать с этой функцией nattefrost С/С++ 3 22.01.2006 16:42
Детали А*алгоритма tentul Prolog 3 20.10.2005 15:44
В чем суть алгоритма А Anton Y. Yakovlev Алгоритмы 6 24.09.2005 13:32
Нужна идея для алгоритма. Shurik_A PHP 9 05.06.2005 01:42
Проблема с реализацией алгоритма DSA Dungeon_Keeper Алгоритмы 1 04.05.2005 15:19
Написание алгоритма для математики Vlrus Вопросы начинающих программистов 2 24.06.2004 04:18



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов