| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > построить дерево оптимального поиска |
| Автор: марина 21.4.2007, 23:05 |
| нужны ссылки, не могу найти понятное обьяснение алгоритма, как построить дерево оптимального поиска с помощью динамического программирования... или код на java или c++ с комментариями, по которому можно понять что в нем происходит не понятно следующее почему именно так взаимодейтвуют друг с другом таблицы T и P И как из них находить уже это оптимальное дерево, или его вообще надо находить во время построения этих таблиц static int[] p = { 3, 10, 5, 15, 5, 9, 20, 10, 5, 18 }; static int n = p.length; static int[][] T = new int[n][]; static int[][] P = new int[n][]; public static int optimum() { for (int i = 0; i < n; ++i) { T[i] = new int[n]; T[i][i] = p[i]; P[i] = new int[n]; P[i][i] = p[i]; } for (int d = 1; d < n; ++d) { // по диагоналям for (int i = 0; i < n-d; ++i) { // по элементам диагонали P[i][i+d] = p[i] + P[i+1][i+d]; T[i][i+d] = Math.min(T[i][i+d-1], T[i+1][i+d]); for (int j = i; j < i+d-1; ++j) { // выбор минимума int s = T[i][j] + T[j+2][i+d]; if (s < T[i][i+d]) T[i][i+d] = s; } T[i][i+d] += P[i][i+d]; } } return T[0][n-1]; } |