4X_Pro
Руководитель Проекта
Настоящий Компьютерщик
Откуда: Москва Всего сообщений: 2994 Рейтинг пользователя: 79 Дата регистрации на форуме: 29 сен. 2001
|
Профиль | Сообщить модератору | ИгнорироватьNEW! Сообщение отправлено: 15 мая 2005 14:57
Интересно, что же это за задача такая что там столько переменных?
Но вообще, сложность зависит не только от количества переменных, но и от количества ограничений (причем в моем варианте реализации от последнего - значительно больше). Общий вид зависимости сложности сказать затрудняюсь, замечу только, что она значительно больше, чем полиномиальная, но меньше, чем экспоненциальная (т.к. у меня предусмотрена некоторая "отсчека" тупиковых вариантов при обходе дерева).
Хотя для такой большой задачи, думаю, мою версию Simplexа придется дорабатывать. Там есть особенность реализации метода ветвей и границ: я совершаю обход дерева "вглубь" т.е. сначала захожу в одну ветвь и иду до самого низа, а уже потом - в другую. Так намного проще реализовать метод программно, а для тех задач, для которых я его писал, особой разницы в производительности не наблюдалось. Но для большого количества переменных лучше было бы совершать обход не вглубь, а по ярусам, т.е. просматривать все варианты одинаковой глубины, а также сделать еще кое-какие усовершенствования.
--- Каждый человек всегда может найти, чем он может быть полезен окружающим. Проблема только в одном: слишком многие не хотят это искать.
|