Спрощений алгоритм з обмеженням пам'яті

Спро́щений алгори́тм A* з обмеже́нням па́м'яті (англ. «SMA* (Simplified Memory-Bounded A*) algorithm») — це варіант A* пошуку з обмеженою пам'яттю.

Основна ідея алгоритму ред.

Якщо немає вільного місця, відбирати найменш перспективний вузол з черги, але й відстежувати найкраще забуте значення предка вузла.

Властивості ред.

  • Повний — якщо d (глибина оптимального вузла в дереві пошуку) менша за обсягом пам'яті (виражений у вузлах)
  • Оптимальний — якщо це рішення можна досягнути

Принцип роботи ред.

Алгоритм SMA* діє повністю аналогічно пошуку A*, розгортаючи найкращі листові вузли до тих пір, поки не буде вичерпана доступна пам'ять. З цього моменту він не може додати новий вузол до дерева пошуку, не знищивши при цьому старий. В алгоритмі SMA* завжди знищується найгірший листовий вузол (той, який має найбільше оцінки). Як і в алгоритмі RBFS, після цього в алгоритмі SMA* значення забутого (знищеного) вузла резервується в його батьківському вузлі. Завдяки цьому предок забутого піддерева дозволяє визначити якість найкращого шляху в цьому піддереві. Оскільки є дана інформація, в алгоритмі SMA* піддерево відновлюється, тільки якщо виявляється, що всі інші шляхи виглядають менш перспективними у порівнянні з забутим шляхом.

 
Ілюстрація пошуку SMA* для трьох вузлів.

На зображенні продемонстровано приклад роботи алгоритму для дерева з трьох вузлів, який реалізовано за вісім кроків.

Якщо всі листові вузли мають однакове f-значення оцінки? В такому разі може виявитися, що алгоритм вибирає для видалення і розгортання один і той самий вузол. В алгоритмі SMA* ця проблема вирішується шляхом розгортання найновішого найкращого листового вузла і видалення найстаршого найгіршого листового вузла. Ці два вузли можуть виявитися одним і тим самим вузлом, тільки якщо існує лише один листовий вузол; в такому випадку поточне дерево пошуку повинно являти собою єдиний шлях від кореня до листового вузла, що заповнює всю пам'ять. Це означає, що якщо даний листовий вузол не є цільовим вузлом, то рішення недосяжно при доступному обсязі пам'яті, навіть якщо цей вузол знаходиться на оптимальному шляху вирішення. Тому такий вузол може бути відкинутий точно так само, як і в тому випадку, якщо він не має нащадків.

Алгоритм пошуку SMA* можна представити у вигляді псевдокоду ред.

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;
   node := queue.begin(); // мінімальне f-значення вузла
   if problem.is-goal(node) then return success;

   s := next-successor(node)
   f(s) := max(f(node), g(s) + h(s))
   if no more successors then
     update node-s f-cost and those of its ancestors if needed

   if node.successors ⊆ queue then queue.remove(node);
   if memory is full then begin
     badNode := queue.popEnd(); // видаляємо вузли з найвищим f-значенням з черги
     for parent in badNode.parents do begin
       parent.successors.remove(badNode);
       if needed then queue.insert(parent); 
     end;
   end;
   queue.insert(s);
 end;
end;

Застосування ред.

З точки зору практики алгоритм SMA* цілком може виявитися найкращим алгоритмом загального призначення для пошуку оптимальних рішень, особливо якщо простір станів являє собою граф, вартості етапів не однакові, а операція формування вузлів є більш дорогою в порівнянні з додатковими витратами супроводу відкритих і закритих списків.

Однак при вирішенні дуже складних завдань часто виникають ситуації, в яких алгоритм SMA* змушений постійно перемикатися з одного шляху вирішення на інший в межах множини можливих шляхів вирішення, і в пам'яті може поміститися тільки невелика підмножина цієї множини. В такому випадку на повторне формування одних і тих же вузлів витрачається додатковий час, а це означає, що завдання, які були б фактично можна вирішити за допомогою пошуку А * при наявності необмеженої пам'яті, стають важковирішуваними для алгоритму SMA*. Іншими словами, через обмеження в обсязі пам'яті деякі завдання можуть ставати важковирішуваними з точки зору часу обчислення. Хоча відсутня теорія, що дозволяє знайти компроміс між витратами часу і пам'яті, створюється враження, що часто уникнути виникнення цієї проблеми неможливо. Єдиним способом подолання такої ситуації стає часткова відмова від вимог до оптимальності рішення.

Див. також ред.

Джерела ред.

1. Russell, S. 1992. Efficient memory-bounded search methods [Архівовано 8 жовтня 2012 у Wayback Machine.]. In Proceedings of the 10th European Conference on Artificial intelligence (Vienna, Austria). B. Neumann, Ed. John Wiley & Sons, New York, NY, 1-5.