matching order 범위 관련 질문

[ialy1595]

기존의 알고리즘의 경우 backtracking 단계에서 DAG-Graph DP에 사용했던 q_D를 그대로 이용하여 DAG-Ordering을 한 후, 이 ordering 안에서 extendable vertex가 여러개인 경우 adaptive matching order를 사용한다고 이해했습니다. 따라서 처음에는 이번 챌린지에서 말하는 matching order가 위 단계에서 adaptive matching order를 의미하는 것으로 생각했습니다. 그러나 이 경우에는 DAG-Graph DP에 사용되었던 q_D가 주어지지 않기 때문에 구현에 따라 q_D가 달라질 문제가 있는 것 같아서 이슈를 살펴보던 중 #11 이슈에서 조교님이 q_D를 아는 것이 필수가 아닌 것 처럼 말씀하신 것을 보았습니다. 이에 따라 논문을 다시 살펴본 결과 matching order와 adaptive matching order를 서로 다른 용어로 사용하는 것 처럼 보였습니다. 이러한 연유로 챌린지에서 의도하는 matching order의 범위와 q_D에 대해 다음 중 어떤 게 맞는지 여쭙고 싶습니다.

1. matching order는 DAG-Ordering와 adaptive matching order를 모두 포함하는 용어이다. 따라서 이번 챌린지에서 DAG-Ordering을 사용할지 여부도 자유이다.

2. matching order는 adaptive matching order를 의미한다. 따라서 DAG-Ordering을 필수로 사용해야 하지만, q_D는 DAG-Graph DP에서 사용된 q_D와 달라도 된다.

3. matching order는 adaptive matching order를 의미한다. 따라서 DAG-Ordering을 필수로 사용해야 하고, q_D 또한 DAG-Graph DP에서 사용된 것과 동일하게 만들어내야 한다.

[JihoonJang]

안녕하세요.

말씀해주신 3가지 중 1번이 맞습니다 (엄밀히 말하면 논문에서 정의된 DAG-Ordering도 adaptive matching order에 해당합니다). DAG-ordering은 하나의 답이 될 수 있지만 꼭 DAG-ordering으로 구현하시지 않으셔도 됩니다.

감사합니다.

[ialy1595]

답변 감사합니다!