Coding StudyRoom

보호되어 있는 글입니다.

Traveling Salesman Problem(Traveling Sales-Person Problem) minimization optimization 조합 최적화 문제 택배 배달 시스템. 1,000개 boxes -> 가장 먼저 퇴근경로? h-value estimation in TSP Minimization Optimization: h = under-estimate -> TSP : under-estimation ==> 실수 X. incorrect prune X. -> 0 h = h* - alpha(smaller) #include using namespace std; const int N = 4;// 노드 수 int final_path[N + 1];// 경로 저장 ..

0/1 Knapsack Example using Branch&Bound #include #include #include using namespace std; struct Item { double weight; // 무게 int value; // 가치 }; struct Node { int level, profit, bound; double weight; }; bool cmp(Item a, Item b) { double r1 = a.value / a.weight; double r2 = b.value / b.weight; return r1 > r2; } // bounding function int bound(Node u, int n, int W, Item arr[]) { if (u.weight >= W) re..

Backtracking = DFS visit + bound function --> DFS를 BFS visit으로 전환하면? --> Branch and Bound. Backtracking = DFS + bound function Branch&Bound = BFS + bound function --> 차이는 DFS vs BFS. Q1. DFS vs BFS 장단점을 논하시오. --> in practice, Branch&Bound >> Backtracking. --> BFS: 신뢰성이 더 좋음 Q2. f = g + h tree traverse(child visit)순서에 따라, g value, h value는 update 차이 발생 ** 미..