최소 단어 이상 선택하여야 합니다.
최대 10 단어까지만 선택 가능합니다.
다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기The journal of the institute of internet, broadcasting and communication : JIIBC, v.19 no.1, 2019년, pp.253 - 259
The wedding seating problem(WSP) is to finding a minimum loss of guest relations(sit together preference) with restricted seats of a table for complex guest relation network. The WSP is NP-hard because of the algorithm that can be find the optimal solution within polynomial-time is unknown yet. Ther...
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
핵심어 | 질문 | 논문에서 추출한 답변 |
---|---|---|
결혼 연회장 좌석 배정 문제란? | 복잡한 관계(동석 선호도)망을 갖고 있는 결혼 연회장에 참석하는 하객들에 대해 테이블 당 좌석 수가 한정되어 있는 경우, 최소의 관계 손실을 갖도록 좌석을 배정하는 문제를 결혼 연회장 좌석 배정 문제(WSP)라 한다. 이 문제는 다항시간을 해를 구하는 방법이 알려져 있지 않아 NP-난제로 분류되어 있으며, 컴퓨터 프로그램 도움 없이 손으로 다항시간으로 해를 구하는 알고리즘은 알려져 있지 않다. | |
WSP는 어떤 난제로 분류되어 있는가? | 복잡한 관계(동석 선호도)망을 갖고 있는 결혼 연회장에 참석하는 하객들에 대해 테이블 당 좌석 수가 한정되어 있는 경우, 최소의 관계 손실을 갖도록 좌석을 배정하는 문제를 결혼 연회장 좌석 배정 문제(WSP)라 한다. 이 문제는 다항시간을 해를 구하는 방법이 알려져 있지 않아 NP-난제로 분류되어 있으며, 컴퓨터 프로그램 도움 없이 손으로 다항시간으로 해를 구하는 알고리즘은 알려져 있지 않다. 본 논문에서는 최대 관계를 갖는 두 하객을 분리하면 최소 절단(관계 손실 최소화)을 얻지 못한다는 이론에 기반하여 최소절단 값을 갖도록 하객 관계망을 분할하는 규칙을 적용하였다. | |
최소절단 알고리즘은 어떤 개념에 입각하는가? | 최소절단 알고리즘은 최대 동석 선호도를 가진 두 하객은 서로 다른 테이블로 분리시키지 않아야만 선호도 손실을 최소로 할 수 있다는 개념에 입각하여, 최대 선호도 값을 가진 두 정점을 하나의 정점으로 묶는 양분법으로 1:n-1, 2:n-2, ⋯, n-1:1을 수행하고, 1:n-1과 n-1:1 중에서 최소 절단 값을 가진 경우를 결정하였다. 또한, 추가적으로 필요한 2:2:2⋯,3:3:⋯,2:3:⋯등도 구하였다. |
M. L. Bellows and J. D. Luc Peterson, "Finding an Optimal Seating Chart," Annals of Improbable Research, pp. 1-7, Feb. 2012.
R. Lewis, "Constructing Wedding Seating Plans: A Tabu Subject," The International Conference on Genetic and Evolutionary Methods, pp. 1-7, Jul. 2013.
R. M. R. Lewis, "A Guide to Graph Colouring: Algorithms and Applications," p. 153, Springer, 2016, ISBN:978-3-319-5728.
R. Lewis and F. Carroll, "Creating Seating Plans: A Practical Application," Journal of the Operational Research Society, Vol, 67, No. 11, pp. 1353-1362, Oct. 2016, doi:10.1057/jors.2016.34
M. Stiles, "Optimizing Wedding Reception Seating Charts Using Genetic Algorithm," https://github.com/meganstiles/Seating_Chart/blob/master/OptimizingWeddingReceptionSeatingChartUsingaGeneticAlgorithm.pptx, May 2017.
R. A. Martin, "Optimising Linear Seating Arrangements with a First-Principles Genetic Algorithm," Data Structures and Algorithms, viXra.org, May 2016, viXra:1605.0109
P. Olivier, A. Lodi, and G. Pesant, "A Comparison of Optimization Methods for Multi-Objective Constrained Bin Packing Problems," Data Science for Real-time Decision Making, Dec. 2017, DS4DM-2017-015
A. Tajima and S. Misono, "Using a Set Packing Formulation to Solve Airline Seat Allocation/Reallocation Problems," Journal of the Operations Research Society of Japan, Vol. 42, No. 1, pp. 32-44, Mar. 1999, doi:10.1016/S0453-4514 (99)80003-9
A. Vidotto, K. N. Brown, and J. C. Beck, "Managing Restaurant Tables Using Constraints," Knowledge-Based Systems, Vol. 20, No. 2, pp. 160-169, Mar. 2007, doi:10.1016/j.knosys.2006.11.002
O. D. Soleil, "Excel Solution: Who Should Sit Where?," http://datascopic.net/seating/, Jul. 2015.
E. Lawler "Combinatorial Optimization Networks and Matroids: 4.5. Combinatorial Implications of Max-Flow Min-Cut Theorem, 4.6. Linear Programming Interpretation of Max-Flow Min-Cut Theorem," Dover. pp. 117-120, 2001, ISBN:0-486-41453-1.
*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.
출판사/학술단체 등이 한시적으로 특별한 프로모션 또는 일정기간 경과 후 접근을 허용하여, 출판사/학술단체 등의 사이트에서 이용 가능한 논문
※ AI-Helper는 부적절한 답변을 할 수 있습니다.