Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 26 views

    Backtracking 1

    Uploaded by

    RATNESHWAR 20BAI1192
    Backtracking is an algorithmic technique for solving problems by incrementally building candidates to the solutions, and abandoning each partial candidate ("backtracking") as soon as it is determined that the candidate cannot possibly be completed to a valid solution. The document provides definitions of backtracking and describes how it works using the 8-Queens problem as an example. It outlines the formal representation of the problem as an n-tuple, defines the criterion function, and explains how backtracking minimizes test cases by pruning search spaces and backtracking to previous states when no solution is found.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Backtracking 1

    Uploaded by

    RATNESHWAR 20BAI1192
    26 views18 pages
    Backtracking is an algorithmic technique for solving problems by incrementally building candidates to the solutions, and abandoning each partial candidate ("backtracking") as soon as it is determined that the candidate cannot possibly be completed to a valid solution. The document provides definitions of backtracking and describes how it works using the 8-Queens problem as an example. It outlines the formal representation of the problem as an n-tuple, defines the criterion function, and explains how backtracking minimizes test cases by pruning search spaces and backtracking to previous states when no solution is found.

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Backtracking is an algorithmic technique for solving problems by incrementally building candidates to the solutions, and abandoning each partial candidate ("backtracking") as soon as it is determined that the candidate cannot possibly be completed to a valid solution. The document provides definitions of backtracking and describes how it works using the 8-Queens problem as an example. It outlines the formal representation of the problem as an n-tuple, defines the criterion function, and explains how backtracking minimizes test cases by pruning search spaces and backtracking to previous states when no solution is found.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    26 views18 pages

    Backtracking 1

    Uploaded by

    RATNESHWAR 20BAI1192
    Backtracking is an algorithmic technique for solving problems by incrementally building candidates to the solutions, and abandoning each partial candidate ("backtracking") as soon as it is determined that the candidate cannot possibly be completed to a valid solution. The document provides definitions of backtracking and describes how it works using the 8-Queens problem as an example. It outlines the formal representation of the problem as an n-tuple, defines the criterion function, and explains how backtracking minimizes test cases by pruning search spaces and backtracking to previous states when no solution is found.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    You are on page 1of 18

    Backtracking

    Definition
    • According to Wiki

    Backtracking can be defined as a general algorithmic


    technique that considers searching every possible
    combination in order to solve a computational
    problem.
    Practical Example – Maze Problem
    Formal Notion of Backtracking
    • Desired Solution is represented as an 𝑛 −
    𝒕𝒖𝒑𝒍𝒆 (𝒗𝒆𝒄𝒕𝒐𝒓) denoted by (𝒙𝟏, 𝒙𝟐 , 𝒙𝟑 , …, 𝒙𝒏 )
    where each 𝑥𝑖 are chosen from some finite set 𝑆𝑖 .

    • Define a criterion function 𝑷(𝒙𝟏, 𝒙𝟐 , 𝒙𝟑 , …, 𝒙𝒏).

    • Aim is to seek some or all of the vectors (𝑥1, 𝑥2, 𝑥3,


    …, 𝑥 𝑛 ) that maximize / minimize / satisfy 𝑃(𝑥1, 𝑥2,
    𝑥3, …, 𝑥 𝑛 ).
    Backtracking approach
    • Brute Force approach
    – tests all the vectors to find those
    vectors that satisfy 𝑃.
    • Backtracking
    – Minimizes the test cases by pruning search if a
    solution that satisfies 𝑃 cannot be found further.
    – Traces back to the most previous state and
    searches an alternative path for a possible
    solution vector.
    8-Queens Problem
    Problem Definition

    Given an (8 × 8) chess board, the problem is to


    place 8 Queens on the board so that no two
    Queens attack each other, (i.e.) no two Queens
    are on the same row, same column or same
    diagonal.
    8-Queens Problem – Formal Definition
    • Let (𝑖, 𝑗) represent a grid of the chess board
    where, 𝑖, 𝑗 = 1,2, … , 8.
    • Assume each queen 𝑄𝑖 is to be placed on
    the
    𝑖 𝑡 ℎ row. Here, 𝑖 = 1,2, … , 8.
    • All solutions of the 8-Queens problem can
    therefore be represented as a vector𝑃(𝑥1 ,
    𝑥2 ,
    𝑥 3, …, 𝑥8) where 𝑥𝑖 represents the column in
    𝑡ℎ
    Example of a Solution space
    𝑄1
    𝑄2
    𝑄3
    𝑄4

    (𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 ,𝒙𝟒 ) = (𝟐, 𝟒, 𝟏,


    𝟑)
    How Backtracking works in 4-Queens
    1 1 1

    2 2

    - Not possible to place the 3rd Queen


    - Backtrack to the previous state

    Note that a state refers to the board with current sub-set of Queens placed on the board.
    1 1 1

    2 2

    2
    - We are unable to place the 4𝑡ℎQueen
    3
    - Backtracking to displace the 3𝑟 𝑑 Queen
    1 1 1

    2 2

    - Note that Queen 3 cannot be placed in either (3,3 or (3,4)


    - Backtrack to the parent node.
    1 1

    - Note that all possible positions of Queen 2 have been explored


    - Backtrack to the parent node.
    1 1 1

    2 2

    1
    2

    4
    Recursive Backtracking algorithm
    procedure NQueens(𝑛, 𝑘)
    integer X[1…n]
    for 𝑙 ≔ 1 to 𝑛 do
    if ( 𝑃𝑙𝑎𝑐𝑒(𝑘, 𝑙)) then
    {
    𝑋[𝑘] = 𝑙;
    if (𝑘 = 𝑛) then
    print 𝑋[𝑙], 𝑙 = 1,2,
    …,𝑛
    else
    NQueens(𝑛, 𝑘 + 1);
    }
    Backtracking algorithm Contd..
    procedure Place 𝑘, 𝑙
    // Let (𝑗, 𝑋[𝑗]) represent the 𝑗 𝑡 ℎ Queen in
    the
    𝑋[𝑗]𝑡 ℎ column for 𝑗 = 1, 2, … , 𝑘 − 1.
    forif𝑗 (≔(X[𝑗]
    1 to=𝑘 𝑖)
    − or
    1 do
    (𝑋 𝑗 = |𝑗 − 𝑘|) )
    −𝑙
    return false;
    return
    true;
    Efficiency (𝑛!)
    With n=4, T(n) = T(4) = 4! = 24
    Practice Problem
    Consider an (𝑛 × 𝑛) chess board where (𝑖, 𝑗)
    represents a grid on the chess board. The
    problem is to place several queens on the board
    so that each grid (𝑖, 𝑗) is covered/attacked/seen
    by at least one queen. Write a recursive
    backtracking algorithm to minimize the number
    of queens required to cover all the grids.
    Reference
    s
    • Cormen, Thomas H.; Leirson, Charles E.; Rivest,
    Ronald L.; Stein, Clifford (2009) Introduction to
    Algorithms (3rd ed.). MIT Press and McGraw-Hill.

    • Ellis Horowitz, Sartaj Sahni: Fundamentals of


    Computer Algorithms. Computer Science
    Press 1978
    •

    You might also like