In University ☆ In Bucket Place ☆ Hobby & Study Room ☆

* 특징 - 되추적 기법과 같이 상태공간트리를 구축하여 문제를 해경한다. - 최적의 해를 구하는 문제에 적용할 수 있다.(되추적기법은 특정해를 구하는 문제에 적용) - 최적의 해를 구하기 위해서는 모든 해를 다 고려해 보아야 하므로 트리의 노드를 순회하는 방법에 구애받지 않는다. * 분기한정 알고리즘의 원리 - 각 노드를 검색할 때마다 그 노드가 유망한지의 여부를 결정하기 위해 한계치(bound)를 계산한다. - 그 한계치는 그 노드로부터 가지를 뻗어 나가서(Branch)를 얻을 수 있는 해답의 한계치를 나타낸다. - 만약 그 한계치가 지금까지 찾은 최적의 해답치 보다 좋지 않은 경우는 더 이상 가지를 뻗어 나가서 검색을 계속 할 필요가 없으므로 그 노드는 유망하지 않다고 할 수 있다. * 최적화 문제를..

import java.util.Scanner; public class hamiltonian { private boolean W[][]; private int nodeCount; private int vindex[]; hamiltonian(int n){ nodeCount = n; W = new boolean[nodeCount][nodeCount]; vindex = new int[nodeCount]; vindex[0] = 0; Scanner sc = new Scanner(System.in); char isTrue; for ( int i = 1 ; i

import java.util.*; public class mColoring { private int n; private int m; private int W[][]; private int vcolor[]; mColoring(int count, int colornumber){ int i, j; // for loop char isTrue; Scanner sc = new Scanner(System.in); n = count; m = colornumber; W = new int[n][n]; vcolor = new int[n]; vcolor[0] = 1; for ( i = 1 ; i

* 해밀토니안 회로 - 연결된 비방향성 그래프에서 어떤 한 정점에서 출발하여 그래프사으이 각 정점을 정확히 한번씩만 경유하여 다시 출발 정점으로 돌아오는 경로 ex) * 해밀토니안 회로문제 - 연결된 비방향성 그래프에서 해밀토니안 회로를 찾아라 - 상태공간트리 > 시작 정점을 트리의 수준(level) 0에 놓는다. > 수준 1에 시작 정점이 아닌 정점들을 놓는다. > 다른 수준에도 같은 방식으로 시작 정점이 아닌 정점들을 놓는다. > 마지막 수준에는 시작 정점을 놓는다. - 되추적 방법을 적용하기 위해서 다음 사항을 고려해야한다. > 경로상의 i번째 정점은 그 경로상의 (i-1)번째 정점과 반드시 인접해야한다.(인접하지 않으면 패스) > (n-1)번째 정점은 반드시 시작 정점과 인접해야한다.(마지막(n번..

* m - 색칠하기 문제 비방향 그래프에서 서로 인접한 종점들이 같은 색을 갖지 않도록 하면서 최대 m개의 다른 색으로 칠하는 모든 방법을 찾아라. * 평면그래프(Planar graph) - 평면 상에서 연결선들이 서로 교차하지 않는 그래프 옆 그래프는 연결선이 서로 교차하지 않으므로 평면 그래프라고 할 수 있다. 위 그래프에서 두개의 연결선 (v1,v5)와 (v2,v3)를 추가하면 연결 선중 일부는 교차하게 되고, 이에 따라 평면 그래프가 될 수 없다. * 지도와 평면 그래프 - 지도에서 각 지역을 그래프의 정점으로 하고, 한 지역이 어떤 다른 지역과 인접해 있으면 그 지역들을 나타내는 정점들 사이에 연결선을 그으면, 모든 지도는 그에 상응하는 평면 그래프로 표시할 수 있다. * m - 색칠하기 되추적..

* 상태 공간 트리(State Space Tree) - 미로 찾기에서 입구에서 출구까지 가는 경로를 찾기 위해서 선택할 수 있는 모든 경로를 트리로 만들 수 있다. 막다른 곳이나 출구가 종단 노드(leaf node)에 위치하게 된다. 이 트리가 상태공간 트리이다. - 상태 공간 트리를 깊이 우선 검색을 하여 해답 후보들 중에서 해답을 찾을 수 있다. > 상태 공간 트리를 깊이 우선 검색을 하여 해답 후보들을 모두 순회하면서 해답을 찾을 수 있다. 그러나 이방법은 해답이 될 가능성이 전혀 없는 노드의 후손 노드들도 모두 검색해야 하므로 비효율 적이다. * 되추적 기술 - 노드의 유망성 > 전혀 해답이 나올 가능성이 없는 노드는 유망하지 않다고 판단을 한다.(non-promising) 이와 반대로 가능성이 ..

* 되추적이란? - 미로에서 출구를 찾다보면 막다른 곳에 도달 할 수 있다. 이때 마지막 분기점으로 되돌아 가서 다른 길로 갈 수 있다. 이처럼 되추적은, 어떤 집합에서 특정 기준을 만족하면서 그 집합에 속한 대상의 순서를 손택하는 문제를 푸는데 사용한다. 되추적의 기본은 상태 공간 트리로 깊이 우선 검색과 밀접한 관련이 있다. 일단 깊이 우선 검색을 먼저 알아보도록 하자. * 깊이우선 검색 - 한 그래프의 정점들을 방문하는 하나의 방법 - 슈도코드 void DFSEARCH(v){ 정점 v를 "방문함"으로 표시한다. v에 인접한 모든 정점 w에 대해서 다음을 수행한다. > w가 방문하지 않은 상태면 DFSEARCH(w)를 수행 > w가 이미 방문했던 상태면 수행을 종료한다. } // 처음 모든 정점들은 ..

* 단일 출발점 최단 경로 문제 - 가중치가 있는 방향성 그래프에서 한 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 것. * 단일 출발점 최단 경로 문제 알고리즘 - 특정 정점에서 모든 정점들로 가는 최단 경로를 찾는다. - 아이디어 : 트리를 만들어서 사용한다. * 슈도코드 V = 모든 노드의 집합 Y = {v1};// 시작하는 노드 F = null; // 트리내의 화살표들의 집합 while(최종해답을 얻을 때까지) - "V-Y"에 속한 정점들중에서 V에서 Y에 속한 정점들만을 거쳐서 최단경로가 되는 정점을 선택한다. - 그 정점을 Y에 추가한다. - V에서 F로 이어지는 최단 경로상의 연결선을 F에 추가한다. - Y = V이면 T=(V,F)가 최단 경로를 나타내는 트리이다. >> 소스코..

public class Dijkstra { private int[][] w;// 가중치 행렬 private int length[];// 시작점에서 각 정점으로 가는 최소값을 저장하는 곳 private int touch[];// 출발점에서 목적지까지 가는데 걸리는 최소 가중치 private boolean isSelect[];// 정점이 선택되었는지를 판별하기 위한 것 private char vertex[];// 숫자로 한계산을 영어로 치환하기 위한 것 private int n;// 정점들의 수 // 정점의 개수를 받아서 그 만큼 할당을 해주면서 초기화하는게 옳은 것 // 다른 부분은 그렇게했지만 가중치 받는 것은 문제에서 가중치가 주어졌기때문에 // -> 고정되어서 입력없이 바로 입력되게하였다. Dijks..

public class Prim { private int[][] w;// 가중치 행렬 private boolean isblue[];// 정점 v가 이미 선택되었는가, 아닌가 private int near[];// 선택된 정점들중에서 가장 가벼운 가중치 private int n;// 정점들의 수 private char vertex[];// 숫자로 한계산을 영어로 치환하기 위한 것 // 정점의 개수를 받아서 그 만큼 할당을 해주면서 초기화하는게 옳은 것 // 다른 부분은 그렇게했지만 가중치 받는 것은 문제에서 가중치가 주어졌기때문에 // -> 고정되어서 입력없이 바로 입력되게하였다. Prim(int n){ this.n = n; w = new int[n][n]; isblue = new boolean[n]; n..