Please enable JavaScript.

Coggle requires JavaScript to display documents.

Backtracking, Examples, branch-and-bound - Coggle Diagram

- - - - Promissing
        
        if it corresponds to a
        partially constructed solution that may still lead to a complete solution;
        
        nonpromising
        
        If its not promissing..
- - - - The node represents no feasible solutions because the constraints of the
        problem are already violated
        
        The subset of feasible solutions represented by the node consists of a single point (and hence no further choices can be made)—in this case, we compare the value of the objective function for this feasible solution with that of the best solution seen so far and update the latter with the former if the new solution is better
        
        feasible solution is a point in the problem’s search space that satisfies all the problem’s constraints whereas an optimal solution is a feasible solution with the best value of the objective function
    - - Assignment Problem
        
        The assignment problem consists of finding, in a weighted bipartite graph, a matching of a given size, in which the sum of weights of the edges is minimum. If the numbers of agents and tasks are equal, then the problem is called balanced assignment. Otherwise, it is called unbalanced assignment.
      - Knapsack Problem
        
        is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem often arises in resource allocation where the decision-makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively.
      - Traveling Salesman Problem
        
        asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research. The travelling purchaser problem and the vehicle routing problem are both generalizations of TSP. In the theory of computational complexity, the decision version of the TSP (where given a length L, the task is to decide whether the graph has a tour of at most L) belongs to the class of NP-complete problems. Thus, it is possible that the worst-case running time for any algorithm for the TSP increases superpolynomially (but no more than exponentially) with the number of cities.