thiết kế và đánh giá thuật toán - trần tuấn minh -8

Có lẽ quan trọng và áp dụng rộng rãi nhất là kỹ thuật thiết kế “Chia để trị” . Nó phân rã bài toán kích thước n thành các bài toán con nhỏ hơn mà việc tìm lời giải của chúng là cùng một cách. Lời giải của bài toán đã cho được xây dựng từ lời giải của các bài toán con này. Ta có thể nói vắn tắt ý tưởng chính của phương pháp này là : chia dữ liệu thành từng miền đủ nhỏ, giải bài toán trên các miền đã chia rồi tổng hợp kết quả...
Nội dung trích xuất từ tài liệu:
thiết kế và đánh giá thuật toán - trần tuấn minh -8 Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 113 - ⎧1; Neáu a i = b j trong ñoù : x = ⎨ ⎩0; Ngöôïc laïi Ta coù theå xem L laø moät m × n ma traän : (Lij)mxn.Ta tính vaø laøm ñaày caùc phaàn töû cuûa ma traän naøycoù theå xem Tính Lij, caàn phaûi bieát Li , j −1 , Li −1, j , Li −1, j −1 . Ta tính caùc phaàn töû cuûa ma traän L töø goùc beân traùi laàn löôït theo caùc ñöôøng cheùo song song vôùi ñöông cheùo ngöôïc 1 2 3 j ... n 1 2 3 . i Lij . X . Lmn m X Input a,b,m,n Output L Qhd(a,m,b,n,L) ≡ for (i = 1; i Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 114 - return Lmn ; Ghi chuù : Ñeå tìm daõy c töø ma traän L, ta xuaát phaùt töø oâ Lmn . Giaû söû ñang ôû oâ Lij , vaø caàn xaùc ñònh ci . (1 ≤ i ≤ Lmn ). Neáu ai = bj thì ci = ai , coøn ngöôïc laïi thì Lij = Li,j-1 hoaëc Lij = Li-1,j . Neáu Lij = Li,j-1 ta ñi ñeán oâ Li,j-1, coøn neáu Lij = Li-1,j thì ñi ñeán oâ Li-1,j Minh hoïa : Vôùi döõ lieäu a, b nhö treân, ta coù : ⎡0 1⎤ 0 1 1 1 ⎢0 2⎥ 1 1 2 2 ⎢ ⎥ ⎢1 3⎥ 1 1 2 2 L = (Lij )7×6 ⎢ ⎥ 3⎥ ; c = ( 1, 5, 5, 3) = ⎢1 1 2 2 3 ⎢1 3⎥ 2 2 3 3 ⎢ ⎥ ⎢1 2 2 3 3 3⎥ ⎢1 4⎥ 2 3 3 4 ⎣ ⎦ 4. Ñoä phöùc taïp cuûa thuaät toaùn T(n) ∈ O(n2 ). 5. Caøi ñaët int Bt_Dcnd(int a[MAX], int m, int b[MAX], int n, int L[MAX][MAX]) { int i, j, x; for (i = 1; i Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 115 - else x = 0; L[i][j] = Max(L[i][j-1], L[i-1][j], L[i-1][j-1]+ x); } int k = L[m][n]; return k; } //******************* void Dcdn(int a[MAX],int b[MAX],int m,int n,int L[MAX][MAX],int c[MAX], int &l) { int i = m, j = n; l = 0; while ( i > 0 && j > 0) { if( a[i] == b[j]) { l++; c[l] = a[i]; i--; j--; } else if(L[i][j] ==L[i][j-1]) j--; else i--; } for(i = 1; i Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 116 - 1. YÙ töôûng Giaû söû coù moät chu trình thoûa yeâu caàu baøi toaùn vaø baét ñaàu töø ñænh 1 veà ñænh 1. Khi ñoù chu trình naøy bao goàm cung (1,k), vôùi k ∈ V\{1}, vaø ñöôøng ñi töø k ñeán 1, ñi qua moãi ñænh coøn laïi thuoäc V\{1,k}, moãi ñænh ñuùng 1 laàn. Neáu chu trình naøy coù troïng soá nhoû nhaát ( toái öu ), thì theo nguyeân lyù toái öu ñöôøng ñi töø k ñeán 1 cuõng coù troïng s ...