2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Оптимизация дерева
Сообщение06.04.2014, 16:52 
Доброго времени суток.

Есть некий функционал заданный на графах (в первом приближении можно считать, что на корневых двоичных деревьях).

Функционал зависит от структуры дерева. Ну то есть в матрице смежности либо нуль, либо один. И такой матрицей значение функционала полностью определено.

На максимальную глубину деревьев задано ограничение, около 6-8.
Т.е. глубина в целом не очень большая, но число возможных рёбер и вершин и число разных деревьев злобно кусаются. Число элементов в матрице смежности порядка миллиона.

Первый вопрос, который у меня тут есть, до какой размерности линейный задачи (целочисленный и непрерывные) сейчас считаются задачами малой размерности.
Т.е. их решение не выливается в отдельную эпопею, а решается существующим ПО на современных системах за условно за минуты.

Попытки поиска по теме оптимизации графов уводят меня постоянно в оптимизацию потоков и путей, где функционал линейный. У меня конкретный аналитический вид функционала не известен, хотя можно пытаться делать какие-то предположения.
Второй вопрос, который меня интересует, расстраивались ли где-то кем-то задачи на графах с функционалами более общего вида. кто-нибудь сталкивался с чем-то подобным? Посоветуете, пожалуйста, литературу по теме.

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group