Спро́щений алгори́тм A* з обмеже́нням па́м'яті (англ. «SMA* (Simplified Memory-Bounded A*) algorithm») — це варіант A* пошуку з обмеженою пам'яттю.
Основна ідея алгоритму
Якщо немає вільного місця, відбирати найменш перспективний вузол з черги, але й відстежувати найкраще забуте значення предка вузла.
Властивості
- Повний — якщо d (глибина оптимального вузла в дереві пошуку) менша за обсягом пам'яті (виражений у вузлах)
- Оптимальний — якщо це рішення можна досягнути
Принцип роботи
Алгоритм SMA* діє повністю аналогічно пошуку A*, розгортаючи найкращі листові вузли до тих пір, поки не буде вичерпана доступна пам'ять. З цього моменту він не може додати новий вузол до дерева пошуку, не знищивши при цьому старий. В алгоритмі SMA* завжди знищується найгірший листовий вузол (той, який має найбільше оцінки). Як і в алгоритмі RBFS, після цього в алгоритмі 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.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Spro shenij algori tm A z obmezhe nnyam pa m yati angl SMA Simplified Memory Bounded A algorithm ce variant A poshuku z obmezhenoyu pam yattyu Osnovna ideya algoritmuYaksho nemaye vilnogo miscya vidbirati najmensh perspektivnij vuzol z chergi ale j vidstezhuvati najkrashe zabute znachennya predka vuzla VlastivostiPovnij yaksho d glibina optimalnogo vuzla v derevi poshuku mensha za obsyagom pam yati virazhenij u vuzlah Optimalnij yaksho ce rishennya mozhna dosyagnutiPrincip robotiAlgoritm SMA diye povnistyu analogichno poshuku A rozgortayuchi najkrashi listovi vuzli do tih pir poki ne bude vicherpana dostupna pam yat Z cogo momentu vin ne mozhe dodati novij vuzol do dereva poshuku ne znishivshi pri comu starij V algoritmi SMA zavzhdi znishuyetsya najgirshij listovij vuzol toj yakij maye najbilshe ocinki Yak i v algoritmi RBFS pislya cogo v algoritmi SMA znachennya zabutogo znishenogo vuzla rezervuyetsya v jogo batkivskomu vuzli Zavdyaki comu predok zabutogo piddereva dozvolyaye viznachiti yakist najkrashogo shlyahu v comu pidderevi Oskilki ye dana informaciya v algoritmi SMA pidderevo vidnovlyuyetsya tilki yaksho viyavlyayetsya sho vsi inshi shlyahi viglyadayut mensh perspektivnimi u porivnyanni z zabutim shlyahom Ilyustraciya poshuku SMA dlya troh vuzliv Na zobrazhenni prodemonstrovano priklad roboti algoritmu dlya dereva z troh vuzliv yakij realizovano za visim krokiv Yaksho vsi listovi vuzli mayut odnakove f znachennya ocinki V takomu razi mozhe viyavitisya sho algoritm vibiraye dlya vidalennya i rozgortannya odin i toj samij vuzol V algoritmi SMA cya problema virishuyetsya shlyahom rozgortannya najnovishogo najkrashogo listovogo vuzla i vidalennya najstarshogo najgirshogo listovogo vuzla Ci dva vuzli mozhut viyavitisya odnim i tim samim vuzlom tilki yaksho isnuye lishe odin listovij vuzol v takomu vipadku potochne derevo poshuku povinno yavlyati soboyu yedinij shlyah vid korenya do listovogo vuzla sho zapovnyuye vsyu pam yat Ce oznachaye sho yaksho danij listovij vuzol ne ye cilovim vuzlom to rishennya nedosyazhno pri dostupnomu obsyazi pam yati navit yaksho cej vuzol znahoditsya na optimalnomu shlyahu virishennya Tomu takij vuzol mozhe buti vidkinutij tochno tak samo yak i v tomu vipadku yaksho vin ne maye nashadkiv Algoritm poshuku SMA mozhna predstaviti u viglyadi psevdokodufunction 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 minimalne f znachennya vuzla 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 vidalyayemo vuzli z najvishim f znachennyam z chergi for parent in badNode parents do begin parent successors remove badNode if needed then queue insert parent end end queue insert s end end ZastosuvannyaZ tochki zoru praktiki algoritm SMA cilkom mozhe viyavitisya najkrashim algoritmom zagalnogo priznachennya dlya poshuku optimalnih rishen osoblivo yaksho prostir staniv yavlyaye soboyu graf vartosti etapiv ne odnakovi a operaciya formuvannya vuzliv ye bilsh dorogoyu v porivnyanni z dodatkovimi vitratami suprovodu vidkritih i zakritih spiskiv Odnak pri virishenni duzhe skladnih zavdan chasto vinikayut situaciyi v yakih algoritm SMA zmushenij postijno peremikatisya z odnogo shlyahu virishennya na inshij v mezhah mnozhini mozhlivih shlyahiv virishennya i v pam yati mozhe pomistitisya tilki nevelika pidmnozhina ciyeyi mnozhini V takomu vipadku na povtorne formuvannya odnih i tih zhe vuzliv vitrachayetsya dodatkovij chas a ce oznachaye sho zavdannya yaki buli b faktichno mozhna virishiti za dopomogoyu poshuku A pri nayavnosti neobmezhenoyi pam yati stayut vazhkovirishuvanimi dlya algoritmu SMA Inshimi slovami cherez obmezhennya v obsyazi pam yati deyaki zavdannya mozhut stavati vazhkovirishuvanimi z tochki zoru chasu obchislennya Hocha vidsutnya teoriya sho dozvolyaye znajti kompromis mizh vitratami chasu i pam yati stvoryuyetsya vrazhennya sho chasto uniknuti viniknennya ciyeyi problemi nemozhlivo Yedinim sposobom podolannya takoyi situaciyi staye chastkova vidmova vid vimog do optimalnosti rishennya Div takozhA D Spisok algoritmivDzherela1 Russell S 1992 Efficient memory bounded search methods 8 zhovtnya 2012 u Wayback Machine In Proceedings of the 10th European Conference on Artificial intelligence Vienna Austria B Neumann Ed John Wiley amp Sons New York NY 1 5