두 점 A와 B가 있습니다. A에서 B까지 최단 경로를 찾고 싶지만 N (최대 200) 개의 직사각형이 있으며 경로는이 직사각형과 교차 할 수 없습니다 . 패스와 직사각형은 직사각형의 정점과 직사각형의 측면에서만 교차 할 수 있습니다. 최단 경로의 길이는 얼마입니까? 직사각형은 교차 할 수 없습니다. 그들은 포인트 또는 사이드를 공유 할 수 있습니다. 그래서 두 사람이 한 편을 공유한다면 그들 사이를 지나칠 수 있습니다.좌표계의 두 점 사이의 최단 경로
일반적으로 이런 종류의 문제에 대한 최상의 알고리즘은 Manhattan Distance과 같은 간단한 경험적 방법을 사용하여 A*입니다. 하지만 먼저 불법 포인트를 찾아야합니다. 불법 포인트는이 문제에 입력 할 수없는 포인트입니다. 사각형 내부의 포인트는 불법입니다 (직사각형의 측면에있는 포인트는 통과 할 수 있으므로 합법입니다). 이 점을 찾은 후 A * 알고리즘을 구현하여 A과 B 사이의 최단 경로를 찾습니다.
이 문제에서 가장자리 가중치가 없으므로 BFS를 실행하여 최단 경로를 찾을 수 있지만 A *만큼 빠르지는 않습니다.
검색 공간이 매우 크고 A *를 사용하여 메모리가 부족한 경우 IDA*을 사용하여 메모리를 덜 소모하지만 노드를 두 번 이상 탐색해야합니다.
문제를 그래프 문제로 나타내고 Dijsktra의 알고리즘을 사용한다고 생각하십시오. –
경로에 직사각형이 없으면 경로가 대각선이 될 수 있습니까? 사각형의 크기는 얼마입니까? 수정 또는 변수? 알고리즘을 얻으려면 초기 데이터 형식을 제공하는 것이 더 좋습니다 –
크로스 게시 : http://math.stackexchange.com/q/1944808/14578, http://stackoverflow.com/q/39744007/781723. [여러 사이트에 동일한 질문을 게시하지 마십시오.] (http://meta.stackexchange.com/q/64068). 아무도 시간 낭비없이 응답 할 때 각 지역 사회는 솔직한 기회를 가져야합니다. 추신 이 문제가 발생한 상황은 무엇입니까? 이것은 프로그래밍 경연 대회 질문입니까? –