Лекция 11. Методы разработки алгоритмов

  • Published on
    20-Jul-2015

  • View
    114

  • Download
    4

Embed Size (px)

Transcript

  • 11

    E-mail: mkurnosov@gmail.comWWW: www.mkurnosov.net

    () , 2015

  • 22

    (brute force, )

    (decomposition, )

    ( )

    ( )

    (greedy algorithms)

    (dynamic programming)

    (backtracking)

    (local search)

  • (brute force)

    ,

    a n

    an = a a a

    (brute force)

    33

    n

  • (brute force)

    44

    function pow(a, n)

    pow = a

    for i = 2 to n do

    pow = pow * a

    end for

    return pow

    end function

    TPow = O(n)

  • (brute force)

    55

    , :

    O(n3)

    /

    (Selection sort, O(n2))

    (Bubble sort, O(n2))

  • 6function strcmp(s, p)

    n = strlen(s)

    m = strlen(p)

    for i = 1 to n m do

    j = 1

    while j m then

    return i

    end if

    end for

    end function

    (String match)

    H e l l o W o r l d

    l o W o

    s

    p

    i = 4

    p s :

  • (Closest points)

    77

    . n , ( )

    : Pi = (xi, yi)

    d(i, j) :

    d(i, j) = sqrt((xi xj)2 + (yi yj)

    2)

  • 8function SearchClosestPoints(x[1..n], y[1..n])

    dmin = Infinity

    for i = 1 to n 1 do

    for j = i + 1 to n do

    d = sqrt((x[i] x[j])^2 +

    (y[i] y[j])^2)

    if d < dmin then

    dmin = d

    imin = i

    jmin = j

    end if

    end for

    end for

    return imin, jmin

    end function

    (Closest points)

    ?

  • 9function SearchClosestPoints(x[1..n], y[1..n])

    dmin = Infinity

    for i = 1 to n 1 do

    for j = i + 1 to n do

    d = sqrt((x[i] x[j])^2 +

    (y[i] y[j])^2)

    if d < dmin then

    dmin = d

    imin = i

    jmin = j

    end if

    end for

    end for

    return imin, jmin

    end function

    (Closest points)

    ?

    T = O(n2)

  • (Decomposition)

    1010

    (decomposition method, divide and conquer)

    , :

    1.

    2. ( )

    3.

    Problem = SubProblemA + SubProblemB

    A B

    Problem

  • 1111

    . a0, a1, .., an 1

    (brute force, ):

    function sum(a[0, n - 1])sum = 0for i = 0 to n - 1 do

    sum = sum + a[i]end for

    end functionTSum = O(n)

  • 1212

    . a0, a1, .., an 1.

    :

    + ++ =

    ++ + ++

    4 + 5 + 1 + 9 + 13 + 11 + 7 =

    (4 + 5 + 1) + (9 + 13 + 11 + 7) =

    = ((4) + (5 + 1)) + ((9 + 13) + (11 + 7)) = 50

  • int sum(int *a, int l, int r){

    int k;

    if (l == r)return a[l];

    k = (r - l + 1) / 2;return sum(a, l, l + k - 1) +

    sum(a, l + k, r);}

    int main() {

    s = sum(a, 0, N - 1);}

    ()

    1313

  • ()

    1414

    [0, 6]

    [0, 2] [3, 6]

    [0, 0] [1, 2]

    [1, 1] [2, 2]

    [3, 4]

    [3, 3] [4, 4]

    [5, 6]

    [5, 5] [6, 6]

    4 + 5 + 1 + 9 + 13 + 11 + 7 = (4 + 5 + 1) + (9 + 13 + 11 + 7) =

    = ((4) + (5 + 1)) + ((9 + 13) + (11 + 7)) = 50

    sum(0, 6)

  • n

    1515

    . a n

    . :

    = 2 2 , > 1

    , = 1

    TPow = O(n)

    int pow_decomp(int a, int n){

    int k;if (n == 1)

    return a;

    k = n / 2;return pow_decomp(a, k) * pow_decomp(a, n - k);

    }

  • (Decomposition)

    1616

    n n / b, a (b > 1, a 0)

    T(n) , ,

    T(n) = aT(n / b) + f(n), (*)

    f(n) ,

    (*) (general divide-and-conquer recurrence)

  • (Decomposition)

    1717

    . f(n) = (nd), d 0,

    =

    , < ,

    log , = ,

    log , > .

  • n

    1818

    b = 2 ( 2 )

    = 2 ( )

    f(n) = 1 ( 2 ( +) O(1))

    T(n) = 2T(n / 2) + 1

    f(n) = 1 = n0, d = 0, n

    = log22 =

  • (Decomposition)

    1919

    , :

    (MergeSort)

    (QuickSort)

    (Binary Search)

    (Tree traverse)

  • (MergeSort)

    2020

    function MergeSort(a[0, n - 1])if n > 1 then

    k = n / 2Copy(a[0, k - 1], b[0, k - 1])Copy(a[k, n - 1], c[0, k - 1])MergeSort(b)MergeSort(c)Merge(b, c, a)

    end ifend function

  • (MergeSort)

    2121

    function Merge(b[p], c[q], a[n])i = j = k = 0while i < p and j < q do

    if b[i] c[j] thena[k] = b[i]i = i + 1

    elsea[k] = c[j]j = j + 1

    end ifk = k + 1

    end whileif i = p then

    Copy(c[j, q - 1], a[k, p + q - 1])else

    Copy(b[i, p - 1], a[k, p + q - 1])end if

    end function

  • 2222

    b = 2 ( 2 )

    = 2 ( )

    f(n) = TMerge(n) TMerge(n) = n 1

    T(n) = 2T(n / 2) + n 1

    f(n) = n 1 = (n), d = 1,

    = log = log

    , ,

    log2 ! log2 1.44

  • 2323

    (Dynamic programming) ( )

    , ( , )

    ,

    . 1940 50-

  • 2424

    0, 1, 1, 2, 3, 5, 8, 13, 21, 34,

    F(n) = F(n 1) + F(n 2), n > 1

    F(0) = 0, F(1) = 1

    n-

    F(n) = ?

  • 2525

    function Fibo(n)

    if n

  • 2626

    Fibo(5)

    Fibo(4) Fibo(3)

    Fibo(3) Fibo(2) Fibo(2) Fibo(1)

    Fibo(1) Fibo(0)Fibo(2) Fibo(1)

    Fibo(1) Fibo(0)

    Fibo(1) Fibo(0)

    : Fibo(3), Fibo(2),

    Fibo

  • ,

    ( )

    2727

    function Fibo(n)

    F[0] = 0

    F[1] = 1

    for i = 2 to n do

    F[i] = F[i - 1] + F[i - 2]

    end for

    return F[n]

    end function

  • (Greedy)

    2828

    (Greedy algorithms) , -

    ,

    :

    o

    o

    o

    o ()

  • (Change-making problem)

    2929

    () a1 < a2 < < an

    S

    1, 2, 5 10 S = 27

    (): 2 10 ., 1 5, 1 2

    an ( )

  • (Change-making problem)

    3030

    () a1 < a2 < < an

    S

    1, 5 7 S = 24

    : 3 7, 3 1 = 6

    : 2 7, 2 5 = 4

  • 3131

    (Huffman)

    . . 1952 (, MIT)

  • 3232

    ( )

    A = {a1, a2, , an} ()

    P = {p1, p2, , pn}

    (codeword)

    (A, P) = {c1, c2, , cn}

    A B C D _

    () 11 100 00 01 101

  • 3333

    1. n

    A0.35

    B0.1

    C0.2

    D0.2

    _0.15

  • 3434

    2.

    2

  • 3535

    B _ C D A

    0.1 0.15 0.2 0.2 0.35

    B _ C D A

  • 0.25

    3636

    B _ C D A

    0.25 0.2 0.2 0.35

    B _ C D A

  • 0.25

    3737

    C D B, _ A

    0.4 0.25 0.35

    B _C D A

    0.4

  • 0.25

    3838

    C D B, _ A

    0.4 0.6

    B _

    C D

    A

    0.4 0.6

  • 0.25

    3939

    B _

    C D

    A

    0.4 0.6

    1.0

    root

  • 0.25

    4040

    B _

    C D

    A

    0.4 0.6

    1.0

    1

    1

    0

    0 1 0

    10

    A 11

    B 100

    C 00

    D 01

    _ 101

    1 0

  • (Backtracking)

    41

    (Backtracking) ,

    , , .

    Backtrack 1950 . D. H. Lehmer

    :

    o o o o o

    41

  • 4242

    6 91 11 1 1 1 1 1 1 1 11 0 0 0 0 0 1 1 11 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 11 0 0 1 0 1 1 0 1 1 1 1 1 0 1 1 1 1

    6 , 9

    : c 1, 1

    1 0 , ,

  • (Backtracking)

    4343

    int main(int argc, char **argv){

    if (argc < 2) {fprintf(stderr,

    "usage: maze \n");exit(1);

    }

    load_maze(argv[1]);print_maze();

    backtrack(startrow, startcol);

    printf("Exit not found\n");

    return 0;}

  • 4444

    void backtrack(int row, int col){

    int drow[4] = {-1, 0, 1, 0};int dcol[4] = {0, 1, 0, -1};int nextrow, nextcol, i;

    maze[row][col] = 2; // if (row == 0 || col == 0 ||

    row == (nrows - 1) || col == (ncols - 1)) {

    print_maze(); // }

    for (i = 0; i < 4; i++) {nextrow = row + drow[i];nextcol = col + dcol[i];if (maze[nextrow][nextcol] == 0) // ?

    backtrack(nextrow, nextcol);}maze[row * ncols + col] = 0;

    }

  • 4545

    1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 1 1 1 1 0 0 1 1 2 0 0 1 1 1 0 0 2 2 1 0 1 1 0 0 1 2 1 1 0 1 1 1 1 1 2 1 1 1 1

  • backtracking

    4646

    int main() {

    backtracking(1);}

    void backtracking(int step){

    save_variant();

    if (is_solution_found()) { print_solution();exit(1);

    }

    for (i = 0; i < nvariants; i++) {if (is_correct_variant())

    backtracking(step + 1); } delete_variant();

    }

  • (eight queens puzzle)

    47

    64- 8 () ,

    47

    88 , 8, ,

  • (eight queens puzzle)

    4848

    1850 . (Carl Friedrich Gaub)

    64- : 92

  • (eight queens puzzle)

    4949

    X1

  • (eight queens puzzle)

    5050

    X1X

    X

    X

    X

    X

    X

    2

  • (eight queens puzzle)

    5151

    X1X

    X

    X

    X

    X

    X

    2

    XX

    X

    3

    X

    X

    X

  • (eight queens puzzle)

    5252

    X1X

    X

    X

    X

    X

    X

    2

    XX

    X

Recommended

View more >