SMA* / Modern Memory Bounded A*

Pengertian dan Penjelasan

SMA * atau Modern Memory Bounded A * adalah algoritma jalur terpendek berdasarkan A * algoritma. Keuntungan utama dari SMA * adalah bahwa ia menggunakan memori dibatasi, sedangkan A * algoritma mungkin perlu memori eksponensial. Semua karakteristik lain dari SMA * diwariskan dari A *. (!@#$%^&?) o_O

Seperti A *, memperluas cabang yang paling menjanjikan menurut heuristik tersebut. Apa yang membuat SMA * terpisah adalah bahwa hal itu prunes nodes  yang ekspansi telah mengungkapkan kurang menjanjikan dari yang diharapkan. Pendekatan ini memungkinkan algoritma untuk mengeksplorasi cabang dan mundur untuk mengeksplorasi cabang lainnya.

Ekspansi dan pemangkasan node didorong dengan menjaga dua nilai dari f untuk setiap node. Node x toko nilai f (x) yang memperkirakan biaya mencapai tujuan dengan mengambil jalan melalui simpul itu. Semakin rendah nilai, semakin tinggi prioritas. Seperti di A * nilai ini diinisialisasi untuk h (x) + g (x), tetapi kemudian akan diperbarui untuk mencerminkan perubahan perkiraan ini ketika anak-anak yang diperluas. Sebuah node sepenuhnya diperluas akan memiliki nilai f setidaknya setinggi itu dari penerusnya. Selain itu, node menyimpan nilai f dari penerus terbaik dilupakan. Nilai ini dikembalikan jika penerus lupa diturunkan menjadi penerus yang paling menjanjikan. (!@#$%^&?) o_O

Dimulai dengan node pertama, ia mempertahankan OPEN, memerintahkan leksikografis oleh f dan kedalaman. Ketika memilih sebuah node untuk memperluas, ia memilih yang terbaik sesuai dengan urutan itu. Ketika memilih sebuah node untuk memangkas, ia memilih yang terburuk.

Pelaksanaan SMA * sangat mirip dengan salah satu dari A *, satu-satunya perbedaan adalah bahwa ketika tidak ada ruang yang tersisa, node dengan tertinggi f-biaya yang dipangkas dari antrian. Karena mereka node dihapus, SMA * juga harus mengingat f-biaya anak terbaik lupa dengan node induk. Ketika tampaknya semua jalan dieksplorasi lebih buruk daripada seperti jalur lupa, jalan tersebut kembali dihasilkan.

Pseudo code:

function SMA-star(problem): path
  queue: set of nodes, ordered by f-cost;
begin
  queue.insert(problem.root-node);

  while True do begin
    if queue.empty() then return failure; //there is no solution that fits in the given memory
    node := queue.begin(); // min-f-cost-node
    if problem.is-goal(node) then return success;
    
    s := next-successor(node)
    if !problem.is-goal(s) && depth(s) == max_depth then
        f(s) := inf; 
        // there is no memory left to go past s, so the entire path is useless
    else
        f(s) := max(f(node), g(s) + h(s));
        // f-value of the successor is the maximum of
        //      f-value of the parent and 
        //      heuristic of the successor + path length to the successor
    endif
    if no more successors then
       update f-cost of node and those of its ancestors if needed
    
    if node.successors ⊆ queue then queue.remove(node); 
    // all children have already been added to the queue via a shorter way
    if memory is full then begin
      badNode := shallowest node with highest f-cost;
      for parent in badNode.parents do begin
        parent.successors.remove(badNode);
        if needed then queue.insert(parent); 
      endfor
    endif

    queue.insert(s);
  endwhile
end

 (!@#$%^&?) o_O