Basic ConceptsSuppose a salesperson is planning a sales trip that includes 20 cities. Each city is connected to some of the other cities by a road. To minimize travel time, we want to determine a shortest route that starts at the salesperson’s home city, visits each of the cities once, and ends up at the home city. This problem of determining a shortest route is called the Traveling Salesperson ..

Basic ConceptsIn general, the breadth-first search strategy has no advantage over a depth-first search (backtracking).🔗 Backtracking with the 0-1 Knapsack problem (Depth-First Search)🔗 Branch-and-Bound with the 0-1 Knapsack problem (Breadth-First Search)However, we can improve our search by using our bound to do more than just determine whether a node is promising. After visiting all the child..

Basic ConeptWe show how to use the branch-and-bound design strategy by applying it to the 0-1 Knapsack problem. First we discuss a simple version called breadth-first search with branch-and-bound pruning. After that, we show an improvement on the simple version called best-first search with branch-and-bound pruning. 👉 분기 한정 설계 전략을 0-1 배낭 문제에 적용한다. 먼저, 분기 한정 가지치기를 적용한 너비 우선 탐색(Breadth-First Sear..

Basic ConceptThe branch-and-bound design strategy is very similar to backtracking in that a state space tree is used to solve a problem. The differences are that the branch-and-bound method (1) does not limit us to any particular way of traversing the tree and (2) is used only for optimization problems. A branch-and-bound algorithm computes a number (bound) at a node to determine whether the nod..

Basic ConceptRecall that in this problem we have a set of items, each of which has a weight and a profit. The weights and profits are positive integers. A thief plans to carry off stolen items in a knapsack, and the knapsack will break if the total weight of the items placed in it exceeds some positive integer $W$. The thief’s objective is to determine a set of items that maximizes the total pro..

Basic ConceptThe m-Coloring problem concerns finding all ways to color an undirected graph using at most m different colors, so that no two adjacent vertices are the same color. We usually call the m-Coloring problem a unique problem for each value of m. An important application of graph coloring is the coloring of maps. 👉 m-그래프 채색 문제는 비방향그래프에서 서로 인접한 정점이 같은 색을 갖지 않도록 최대 m개의 다른 색으로 칠하는 방법을 모두 찾..