Algorithms For Dummies. John Paul Mueller

Чтение книги онлайн.

СКАЧАТЬ of years.

      This isn’t to say that some mathematicians haven’t overturned the apple cart over the years. For example, John Nash’s theory, Nash Equilibrium, significantly changed how economics is considered today (see https://www.masterclass.com/articles/nash-equilibrium-explained). Of course, recognition for such work comes slowly. Nash had to wait for a long time before he received much in the way of professional recognition (see the story at https://www.princeton.edu/main/news/archive/S42/72/29C63/index.xml) despite having won a Nobel Prize in economics for his contributions. Just in case you’re interested, John Nash’s story is depicted in the movie A Beautiful Mind, which contains some much-debated scenes, including one containing a claim that the Nash Equilibrium somehow overturns some of the work of Adam Smith, another contributor to economic theories. (See one such discussion at https://www.quora.com/Was-Adam-Smith-wrong-as-claimed-by-John-Nash-in-the-movie-A-Beautiful-Mind.)

Dividing and Conquering

      If solving problems were easy, everyone would do it. However, the world is still filled with unsolved problems and the condition isn’t likely to change anytime soon, for one simple reason: Problems often appear so large that no solution is imaginable. Ancient warriors faced a similar problem. An opposing army would seem so large and their forces so small as to make the problem of winning a war unimaginably hard, perhaps impossible. Yet, by dividing the opposing army into small pieces and attacking it a little at a time, a small army could potentially defeat a much larger opponent. (The ancient Greeks, Romans, and Napoleon Bonaparte were all great users of the divide-and-conquer strategy; see Napoleon For Dummies, by J. David Markham [Wiley], for details.)

      You face the same problem as those ancient warriors. Often, the resources at your disposal seem quite small and inadequate. However, by dividing a huge problem into small pieces so that you can understand each piece, you can eventually create a solution that works for the problem as a whole. Algorithms have this premise at their core: to use steps to solve problems one small piece at a time. The following sections help you understand the divide-and-conquer approach to problem solving in more detail.

      Avoiding brute-force solutions

      A brute-force solution is one in which you try each possible answer, one at a time, to locate the best possible answer. (This is also called an exhaustive approach, mostly because you’re so tired when you finish.) It’s thorough, this much is certain, but it also wastes time and resources in most cases. Testing every answer, even when it’s easy to prove that a particular answer has no chance of success, wastes time that an algorithm can use on answers that have a better chance of success. In addition, testing the various answers using this approach generally wastes resources, such as memory. Think of it this way: You want to break the combination for a lock, so you begin at 0, 0, 0, even though you know that this particular combination has no chance of success given the physical characteristics of combination locks. A brute-force solution would proceed with testing 0, 0, 0 anyway and then move on to the equally ridiculous 0, 0, 1.

      

Every solution type does come with advantages, although sometimes quite small. A brute-force solution has one such advantage. Because you test every answer, you don’t need to perform any sort of preprocessing. The time saved in skipping the preprocessing, though, is unlikely to ever pay back the time lost in trying every answer. However, you may find occasion to use a brute-force solution when

       Finding a perfect solution, if one exists, is essential.

       The problem size is limited.

       You can use heuristics to reduce the size of the solution set.

       Simplicity of implementation is more important than speed.

      Keeping it simple, silly (KISS)

      The brute-force solution, described in the previous section, has a serious drawback. It looks at the entire problem at one time. It’s sort of like going into a library and hunting book by book through the shelves without ever considering any method of making your search simpler. The divide-and-conquer approach to book searches is different. In this case, you begin by dividing the library into children’s and adults’ sections. After that, you divide the adults’ section into categories. Finally, you search just the part of the category that contains the book of interest. This is the purpose of classification systems such as the Dewey Decimal System (see https://mcpl.info/childrens/how-use-dewey-decimal-system). The point is that divide and conquer simplifies the problem.

The divide part of divide and conquer is an essential way to understand a problem better as well. Trying to understand the layout of an entire library could prove difficult. However, knowing that the book you want to find on comparative psychology appears as part of Class 100 in Division 150 of Section 156 makes your job easier. You can understand this smaller problem because you know that every Section 156 book will contain something about the topic you want to know about. Algorithms work the same way. By making the problem simpler, you can create a set of simpler steps to finding a problem solution, which reduces the time to find the solution, reduces the number of resources used, and improves your chances of finding precisely the solution you need.

      Breaking down a problem is usually better

      After you have divided a problem into manageable pieces, you need to conquer the piece in question. This means creating a precise problem definition. You don’t want just any book on comparative psychology; you want one written by George Romanes. Knowing that the book you want appears in Section 156 of the Dewey Decimal System is a good start, but it doesn’t solve the problem. Now you need a process for reviewing every book in Section 156 for the specific book you need. The process might go further still and look for books with specific content. To make this process viable, you must break the problem down completely, define precisely what you need, and then, after you understand the problem thoroughly, use the correct set of steps (algorithm) to find what you need.

Learning that Greed Can Be Good

      In some cases, you can’t see the end of a solution process or even know whether you’re winning the war. All you can really do is ensure that you win the individual battles to create a problem solution in hopes of also winning the war. A greedy method to problem solving uses this approach. It looks for an overall solution by choosing the best possible outcome at each problem solution stage.

      

It seems that winning each battle would necessarily mean winning the war as well, but sometimes the real world doesn’t work that way. A Pyrrhic victory is one in which someone wins every battle but ends up losing the war because the cost of the victory exceeds the gains of winning by such a large margin. You can read about five Pyrrhic victories at https://www.history.com/news/5-famous-pyrrhic-victories. These histories show that a greedy algorithm often does work, but not always, so you need to consider the best overall solution to a problem rather than become blinded by interim wins. The following СКАЧАТЬ