http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
이상운(Sang-Un Lee) 한국컴퓨터정보학회 2013 韓國컴퓨터情報學會論文誌 Vol.18 No.11
본 논문은 NP-완전 문제인 간선 색칠과 그래프 부류 결정 문제를 동시에 해결하는 O(E)의 다항시간 알고리즘을 제안하였다. 제안된 알고리즘은 최대차수-최소차수 정점 쌍 간선을 단순히 선택하는 방법으로 간선 채색수 x'(G)를 결정하였다. 결정된 x'(G)는 △(G)또는 △(G)+1을 얻는다. 결국, 알고리즘 수행 결과 얻은 x'(G)로부터 x'(G) = △(G)이면 부류 1, x'(G) = △(G)+1이면 부류 2로 분류할 수 있다. 또한, 미해결 문제로 알려진 "최대차수가 6인 단순, 평면 그래프는 부류 1이다."라는 Vizing의 평면 그래프 추정도 증명하였다. This paper proposes a O(E) polynomial-time algorithm that has been devised to simultaneously solve edge-coloring problem and graph classification problem both of which remain NP-complete. The proposed algorithm selects an edge connecting maximum and minimum degree vertices so as to determine the number of edge coloring x'(G). Determined x'(G)is in turn either △(G) or △(G)+1. Eventually, the result could be classified as class 1 if x'(G) = △(G) and as category 2 if x'(G) = △(G)+1. This paper also proves Vizing's planar graph conjecture, which states that 'all simple, planar graphs with maximum degree six or seven are of class one, closing the remaining possible case', which has known to be NP-complete.
이상운(Sang-Un Lee) 한국컴퓨터정보학회 2012 韓國컴퓨터情報學會論文誌 Vol.17 No.9
본 논문에서는 할당 문제의 최적해를 간단히 찾을 수 있는 알고리즘을 제안하였다. 일반적으로 할당 문제의 최적해는 Hungarian 알고리즘으로 구한다. 제안된 알고리즘은 Hungarian 알고리즘의 4단계 수행 과정을 1단계로 단축시켰으며, 행과 열의 최소 비용만을 선택하여 비용을 감소시키는 최적화 과정을 거쳐 최적해를 구하였다. 제안된 알고리즘을 27개의 균형 할당 문제와 7개의 불균형 할당 문제에 적용한 결과 유전자 알고리즘으로 찾지 못한 최적해를 찾는데 성공하였다. 제안된 알고리즘은 Hungarian 알고리즘의 수행 복잡도 O(n³)을 O(n)으로 향상시켰다. 따라서 제안된 알고리즘은 Hungarian 알고리즘을 대체하여 할당 문제에 일반적으로 적용할 수 있는 알고리즘으로 널리 활용될 수 있을 것이다. This paper suggests simple search algorithm for optimal solution in assignment problem. Generally, the optimal solution of assignment problem can be obtained by Hungarian algorithm. The proposed algorithm reduces the 4 steps of Hungarian algorithm to 1 step, and only selects the minimum cost of row and column then gets the optimal solution simply. For the 27 balanced and 7 unbalanced assignment problems, this algorithm finds the optimal solution but the genetic algorithm fails to find this values. This algorithm improves the time complexity O(n³) of Hungarian algorithm to O(n). Therefore, the proposed algorithm can be general algorithm for assignment problem replace Hungarian algorithm.
이상운(Sang-Un Lee) 한국컴퓨터정보학회 2013 韓國컴퓨터情報學會論文誌 Vol.18 No.7
일반적으로 재료절단 문제는 재료를 절단할 수 있는 패턴을 찾고 선형계획법으로 최적의 패턴 수를 찾는다. 그러나 패턴 수는 일반적으로 지수적으로 증가하기 때문에 사전에 모든 패턴을 고려하는 것은 비현실적인 것으로 알려져 있다. 본 논문은 Suliman의 실현 가능 패턴을 구하는 방법을 적용하여 사전에 패턴을 구하는 방법을 적용하였다. 또한, 실현 가능 패턴들을 대상으로 선형계획법이나 근사 알고리즘을 적용하지 않고 정확한 해를 다항시간으로 얻는 방법을 제안하였다. 제안된 방법은 실현 가능 패턴들 중 모든 요구의 1st 발생 빈도가 손실량 0에 모두 분포하는 경우와 다양한 손실량에 분산되어 분포하는 경우로 구분하여 패턴 수를 분배하는 방법을 적용하였다. 제안된 알고리즘을 2개의 데이터에 적용한 결과 모든 데이터에서 정확한 해를 구하는데 성공하였다. Commonly, one seeks a particular pattern suitable for stock cutting and the number of such patterns through linear programming. However, since the number of the patterns increases exponentially, it is nearly impossible to predetermine all the existing patterns beforehand. This paper thus proposes an algorithm whereby one could accurately predetermine the number of existing patterns by applying Suliman's feasible pattern method. Additionally, this paper suggests a methodology by which one may obtain exact polynomial-time solutions for feasible patterns without applying linear programming or approximate algorithm. The suggested methodology categorizes the feasible patterns by whether the frequency of first occurrence of all the demands is distributed in 0 loss or in various losses. When applied to 2 data sets, the proposes algorithm is found to be successful in obtaining the optimal solutions.
이상운(Sang-Un Lee) 한국컴퓨터정보학회 2013 韓國컴퓨터情報學會論文誌 Vol.18 No.6
통신채널 최적 할당 문제는 아직까지 결정론적 규칙이 알려지지 않고 있어 비결정론적 방법인 휴리스틱 알고리즘으로 대부분 해를 구하고 있다. 본 논문은 통신채널 최적 할당 문제에 대해 결정론적 방법으로 채널 배정을 할 수 있음을 보인다. 채널 배정 규칙을 적용하여 필라델피아의 9개 사례에 대해 적용한 결과 최적해를 구하였다. In the absence of a single deterministic rule for the channel assignment problems, heuristic algorithms are predominantly employed to partly solve the problems. This paper thus proposes deterministic rules for the channel assignment problems. These deterministic rules have successfully yielded the optimal solution when applied to the Philadelphia's 9 case examples.
단일모델 단측 조립라인 균형문제의 주경로 군집화 알고리즘
이상운(Sang-Un Lee) 한국컴퓨터정보학회 2014 韓國컴퓨터情報學會論文誌 Vol.19 No.5
본 논문은 NP-난제 문제로 알려진 단일모델 단방향 조립라인 균형문제에 대해 휴리스틱 알고리즘을 제안하였다. 조립라인 균형문제는 주로 메타휴리스틱 방법들을 적용하고 있는 추세이다. 제안된 알고리즘은 최종제품이 생산될 때까지 가장 많은 공정으로 조립되는 경로를 주경로로 설정하고, 주경로를 따라가면서 각 작업자에게 순환시간 조건을 만족하는 작업량을 배정하는 군집화 알고리즘을 제안하였다. 제안된 알고리즘은 최소의 작업자수를 결정하고, 순환시간도 단축시키는 결과를 얻었다. 9개의 다양한 실험 데이터에 제안된 주경로 군집화 휴리스틱 알고리즘을 적용한 결과 메타휴리스틱 방법들에 비해 보다 좋은 성능을 갖고 있음을 보였다. This paper suggests heuristic algorithm for single-model simple assembly line balancing problem that is a kind of NP-hard problem. This problem primarily can be solved metaheuristic method. This heuristic algorithm set the main-path that has a most number of operations from start to end-product. Then the clustering algorithm can be assigns operations to each workstation within cycle time follow main-path. This algorithm decides minimum number of workstations and can be reduces the cycle time. This algorithm can be better performance then metaheuristic methods.
이상운(Sang-Un Lee) 한국컴퓨터정보학회 2015 韓國컴퓨터情報學會論文誌 Vol.20 No.4
시험 일정 계획 수립 문제는 정확한 해를 다항시간으로 구하는 알고리즘이 알려져 있지 않은 NP-완전이다. 이 문제에 대해, Gueret et al.은 O(m⁴) 수행 복잡도의 선형계획법으로 해를 얻고자 하였다. 반면에, 본 논문에서는 O(m) 복잡도의 채색 수 알고리즘을 제안하였다. 제안된 방법은 원 데이터를 교과목에 대한 부적합성 행렬과 그래프로 변환시켰다. 다음으로, 부적합성 제약조건을 충족하면서 최소의 시간으로 시험을 치루기 위해, 최소 차수 정점(교과목)부터 인접하지 않은 정점들을 Ci 색으로 배정하여 Bi상자에 채웠다. 실험 결과, 제안된 알고리즘은 시험일정 계획 수립 문제에 대해 선형계획법의 O(m⁴)를 O(m)으로 단축시키면서도 동일한 해를 얻었다. The exam scheduling problem has been classified as nondeterministic polynomial time-complete (NPcomplete) problem because of the polynomial time algorithm to obtain the exact solution has been unknown yet. Gueret et al. tries to obtain the solution using linear programming with O(m⁴) time complexity for this problem. On the other hand, this paper suggests chromatic number algorithm with O(m) time complexity. The proposed algorithm converts the original data to incompatibility matrix for modules and graph firstly. Then, this algorithm packs the minimum degree vertex (module) and not adjacent vertex to this vertex into the bin Bi with color Ci in order to exam within minimum time period and meet the incompatibility constraints. As a result of experiments, this algorithm reduces the O(m⁴) of linear programming to O(m) time complexity for exam scheduling problem, and gets the same solution with linear programming.
빈도수 기반 주 내포 항 선택과 삭제 알고리즘을 적용한 회로 최소화
이상운(Sang-Un Lee) 한국컴퓨터정보학회 2015 韓國컴퓨터情報學會論文誌 Vol.20 No.4
본 논문은 회로 최소화 문제를 간단하게 풀 수 있는 알고리즘을 제안하였다. 회로 최소화 문제는 수기식 방법인 카르노 맵과 전산화가 가능한 휴리스틱 방법인 Quine-McCluskey 알고리즘이 있다. 그러나 Quine- McCluskey 알고리즘은 변수 개수 n이 증가하면 3<SUP>n</SUP>/n의 메모리와 수행횟수가 요구되는 단점을 갖고 있다. 제안된 방법은 빈도수에 기반하여 내포 항 표를 이용하여 주어진 부울 함수의 최소 항을 포함하는 주 내포 항을 빠르게 추출하는 방법을 적용하였다. 추출된 주 내포 항들 중에서 중복 선택된 여분의 주 내포 항을 빈도수를 적용하여 제거하는 방법을 제안하였다. 제안된 알고리즘은 비록 변수 개수 ?이 증가하여도 다항시간으로 회로를 최소화시킬 수 있는 해를 구할 수 있는 장점을 갖고 있다. 제안된 알고리즘을 3-변수와 4-변수의 다양한 사례들에 적용한 결과 해를 빠르고 정확하게 구할 수 있었다. This paper proposes a simple algorithm for circuit minimization. There are currently two effective heuristics for circuit minimization, namely manual Karnaugh maps and computable Quine-McCluskey algorithm. The latter, however, has a major defect: the runtime and memory required grow 3<SUP>n</SUP>/n times for every increase in the number of variables n. The proposed algorithm, however, extracts the prime implicants (PI) that cover minterms of a given Boolean function by deriving an implicants table based on frequency. From a set of the extracted prime implicants, the algorithm then eliminates redundant PIs again based on frequency. The proposed algorithm is therefore capable of minimizing circuits polynomial time when faced with an increase in n. When applied to various 3-variable and 4-variable cases, it has proved to swiftly and accurately obtain the optimal solutions.
이상운(Sang-Un Lee) 한국컴퓨터정보학회 2014 韓國컴퓨터情報學會論文誌 Vol.19 No.11
본 논문은 NP-완전인 DSP에 대해 O(m)의 다항시간으로 근사 해를 찾는 규칙을 제시한 휴리스틱 알고리즘을 제안하였다. 제안된 알고리즘은 m개의 주어진 운행계획에 대해, 최소의 운전기사인 n명을 배정한 초기 배정 결과를 얻는다. 다음으로, 교환 또는 삽입의 5개 규칙들을 적용하여 초과시간 (OT)과 유휴시간 (IT)를 감소시켜 최소의 비용 (TC)을 얻었다. 제안된 알고리즘은 최적 (또는 근사) 해를 찾는 규칙을 제안한 O(m) 복잡도의 휴리스틱 다항시간 알고리즘임에도 불구하고, 5개의 실험 데이터에 적용한 결과 메타 휴리스틱 기법들과 필적하는 결과를 얻었다. 결론적으로, 본 논문에서는 CSP에 있어서 최적 해를 찾아가는 규칙이 전혀 없는 NP-완전이 아닌 다항시간의 규칙이 존재하는 P-문제가 될 수 있음을 보였다. This paper suggests O(m) polynomial time heuristic algorithm to obtain the solution for the driver scheduling problem, DSP, that has been classified as NP-complete problem. The proposed algorithm gets the initial assignment of n minimum number of drivers from given m schedules. Nextly, this algorithm gets the minimum total time (TC) using 5 rules of swap and insert for decrease of over times (OT) and idle times (IT). Although this algorithm is a heuristic polynomial time algorithm with O(m) time complexity rules to be find a optimal (or approximate) solution, this algorithm is equal to metaheuristic methods for the 5 experimental data. To conclude, this paper shows the DSP is not NP-complete problem but Polynomial time (P)-problem with polynomial time rules.
이상운(Sang-Un Lee) 한국컴퓨터정보학회 2015 韓國컴퓨터情報學會論文誌 Vol.20 No.1
본 논문은 NP-완전으로 알려진 최대 클릭의 정확한 해를 선형시간으로 찾는 알고리즘을 제안하였다. 먼저, 주어진 그래프 G=(V,E)에서 최대 차수 Δ(G) 정점 vi를 클릭의 대표 정점으로 결정한다. vi인접 정점 NG(vi)에서 Δ(G) 정점 vi를 선택하여 NG(vi)∩NG(vj)를 후보 클릭 w와 vk로 결정한다. dG(vk) 내림차순으로 w=w∩NG (vk)를 얻는다. 마지막으로, G?w그래프에서 동일한 절차를 수행하여 얻은 클릭이 기존에 얻은 클릭과 동일하거나 크면 이 클릭을 선정하는 검증과정을 거쳤다. 이와 같은 방법으로 독립된 다수의 클릭도 얻을 수 있는 장점이 있다. 제안된 알고리즘을 다양한 정규와 비정규 그래프에 적용한 결과 모든 그래프에 대해 선형시간 O(n)으로 정확한 해를 구하였다. In this paper, I propose a linear time algorithm devised to produce exact solution to NP-complete maximum clique problem. The proposed algorithm firstly, from a given graph G=(V,E), sets vertex vi of the maximum degree Δ(G) as clique’s major vertex. It then selects vertex vj of Δ(G) among vertices NG(vi) that are adjacent to vi, only to determine NG(vi)∩NG(vj) as candidate cliques w and vk . Next it obtains w=w∩NG(vk)by sorting dG(vk)in the descending order. Lastly, the algorithm executes the same procedure on G?w graph to compare newly attained cliques to previously attained cliques so as to choose the lower. With this simple method, multiple independent cliques would also be attainable. When applied to various regular and irregular graphs, the algorithm proposed in this paper has obtained exact solutions to all the given graphs linear time O(n).