1
다음 문제에 대한 알고리즘이나 관련 작업이 있습니까?최소한의 움직임으로 교차점을 제거하기 위해 선분을 이동하는 방법은 무엇입니까?
2D에서 선분 세트가 주어지면 선분을 (수평 또는 수직으로) 움직여 교차를 제거하여 전체적인 움직임을 최소화하는 방법은 무엇입니까? 끝점의 교차점을 허용 할 수 있습니다.
A
답변
0
당신은 세그먼트의 움직임의 수를 최소화하려는 경우 각 세그먼트는 그래프의 정점이다 을하고있는 경우 두 꼭지점 사이의 가장자리가 :
당신은 그래프 문제로 선분의 문제를 변환 할 수 있습니다 두 개의 세그먼트가 서로 교차합니다. 모든 모서리 중 적어도 하나의 끝점을 포함하는 최소 정점 수를 찾고 싶습니다 (모든 세그먼트를 이동하면 더 이상 교차가 없기 때문입니다). 이것은 불행하게도 NP 하드이지만, 근사 알고리즘이 존재하는 버텍스 커버 문제입니다.
관련 문제
- 1. confim 대화 상자를 제거하기 위해 greasemonkey 스크립트를 작성하는 방법은 무엇입니까?
- 2. 장치의 특정 응용 프로그램을 제거하기 위해 broadcastrecevier를 구현하는 방법은 무엇입니까?
- 3. 공백/점프를 제거하기 위해 SQL 색인을 수정하는 방법은 무엇입니까?
- 4. 간단한 2D 이미지에서 선분을 추출하는 간단하고 효율적인 방법은 무엇입니까?
- 5. 청취자가 sd 카드를 제거하기 위해
- 6. 텍스트보기를 이동하는 방법은 무엇입니까?
- 7. 중복을 제거하기 위해 C# group by
- 8. 예외로 파일을 이동하는 방법은 무엇입니까?
- 9. 구조체를 클래스로 이동하는 방법은 무엇입니까?
- 10. 파이썬에서 N-many리스트의 교차점을 취함
- 11. 중복을 제거하기 위해 핵심 데이터를 술어로 정렬
- 12. 링크를 제거하기 위해 jquery를 사용하지만 이미지는 제외합니다.
- 13. 별도의 DB 쿼리를 제거하기 위해 리팩터링 코드
- 14. REST 서비스에서 .SVC를 제거하기 위해 라우팅 추가하기
- 15. FIND_IN_SET을 제거하기 위해 쿼리를 다시 작성 하시겠습니까?
- 16. 부모로부터 요소를 제거하기 위해 jquery를 사용한다.
- 17. 주변을 제거하기 위해 문자열을 나누기 < and > 문자
- 18. 파이썬에서 행렬의 가능한 모든 교차점을 결정하는 가장 좋은 방법은 무엇입니까?
- 19. mssql 데이터베이스에서 Access로 데이터를 이동하는 방법은 무엇입니까?
- 20. Android : sqlite 데이터베이스 제거하기
- 21. foreach 루프에서 단계를 뒤로 이동하는 방법은 무엇입니까?
- 22. VBScript에서 최소한의 구분 기호와 시간대를 사용하여 datetime을 포맷하는 방법은 무엇입니까?
- 23. 간격의 교차점을 찾는 알고리즘
- 24. 최소한의 프로젝트 재구성?
- 25. 최소한의 응용 프로그램 서버 종속성을 유지하는 방법은 무엇입니까?
- 26. jQuery SVG를 사용하여 SVG를 이동하는 방법은 무엇입니까?
- 27. 최소한의 메모리 사용을 위해 SAX 핸들러의 character() 함수를 구현하는 방법은 무엇입니까?
- 28. 최소한의 성능 저하로 C & C++ 라이브러리를 동기화하는 방법은 무엇입니까?
- 29. Derby.log 제거하기
- 30. 최소한의 중복 코드로 유지 보수 가능한 코드를 만드는 방법은 무엇입니까?
최소를 어떻게 정의합니까? 최소 이동 횟수 또는 거리의 거리/제곱합의 최소값? – biziclop
또한 줄 끝점을 개별적으로 이동할 수 있습니까? 아니면 줄 길이와 방향이 const입니까? – LumpN