.
 Vyom World.com  . Let's Touch the Sky Together!  
.
. . . . . . .
 Home
VyomWorld.com Home
Free Magazines!
VyomLinks.com Home
JobsAssist.com Home
Vyom Network
Contact Us
 Jobs & Careers
Resume Submitter
Placement Papers
IT Companies Directory
Computer Jobs
Interview Questions
Online Exams
Vyom Career eMag.
 Fun
Screensavers New!
Send FREE SMS!
SMS Jokes
 Source Codes Library
Source Codes Home
ASP Source Codes
C Source Codes
C++ Source Codes
COBOL Source Codes
Java Source Codes
Pascal Source Codes
Submit Source Codes
 GATE
GATE an Overview
GATE Preparation
Study Materal
 GRE
GRE an Overview
GRE Questions
GRE Preparation
GRE Universities
 TOEFL Preparation
TOEFL Resources
 GMAT Preparation
GMAT Resources
 MBA Preparation
MBA Resources
 Networking Concepts
Networking Concepts
 Testing Preparation
Testing Resources
 Webmasters
Free Traffic Builder
Webmaster Articles
Web Hosting
 Tutorials
Hardware Tutorial
1500 Free eBooks New!
 FREE Publications
Vyom Career eMag.
 
.
Get 9,000+ Interview Questions & Answers in an eBook.


  • 9,000+ Interview Questions
  • All Questions Answered
  • 5 FREE Bonuses
  • Free Upgrades

    Get it now!


    Post your Resume to 5800+ Companies

    Reliable Web Hosting

  •  
     
     
    Get 9,000+ Interview Questions with Answers in an eBook


     Home

    Analysis and Design of Algorithms


    Advertisements
    Advertisements

    6.1 Backtracking

    Problems, which deal with searching a set of solutions, or which ask for an optimal solution satisfying some constraints can be solved using the backtracking formulation. The backtracking algorithm yields the proper solution in fewer trials.

    The basic idea of backtracking is to build up a vector one component at a time and to test whether the vector being formed has any chance of success. The major advantage of this algorithm is that if it is realized that the partial vector generated does not lead to an optimal solution then that vector may be ignored.

    Backtracking algorithm determine the solution by systematically searching the solution space for the given problem. This search is accomplished by using a free organization. Backtracking is a depth first search with some bounding function. All solutions using backtracking are required to satisfy a complex set of constraints. The constraints may be explicit or implicit.

    Explicit constraints are rules, which restrict each vector element to be chosen from the given set. Implicit constraints are rules, which determine which of the tuples in the solution space, actually satisfy the criterion function.





    6.1.1 Cassette filling problem:

    There are n programs that are to be stored on a tape of length L. Every program i is of length li. All programs can be stored on the tape if and only if the sum of the lengths of the programs is at most L. In this problem, it is assumed that whenever a program is to be retrieved, the tape is positioned at the start end. Hence, the time tj needed to retrieve program ij from a tape having the programs in the order i1,i2, ,in is called mean retrieval time(MRT) and is given by

    tj =S lik k=1,2,,j

    In the optimal storage on tape problem, we are required to find a permutation for the n programs so that when they are stored on the tape, the MRT is minimized.

    Let n=3 and (l1,l2,l3)=(5,10,3),there are n!=6 possible orderings. These orderings and their respective MRT is given in the fig 6.1. Hence, the best order of recording is 3,1,2.

    6.1.2 Subset problem:

    There are n positive numbers given in a set. The desire is to find all possible subsets of this set, the contents of which add onto a predefined value M.

    Let there be n elements in the main set. W=w[1..n] represent the elements of the set. i.e., w = (w1,w2,w3,,wn) vector x = x[1..n] assumes either 0 or 1 value. If element w(i) is included in the subset then x(i) =1.

    Consider n=6 m=30 and w[1..6]={5,10,12,13,15,18}. The partial backtracking tree is shown in fig 6.2. The label to the left of a node represents the item number chosen for insertion and the label to the right represents the space occupied in M. S represents a solution to the given problem and B represents a bounding criteria if no solution can be reached. For the above problem the solution could be (1,1,0,0,1,0), (1,0,1,1,0,0) and (0,0,1,0,0,1). Completion of the tree structure is left as an assignment for the reader.

    6.3.3 8 queen problem:

    The 8 queen problem can be stated as follows. Consider a chessboard of order 8X8. The problem is to place 8 queens on this board such that no two queens are attack can attack each other.

    Illustration.

    Consider the problem of 4 queens, backtracking solution for this is as shown in the fig 6.3. The figure shows a partial backtracking tree. Completion of the tree is left as an assignment for the reader.

    Study Notes Home | Next Section>>




     

    Discussion Center

    Discuss

    Query

    Feedback/ Suggestion

    Yahoo Groups

    Sirfdosti Groups

    Contact Us


    .

    Recently Updated: New Placement Papers added.
    Vyom Network : Web Hosting | Dedicated Server | Free SMS, GRE, GMAT, MBA | Online Exams | Freshers Jobs | Software Downloads | Programming & Source Codes | GRE Preparation | Jobs, Discussions | Software Listing | Free eBooks | Free eBooks | Free Business Info | Interview Questions | Free Tutorials | International Business Information | IAS Preparation | Jokes, Songs, Fun | Free Classifieds | Free Recipes | FAQs | Free Downloads | Bangalore Info | Tech Solutions | Project Outsourcing, Web Hosting | GATE Preparation | MBA Preparation | SAP Info | Excellent Mobiles | Software Testing | Interview Questions | Freshers Jobs | Server Insiders | File Extension Directory

    Copyright ©2003-2017 Vyom Technosoft Pvt. Ltd., All Rights Reserved. Read our Privacy Policy