Bagaimana cara menemukan jalur terpendek di antara 100 target bergerak? (Termasuk demo langsung.)

89

Latar Belakang

Gambar ini mengilustrasikan masalahnya: square_grid_with_arrows_giving_directions

Saya bisa mengontrol lingkaran merah. Targetnya adalah segitiga biru. Panah hitam menunjukkan arah pergerakan target.

Saya ingin mengumpulkan semua target dalam jumlah langkah minimum.

Setiap belokan saya harus bergerak 1 langkah ke kiri / kanan / atas atau bawah.

Setiap belokan target juga akan bergerak 1 langkah sesuai dengan petunjuk yang tertera di papan.

Demo

Saya telah membuat demo yang bisa dimainkan dari masalah ini di sini di Google appengine .

Saya akan sangat tertarik jika ada yang bisa mengalahkan skor target karena ini akan menunjukkan bahwa algoritme saya saat ini kurang optimal. (Pesan selamat harus dicetak jika Anda mengatur ini!)

Masalah

Algoritme saya saat ini berskala sangat buruk dengan jumlah target. Waktu bertambah secara eksponensial dan untuk 16 ikan sudah beberapa detik.

Saya ingin menghitung jawaban untuk ukuran papan 32 * 32 dan dengan 100 target bergerak.

Pertanyaan

Apa algoritme yang efisien (idealnya dalam Javascript) untuk menghitung jumlah langkah minimum untuk mengumpulkan semua target?

Apa yang saya coba

Pendekatan saya saat ini didasarkan pada memoisation tetapi sangat lambat dan saya tidak tahu apakah itu akan selalu menghasilkan solusi terbaik.

Saya memecahkan sub-masalah "berapa jumlah minimum langkah untuk mengumpulkan serangkaian target tertentu dan berakhir pada target tertentu?".

Masalah ini diselesaikan secara rekursif dengan memeriksa setiap pilihan untuk target yang dikunjungi sebelumnya. Saya berasumsi bahwa itu selalu optimal untuk mengumpulkan subkumpulan target sebelumnya secepat mungkin dan kemudian berpindah dari posisi yang Anda selesaikan ke target saat ini secepat mungkin (walaupun saya tidak tahu apakah ini asumsi yang valid).

Ini menghasilkan n * 2 ^ n status yang akan dihitung yang tumbuh dengan sangat cepat.

Kode saat ini ditunjukkan di bawah ini:

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;
}

Apa yang saya pertimbangkan

Beberapa opsi yang membuat saya penasaran adalah:

  1. Caching hasil menengah. Penghitungan jarak mengulangi banyak simulasi dan hasil antara dapat disimpan dalam cache.
    Namun, saya tidak berpikir ini akan menghentikannya memiliki kompleksitas eksponensial.

  2. Algoritme pencarian A * meskipun tidak jelas bagi saya heuristik yang dapat diterima yang sesuai dan seberapa efektif ini dalam praktiknya.

  3. Menyelidiki algoritme yang baik untuk masalah penjual keliling dan melihat apakah algoritme tersebut berlaku untuk masalah ini.

  4. Mencoba membuktikan bahwa masalahnya NP-hard dan karenanya tidak masuk akal untuk mencari jawaban yang optimal untuk itu.

javascript algorithm graph-theory Peter de Rivaz
sumber
1
Saya akan memilih # 4 dan selanjutnya # 3: Dengan papan yang cukup besar, itu meniru TSP dengan cukup baik.
John Dvorak
2
Sejauh yang saya tahu, TSP adalah NP-hard dengan metrik euclidean serta metrik manhattan (grid persegi).
John Dvorak
1
Jika Anda melakukannya dengan pencarian pohon sederhana, ya, itu akan menjadi eksponensial. Namun, jika Anda dapat menemukan heuristik yang layak di setiap langkah, ini mungkin tidak benar-benar optimal, tetapi mungkin sangat bagus. Satu kemungkinan heuristik adalah, dengan melihat kumpulan ikan saat ini, mana yang dapat dicapai paling cepat? Bisa jadi heuristik sekunder, 2 ikan mana yang bisa saya jangkau paling cepat?
Mike Dunlavey
2
@MikeDunlavey yang akan sesuai dengan algoritma TSP yang rakus, dan ini bekerja dengan sangat baik dalam praktiknya. Mencari ikan terdekat sepertinya ide yang bagus
John Dvorak
1
+1 untuk salah satu pertanyaan terbaik yang saya lihat belakangan ini, baik untuk konten maupun struktur.
surfitscrollit

Jawaban:

24

Sudahkah Anda mencari literatur? Saya menemukan makalah ini yang tampaknya menganalisis masalah Anda:

UPDATE 1:

Dua makalah di atas tampaknya berkonsentrasi pada gerakan linier untuk metrik euclidian.

uldall
sumber
Terima kasih - Saya belum pernah melihat kertas-kertas itu tetapi kelihatannya sangat relevan. Saya akan melihat apakah saya dapat mengadaptasi algoritma genetika untuk bekerja dalam kasus saya dan membandingkannya dengan hasil dari pendekatan brute force.
Peter de Rivaz
13

Metode serakah

Salah satu pendekatan yang disarankan dalam komentar adalah pergi ke target terdekat terlebih dahulu.

Saya telah menyiapkan versi demo yang mencakup biaya yang dihitung melalui metode serakah di sini .

Kodenya adalah:

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;
}

Untuk 10 target jaraknya sekitar dua kali jarak optimal, tetapi terkadang jauh lebih banyak (mis. * 4) dan terkadang bahkan mencapai jarak optimal.

Pendekatan ini sangat efisien sehingga saya dapat membeli beberapa siklus untuk meningkatkan jawabannya.

Selanjutnya saya mempertimbangkan untuk menggunakan metode koloni semut untuk melihat apakah mereka dapat menjelajahi ruang solusi secara efektif.

Metode koloni semut

Sebuah metode koloni semut tampaknya bekerja luar biasa baik untuk masalah ini. Tautan dalam jawaban ini sekarang membandingkan hasil saat menggunakan metode koloni semut dan serakah.

Idenya adalah bahwa semut memilih rute mereka secara probabilistik berdasarkan tingkat feromon saat ini. Setelah setiap 10 percobaan, kami menyetorkan feromon tambahan di sepanjang jalur terpendek yang mereka temukan.

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;
}

Hasil

Metode koloni semut ini menggunakan 100 pengulangan 10 semut masih sangat cepat (37ms untuk 16 target dibandingkan dengan 3700ms untuk pencarian menyeluruh) dan nampaknya sangat akurat.

Tabel di bawah ini menunjukkan hasil untuk 10 percobaan dengan menggunakan 16 target:

   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

Metode semut tampaknya jauh lebih baik daripada rakus dan seringkali sangat mendekati optimal.

Peter de Rivaz
sumber
Bagus. Anda mungkin belum mendapatkan hasil yang optimal dari pencarian menyeluruh (atau mungkin tidak pernah karena sifatnya yang keras!) Tetapi akan menarik untuk melihat bagaimana koloni semut berskala dengan ukuran papan (32x32) dengan jumlah target yang sama.
timxyz
8

Masalahnya mungkin direpresentasikan dalam istilah Masalah Penjual Perjalanan Umum, dan kemudian diubah menjadi Masalah Penjual Perjalanan konvensional. Ini adalah masalah yang dipelajari dengan baik. Ada kemungkinan bahwa solusi paling efisien untuk masalah OP tidak lebih efisien daripada solusi untuk TSP, tetapi tidak pasti (saya mungkin gagal memanfaatkan beberapa aspek dari struktur masalah OP yang akan memungkinkan solusi yang lebih cepat , seperti sifat siklusnya). Bagaimanapun, ini adalah titik awal yang baik.

Dari C. Noon & J. Bean, Transformasi Efisien dari Masalah Penjual Bepergian Umum :

The Traveling Salesman Generalized Masalah (GTSP) adalah model yang berguna untuk masalah yang melibatkan keputusan seleksi dan urutan. Versi asimetris dari masalah didefinisikan pada grafik berarah dengan node N, menghubungkan busur A dan vektor biaya busur yang sesuai c. Node dikelompokkan menjadi m node yang saling eksklusif dan lengkap. Busur penghubung hanya didefinisikan antara node yang memiliki set yang berbeda, yaitu, tidak ada busur intraset. Setiap busur yang ditentukan memiliki biaya non-negatif yang sesuai. GTSP dapat dikatakan sebagai masalah dalam menemukan biaya minimum siklus m-arc yang mencakup tepat satu node dari setiap node .

Untuk masalah OP:

  • Setiap anggota Nadalah lokasi ikan tertentu pada waktu tertentu. Mewakili ini sebagai (x, y, t), di mana (x, y)adalah koordinat kisi, dan tmerupakan waktu di mana ikan akan berada di koordinat ini. Untuk ikan paling kiri dalam contoh OP, beberapa ikan pertama (berbasis 1) adalah: (3, 9, 1), (4, 9, 2), (5, 9, 3)saat ikan bergerak ke kanan.
  • Untuk setiap anggota N biarkan fish(n_i)mengembalikan ID ikan yang diwakili oleh node. Untuk setiap dua anggota N kita dapat menghitung manhattan(n_i, n_j)jarak manhattan antara dua node, dan time(n_i, n_j) untuk waktu offset antar node.
  • Jumlah himpunan bagian yang terputus m sama dengan jumlah ikan. Subset terputus-putus S_ihanya akan terdiri dari node yang untuknya fish(n) == i.
  • Jika selama dua node idan j fish(n_i) != fish(n_j)kemudian ada busur antara idanj .
  • Biaya antara node i dan node j adalah time(n_i, n_j), atau tidak ditentukan jika time(n_i, n_j) < distance(n_i, n_j)(yaitu lokasi tidak dapat dicapai sebelum ikan sampai di sana, mungkin karena waktunya mundur). Busur jenis terakhir ini dapat dihilangkan.
  • Node tambahan perlu ditambahkan yang mewakili lokasi pemutar dengan busur dan biaya ke semua node lainnya.

Memecahkan masalah ini kemudian akan menghasilkan satu kunjungan ke setiap subset node (yaitu setiap ikan diperoleh satu kali) untuk jalur dengan biaya minimal (yaitu waktu minimal untuk mendapatkan semua ikan).

Makalah ini selanjutnya menjelaskan bagaimana rumusan di atas dapat diubah menjadi Masalah Penjual Perjalanan tradisional dan kemudian diselesaikan atau diperkirakan dengan teknik yang ada. Saya belum membaca detailnya tetapi makalah lain yang melakukan ini dengan cara yang diklaim efisien adalah yang ini .

Ada masalah yang jelas dengan kompleksitas. Secara khusus, ruang node tidak terbatas! Ini dapat diatasi dengan hanya menghasilkan node hingga jangka waktu tertentu. Jika tjumlah langkah waktu untuk menghasilkan node dan fjumlah ikan maka ukuran ruang node akan menjadi t * f. Node pada suatu waktu jakan memiliki paling banyak (f - 1) * (t - j)busur keluar (karena tidak dapat mundur ke masa lalu atau ke subsetnya sendiri). Jumlah total busur akan berada dalam urutan t^2 * f^2busur. Struktur busur mungkin dapat dirapikan, untuk memanfaatkan fakta bahwa jalur ikan pada akhirnya bersifat siklis. Ikan akan mengulangi konfigurasi mereka sekali setiap penyebut umum terendah dari panjang siklusnya jadi mungkin fakta ini dapat digunakan.

Saya tidak cukup tahu tentang TSP untuk mengatakan apakah ini layak atau tidak, dan menurut saya itu tidak berarti bahwa masalah yang diposting pasti NP-hard ... tetapi ini adalah salah satu pendekatan untuk menemukan solusi yang optimal atau terbatas .

timxyz
sumber
Terima kasih, ini baru bagi saya dan sangat menarik. Saya rasa saya harus dapat menggunakan transformasi ini dalam kombinasi dengan algoritma Christofides untuk secara efisien menemukan solusi dalam faktor perkiraan 3/2 dari optimal. Jika saya membuatnya berfungsi, saya akan menambahkan rute yang diproduksi ke halaman demo.
Peter de Rivaz
Ah, saya pikir ada masalah dengan rencana saya karena meskipun masalah awal saya adalah grafik lengkap yang memenuhi ketidaksamaan yang sesuai pada metrik, transformasi yang dijelaskan menghasilkan grafik yang tidak lengkap sehingga algoritme Christofides tidak lagi berlaku. Terima kasih untuk perspektif yang menarik.
Peter de Rivaz
Ya, saya lupa menyebutkan bahwa ketimpangan segitiga tidak lagi berlaku. Ini adalah titik awal yang baik untuk solusi heuristik dan perkiraan yang lebih umum.
timxyz
1

Saya pikir pendekatan lain adalah:

  • menghitung jalur target - prediktif.
  • daripada menggunakan diagram Voronoi

Kutipan wikipedia:

Dalam matematika, diagram voronoi adalah cara membagi ruang menjadi beberapa daerah. Satu set titik (disebut benih, lokasi, atau generator) ditentukan sebelumnya dan untuk setiap benih akan ada wilayah terkait yang terdiri dari semua titik yang lebih dekat ke benih itu daripada yang lain.

Jadi, Anda memilih target, ikuti jalurnya untuk beberapa langkah dan tetapkan titik awal di sana. Lakukan ini dengan semua target lainnya juga dan Anda mendapatkan diagram voroni. Bergantung di area mana Anda berada, Anda pindah ke titik benih itu. Viola, kamu mendapat ikan pertama. Sekarang ulangi langkah ini sampai Anda mendapatkan semuanya.

Jürgen Stürmer
sumber