지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2015.9
- 수록면
- 97 - 103 (7page)
- DOI
- 10.14801/jkiit.2015.13.9.97
이용수
초록· 키워드
오류제보하기
n명의 참석자 각각에 대한 n-1명의 선호도를 조사한 데이터가 주어졌을 때, 안정된 동숙자 문제의 최적 해는 일반적으로 O(n) O(n<SUP>2</SUP>) 복잡도의 Irving 알고리즘으로 구한다. Irving 알고리즘은 단계 1에서 O(n<SUP>2</SUP>)의 Gale-Shapley 알고리즘으로 초기 해 S를 구한 다음, 단계 2에서는 회전에 의해 반복적으로 집합 S를 변경한다. 본 논문은 안정된 동숙자 문제에 대해 O(n) 알고리즘을 제안한다. 먼저, 사전에 n-1 × n 행렬의 상삼각행렬에 대해 선호도 합 s<SUB>ij</SUB> (p<SUB>i</SUB>의 선호도 +p<SUB>i</SUB>의 p<SUB>i</SUB> 선호도)을 구하였다. 단계 1에서는 최소 선호도 합 min s<SUB>ij</SUB>를 선택하고, i, j의 행과 열의 값을 삭제하는 과정을 n/2회 수행하였다. 단계 2에서는 방해 쌍 존재시 해를 개선하였다. 제안된 알고리즘을 10개의 동숙자 문제에 적용한 결과 O(n) 복잡도로 간단하면서도 빠르게 해를 구하였다.s<SUB>ij</SUB>
목차
요약
Abstract
Ⅰ. 서론
Ⅱ. Irving 알고리즘
Ⅲ. 최소 선호도 합 선택 알고리즘
Ⅳ. 알고리즘 적용 및 결과 분석
Ⅴ. 결론 및 추후 연구과제
References
참고문헌 (10)
참고문헌 신청
[학술지(정기간행물)] - R. W. Irving / 2002 / The Stable Roommates Problem with Ties / Journal of Algorithms 43 (1) : 85 ~ 105
[인터넷자원] - Wikipedia / / Stable Marriage Problem
[단행본] - D. Abraham / 2006 / Approximation and Online Algorithms / Springer : 1 ~ 14
[보고서] - M. X. Goemans / 2007 / 18,433 Combinatorial Operation:Lecture Notes on Bipartite Matching
[학술지(정기간행물)] - D. Gale / 1962 / College Admissions and the Stability of Marriage / American Math. Monthly 69 (1) : 9 ~ 15
[인터넷자원] - Wikipedia / / Stable Marriage Problem
[단행본] - D. Abraham / 2006 / Approximation and Online Algorithms / Springer : 1 ~ 14
[보고서] - M. X. Goemans / 2007 / 18,433 Combinatorial Operation:Lecture Notes on Bipartite Matching
[학술지(정기간행물)] - D. Gale / 1962 / College Admissions and the Stability of Marriage / American Math. Monthly 69 (1) : 9 ~ 15
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
정수계획모형과 완화 기법을 활용한 사관학교 생활관 배정 알고리즘
한국경영공학회지
2022 .09
-
모바일 접근성을 고려한 동거인들의 원활한 의사소통을 위한 애플리케이션 구현
디지털콘텐츠학회논문지
2019 .04
-
최대 반감도 합-삭제 방법에 기반한 결혼문제 알고리즘
한국인터넷방송통신학회 논문지
2015 .01
-
한계 알고리즘을 적용한 결혼문제
한국컴퓨터정보학회논문지
2015 .11
-
이중경로 경쟁 방식을 적용한 할당문제 알고리즘
한국정보기술학회논문지
2015 .12
-
An Assignment Problem Algorithm Using Minimum Cost Moving Method
한국컴퓨터정보학회논문지
2015 .08
-
Stable Diffusion 을 이용한 얼굴 비식별화 기법
한국통신학회 학술대회논문집
2023 .06
-
Research of Graph-analytical Methods for a Vehicle Motion Planning
제어로봇시스템학회 국제학술대회 논문집
2015 .10
-
Survival Probability Map Based Path Planning of Mobile Robots
제어로봇시스템학회 국제학술대회 논문집
2015 .10
-
안정된 결혼문제에 대한 최적화 알고리즘
한국인터넷방송통신학회 논문지
2018 .01
-
An Improved Stereo Matching Algorithm with Robustness to Noise Based on Adaptive Support Weight
JIPS(Journal of Information Processing Systems)
2017 .01
-
A Fast Image Matching Method for Oblique Video Captured with UAV Platform
한국측량학회지
2020 .04
-
Method for the Initial Value of Weights to Obtain Stable Results of Unsupervised Neural Network
Proceedings of The International Workshop on Future Technology
2019 .01
-
위성 간 링크된 다중통신위성 일정계획 문제의 다항시간 알고리즘
한국정보기술학회논문지
2015 .08
-
Complete Time Algorithm for Stadium Construction Scheduling Problem
한국컴퓨터정보학회논문지
2015 .09
-
Parallel Computation of Z-Function for Order-Preserving Pattern Matching and Order-Preserving Multiple Pattern Matching
Journal of KIISE
2018 .08
-
Stable Diffusion 기반의 3D 캐릭터 생성에 대한 활용 및 비교 분석
한국정보과학회 학술발표논문집
2024 .06
-
Stable Marriage 알고리즘에 기반한 드론택시 승객 스케쥴링 기법
한국통신학회 학술대회논문집
2022 .06
-
Stable Diffusion 모델의 가속화 및 경량화 기법
한국통신학회 학술대회논문집
2024 .11
-
V2G 서비스에 대한 소비자 선호도 조사
대한산업공학회 추계학술대회 논문집
2024 .10
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2016-566-001867090