식료품 점을 통한 최단 경로 계산

Question

식료품 점을 통한 최단 경로 찾기 (쇼핑 목록)를 찾는 방법을 찾고 있습니다. 경로는 지정된 시작 위치에서 시작하고 여러 끝 위치에서 끝날 수 있습니다 (여러 체크 아웃 카운터가 있음). 또한 경로에 미리 정의 된 제약 조건이 있습니다 (예 : "쇼핑 목록의 항목 x는 경로의 마지막 항목, 두 번째 마지막 항목 또는 세 번째 항목이어야합니다"). 주어진 경로에 대해 참 또는 거짓을 리턴하는 함수가 있습니다. 마지막으로, 이것은 (스마트 폰에서) 제한된 CPU 전력으로 1 초 정도 계산되어야합니다. 이것이 가능하지 않다면, 최적 경로에 대한 근사도 가능합니다.

이것이 가능합니까? 지금까지는 A * 또는 Dijkstra와 같은 것을 사용하여 목록의 모든 항목 사이의 거리를 계산해야한다고 생각합니다. 그 후, 여행 판매원 문제처럼 취급해야합니까? 내 문제에는 지정된 시작 노드, 지정된 끝 노드 및 여행 판매원 문제가 아닌 몇 가지 제약이 있기 때문입니다.

Answer 1

글쎄, 기본적으로 여행 판매원 문제이지만 요구 사항에 따라 검색 공간이 제한됩니다. 너무 많은 위치가 없으면 모든 가능한 옵션을 계산할 수 있지만 가능하지 않은 경우 검색 공간을 더 제한해야합니다.

검색 시간을 제한하여 1 초 만에 찾을 수있는 최단 경로를 반환 할 수 있지만 그 중 가장 짧지는 않을 수도 있지만 어쨌든 꽤 짧습니다.

 
def find_shortest_path(current_path, best_path): 
    if time_limit() 
    return 

    if len(current_path) == NUM_LOCATIONS: 
     # destionation reached 
     if calc_len(current_path) < calc_len(best_path): 
      best_path = current_path 
     return 

    # You need to sort the possible locations well to maximize your chances of finding the 
    # the shortest solution 
    sort(possible_locations) 

    for location in possible_locations: 
     find_shortest_path(current_path + location, best_path) 

Answer 2

글쎄, 당신은 검색을 제한 할 수 있습니다 :

또한 다음 등 가능한 솔루션에 대한 의사 코드

다음 가장 가까운 위치를 선택 Backtracking를 사용하여, 다음 가장 가까운 위치를 찾을 Greedy algorithm을 적용 할 수 저장소의 레이아웃에 대한 정보를 사용하여 예를 들어, 전형적인 상점 (적어도 독일에서는 여기에)에는 많은 선반이있어 차선을 형성하는 것으로 간주 될 수 있습니다. 사이에는 선반 차선을 연결하는 직교 차선이 있습니다. 이제 교차점을 노드로 정의하고 차선을 가장자리로 정의합니다. 가장자리에는 해당 구역의 선반에있는 모든 항목으로 레이블이 지정됩니다. 자, 큰 상점이라 할지라도이 그래프는 꽤 작을 것입니다. 이제 모든 가장자리 레이블 (항목)이 포함 된 최단 경로를 찾아야합니다. greedy/backtracking 접근 방식 인 Tuomas Pelkonen suggested을 사용하면 가능합니다.

이것은 단지 아이디어 일 뿐이며 실제로 작동하는지 모르겠지만 여기에서 가져올 수 있습니다.

Answer 3

너비가 가장 큰 검색 만 현재의 "최상의"솔루션보다 저장소를 통과하는 경로를 "놓치지"않습니다.하지만 경로의 모든 노드를 검색 할 필요는 없습니다. 현재의 "최상의"솔루션보다 "명백하게"긴 노드는 나중에 확장 될 수 있습니다.

이것은 "호흡 우선"검색과 같은 문제에 접근하지만 이동 한 현재 거리를 기준으로 노드 확장을 변경한다는 것을 의미합니다. 검색 트리의 일부 분기는 동일한 시간 내에 더 많은 노드를 방문하기 때문에 다른 노드보다 빠르게 확장됩니다.

노드 확장이 정말로 호흡 우선이 아니라면 왜 계속 그 단어를 사용합니까? 솔루션을 찾은 후에는 각 검색 경로가 솔루션을 초과 할 때까지 "고려 노드"의 현재 세트를 확장해야합니다. 이렇게하면 많은 시간이 소요되는 초기 다리가있는 경로가 누락되지 않지만 마지막 단계는 빠르게 점등되기 때문에 현재 솔루션보다 빠르게 완료됩니다.

Answer 4

시작 노드의 요구 사항은 실제 데이터가 아닙니다. TSP를 사용하면 솔루션 비용을 변경하지 않고 원하는 시작 노드를 선택할 수있는 둘러보기로 끝납니다.

카운터에 관해서는 약간 까다 롭습니다 : 필요한 것은 몇 가지 호가없는 방향 그래프에서 문제를 해결하는 것입니다 (또는 어떤 호가 실제로 비용이 많이 드는 것과 동일합니다).

1. 는
2. 이 항목
에 카운터에서가 거부 시작 노드 항목에서가는 거부 :

당신이 순서대로 적절한 아크의 비용을 수정해야합니다 전체 방향 그래프 시작

3. 는
4. 톤 인출 한 후 (이는 전용 경로를 닫을 필요)
5. 제로 비용 시작 노드에서 카운터 갈 수 카운터를 시작 노드로부터가는 부정 내가 뭔가 :

HTH

Answer 5

그것은 TSP 문제가 더 어려워로 보는 것 같아 놓친 경우 그 것은 아래로, 말해. 누군가 식료품 이야기가 그렇게 복잡한 것은 아니라고 지적했습니다. 내가 (미국에서) 친숙한 식료품 점에는 그다지 합리적인 경로가 없다. 특히 주어진 출발점이있는 경우. 나는 잘 숙고 된 경험주의가 아마 그 트릭을 할 것이라고 생각한다.

예 : 일반적으로 한쪽에서 시작합니다. 큰 여행이라면 냉동 식품을 마지막으로 통과해야합니다.하지만 종종 문제가되지 않으며 매장에 가장 가까이부터 시작합니다. . 나는 일반적으로 바깥을 돌아 다니며, 그 중 하나에 뭔가가 필요한 경우 개별 통로로 내려갑니다. 통로에 들어가면 그 통로의 모든 것을 가져 오십시오. 한 쪽 끝으로 들어가서 물건을 잡고 시작 지점으로 돌아가는 통로가있는 통로와 전체 통로로 옮길 수있는 통로가있는 통로가 있습니다. 통로에서 필요한 마지막 항목의 기능과 필요한 곳 다음으로 - 복도에서 나가는 방법은 필요한 다음 항목에 달려 있습니다. 역행을 포함하거나 포함하지 않을 수도 있지만 컴퓨터는 다음 항목에 대한 최단 경로를 쉽게 계산할 수 있습니다.

위의 다른 문제에 대한 유용한 힌트에 동의하지만, 덜 일반적인 알고리즘이 적용될 수 있습니다. 제한된 자원으로 더 잘 작동 할 것입니다. 그러나 TSP는 이것이 최적의 접근 방식이라고 증명할 수는 없지만 실제로는 필요하지 않다고 생각합니다.