여행 세일즈맨 알고리즘을 사용하여 문제를 해결 했습니까?
https://stackoverflow.com/questions/264050
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
NP 완전성의 맥락에서 대학에서 TSP를 공부했습니다. 나는 실제로 실제 문제에 적용되는 상황이 없었습니다. 약간의 연구에 따르면 드릴을 옮기기 위해 가장 저렴한 경로를 선택하는 데 사용되었으며, 이는 회로 보드에 구멍을 뚫는 것입니다. 그게 내가 찾을 수있는 전부입니다.
당신은 그것을 사용하고 있습니까? TSA에는 어떤 다른 실제 응용 프로그램이 있습니까?
해결책
이 스레드의 다른 사람들과 마찬가지로 나는 대학에서 NP 완전한 문제에 대한 솔루션을 만들었습니다 (친구를위한 부업 프로젝트) - 스케줄링 프로그램. 내가 그의 문제에 대해 일하기로 동의했을 때 나는 NP가 무엇인지 몰랐다. 나는 나중에 문제를 해결하기 위해 상당히 좋은 휴리스틱을 생각해 냈다는 것을 깨달았습니다. 물론 실제 속임수는 사용자에게 해결책이없고 문제를 과도하게 제한했다고 언제 알 수있었습니다.
그것은 나의 최종 이론적 수업과 현실 세계를 하나로 모으는 좋은 방법이었습니다.
다시 말하지만, 휴리스틱과 "충분히 충분히"는 이상적인 솔루션을 찾고 구현하는 비용으로 인해 거의 최적화 된 솔루션이 선호되는 실제 세계 사용에 일반적으로 적합합니다.
다른 팁
나는 한때 "스 퀴글 (squiggle)"으로 직사각형 영역을 상당히 균일하게 채우는 프로그램을 작성하는 작업을 받았다. 나의 첫 번째 시도는 사각형 내에서 임의의 포인트를 생성하고 (반드시 절대 가장 짧은 것은 아님) 여행을 찾는 것이 었습니다. 불행히도이 접근법은 잘 작동하지 않았으며 포기했습니다.
그래도 결국 문제를 해결했습니다.
나의 성공적인 방법은 TSP와 관련이 없지만 호기심을 위해 다음을 요약 할 것입니다.
단일 라인 세그먼트로 시작하십시오. 이제 루프 : 라인이 "너무 길다"라면 두 개로 나누십시오. 각 지점을 무작위로 조금 움직이지만 점수를 서로 격퇴하십시오. 거의 진행할 수 없을 때 루프를 끝내십시오. 세부 사항이 있지만 아이디어를 얻을 수 있기를 바랍니다.
물론 이것은 각도 경로를 생성하지만 (허용 가능했을 것입니다) 모서리를 부드러운 호로 바꾸는 것은 쉽습니다.
그리고 네 코드를 유지했습니다.
나는 개인적으로 그것을 사용한 적이 없지만 드릴링 회로 보드 외에 다른 응용 프로그램은 여러 곳으로 가고 싶다면 진공 청소기를 판매하는 것입니다. 문제 해결책을 사용하여 정확히 한 번 어디에서나 방문하는 가장 저렴한 방법을 결정할 수 있습니다.
문제가 언제인지 아는 것은 NP-HARD가 해당 문제를 해결하는 솔루션을 배제하는 데 유용합니다. TSP (또는 다른 NP- 하드 문제)가 사소한 크기의 문제에 대한 추악한 머리를 뒷받침 할 때마다 알다 당신은 잘못된 길로 향하고 있습니다. 당신은 그것을 알고있을뿐만 아니라 당신은 왜, 그리고 자신의 상사/팀원/누구에게도 자신있게 말할 수 있습니다.
그것은 말한다 http://en.wikipedia.org/wiki/concorde 그것을 드러냅니다 :
콩코드는 유전자 매핑 문제, [1] 단백질 기능 예측, [2] 차량 라우팅, [3] 비트 맵 이미지를 연속 선 그림으로 전환, [4] 지진 조사, [5] 및 조합 최적화 문제의 스케일링 특성 연구. [6
예, 경로 계획을위한 Geocaching 응용 프로그램에서 사용합니다.
현재 포인트 사이의 직선 거리를 사용하지만 올바르게 (내가 돌아 다닐 때) 도로를 사용하여 점 사이의 거리를 계산해야합니다.
대부분의 경우 NP- 완성/하드 문제를 해결하는 알고리즘을 사용하고 싶지 않습니다. 당신은 단지 "충분히 좋은"알고리즘을 원합니다. 이들은 일반적으로 휴리스틱을 기반으로하며 합리적인 근사치를 제공합니다.
나는 독립적 인 세트 (NP-Complete)의 인스턴스 인 한 가지 문제가 있었지만, 대부분의 경우에 꽤 좋은 결과를 얻은 탐욕스러운 알고리즘을 발견했으며 효율적인 런타임이있었습니다.
자동차 풀 픽업, UPS 패키지 전달 등과 같은 많은 유형의 최적화 된 순서. 노드 트래버스 요구 사항이 시간 또는 거리와 같은 한 차원의 노력으로 표현 될 수있는 경우.
TSP는입니다 안녕하세요 세계 NP의 완전한 문제. 그것은 순수한 표준 형태로, 당신은 자주 야생에서 그것을 찾을 수 없습니다 (이와 같은 데모는 포함되지 않습니다), 그러나 NP 전체 문제의 엄청난 하위 집합은 다음과 같은 TSP를 기반으로합니다.
- 차량 라우팅 (공급 트럭 라우팅 포함)
- 항공/비행 라우팅
- 기차 라우팅
- 스키 슬로프 쟁기 기계 라우팅
이들 각각에는 추가적인 도메인 별 구속 조건이있어 해결하기가 더 어려워집니다. 따라서 TSP는 NP의 완전한 문제에 대한 좋은 소개이며 본질을 이해합니다.
실제 생활에서 수학 수업에서 배우는 것과 일치하는 문제는 거의 없습니다. 문제는 단순화되고 추상화되어 수학을 볼 수 있고 세부 사항에 의해 산만 해지지 않습니다. 당신이 언급했듯이 대형 TSP의 최고의 실제 예는 실제로 여행하는 세일즈맨과 관련이 없습니다. 시퀀스 의존적 설정 시간. 여기에는 팔이 다른 사이트 주변의 도구를 움직이는 기계와 일부 페인팅 응용 프로그램이 포함됩니다 (Red-> Orange-> 노란색은 빨간색보다> 노란색-> 오렌지보다 쉽습니다). 일부 응용 프로그램도 있습니다 X- 선 결정학 결정의 일부 샘플을 여러 다른 각도로 배향해야합니다.
이 회사는 개선 된 TSP 알고리즘을 기반으로했습니다.
그들은 다른 문제들 중에서도 NYC 주변의 케이블 TV 설치 프로그램과 수리공을 라우팅합니다.
인간은 일반적으로 20-60 노드가있는 맵의 대부분의 알고리즘보다 PAR에서 TSP 문제를 해결할 수 있기 때문에 컴퓨터가 문제를 해결하는 것은 일반적이지 않습니다. 비용이 충분히 높으면 컴퓨터가 사람보다 1-2% 개선되면 계산을 수행하는 데 드는 비용이 가치가 있습니다. 경로가 바뀌지 않으면 최적화하는 데 시간을 보내는 것을 정당화 할 수 있습니다. 이것은 통합 회로 설계에서 일반적입니다.
항공사 여행 웹 사이트는 항공사 목록과 각 경로의 가격을 보여줄 때 TSP 문제의 특수 버전을 사용합니다. 차이점은 거리 대신, 비용을 최적화하며 각 도시를 한 번 방문 할 필요가 없습니다! LGA에서 LAX로 날고 싶다고 가정 해 봅시다. 약 1/2 개의 직접 경로와 무한한 수의 다른 경로가 있습니다. lga-> ord-> lax 또는 lga-> dwf-> lax를 제안 할 수 있습니다. 노선을 수동으로 수동으로 할 수있는 인간은 때때로 여행 사이트에서 검색 한 것보다 낮은 요금을 찾을 수 있습니다. 일반적으로 사람들은 두 개 이상의 연결을 원하지 않지만 주어진 비행의 연결 수의 상한은 없습니다.
나는 그것을 사용하여 내 경로를 해결하는 데 사용했습니다 여행 세일즈맨 iPhone 게임. 흥미로운 점은 사람들이 가장 짧은 경로를 해결하는 데 매우 능숙하지만 가장 긴 경로를 해결하는 것은 아닙니다. 가장 길고 가장 짧은 경로는 동일한 복잡성을 가지고 있지만 사람들은 가장 짧은 경로를 찾을 수있는 훈련을받는 것처럼 보이며, 종종 컴퓨터가 할 수있는 것보다 빠르고 더 좋습니다.
첫 직장에서 우리는 가정 간호 일정 신청서를 구축했습니다.
일부 비 선형 시간 제약과 추가 비 선형 비용 기능으로 TSP 문제를 해결했습니다.
우리는 비 최적 솔버를 사용하여 문제를 해결했습니다.
Google지도 (및 다른 모든 맵 기반 라우팅 소프트웨어)가 운전 방향을 해결하기 위해 일종의 여행 세일즈맨을 사용하지 않습니까?
나는 아는 한 TSP를 사용하지 않았지만 미로를 가로 지르기 위해 많은 자율 로봇을 연구했습니다. 따라서 TSP가 미로 해결에 적용될 수 있는지 궁금합니다.
