아래 그림과 같은 값의 래스터 그리드가 있습니다 (흰색은 높은 값이고 검은 색 배경 값은 0 임). 나는 선 중 하나의 끝에서 시작하고 (가능한 가장 높은 값을 통해 가고, 다른 쪽 끝을 추적하는 경로 다음 코드의 일종을 쓰기 위해 노력하고있어알고리즘을 따르는 래스터 경로
즉, 선이 더 좋게 선택된 픽셀이 더 희박함) 그러나 여전히 다른 쪽 끝을 향합니다.
나는 잠시 동안이 문제에 시달렸으며, 내가 일하려고하는 어떤 것도 얻을 수없는 것처럼 보였다. 그래서 궁금한 점은 이런 종류의 문제에 대해 일반적인 알고리즘이 이미 개발 되었습니까? 나는 많은 검색을 해왔지만, 대부분의 경로 알고리즘은 이와 같은 래스터 그리드가 아닌 벡터/네트워크에서 작동하도록 설계된 것 같습니다.
아이디어가 있으십니까?
유전자 알고리즘이나 우스운 이야기가 필요하지 않다고 생각합니다. 좋은 구식 재귀 및 동적 프로그래밍만으로 충분할 것입니다. 처음에는 폭 넓은 첫 번째 검색을 수행하여 목표를 달성 할 수 있어야한다고 생각합니다. 시작 지점부터 그 경로 값보다 큰 점수를 가진 모든 이웃을 방문합니다. 모든 셀은 무한대부터 시작하며 검정색 셀에 대한 비용은 무한대가됩니다.이 경로는 잘라낼 수있는 경로입니다. 일단 목적지에 도착하면 도달 할 수 있으면 경로를 찾기 위해 되돌릴 수 있어야합니다. 욕심이 많습니다 만, 만약 당신의 경로가 이처럼 잘 행동한다면 괜찮을 것입니다.
더 많은 회색과 비틀기가있는 경로의 경우, 가장자리 가중치가 이웃의 회색조 값 (또는 그레이 스케일 값의 차이) 인 래스터 이미지를 그래프로 변환하는 것이 좋습니다. 이 데이터가 실제로 무엇을 의미하는지에 따라). 따라서, 당신은 그 해석에 기초한 최단 경로에 대해 어떤 알고리즘을 사용할 수 있어야합니다.
응답 해 주셔서 감사합니다. . 죄송합니다 - 일반적인 문제를 해결하는 것과는 달리 다양한 경로 찾기 문제에서 작동하는 일반적인 알고리즘을 의미했습니다. 폭 넓은 우선 검색을 살펴 보겠습니다. – robintw
Opps ... 이것은 하루 종일 화면을 보았을 때 일어나는 일입니다. 1/I/l 또는 o/0이 혼란 스러울 때 폰트 문제가 있습니다. r/t가 혼란 스러울 때, 정신적 문제가 있습니다. 그러나이 경우 래스터 이미지를 그래프로 변환하거나 그래프로 생각하면 가장 짧은 경로 알고리즘을 사용할 수 있어야합니다. – nlucaroni
가장 간단한 아이디어는 각 픽셀이 노드이고 노드의 비용이 픽셀 어둠 인 A* algorithm을 사용하는 것입니다.
업데이트 : 멋진 tutorial을 찾았습니다. 이 작업을 수행하는
한 가지 방법 :
잘 작동하려면 약간의 조정이 필요하지만 이렇게하는 것은 가능합니다. 다른 하나의 변형은 1 또는 2 또는 3 픽셀보다 넓은 경우 흰색 섹션을 윤곽선으로 표시하고 이후에 이중선을 결합하는 것입니다.
당신은 큰 규모로이 일을하거나 연구를위한 당신은 http://en.wikipedia.org/wiki/Ant_colony_optimization 오순절하려고하지만, 돈을 위해이 일을하는 경우 단지 홍수 같은이가있는 고전 비용 거리 문제 http://en.wikipedia.org/wiki/Flood_fill
을 채우기 데리러 경우 여러 번 래스터 데이터 용으로 개발되었습니다. 예를 들어 R에서는 gdistance 패키지를 사용할 수 있습니다. – RobertH
감사합니다. @RobertH - 유용한 패키지처럼 보입니다. 내가 아직도 고민하고있는 비트는 라인의 시작과 끝이 어디에 있는지를 알 필요가 없을 때 이것을 수행하는 방법이다 : 즉, 라인의 끝점을 인식해야한다! 그런 생각이 들었다면 알려주세요. – robintw
아마도 흰색은 250보다 큰 값이라고 가정하면됩니다.'r <- raster ('file'); 시작 <- 어느 (r [1,]> 250); 끝과 끝에서'xyFromCell (r, start) '처럼 좌표를 계산할 수 있습니다. – RobertH