• Home
  • /
  • Blog
  • /
  • कुशल समस्या समाधान के लिए 8 प्रकार के एल्गोरिदम को समझें

कुशल समस्या समाधान के लिए 8 प्रकार के एल्गोरिदम को समझें

एल्गोरिदम के प्रकार

This post is also available in: English (English) العربية (Arabic)

एल्गोरिथ्म क्या है?

एल्गोरिथ्म एक प्रक्रिया या एक समस्या को हल करने के लिए सूत्र है, जो निर्दिष्ट कार्यों के अनुक्रम का संचालन करने पर आधारित है। एक कंप्यूटर प्रोग्राम को एक विस्तृत एल्गोरिथ्म के रूप में देखा जा सकता है। गणित और कंप्यूटर विज्ञान में, एक एल्गोरिथ्म का मतलब आमतौर पर एक छोटी प्रक्रिया होती है जो एक आवर्तक समस्या को हल करती है।

आईटी (सूचना प्रौद्योगिकी) के सभी क्षेत्रों में एल्गोरिदम का व्यापक रूप से उपयोग किया जाता है। एक खोज (सर्च) इंजन एल्गोरिथ्म, उदाहरण के लिए, इनपुट के रूप में कीवर्ड और ऑपरेटरों के खोज स्ट्रिंग लेता है, प्रासंगिक वेब पेजों के लिए अपने संबंधित डेटाबेस को खोजता है, और परिणाम देता है।

इस लेख में, हम 8 प्रकार के एल्गोरिदम के बारे में चर्चा करेंगे।

एक अच्छे एल्गोरिदम की विशेताएं

एक अच्छे एल्गोरिथ्म में निम्नलिखित गुण होने चाहिए:

  • इनपुट और आउटपुट को सटीक रूप से परिभाषित किया जाना चाहिए।
  • एल्गोरिथ्म में प्रत्येक चरण स्पष्ट और स्पष्ट होना चाहिए।
  • किसी समस्या को हल करने के लिए कई अलग-अलग तरीकों में एल्गोरिदम सबसे प्रभावी होना चाहिए।
  • एक एल्गोरिथ्म में कंप्यूटर कोड शामिल नहीं होना चाहिए। इसके बजाय, एल्गोरिथ्म को इस तरह से लिखा जाना चाहिए कि इसका उपयोग विभिन्न प्रोग्रामिंग भाषाओं में किया जा सके।

एल्गोरिथम का उदाहरण – तीन नंबरों में सबसे बड़ा खोजना

Step 1: Start
Step 2: Declare variables a, b and c
Step 3: Read variables a, b and c.
Step 4: If a > b
		If a > c 
				Display a is the largest number
		Else
				Display c is the largest number
	Else
		If b > c
			Display b is the largest number
		Else
			Display c is the largest number
Step 5: Stop

एल्गोरिदम के प्रकार

समान समस्या-समाधान दृष्टिकोण का उपयोग करने वाले एल्गोरिदम को एक साथ समूहीकृत किया जा सकता है। यह वर्गीकरण योजना न तो संपूर्ण है और न ही असहमति। एल्गोरिदम को वर्गीकृत करने का उद्देश्य विभिन्न तरीकों को उजागर करना है, जिसमें किसी समस्या पर हमला किया जा सकता है।

कार्य सिद्धांत के आधार पर, एल्गोरिदम को 8 विभिन्न प्रकारों में वर्गीकृत किया गया है।

  • सरल पुनरावर्ती (सिंपल रिकर्सिव) एल्गोरिदम
  • बैक ट्रैकिंग एल्गोरिदम
  • डिवाइड और कॉनकोर एल्गोरिदम
  • डायनामिक प्रोग्रामिंग एल्गोरिदम
  • ग्रीडी एल्गोरिदम
  • ब्रांच एंड बाउंड एल्गोरिदम
  • ब्रूट फ़ोर्स एल्गोरिदम
  • यादृच्छिक (राडोमाइज़्ड) एल्गोरिदम

सिंपल रिकर्सिव अल्गोरिथम

कंप्यूटर विज्ञान में, पुनरावृत्ति एक समस्या को हल करने का एक तरीका है जहां समाधान उसी समस्या के छोटे उदाहरणों के समाधान पर निर्भर करता है। ऐसी समस्याओं को आम तौर पर पुनरावृत्ति द्वारा हल किया जा सकता है, लेकिन इसके लिए प्रोग्रामिंग समय में छोटे उदाहरणों को पहचानने और अनुक्रमित करने की आवश्यकता होती है। पुनर्संयोजन ऐसे पुनरावर्ती समस्याओं को हल करता है कार्यों का उपयोग करके जो अपने कोड से स्वयं को कॉल करते हैं। दृष्टिकोण को कई प्रकार की समस्याओं पर लागू किया जा सकता है, और पुनरावृत्ति कंप्यूटर विज्ञान के केंद्रीय विचारों में से एक है।

एक पुनरावर्ती एल्गोरिथ्म एक एल्गोरिथ्म है जो खुद को “छोटे (या सरल)” इनपुट मूल्यों के साथ कहता है, और जो वर्तमान इनपुट के लिए परिणाम को छोटे (या सरल) इनपुट के लिए लौटाए गए मान पर सरल ऑपरेशन लागू करके प्राप्त करता है। अधिक आम तौर पर यदि किसी समस्या को उसी समस्या के छोटे संस्करणों के समाधान का उपयोग करके हल किया जा सकता है, और छोटे संस्करण आसानी से हल करने योग्य मामलों में कम हो जाते हैं, तो उस समस्या को हल करने के लिए एक पुनरावर्ती एल्गोरिदम का उपयोग कर सकते हैं। उदाहरण के लिए, पुनरावर्ती रूप से परिभाषित सेट के तत्व, या पुनरावर्ती एल्गोरिथ्म द्वारा पुनरावर्ती रूप से परिभाषित फ़ंक्शन का मान प्राप्त किया जा सकता है।

पुनरावर्ती एल्गोरिदम के प्रारंभिक चरण पुनरावर्ती परिभाषा के मूल खंड के अनुरूप हैं और वे मूल तत्वों की पहचान करते हैं। इसके बाद उन्हें प्रेरक खंड के अनुरूप चरणों का पालन किया जाता है, जो एक पीढ़ी के तत्व के लिए गणना को तुरंत पूर्ववर्ती पीढ़ी के तत्वों के लिए कम कर देता है।

सामान्य तौर पर, पुनरावर्ती कंप्यूटर प्रोग्राम को पुनरावृत्ति एल्गोरिदम के साथ तुलना में अधिक स्मृति और गणना की आवश्यकता होती है, लेकिन वे सरल और कई मामलों में समस्या के बारे में सोचने का एक स्वाभाविक तरीका है।

आइए एक समस्या पर विचार करें कि एक प्रोग्रामर को पहले n प्राकृतिक संख्याओं का योग निर्धारित करना है, ऐसा करने के कई तरीके हैं लेकिन सबसे सरल तरीका यह है कि संख्याओं को 1 से n तक जोड़ना है। तो फ़ंक्शन बस ऐसा लगता है, बस एक-एक करके जोड़ रहा है – f (n) 1 + 2 + 3 +…

पुनरावर्ती दृष्टिकोण में, यह हो जाता है:

f(n) = 1,       		n = 1;
f(n) = n + f(n - 1),	        n > 1;

पहले दृष्टिकोण और दूसरे दृष्टिकोण के बीच एक सरल अंतर है और वह यह है कि दूसरे दृष्टिकोण में फ़ंक्शन “f ()” खुद को फ़ंक्शन के अंदर बुलाया जा रहा है, इसलिए इस घटना को रिकर्सन नाम दिया गया है और फ़ंक्शन जिसमें पुनरावृत्ति है पुनरावर्ती फ़ंक्शन कहा जाता है, अंत में, यह प्रोग्रामर के हाथ में कुछ समस्याओं को बहुत आसान और कुशल तरीके से कोड करने के लिए एक महान उपकरण है।

बैकट्रैकिंग अल्गोरिथम

बैकट्रैकिंग कुछ कम्प्यूटेशनल समस्याओं के लिए सभी (या कुछ) समाधान खोजने के लिए एक सामान्य एल्गोरिथ्म है, जैसे कि बाधा संतुष्टि समस्याएं, जो कि इंक्रीमेंटल रूप से समाधान करने के लिए उम्मीदवारों का निर्माण करती हैं, और एक उम्मीदवार (“बैकट्रैक”) को छोड़ देता है जैसे ही वह निर्धारित करता है कि उम्मीदवार नहीं कर सकता संभवतः एक वैध समाधान के लिए पूरा किया।

बैकट्रैकिंग के उपयोग की क्लासिक पाठ्यपुस्तक का उदाहरण आठ रानियों की पहेली है, जो एक मानक बिसात पर आठ शतरंज रानियों की सभी व्यवस्था करने के लिए कहता है ताकि कोई रानी किसी अन्य पर हमला न करे। सामान्य बैकट्रैकिंग दृष्टिकोण में, आंशिक उम्मीदवार बोर्ड की पहली k पंक्तियों में k रानियों की व्यवस्था करते हैं, सभी अलग-अलग पंक्तियों और स्तंभों में। किसी भी आंशिक समाधान में दो परस्पर आक्रमण करने वाली रानियों को छोड़ दिया जा सकता है।

बैकट्रैकिंग को केवल “आंशिक उम्मीदवार समाधान” की अवधारणा को स्वीकार करने वाली समस्याओं के लिए लागू किया जा सकता है और यह संभवत: एक वैध समाधान के लिए पूरा किया जा सकता है या नहीं इसका अपेक्षाकृत त्वरित परीक्षण। निम्नलिखित उदाहरण के लिए यह बेकार है – किसी अनियंत्रित तालिका में दिए गए मान का पता लगाने के लिए। जब यह लागू होता है, हालांकि, सभी पूर्ण उम्मीदवारों की क्रूर बल गणना की तुलना में बैकट्रैकिंग अक्सर बहुत तेज होती है, क्योंकि यह एक परीक्षण के साथ कई उम्मीदवारों को समाप्त कर सकता है।

क्रॉसरवर्ड, वर्बल अरिथमेटिक, सुडोकू, और कई अन्य पहेलियों जैसे बाधा संतुष्टि समस्याओं को हल करने के लिए बैकट्रैकिंग एक महत्वपूर्ण उपकरण है। यह अक्सर पारसिंग के लिए सबसे सुविधाजनक (यदि सबसे कुशल नहीं है) तकनीक है, नैकपैक समस्या और अन्य दहनशील अनुकूलन समस्याओं के लिए। यह आइकॉन, प्लानर और प्रोलॉग जैसी तथाकथित लॉजिक प्रोग्रामिंग भाषाओं का आधार भी है।

बैकट्रैकिंग समस्याओं को हल करने के लिए एल्गोरिदम पर आधारित एक तकनीक है। यह समय के साथ बढ़ते मूल्यों द्वारा समाधान कदम का निर्माण करके समाधान खोजने के लिए पुनरावर्ती कॉलिंग का उपयोग करता है। यह उन समाधानों को हटा देता है जो समस्या को हल करने के लिए दी गई बाधाओं के आधार पर समस्या के समाधान को जन्म नहीं देते हैं।

  • बैकट्रैकिंग एल्गोरिथ्म को कुछ विशिष्ट प्रकार की समस्याओं पर लागू किया जाता है, जैसे कि
  • डिसिशन प्रॉब्लम समस्या के लिए एक संभव समाधान खोजने के लिए इस्तेमाल किया।
  • ऑप्टिमिज़िंग प्रॉब्लम का सबसे अच्छा समाधान खोजने के लिए उपयोग किया जाता है जिसे लागू किया जा सकता है।
  • एनुमेरशन प्रॉब्लम का उपयोग समस्या के सभी संभव समाधानों के सेट को खोजने के लिए किया जाता है।

बैकट्रैकिंग प्रॉब्लम में, एल्गोरिथ्म समाधान के लिए एक अनुक्रम पथ खोजने की कोशिश करता है, जिसमें कुछ छोटे चेकपॉइंट्स होती हैं, जहां से समस्या के लिए कोई संभव समाधान नहीं मिलने पर समस्या वापस आ सकती है।

एन-क्वीन समस्या का समाधान खोजने के लिए इस बैकट्रैकिंग समस्या का उपयोग करें।

एन-क्वीन समस्या में, हमें एक N × N शतरंजबोर्ड दिया जाता है और हमें n क्वीन्स को बोर्ड पर इस तरह रखना होता है कि कोई भी दो रानियां एक-दूसरे पर हमला न करें। एक रानी दूसरी रानी पर हमला करेगी यदि उसे क्षैतिज, ऊर्ध्वाधर, या विकर्ण बिंदुओं में रखा जाए। यहां, हम 4-रानी समस्या के बारे में बात करेंगे।

Here, the solution is −

8 प्रकार के एल्गोरिदम
4-Queen problem

The binary output for n queen problem with 1s as queens to the positions placed.

{0 , 1 , 0 , 0}

{0 , 0 , 0 , 1}

{1 , 0 , 0 , 0}

{0 , 0 , 1 , 0}

For solving the n queens problem, we will try placing the queen into different positions of one row. And checks if it clashes with other queens. If they are attacking, we will backtrack to the previous location of the queen and change its positions. And check the clash of the queen again.

Algorithm for solving the n-Queen problem:

Step 1 − Start from 1st position in the array.

Step 2 − Place queens on the board and check. Do,

Step 2.1 − After placing the queen, mark the position as a part of the solution and then recursively check if this will lead to a solution.

Step 2.2 − Now, if placing the queen doesn’t lead to a solution and trackback and go to step (a) and place queens to other rows.

Step 2.3 − If placing the queen returns a lead to solution return TRUE.

Step 3 − If all queens are placed return TRUE.

Step 4 − If all rows are tried and no solution is found, return FALSE.

डिवाइड और कॉनकोर एल्गोरिदम

In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

The divide-and-conquer technique is the basis of efficient algorithms for many problems, such as sorting (quicksort, merge-sort), multiplying large numbers (e.g., Karatsuba algorithm), finding the closest pair of points, syntactic analysis (e.g., top-down parsers), and computing the discrete Fourier transform.

Designing efficient divide-and-conquer algorithms can be difficult. As in mathematical induction, it is often necessary to generalize the problem to make it amenable to a recursive solution. The correctness of a divide-and-conquer algorithm is usually proved by mathematical induction, and its computational cost is often determined by solving recurrence relations.

This technique can be divided into the following three parts:

  1. Divide: This involves dividing the problem into some sub-problem.
  2. Conquer: Sub problem by calling recursively until the sub-problem is solved.
  3. Combine: The Sub problem Solved so that we will find a problem solution.

The following are some standard algorithms that follow the Divide and Conquer algorithm.

  1. Binary Search is a searching algorithm. In each step, the algorithm compares the input element x with the value of the middle element in an array. If the values match, return the index of the middle. Otherwise, if x is less than the middle element, then the algorithm recurs for the left side of the middle element, else recurs for the right side of the middle element.
  2. Quicksort is a sorting algorithm. The algorithm picks a pivot element, rearranges the array elements in such a way that all elements smaller than the picked pivot element move to the left side of a pivot, and all greater elements move to the right side. Finally, the algorithm recursively sorts the subarrays on the left and right of a pivot element.
  3. Merge Sort is also a sorting algorithm. The algorithm divides the array into two halves, recursively sorts them, and finally merges the two sorted halves.
  4. The Closest Pair of Points is a problem to find the closest pair of points in a set of points in the x-y plane. The problem can be solved in O(n^2) time by calculating the distances of every pair of points and comparing the distances to find the minimum. The Divide and Conquer algorithm solves the problem in O(N log N) time.

डायनामिक प्रोग्रामिंग एल्गोरिदम

Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.

In both contexts, it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively. Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have an optimal substructure.

If sub-problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub-problems. In the optimization literature this relationship is called the Bellman equation.

Dynamic programming approach is similar to divide and conquer in breaking down the problem into smaller and yet smaller possible sub-problems. But unlike, divide and conquer, these sub-problems are not solved independently. Rather, results of these smaller sub-problems are remembered and used for similar or overlapping sub-problems.

Dynamic programming is used where we have problems, which can be divided into similar sub-problems, so that their results can be re-used. Mostly, these algorithms are used for optimization. Before solving the in-hand sub-problem, dynamic algorithms will try to examine the results of the previously solved sub-problems. The solutions of sub-problems are combined in order to achieve the best solution.

So we can say that −

  • The problem should be able to be divided into smaller overlapping sub-problem.
  • An optimum solution can be achieved by using an optimum solution of smaller sub-problems.
  • Dynamic algorithms use Memoization.

The following computer problems can be solved using dynamic programming approach −

Dynamic programming can be used in both top-down and bottom-up manner. And of course, most of the time, referring to the previous solution output is cheaper than recomputing in terms of CPU cycles.

ग्रीडी एल्गोरिदम

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not usually produce an optimal solution, but nonetheless, a greedy heuristic may yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

For example, a greedy strategy for the travelling salesman problem (which is of a high computational complexity) is the following heuristic: “At each step of the journey, visit the nearest unvisited city.” This heuristic does not intend to find a best solution, but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps. In mathematical optimization, greedy algorithms optimally solve combinatorial problems having the properties of matroids, and give constant-factor approximations to optimization problems with submodular structure.

Most networking algorithms use the greedy approach. Here is a list of few of them −

ब्रांच एंड बाउंड एल्गोरिदम

Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.

The algorithm depends on efficient estimation of the lower and upper bounds of regions/branches of the search space. If no bounds are available, the algorithm degenerates to an exhaustive search.

The method was first proposed by Ailsa Land and Alison Doig whilst carrying out research at the London School of Economics sponsored by British Petroleum in 1960 for discrete programming, and has become the most commonly used tool for solving NP-hard optimization problems.The name “branch and bound” first occurred in the work of Little et al. on the traveling salesman problem.

Let’s see the Branch and Bound Approach to solve the 0/1 Knapsack problem: The Backtracking Solution can be optimized if we know a bound on the best possible solution subtree rooted with every node. If the best in subtree is worse than current best, we can simply ignore this node and its subtrees. So we compute the bound (best solution) for every node and compare the bound with the current best solution before exploring the node.

Example bounds used in the diagram below are, A down can give $315, B down can $275, C down can $225, D down can $125 and E down can $30.

8 प्रकार के एल्गोरिदम
Branch and Bound algorithm

ब्रूट फ़ोर्स एल्गोरिदम

In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem’s statement.

A brute-force algorithm to find the divisors of a natural number n would enumerate all integers from 1 to n, and check whether each of them divides n without remainder. A brute-force approach for the eight queens puzzle would examine all possible arrangements of 8 pieces on the 64-square chessboard, and, for each arrangement, check whether each (queen) piece can attack any other.

While a brute-force search is simple to implement, and will always find a solution if it exists, its cost is proportional to the number of candidate solutions – which in many practical problems tends to grow very quickly as the size of the problem increases (Combinatorial explosion). Therefore, brute-force search is typically used when the problem size is limited, or when there are problem-specific heuristics that can be used to reduce the set of candidate solutions to a manageable size. The method is also used when the simplicity of implementation is more important than speed.

This is the case, for example, in critical applications where any errors in the algorithm would have very serious consequences; or when using a computer to prove a mathematical theorem. Brute-force search is also useful as a baseline method when benchmarking other algorithms or metaheuristics.Indeed, brute-force search can be viewed as the simplest metaheuristic.Brute force search should not be confused with backtracking, where large sets of solutions can be discarded without being explicitly enumerated (as in the textbook computer solution to the eight queens problem above). The brute-force method for finding an item in a table – namely, check all entries of the latter, sequentially – is called linear search.

For example, imagine you have a small padlock with 4 digits, each from 0-9. You forgot your combination, but you don’t want to buy another padlock. Since you can’t remember any of the digits, you have to use a brute force method to open the lock.

So you set all the numbers back to 0 and try them one by one: 0001, 0002, 0003, and so on until it opens. In the worst case scenario, it would take 104, or 10,000 tries to find your combination.

A classic example in computer science is the traveling salesman problem (TSP). Suppose a salesman needs to visit 10 cities across the country. How does one determine the order in which those cities should be visited such that the total distance traveled is minimized?

The brute force solution is simply to calculate the total distance for every possible route and then select the shortest one. This is not particularly efficient because it is possible to eliminate many possible routes through clever algorithms.

यादृच्छिक (राडोमाइज़्ड) एल्गोरिदम

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the “average case” over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables.

One has to distinguish between algorithms that use the random input so that they always terminate with the correct answer, but where the expected running time is finite (Las Vegas algorithm, for example, Quicksort), and algorithms that have a chance of producing an incorrect result (Monte Carlo algorithm, for example, Monte Carlo algorithm for the MFAS problem) or fail to produce a result either by signaling a failure or failing to terminate. In some cases, probabilistic algorithms are the only practical means of solving a problem.

In common practice, randomized algorithms are approximated using a pseudorandom number generator in place of a true source of random bits; such an implementation may deviate from the expected theoretical behavior.

{"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}
>