A^*-알고리즘의 휴우리스틱 유도를 위한 문제모델의 설정

유석인(Suk In Yoo) 한국정보과학회 1987 정보과학회논문지 Vol.14 No.3

To reduce the search space required to solve a problem using A^*-algorithm, it may be necessary to define the heuristic function f(e_x) = g(e_x) + h(e_x), where e_x is the intermediate state of the problem during the solving process, in such a way that the value of h(e_x) is closer to the actual minimum cost of the path from e_x to the goal state. This paper suggests the method to model a problem on which the tighter value of h(e_x) can be computed. The suggested model is illustrated by the three well-known problems: the 8-puzzle problem, the robot planning problem, and the consistent labeling problem. A^*알고리즘을 이용하여 문제를 풀 때 요구되는 탐색공간을 줄이기 위하여는 각 문제상태를 평가하는 휴우리스틱 값, 즉 주어진 문제상태 부터 최종 문제상태에 까지 이르는 거리의 측정값을 실제값이 접근시키는 방법이 필요하다. 본 논문은 이를 위해 주어진 문제를 어떻게 모델화 하는 것이 최적의 효과를 거둘 수 있는 지에 대해 거론하고 예를 통해 이를 설명한다.

Rete Net에 의한 객체 지향 데이타베이스의 질의 최적화

유석인(Suk I. Yoo),김태권(Tae G. Kim) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.2

진보된 응용프로그램에서 사용되는 복잡한 객체들은 평면적으로 표현하는 관계형 데이타 모델로 다루기가 어렵다. 이러한 객체들을 보다 자연스럽게 모델링하고 다루기 위하여 등장한 객체 지향 데이타 모델은 아직 표준적인 형태가 없고 상대적으로 복잡하기 때문에 처리면에서 어려움이 따른다. 특히 사용자 정의 타입, 경로 수식, 메쏘드 호출 등으로 인하여 질의어 최적화에 어려움이 많다. 본 논문에서는 표준 질의어 SQL을 객체 지향 개념이 제공되도록 확장하고, 인공지능 분야에서 대규모 데이타에 대하여 가장 효율적인 패턴매칭 기법 중의 하나인 Rete 알고리즘을 수정 보완하여 검색 연산의 처리 기법을 제안한다. 이 기법은 질의의 검색 조건에 대응하는 검색망을 만들고, 관련된 모든 객체들을 흘려 보내면 그 조건을 만족하는 객체만 그 망을 통과 하도록 검색 연산을 수행함으로써 전체적인 검색 연산의 효율성을 높이게 한다. In advanced applications it is hard to manipulate the complex objects with a relational data model which treats them by relations only. An object-oriented data model thus has been designed to remedy the shortcomings of the relational model for natural modelling and manipulation, although it has some difficulties in processing its features because of no standard model provided and the ralative complexity. Specially, there are difficulties in query processing and optimization due to path expression, user-defined type, and methods call. This paper suggests one method to process the select operation of a query language which has been developed on the standard SQL for object-oriented paradigm. The method uses a modified algorithm of Rete which has been known to be one of the most efficient pattern matching algorithms for the large data It constructs the selection net corresponding to its condition and flows all objects m a scope into the net. The operation is performed by passing these objects satisfying its condition, which would improve the performance of the operation efficiently.

Obase : 객체지향 데이타베이스 관리 시스템

유석인(Suk I. Yoo),홍은지(Eunji Hong),이영훈(Young-Whun Lee),박현주(Hyunju Park),이주흥(Ju-Heung Lee),전용석(Yong S. Jun),김태권(Tae Gwon Kim),장혜진(Hai Jin Chang) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.10

최근에 새로운 데이타베이스 응용 분야들을 개발하기 위해 객체지향 데이타 모델과 이를 기반으로 하는 객체지향 데이타베이스 관리 시스템들이 등장하였다. 본 논문에서는 이러한 연구 추세와 기존의 객체지향 데이타베이스 시스템들에 대한 분석을 기반으로 새로운 객체지향 데이타베이스 관리 시스템인 Obase의 설계 및 구현을 제시한다. Obase는 C++ 언어의 객체 모델을 확장한 데이타 모델을 기반으로 객체지향 개념들을 지원하고 데이타베이스 관리 기능들과 새로운 응용 분야에서 필요로 하는 기능들을 제공한다. 특히, Obase는 정적인 수정 탐지, 지속적 이름 관리, 정적인 타입 검사 환경에서의 스키마 변화 관리 등의 진보된 기능들을 제공한다. In recent years the object-oriented data models and the object-oriented database management systems have been introduced to support advanced database applications. Based on those introduced data models and systems, this paper presents a new object-oriented database management system, called the Obase, which has been developed using the extended object data model of the C++ language. The Obase supporting object-oriented concepts provides all functionalities necessary for the conventional database management as well as some advanced functionalities such as static update detection, persistent name management, and schema evolution under static type checking.

Integration of Expert Systems and Object-Oriented Database Management Systems

유석인(Suk-In Yoo) 한국정보과학회 1991 한국정보과학회 워크샵 Vol.1991 No.3

일반적 문제 해결법을 위한 A* 알고리즘의 적용

유석인(Suk In Yoo) 한국정보과학회 1986 정보과학회논문지 Vol.13 No.3

이 논문은 A* 알고리즘을 이용하여 일반적인 문제를 해결할 수 있는 방법론을 제시한다. A*이용에 핵심이 되는 휴우리스틱 (heuristics)은 주어진 문제의 제약조건들을 완화시켜 유도되는 단순화된 문제로부터 생성되어진다. 이 논문에서 제시되어지는 일반적인 방법론은 5개의 널리 알려진 문제들을 통해 예증되어지고 그 효율성이 이 5개의 각각에 대해 개발된 특정한 문제풀이 방법과 비교되어진다. This paper provides a methodology for modelling a problem for its solution using the A*algorithm. The heuristic used for A*is computed from the simplified problem which is derived by relaxing each of the predicate formulas describing the rules and the goal state of the problem. The generated heuristic is claimed to satisfy the conditions of admissibility and monotonicity. The overall procedure for deriving the heuristic is illustrated by five well known problems, namely, the 8-puzzle problem, the travel ing salesman problem, the robot planning problem, the theorem proving problem, and the consistent labeling problem. The values of the heuristic generated by our procedure are compared against those for the problem-oriented heuristics for some of these problems.

OpenGDBC : RDBMS를 사용하는 GIS를 위한 미들웨어

유석인(Suk I. Yoo),홍은지(Eunji Hong),이재호(Jaeho Lee),박현주(Hyunju Park),김승민(Seung Min Kim),김선호(Seonho Kim),정소영(SoYoung Jeong),전준범(Joonbeom Jeon) 한국정보과학회 1998 한국정보과학회 학술발표논문집 Vol.25 No.2Ⅰ

실세계에서는 RDBMS가 가장 많이 사용되고 있으며, 가까운 미래에도 RDBMS를 사용하는 경향이 크게 바뀌지 않을 전망이므로, 이미 보유하고 있는 RDBMS를 이용하여 효율적으로 지리 공간 정보를 관리하는 것이 중요하다. 하지만, 기존의 RDBMS는 몇몇 특정한 시스템을 제외하고는 아직 지리 공간 데이터를 위한 특별한 처리를 고려하지 않고 있으며, 공간 연산자를 포함하는 질의를 처리하지 못하고 있다. 본 논문에서는 분산 환경에서 다양한 종류의 RDBMS에 지리 공간 데이터와 이와 연관된 애트리뷰트 값을 함께 저장하려는 GIS를 위한 미들웨어인 OpenGDBC(Open Geo-DataBase Connection)를 제시한다. OpenGDBC는 다음과 같은 특징을 가지고 있다. 첫째, 세계적인 표준 기구인 OpenGIS의 명세를 따른다. 둘째, CORBA를 이용하여 분산 환경을 지원한다. 셋째, 다양한 종류의 RDBMS에 지리 공간 데이터와 이에 연관된 애트리뷰트 값을 통합된 형태로 저장할 수 있도록 지원한다. 넷째, 공간 연산자를 포함한 질의를 입력으로 받아, 이를 분석하여 OpenGDBC가 제공하는 공간 연산자를 수행한 후, RDBMS에 적합한 질의 형태로 변경하고, RDBMS에서 변경된 질의를 수행하게 하여 질의 결과를 반환하므로, 다양한 종류의 RDBMS에 저장된 지리 공간 데이터에 대해 공간 연산자를 포함하는 질의를 처리할 수 있다.

객체지향 데이타베이스에서 스키마 변화를 위한 실험 환경

홍은지,유석인(Eunji Hong),Suk I. Yoo 한국정보과학회 1997 정보과학회 컴퓨팅의 실제 논문지 Vol.3 No.2

객체지향 데이타베이스의 장점인 코드 재사용과 계승은 여러 응용 프로그램에게 클래스를 공유하게 한다. 클래스의 코드는 그 정확성이 검증된 상태에서 사용되지 않는다며, 여러 응용 프로그램에서 그 원인을 발견하기도 어려울 뿐더러 복구하기 힘든 오류가 발생할 가능성이 크다. 기존의 스키마 변화 관리체제는 변화된 클래스 정의를 실험할 수 있는 환경을 제공하지 않기 때문에 변화된 클래스의 정확성을 검증하기 어렵다. 본 논문은 객체지향 데이타베이스에서의 다중 사용자 개발 환경을 위한 새로운 스키마 변화 관리 체제를 제시한다. 본 체제는 사용자가 클래스를 수정한 후 코드가 안정화된 후에 비로소 다른 응용 프로그램에 영향 끼칠 수 있도록 허용해서 오류 발생을 최소화할 수 있도록 지원한다. 또한, 클래스 수정자가 클래스를 수정하고 검증하는 동안에도 해당 클래스를 사용하는 다른 사용자들이 해당 클래스와 그 인스턴스를 공유할 수 있도록 지원한다. Reuse and inheritance which are merits of the object-oriented databases make programs share classes. If the code for a class is used without verification, it is possible to cause errors. It is hard to detect such errors and to correct them. This paper introduces a schema evolution mechanism which provides an experimental environment and reduces a possibility of being shared of error-prone classes. We allow the user to postpone reflecting the effect of the class modification in applications until the class is mature, so errors are minimized. In addition, we allow other users to use the class and its instances as its unmodified definition while he/she modifies and tests the class.

RBF 신경망을 이용한 내용 기반 영상 검색

이형구,유석인,Lee, Hyoung-K,Yoo, Suk-I 한국정보과학회 2002 정보과학회논문지 : 소프트웨어 및 응용 Vol.29 No.3

내용 기반 영상 검색에서 대부분의 기존 방법들은 서로 다른 특징들 사이의 선형 관계를 가정하고 또 사용자가 직접 각 특징의 가중치를 설정하도록 한다 허나 특징들 사이의 관계가 선형적으로 가정된 하에서는 고차원의 개념과 인간의 지각 주관성을 충분히 표현할 수 없는 단점이 있다. 본 논문에서는 신경망에 기반한 영상 검색 모델이 제안된다. 이는 RBFN을 이용한 내용 기반 영상 검색 기법과 인간컴퓨터 상호작용의 접근 방법을 기반으로 구축되었다. RBFN을 이용하여 특징들 사이의 비선형적 관계를 추출해낼 수 있고 사용자가 처음에 질의 영상을 선택하고 관련성 피드백을 통하여 점차적으로 목표 영상을 찾아나가도록 함으로써 영상의 비교를 더 정확하게 할 수 있다. 실험은 145개의 클래스로 구분되며 1,015개의 영상을 포함하는 데이타베이스를 사용하여 재생과 정도를 계산하였다. 실험 결과는 제안된 방법의 재생과 정도가 각각 93.45%과 80.61%로서, 기존의 선형 결합 방법이나 순위 기반 방법 그리고 역전파 알고리즘에 기반한 방법보다 더 뛰어난 검색 성능을 지님을 보여준다. In content-based image retrieval (CBIR), most conventional approaches assume a linear relationship between different features and require users themselves to assign the appropriate weights to each feature. However, the linear relationship assumed between the features is too restricted to accurately represent high-level concepts and the intricacies of human perception. In this paper, a neural network-based image retrieval (NNIR) model is proposed. It has been developed based on a human-computer interaction approach to CBIR using a radial basis function network (RBFN). By using the RBFN, this approach determines the nonlinear relationship between features and it allows the user to select an initial query image and search incrementally the target images via relevance feedback so that more accurate similarity comparison between images can be supported. The experiment was performed to calculate the level of recall and precision based on a database that contains 1,015 images and consists of 145 classes. The experimental results showed that the recall and level of the proposed approach were 93.45% and 80.61% respectively, which is superior than precision the existing approaches such as the linearly combining approach, the rank-based method, and the backpropagation algorithm-based method.

객체 지향 데이타베이스 관리 시스템에서의 사용자 인터페이스 설계 및 구현

전용석(Yong Suk Jun),김태권(Tae Gwon Kim),유석인(Suk I Yoo) 한국정보과학회 1991 한국정보과학회 학술발표논문집 Vol.18 No.2

객체 지향 데이타베이스 관리 시스템은 데이타베이스 관리 시스템의 기법과 객체 지향 프로그래밍 기법을 통합하는 시스템이다. 본 논문에서는, 객체 지향 데이타베이스 관리 시스템의 사용자 인터페이스 언어로 pC++를 설계하였다. 이 pC++는 객체 지향 프로그래밍 언어인 C++에 객체 지향 데이타 모델의 개념을 도입하여, 기존의 데이타베이스 관리 시스템에서의 결합 불일치 문제를 해결한다. 또, C++의 계산 능력과 타입 검사 등의 기능을 이용하여 데이타의 처리 능력과 생산성을 향상시킨다. 그리고, 객체 지향 데이타 모델 상에서의 사용자 인터페이스 유틸리티들을 pC++로 X 윈도우 상에서 구현하였다.

과거의 경험을 이용한 문제해결 방법에 관한 연구

신호근(HoGeun Shin),유석인(Suk I. Yoo) 한국정보과학회 1987 한국정보과학회 학술발표논문집 Vol.14 No.2

본 논문에서는 상태공간(state-space) 으로 표현되는 문제의 해결경로(solution path) 를 구할 때 해결경로를 찾을때까지 소요되는 탐색반경을 줄이는 방법으로 과거의 경험을 이용하는 방법을 제안한다. 즉, 어떤 문제의 예시(instance) A 를 해결하고 나서 이와 동일한 목표 상태를 갖는 다른 예시 B를 풀려고 할 때, A 를 해결하는 수행과정에서 얻어진 경험지식을 이용한다면 B를 해결하는 수행과정의 효율성을 높일 수 있다. 본 논문에서는 이러한 경험적 지식을 저장하여 같은 문제의 여러 예시들을 해결하는데 이 지식을 사용함으로써 문제의 초기상태 부터 보다 적은 수의 중간상태들을 거쳐 목표상태에 도달할 수 있는 방법을 제시한다.