bubbler   2년 전

주어진 입력 파일에서 길이 4000의 경로는 존재하지 않습니다.

아래는 Operations Research SE의 RobPratt 님께서 확인해주신 내용입니다.

https://or.stackexchange.com/a...

ILP 모델링에서 하나의 단순 경로를 보장하는 조건을 넣는 것은 |V|개의 variable이 추가로 필요하고 최적화가 잘 되지 않기 때문에, 이 조건을 빼고 최적화를 시도해볼 수 있습니다. 이렇게 하면 하나의 경로와 0개 이상의 subtour를 포함하는 subgraph가 찾아지게 되어 원래 문제의 답이 되지는 않으나, 문제의 최적해의 upper bound 값을 얻을 수 있습니다. (링크된 글의 그림을 보게 되면 자잘한 닫힌 고리들이 여러 개 보이는데 이들이 subtour입니다.) 이렇게 조건이 완화된 문제의 최적해가 3988이므로, 원래 문제에서도 길이 3988을 초과하는 경로는 존재하지 않습니다.

lycoris1600   2년 전

그 글에 첨부된 사진이 최적해가 아닐 수도 있지 않을까요..? 눈으로 봐도 몇 가지 개선점이 보입니다

lycoris1600   2년 전

preview

제가 동그라미 친 부분만 추가해도 길이가 12 이상 늘어날 것 같습니다

bubbler   2년 전

입력 파일을 보시면 아시겠지만 회색 칸은 입력에서 X인 칸, 그러니까 사용할 수 없는 칸입니다. 제가 보기에는 파란색 표시해주신 어떤 곳에서도 회색 칸을 쓰지 않고 길이를 늘릴 방법은 보이지 않네요.

저 최적해를 구할 때 쓰인 제약조건을 좀 더 구체적으로 다시 쓰면, 회색 칸은 사용 불가이고, 흰 칸 중 일부를 검은색으로 칠하되 모든 검은 칸은 격자 밖에서 시작하는 경로의 양 끝점을 제외하고 모두 정확히 2개의 검은 칸과 이웃해야 합니다. 회색 칸도 그렇지만 막다른 길이 수십 개가 있는데 그것도 하나 빼고 전부 못 쓴다고 보시면 됩니다.

lycoris1600   2년 전

회색 칸이 장애물이었군요.. 제가 착각한 것 같습니다

댓글을 작성하려면 로그인해야 합니다.