100 개의 움직이는 표적 사이의 최단 경로를 어떻게 찾을 수 있습니까?

100 개의 움직이는 표적 사이의 최단 경로를 어떻게 찾을 수 있습니까? (라이브 데모 포함.)

---

배경

이 그림은 문제를 보여줍니다.

빨간색 원을 제어 할 수 있습니다. 대상은 파란색 삼각형입니다. 검은 색 화살표는 표적이 이동할 방향을 나타냅니다.

최소한의 단계로 모든 목표를 수집하고 싶습니다.

회전 할 때마다 왼쪽 / 오른쪽 / 위 또는 아래로 한 단계 씩 이동해야합니다.

매 턴마다 목표물은 보드에 표시된 지시에 따라 1 단계 이동합니다.

데모

여기 Google appengine에 문제의 재생 가능한 데모를 올렸습니다 .

내 현재 알고리즘이 차선책이라는 것을 보여주기 때문에 누구든지 목표 점수를 이길 수 있다면 매우 관심이 있습니다. (이것을 관리한다면 축하 메시지가 출력되어야합니다!)

문제

내 현재 알고리즘은 타겟 수에 따라 정말 심하게 확장됩니다. 시간은 기하 급수적으로 증가하고 16 마리의 물고기는 이미 몇 초입니다.

32 * 32의 보드 크기와 100 개의 움직이는 타겟에 대한 답을 계산하고 싶습니다.

질문

모든 대상을 수집하기위한 최소 단계 수를 계산하는 효율적인 알고리즘 (이상적으로는 Javascript)은 무엇입니까?

내가 시도한 것

내 현재 접근 방식은 메모를 기반으로하지만 매우 느리고 항상 최상의 솔루션을 생성할지 여부는 알 수 없습니다.

"주어진 목표 세트를 수집하고 특정 목표에 도달하는 데 필요한 최소 단계 수는 얼마입니까?"라는 하위 문제를 해결합니다.

하위 문제는 이전 대상이 방문한 각 선택 항목을 검사하여 재귀 적으로 해결됩니다. 가능한 한 빨리 이전 대상 하위 집합을 수집 한 다음 가능한 한 빨리 현재 대상으로 이동 한 다음 (유효한 가정인지 여부는 알지 못하지만) 항상 최적이라고 가정합니다.

이것은 매우 빠르게 증가하는 n * 2 ^ n 상태를 계산합니다.

현재 코드는 다음과 같습니다.

var DX=[1,0,-1,0];
var DY=[0,1,0,-1]; 

// Return the location of the given fish at time t
function getPt(fish,t) {
  var i;
  var x=pts[fish][0];
  var y=pts[fish][1];
  for(i=0;i<t;i++) {
    var b=board[x][y];
    x+=DX[b];
    y+=DY[b];
  }
  return [x,y];
}

// Return the number of steps to track down the given fish
// Work by iterating and selecting first time when Manhattan distance matches time
function fastest_route(peng,dest) {
  var myx=peng[0];
  var myy=peng[1];
  var x=dest[0];
  var y=dest[1];
  var t=0;
  while ((Math.abs(x-myx)+Math.abs(y-myy))!=t) {
    var b=board[x][y];
    x+=DX[b];
    y+=DY[b];
    t+=1;
  }
  return t;
}

// Try to compute the shortest path to reach each fish and a certain subset of the others
// key is current fish followed by N bits of bitmask
// value is shortest time
function computeTarget(start_x,start_y) {
  cache={};
  // Compute the shortest steps to have visited all fish in bitmask
  // and with the last visit being to the fish with index equal to last
  function go(bitmask,last) {
    var i;
    var best=100000000;
    var key=(last<<num_fish)+bitmask;
    if (key in cache) {
      return cache[key];
    }
    // Consider all previous positions
    bitmask -= 1<<last;
    if (bitmask==0) {
      best = fastest_route([start_x,start_y],pts[last]);
    } else {
      for(i=0;i<pts.length;i++) {
        var bit = 1<<i;
        if (bitmask&bit) {
          var s = go(bitmask,i);   // least cost if our previous fish was i
          s+=fastest_route(getPt(i,s),getPt(last,s));
          if (s<best) best=s;
        }
      }
    }
    cache[key]=best;
    return best;
  }
  var t = 100000000;
  for(var i=0;i<pts.length;i++) {
    t = Math.min(t,go((1<<pts.length)-1,i));
  }
  return t;
}

내가 고려한 것

내가 궁금한 몇 가지 옵션은 다음과 같습니다.

1. 중간 결과 캐싱. 거리 계산은 많은 시뮬레이션을 반복하며 중간 결과는 캐시 될 수 있습니다.
   그러나 이것이 기하 급수적 인 복잡성을 갖는 것을 막을 것이라고 생각하지 않습니다.

2. A * 검색 알고리즘은 적절한 허용 가능한 휴리스틱이 무엇인지, 이것이 실제로 얼마나 효과적 일지는 분명하지 않습니다.

3. 출장 세일즈맨 문제에 대한 좋은 알고리즘을 조사하고이 문제에 적용되는지 확인합니다.

4. 문제가 NP가 어렵 기 때문에 이에 대한 최적의 답을 찾는 것이 부당하다는 것을 증명하려고합니다.

---

문헌을 검색 했습니까? 귀하의 문제를 분석하는 것으로 보이는 다음 문서를 찾았습니다.

• "움직이는 표적 추적 및 고정되지 않은 여행하는 세일즈맨 문제": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.85.9940

• "이동 목표 여행하는 세일즈맨 문제": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.6403

업데이트 1 :

위의 두 논문은 유클리드 메트릭에 대한 선형 운동에 집중하는 것 같습니다.

---

욕심 많은 방법

의견에서 제안 된 한 가지 접근 방식은 가장 가까운 대상으로 먼저 이동하는 것입니다.

나는이 욕심 방법을 통해 계산 된 비용이 포함 된 데모 버전 올려 한 여기를 .

코드는 다음과 같습니다.

function greedyMethod(start_x,start_y) {
  var still_to_visit = (1<<pts.length)-1;
  var pt=[start_x,start_y];
  var s=0;
  while (still_to_visit) {
    var besti=-1;
    var bestc=0;
    for(i=0;i<pts.length;i++) {
      var bit = 1<<i;
      if (still_to_visit&bit) {
        c = fastest_route(pt,getPt(i,s));
        if (besti<0 || c<bestc) {
          besti = i;
          bestc = c;
        }
      }
    }
    s+=c;
    still_to_visit -= 1<<besti;
    pt=getPt(besti,s);
  }
  return s;
}

10 개의 표적의 경우 최적 거리의 약 두 배이지만 때로는 훨씬 더 길고 (예 : * 4) 때로는 최적에 도달하기도합니다.

이 접근 방식은 매우 효율적이므로 답변을 개선 할 수있는 몇 가지주기를 가질 수 있습니다.

다음으로 개미 식민지 방법을 사용하여 솔루션 공간을 효과적으로 탐색 할 수 있는지 확인하려고합니다.

개미 식민지 방법

개미 식민지 방법은 이 문제에 대한 놀라운 잘 작동하는 것 같다. 이 답변의 링크는 이제 탐욕스러운 방법과 개미 식민지 방법을 모두 사용할 때 결과를 비교합니다.

아이디어는 개미가 현재의 페로몬 수준에 따라 확률 적으로 경로를 선택한다는 것입니다. 10 번의 시도가 끝날 때마다 발견 된 가장 짧은 흔적을 따라 추가 페로몬을 입금합니다.

function antMethod(start_x,start_y) {
  // First establish a baseline based on greedy
  var L = greedyMethod(start_x,start_y);
  var n = pts.length;
  var m = 10; // number of ants
  var numrepeats = 100;
  var alpha = 0.1;
  var q = 0.9;
  var t0 = 1/(n*L);

  pheromone=new Array(n+1); // entry n used for starting position
  for(i=0;i<=n;i++) {
    pheromone[i] = new Array(n);
    for(j=0;j<n;j++)
      pheromone[i][j] = t0; 
  }

  h = new Array(n);
  overallBest=10000000;
  for(repeat=0;repeat<numrepeats;repeat++) {
    for(ant=0;ant<m;ant++) {
      route = new Array(n);
      var still_to_visit = (1<<n)-1;
      var pt=[start_x,start_y];
      var s=0;
      var last=n;
      var step=0;
      while (still_to_visit) {
        var besti=-1;
        var bestc=0;
        var totalh=0;
        for(i=0;i<pts.length;i++) {
          var bit = 1<<i;
          if (still_to_visit&bit) {
            c = pheromone[last][i]/(1+fastest_route(pt,getPt(i,s)));
            h[i] = c;
            totalh += h[i];
            if (besti<0 || c>bestc) {
              besti = i;
              bestc = c;
            }
          }
        }
        if (Math.random()>0.9) {
          thresh = totalh*Math.random();
          for(i=0;i<pts.length;i++) {
            var bit = 1<<i;
            if (still_to_visit&bit) {
              thresh -= h[i];
              if (thresh<0) {
                besti=i;
                break;
              }
            }
          }
        }
        s += fastest_route(pt,getPt(besti,s));
        still_to_visit -= 1<<besti;
        pt=getPt(besti,s);
        route[step]=besti;
        step++;
        pheromone[last][besti] = (1-alpha) * pheromone[last][besti] + alpha*t0;
        last = besti;
      }
      if (ant==0 || s<bestantscore) {
        bestroute=route;
        bestantscore = s;
      }
    }
    last = n;
    var d = 1/(1+bestantscore);
    for(i=0;i<n;i++) {
      var besti = bestroute[i];
      pheromone[last][besti] = (1-alpha) * pheromone[last][besti] + alpha*d;
      last = besti;
    }
    overallBest = Math.min(overallBest,bestantscore);
  }
  return overallBest;
}

결과

개미 10 개를 100 번 반복하는이 개미 군집 방법은 여전히 ​​매우 빠르며 (완전한 검색의 경우 3700ms에 비해 16 개의 대상에 대해 37ms) 매우 정확 해 보입니다.

아래 표는 16 개 목표를 사용한 10 회 시도의 결과를 보여줍니다.

   Greedy   Ant     Optimal
   46       29      29
   91       38      37
  103       30      30
   86       29      29
   75       26      22
  182       38      36
  120       31      28
  106       38      30
   93       30      30
  129       39      38

개미 방법은 탐욕스러운 것보다 훨씬 낫고 종종 최적에 매우 가깝습니다.

---

The problem may be represented in terms of the Generalized Traveling Salesman Problem, and then converted to a conventional Traveling Salesman Problem. This is a well-studied problem. It is possible that the most efficient solutions to the OP's problem are no more efficient than solutions to the TSP, but by no means certain (I am probably failing to take advantage of some aspects of the OP's problem structure that would allow for a quicker solution, such as its cyclical nature). Either way, it is a good starting point.

From C. Noon & J.Bean, An Efficient Transformation of the Generalized Traveling Salesman Problem:

The Generalized Traveling Salesman Problem (GTSP) is a useful model for problems involving decisions of selection and sequence. The asymmetric version of the problem is defined on a directed graph with nodes N, connecting arcs A and a vector of corresponding arc costs c. The nodes are pregrouped into m mutually exclusive and exhaustive nodesets. Connecting arcs are defined only between nodes belonging to different sets, that is, there are no intraset arcs. Each defined arc has a corresponding non-negative cost. The GTSP can be stated as the problem of finding a minimum cost m-arc cycle which includes exactly one node from each nodeset.

For the OP's problem:

• Each member of N is a particular fish's location at a particular time. Represent this as (x, y, t), where (x, y) is a grid coordinate, and t is the time at which the fish will be at this coordinate. For the leftmost fish in the OP's example, the first few of these (1-based) are: (3, 9, 1), (4, 9, 2), (5, 9, 3) as the fish moves right.
• For any member of N let fish(n_i) return the ID of the fish represented by the node. For any two members of N we can calculate manhattan(n_i, n_j) for the manhattan distance between the two nodes, and time(n_i, n_j) for the time offset between the nodes.
• The number of disjoint subsets m is equal to the number of fish. The disjoint subset S_i will consist only of the nodes for which fish(n) == i.
• If for two nodes i and j fish(n_i) != fish(n_j) then there is an arc between i and j.
• The cost between node i and node j is time(n_i, n_j), or undefined if time(n_i, n_j) < distance(n_i, n_j) (i.e. the location can't be reached before the fish gets there, perhaps because it is backwards in time). Arcs of this latter type can be removed.
• An extra node will need to be added representing the location of the player with arcs and costs to all other nodes.

Solving this problem would then result in a single visit to each node subset (i.e. each fish is obtained once) for a path with minimal cost (i.e. minimal time for all fish to be obtained).

The paper goes on to describe how the above formulation may be transformed into a traditional Traveling Salesman Problem and subsequently solved or approximated with existing techniques. I have not read through the details but another paper that does this in a way it proclaims to be efficient is this one.

There are obvious issues with complexity. In particular, the node space is infinite! This can be alleviated by only generating nodes up to a certain time horizon. If t is the number of timesteps to generate nodes for and f is the number of fish then the size of the node space will be t * f. A node at time j will have at most (f - 1) * (t - j) outgoing arcs (as it can't move back in time or to its own subset). The total number of arcs will be in the order of t^2 * f^2 arcs. The arc structure can probably be tidied up, to take advantage of the fact the fish paths are eventually cyclical. The fish will repeat their configuration once every lowest common denominator of their cycle lengths so perhaps this fact can be used.

I don't know enough about the TSP to say whether this is feasible or not, and I don't think it means that the problem posted is necessarily NP-hard... but it is one approach towards finding an optimal or bounded solution.

---

I think another approch would be:

• calculate the path of the targets - predictive.
• than use Voronoi diagrams

Quote wikipedia:

In mathematics, a Voronoi diagram is a way of dividing space into a number of regions. A set of points (called seeds, sites, or generators) is specified beforehand and for each seed there will be a corresponding region consisting of all points closer to that seed than to any other.

따라서 대상을 선택하고 경로를 따라 몇 단계를 수행 한 다음 거기에 시드 포인트를 설정합니다. 다른 모든 대상에도이 작업을 수행하면 보 로니 다이어그램이 생성됩니다. 당신이 어느 지역에 있는지에 따라, 당신은 그것의 시드 포인트로 이동합니다. 비올라, 당신은 첫 번째 물고기를 얻었습니다. 이제이 단계를 반복 할 때까지 반복하십시오.

참고 URL : https://stackoverflow.com/questions/15485473/how-can-i-find-the-shortest-path-between-100-moving-targets-live-demo-included