Please enable JavaScript.

Coggle requires JavaScript to display documents.

M16 - Coggle Diagram

- - - - F (n) = max{cn + F (n − 2), F (n − 1)} for n > 1,
        F (0) = 0, F(1) = c1.
  - - - F (n) = min
        j : n≥dj
        {F (n − dj )} + 1 for n > 0,
        F (0) = 0.
  - - - Of course, there are no adjacent cells
        above the cells in the first row, and there are no adjacent cells to the left of the
        cells in the first column. For those cells, we assume that F (i − 1,j) and F (i, j − 1)
        are equal to 0 for their nonexistent neighbors. Therefore, the largest number of
        coins the robot can bring to cell (i, j ) is the maximum of these two numbers plus
        one possible coin at cell (i, j ) itself. In other words, we have the following formula
        for F (i, j ):
        F (i, j ) = max{F (i − 1, j ), F (i, j − 1)} + cij for 1 ≤ i ≤ n, 1 ≤ j ≤ m
        F (0, j) = 0 for 1 ≤ j ≤ m and F (i, 0) = 0 for 1 ≤ i ≤ n,
        designing the knapsack problem using dp:
        f(i, j) = f(i - 1,j) j - w < 0
        f(i, j) = max(f(i - 1,j), v + f(i - 1, j - w) j - w >= 0
        f(0, j) = 0 j>=0
        f(i, 0) = 0 i>=0
- - - - Note that the problem of computing F (n) is
        expressed in terms of its smaller and overlapping subproblems of computing
        F (n − 1) and F (n − 2).
        
        Since a majority of dynamic programming applications deal with optimiza-
        tion problems, we also need to mention a general principle that underlines such
        applications. Richard Bellman called it the principle of optimality. In terms some-
        what different from its original formulation, it says that an optimal solution to any
        instance of an optimization problem is composed of optimal solutions to its subin-
        stances. The principle of optimality holds much more often than not. (To give a
        rather rare example, it fails for finding the longest simple path in a graph.) Al-
        though its applicability to a particular problem needs to be checked, of course,
        such a check is usually not a principal difficulty in developing a dynamic program-
        ming algorithm.
- - - - If an instance of the problem in question is very small, we might be able to
        solve it by an exhaustive-search algorithm
        Some such problems can
        be solved by the dynamic programming technique
        
        But even when this approach works in principle, its practicality is limited by
        dependence on the instance parameters being relatively small. The discovery of
        the branch-and-bound technique has proved to be an important breakthrough,
        because this technique makes it possible to solve many large instances of difficult
        optimization problems in an acceptable amount of time. However, such good
        performance cannot usually be guaranteed.
        
        There is a radically different way of dealing with difficult optimization prob-
        lems: solve them approximately by a fast algorithm. This approach is particularly
        appealing for applications where a good but not necessarily optimal solution will
        suffice. Besides, in real-life applications, we often have to operate with inaccurate
        data to begin with. Under such circumstances, going for an approximate solution
        can be a particularly sensible choice.
        Although approximation algorithms run a gamut in level of sophistication,
        most of them are based on some problem-specific heuristic. A heuristic is a
        common-sense rule drawn from experience rather than from a mathematically
        proved assertion. For example, going to the nearest unvisited city in the traveling
        salesman problem is a good illustration of this notion.
        
        DEFINITION A polynomial-time approximation algorithm is said to be a c-
        approximation algorithm, where c ≥ 1, if the accuracy ratio of the approximation
        it produces does not exceed c for any instance of the problem in question:
        
        The performance ratio serves as the principal metric indicating the quality of
        the approximation algorithm. We would like to have approximation algorithms
        with RA as close to 1 as possible. Unfortunately, as we shall see, some approxima-
        tion algorithms have infinitely large performance ratios (RA = ∞). This does not
        necessarily rule out using such algorithms, but it does call for a cautious treatment
        of their outputs.
        
        There are two important facts about difficult combinatorial optimization
        problems worth keeping in mind. First, although the difficulty level of solving
        most such problems exactly is the same to within a polynomial-time transforma-
        tion of one problem to another, this equivalence does not translate into the realm
        of approximation algorithms. Finding good approximate solutions is much easier
        for some of these problems than for others. Second, some of the problems have
        special classes of instances that are both particularly important for real-life appli-
        cations and easier to solve than their general counterparts. The traveling salesman
        problem is a prime example of this situation.
        
        1 more item...
- - - - THEOREM 2 The twice-around-the-tree algorithm is a 2-approximation algo-
        rithm for the traveling salesman problem with Euclidean distances.
        Christofides Algorithm There is an approximation algorithm with a better per-
        formance ratio for the Euclidean traveling salesman problem—the well-known
        Christofides algorithm. It also uses a minimum spanning tree but does
        this in a more sophisticated way than the twice-around-the-tree algorithm. Note
        that a twice-around-the-tree walk generated by the latter algorithm is an Eule-
        rian circuit in the multigraph obtained by doubling every edge in the graph given.
        Recall that an Eulerian circuit exists in a connected multigraph if and only if all
        its vertices have even degrees. The Christofides algorithm obtains such a multi-
        graph by adding to the graph the edges of a minimum-weight matching of all the
        odd-degree vertices in its minimum spanning tree. (The number of such vertices
        is always even and hence this can always be done.) Then the algorithm finds an
        Eulerian circuit in the multigraph and transforms it into a Hamiltonian circuit by
        shortcuts, exactly the same way it is done in the last step of the twice-around-the-
        tree algorithm.
        
        Local Search Heuristics For Euclidean instances, surprisingly good approxima-
        tions to optimal tours can be obtained by iterative-improvement algorithms, which
        are also called local search heuristics. The best-known of these are the 2-opt, 3-
        opt, and Lin-Kernighan algorithms. These algorithms start with some initial tour,
        e.g., constructed randomly or by some simpler approximation algorithm such as
        the nearest-neighbor. On each iteration, the algorithm explores a neighborhood
        around the current tour by replacing a few edges in the current tour by other
        edges. If the changes produce a shorter tour, the algorithm makes it the current
        tour and continues by exploring its neighborhood in the same manner; otherwise,
        the current tour is returned as the algorithm’s output and the algorithm stops.
        The 2-opt algorithm works by deleting a pair of nonadjacent edges in a tour
        and reconnecting their endpoints by the different pair of edges to obtain another
        tour. This operation is called the 2-change. Note that there is
        only one way to reconnect the endpoints because the alternative produces two
        disjoint fragments.
        
        Aproximation algorithms for the knapsack problem
        Greedy Algorithms for the Knapsack Problem :We can think of several greedy
        approaches to this problem. One is to select the items in decreasing order of
        their weights; however, heavier items may not be the most valuable in the set.
        Alternatively, if we pick up the items in decreasing order of their value, there is
        no guarantee that the knapsack’s capacity will be used efficiently. Can we find a
        greedy strategy that takes into account both the weights and values? Yes, we can,
        by computing the value-to-weight ratios vi/wi, i = 1, 2, . . . , n, and selecting the
        items in decreasing order of these ratios. Here
        is the algorithm based on this greedy heuristic.
        Greedy algorithm for the discrete knapsack problem
        Step 1 Compute the value-to-weight ratios ri = vi/wi, i = 1, . . . , n, for the
        items given.
        Step 2 Sort the items in nonincreasing order of the ratios computed in Step 1.
        (Ties can be broken arbitrarily.)
        Step 3 Repeat the following operation until no item is left in the sorted list:
        if the current item on the list fits into the knapsack, place it in the
        knapsack and proceed to the next item; otherwise, just proceed to the
        next item.
        
        Does this greedy algorithm always yield an optimal solution? The answer, of
        course, is no: if it did, we would have a polynomial-time algorithm for the NP-
        hard problem. In fact, the following example shows that no finite upper bound on
        the accuracy of its approximate solutions can be given either.
        Greedy algorithm for the continuous knapsack problem
        Step 1 Compute the value-to-weight ratios vi/wi, i = 1, . . . , n, for the items
        given.
        Step 2 Sort the items in nonincreasing order of the ratios computed in Step 1.
        (Ties can be broken arbitrarily.)
        Step 3 Repeat the following operation until the knapsack is filled to its full
        capacity or no item is left in the sorted list: if the current item on the
        list fits into the knapsack in its entirety, take it and proceed to the next
        item; otherwise, take its largest fraction to fill the knapsack to its full
        capacity and stop.
        
        Approximation Schemes We now return to the discrete version of the knap-
        sack problem. For this problem, unlike the traveling salesman problem, there exist
        polynomial-time approximation schemes, which are parametric families of algo-
        rithms that allow us to get approximations s(k)
        a with any predefined accuracy level:
        f (s∗)/f (s(k)a ) ≤ 1 + 1/k for any instance of size n,
        where k is an integer parameter in the range 0 ≤ k < n. The first approximation generates all
        subsets of k items or less, and for each one that fits into the knapsack it adds the
        remaining items as the greedy algorithm would do (i.e., in nonincreasing order
        of their value-to-weight ratios). The subset of the highest value obtained in this
        fashion is returned as the algorithm’s output.