Algorithms what is backtracking
Download 127.59 Kb.
|
1 2
- Navigate this page:
- 3) What is branch and bound strategy
- 4) What is dynamic programming
- 5) what is Greedy Method
- 6) What is time complexity
| ALGORITHMS
What is backtracking A) For some problems solution is expressible as an N- table (X1,X2-----------Xn) where the Xi are chosen from some finite set Si. The brute force method would yeiled all these n tuples , evaluate each one with the criterion function P and same those which yeid the optimum.Backtracking is a which is used in superior to brute force method. Its basic idea is to buid up the solution vector one component at a time and to use modified criterion functions Pi (x1,x2---------xi), a bounding function to test whether the vector being formed has any chance of success. The major advantage of this method is if it is realized that the partial vector (X1,X2---------Xi) can in no way lead to an optimal solution, then m I+1, …mn possible test vectors can be ignored entirely . The problems which uses backtracking requires that they have to satisfy the constraints divided into two categories. 1) Explicit 2) Implicit Explicit constraints are used that restrict each Xi to take on values only from a given set. Implicit constraints are rules that determined which of the tuples in the solution spare of I satisfy the criterion function. Thus these describe the way in which the Xi must rebate to each other. 2) Which of the sorting algorithms uses Divide and conquer strategy A) Given a function to compute on N inputs the divide and conquer strategy suggests splitting the inputs into k distinct subsets, 1 3) What is branch and bound strategyA) A branch and bound method searches a state stat the using any search mechanism in which all the children of the E-node are generated before another node becomes the E node. Three common strategis are FIF0,LIFO and LC. A cost function C( ) such that C (X)>= C(x) is used to provide lower bounds on solution obtainable form any node X. If u is an upper bound on the cost of a minimu cost solution of live nodes X with C-(x)>U may be killed as all answer nodes rechable form X have cost c(x)>=c-(x)>U. In case an answer node with cost U has already been reached then all live nodes with c(x)>= >U my be killed.4) What is dynamic programmingA) A Dynamic programming is an algorithms design method that can be used when the solution to a problem can be viewed as the result of a sequence of desiccions. We could enumerate all decisions sequences and then pick out the best. The optimal sequence decisions are obtainedo by making explic it appeal to the principle of optimality.The principle of optimality states that an optimal sequnec of decisions has the property that what ever the initial state and desion are, the remaining must constitute an optimal desicion sequnece, with regard to the state resulting from the first decision..5) what is Greedy MethodA) Most of the problems have N inputs and require us to obtain a subset that sales us some constraints. Any subset that satifies these constraints is called a feasible solution. We need to obtain a feasible solution that either maximises / minimizes a given objective function. A feasible solution that does this is called an optimal solotio. The greedy method suggests that one can devise an algorithms that works in stages considering one input at a time. At each stage desicion is made regarding whether a particular input is in an optimal solution (using some selection procudure). If the inclusion of the next input into the partially constructed optimal solution will result in an unfeasible solution, the this this input is not added to the partial solution. otherwise it is added. This version of greedy method is called subset paradigm. For problems that do not call for the selection of an optimal subset in the greedy method, we make decisions by considering the inputs in some order. Each decision is made using an optimization criterion that can be computed using decision already made. This version of greedy technique is called ordering paradegim.6) What is time complexity?A) Time complexity of algorithms • When you need to write a program that needs to be reused many times other issues may arise – how much times does it take to run it? – how much storage space do its variables use? – how much network traffic does it generate? • For large problems the running time is what really determines whether a program should be used • To measure the running time of a program, we – Select different sets of inputs that it should be tested on (for benchmarking). Such inputs may correspond to • the easiest case of the problem that needs to be solved(best case) • the hardest case of the problem that needs to be solved(worse case) • a case that falls between these two extremes(average case) • In many cases, the running time of a program depends on a particular type of input, not just the size of the input – the running time of a factorial program depends on the particular number whose factorial is being sought because this determines the total number of multiplications that need to be performed – the running time of a search program may depend on whether the value being sought occurs in the collection of items to be searched • To assess the running time, we have to accept the idea that certain programming operations take a fixed amount of time (independent of the input size): – arithmetic operations (+, -, *, etc.) – logical operations (and, or, not) – comparison operations (==, <, >, etc.) – array/vector indexing simple assignments (n = 2, etc.)
Directory: images images -> Pelan pentaksiran kursus images -> Military callsign list as of dec 2010 images -> For Date: 02/01/2013 Friday Call Number Time Call Reason Action 13-768 0008 motor vehicle stop warning Issued images -> New embedded S images -> Creating Buy-In – Building Relationships images -> Deadline: Saturday, March 12th, 2016 images -> News items from Raising Our Voices images -> Last year four of the best Afrikaans Christian singers joined forces to tour Down Under with the production ‘Manne wat Glo’ images -> World-renowned vocal ensemble sweet honey in the rock images -> Peoples Voice Café History Download 127.59 Kb. Share with your friends:
|
1 2