Планування в просторі станів icon

Планування в просторі станів



НазваниеПланування в просторі станів
страница1/3
Дата конвертации08.11.2012
Размер380.54 Kb.
ТипДокументы
скачать >>>
  1   2   3

Планування в просторі станів.

План




Вступ


3

Стани і оператори.

4

Опис станів.

4

Оператори.

4

Резюме.

5

Представлення простору станів.

5

Резюме.

6

Методи пошуку в просторі станів.

6

Загальна схема пошуку на графі. «Сліпі» методи пошуку.

6

Евристичні методи пошуку

7

Резюме.

8

Алгоритм Харта, Нільсона і Рафаеля.

9

Опис алгоритму.

9

Припустимість і оптимальність алгоритму.

11
^

Як потрібно обирати еврестичну функцію?


15

Програма «Гра в 8».

16

Лістінг програми «eigths».

16
^

Отримані результати.


22

Література

24



Вступ.


Розглянемо просту гру, яку називають “гра в 8“. Як її вирішити? Один з анйбільш простих способів – це просто перепробувати різні ходи, поки не вдасться отримати цільову конфігурацію. Тобто починаючи з початкової конфігурації, ми могли б побудувати всі конфігурації, що виникають при виконанні кожного з можливих ходів, потім побудувати іншу множину конфігурації, після застосування наступного ходу, і т.д.

Давайте тепер спробуємо більш формально підійти до вирішення цієї гри, але використовуючи ту ж саму ідею. Задамо множину конфігурацій, які можна досягти з початкової конфігурації, у вигляді графу, вершини якого є цими конфігураціями. З’єднаємо кожну з вершин цього графу дугами, кожна з яких виступає у якості певної функції, що переводить данну конфігурацію (вершина-батько), до іншої конфігурації (вершина-син). Таким чином, вирішення “гри в 8“ зведеться до пошуку на нашому графі, де початковій вершині пошуку відповідає вершина з початковою конфігурацією, а шуканій – вершина з цільовою.

Описаний вище метод вирішенні “гри в 8” заснований на плануванні в просторі станів. Більш формальні і чіткі визначення необхідних понять буде наведено далі. При написанні роботи буде детально розглянуто так звану класичну схему пошуку, відому ще як алгоритм Харта, Нільсона та Рафаеля (ХНР). Буде наведено необхідні теоритичні відомості, а також особлива увага буде приділена висвітленню часткових випадків алгоритму А*1, і питанню про залежність ефективності алгоритму від вибору еврестичної функції.


Стани і оператори.


Для вирішення «гри в 8» була запропонована схема пошуку шляху на графі від початкової вершини, що відповідає початковій конфігурації до цільової. В данному контексті видається корисним ввести деякі визначення необхідних понять. В цьому розділі ми дамо визначення таких понять : стани і оператори.

^
Опис станів.


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

Поняття стану для конкретної задачі є дуже важливим, оскільки є основним для побудови опису задачі з використанням простору станів. Тому перед вирішенням тієї чи іншої задачі необхідно чітко розуміти, що уявляють собою стани для данної задачі. Наступним важливим етапом побудови опису задачі з використанням простору станів є вибір певної конкретної форми опису станів цієї задачі. Це може бути будь-яка структура (рядки символів, вектори, масиви, дерева чи списки), але бажано обирати, якщо це можливо, форму, яка має певну фізичну властивість вирішуваної задачі. Так для «гри в 8» природньої формою опису є масив 3*3. При виборі форми необхідно також враховувати те, що застосування оператору2 до певного стану не породжувало додаткових труднощів і було достатньо легким.

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


Оператори.


Оператор перетворює один стан в інший. «Гра в 8» може бути інтерпритована, як гра, в якій є чотири оператори, що відповідають ходам : перемістити пусту клітинку ліворуч, праворуч, вверх і вниз. В деяких випадках певний оператор не може бути застосований до певного стану : при розташуванні пустої клітинки у правому нижньому куті до неї не може бути застосований оператор «перемістити праворуч».

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

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

Як і для опису станів, для опису операторів важливим є питання про форму опису. Ми могли б визначати операторні функції за допомогою таблиць, яка пов’язує з кожним вхідним описом деякий вихідний. Але для великих задач використання такого типу таблиці видається непридатним, тому в загальному випадку, ми будемо вважати, що оператори – це обчислення, які перетворюють одні описи станів в інші.


Резюме.


В цій частині ми дали визначення понять необхідних для представлення задачі в просторі станів і визначили критерії, які необхідні для того, щоб це коректно зробити. Виділимо їх більш чітко.

Отже, для повного і правильного представлення данної задачі в просторі станів необхідно задати :

  • форму опису станів і опис початкового стану;

  • множину операторів іїх дію на описи станів;

  • властивості опису цільового стану.

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


Представлення простору станів.


Перед тим як безпосередньо перейти до опису данного представлення простору станів наведемо деякі загальні теоритичні відомості з теорії графів.

Граф складається з множини вершин. Деякі пари вершин з‘єднані одна з одною за допомогою дуг. У випадку орієнтованого графу ці дуги є напрямленими від однієї вершини до іншої.Якщо деяка дуга напрямлена від вершини до вершини то вершина є дочірньою для вершини , а вершина є батьківською для . Може статися, що деякі дві вершини є дочірніми одна для одної, в цьому випадку пара напрямлених дуг називається ребром графа. У випадку використання графа для представлення в просторі станів з його вершинами пов’язують описи станів, а з дугами – операторами.

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

Іноді дугам графа приписують певні ваги, які відображають вагу використання того чи іншого оператору. Вага шляху між двома вершинами визначається як сума ваг всіх дуг, які з’єднують вершини цього шляху.

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


Резюме.


В цьому розділі було описано один з методів представлення в просторі станів3 і сказано про загальні підходи до вирішення задач за допомогою пошуку шляху на графі

Тут не було розглянуте питання про те, яким саме чином необхідно задавати граф (явним чи неявним), оскільки це питання є очевидним. Для великих графів метод явного задання є абсолютно недоцільним. Техніка неявного задання графа також не була описана, але саме вона буде використана при написанні програми “гра в 8”.

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


Методи пошуку в просторі станів.


Загальна схема пошуку на графі. «Сліпі» методи пошуку.


При формулюванні задачі в просторі станів рішення отримується в результаті застосування операторів до описів станів доти, доки не буде отримано вираз, що описує стан, який відповідає досягненню мети. Домовимось, що простір станів будемо представляти за допомогою орієнтованого графа : вершини якого відповідають відповідним описам станів, а дуги – операторам. Тому видається корисним навести загальну схему методів перебору4 в просторі станів, у термінах теорії графів:

  • початкова вершина відповідає опису початкового стану;

  • вершини, що безпосередньо йдуьб за данною, отримуються в результаті використання операторів, які застосовуються до опису стану, що відповідає данній вершині. Нехай ми маємо деякий оператор, який будує всі вершини, що безпосередньо йдуть за данною. Тоді процес застосування цього оператора до деякої вершини будемо називати розкриттям вершини;

  • від кожної такої наступної вершини до вершини, яка її породила, йдуть вказівники, які дозволяють знайти шлях назад, після знаходження цільової вершини;

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

У випадку повного описання процесу перебору необхідно задати порядок розкриття вершин. Якщо вершини розкриваються в тому порядку в якому вони були породжені, то такий процес називається повний перебір (breadth-first process). Якщо з початку розкривається та вершина, яка була побудована останньою, то ми отримуємо процес перебору в глибину (depth-first process). Наведені вище процеси в літературі отримали спільну назву процедури “сліпого перебору”, оскільки розташування цілі не впливає на порядок в якому розкриваються вершини.


^ Евристичні методи пошуку.


Методи «сліпого» перебору є вичерпними процедурами пошуку шляхів до цільової вершини. Але часто їх неможливо використовувати, оскільки при переборі доведеться розкрити занадто багато вершин. Тому видається розумним знайти такі емпіричні правила, які допомогли зменшити об’єм перебору. Всі такі правила залежать від специфічної інформації про задачу.

Припустимо, що ми маємо певну інформацію про глобальний характер графа і загальне розташування мети пошуку. Така інформація могла б бути використана для того, щоб прискорити процес пошуку в бік мети, розкриваючи в першу чергу найбільш перспективні вершини. Будемо називати таку інформацію евристичною5, а методи пошуку на графі, якій засновані на ідеї її використання - еврестичними методами пошуку.

Розглянемо деякі шляхи використання евристичної інформації:

  • вибір більш “інформованого” оператора;

  • розташування вершин в певному порядку перед тим як їх розкривати (порядок залежить від значень евристичної функції).

Таким чином, у другому випадку, ми на кожному кроці будемо обирати, відповідно до деякого критерію, який залежить від евристичної інформації, вершину, яка є більш перспективною ніж інші. Для цього нам необхідна функція, яка ю оцінювала “перспективність” вершини. Назовемо такі функції оцінюючими.

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

  • оцінювалась вирогідність того, що вершина розташована на кращому шляху;

  • використовувалась відстань, а також інші різниці між вершиною і множиною цільових вершин;

  • кожному стану ставилася у відповідність певна кількість очків, на основі тих рис, якими вона володіє.

Запропонуємо такий варіант еврестичної функції. Нехай задана певна функція , яка могла б бути використана для впорядкування вершин перед тим, як їх розкривати. Через позначимо значення цієї функції для вершини . Домовимось, що вершини, які будуть розкриватись, розташовуються в порядку зростання функції . Тоді можна використати деякий алгоритм, в якому для подальшого розкриття обирається вершина, для якої значення функції є найменшим. В літературі такий алгоритм отримав назву впорядкований перебір (ordered-search algorithm).

Для того, щоб данний алгоритм працював для перебору на довільних графах, необхідно передбачити можливість побудови вершин, які вже знаходяться або в списку OPEN6, або в списку CLOSE7. При використані деякої довільної функції потрібно врахувати, що величина для деякої вершини зі списку CLOSE може понизитися, якщо до неї було знайдено новий шлях. Тоді ми повинні перенести такі вершини назад до списку OPEN і перенаправити вказівники.

Наведемо послідовність кроків, які описують данний алгоритм:

  1. Занести початкову вершину до списку OPEN і підрахувати .

  2. Якщо список OPEN пустий, то на вихід видати сигнал про невдачу, в іншому випадку перейти до настпуного етапу.

  3. Взяти зі списку OPEN ту вершину, для якої має найменше значення, і занести її до списку CLOSE. Дати цій вершині назву . (У випадку співпадання значень функції для декількох вершин обирати вершину з мінімальним довільно, але завжди надавати перевагу цільовій вершині).

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

  5. Розкрити вершину , побудувавши всі вершини, які безпосередньо йдуть за нею. (Якщо таких немає, то перейти до кроку 2) . Для кожної дочірньої вершини підрахувати значення .

  6. Пов’язати з тими з вершин , яких ще немає в списках OPEN чи CLOSE, тільки що підраховані значення . Занести ці вершини до списку OPEN і провести від них до вершини вказівники.

  7. Пов’язати з тими з вершин, які безпосередньо йдуть за , які вже були в списках OPEN чи CLOSE, менше з попередніх і щойно підрахованих значень . Занести до списку OPEN ті з вершин, які безпосередньо йдуть за вершиною , для яких нове значення менше, і змінити напрямок вказівників від всіх вершин, для яких значення зменшилося,спрямувавши їх до .

  8. Перейти до кроку 2.


  1   2   3



Похожие:

Планування в просторі станів iconАналіз результатів Всеукраїнського соціологічного дослідження «Бібліотека та читач у віртуальному просторі. Місце зустрічі» (Волинська обласна бібліотека для юнацтва) Всеукраїнське соціологічне дослідження «Бібліотека та читач у віртуальному просторі.
Всеукраїнське соціологічне дослідження «Бібліотека та читач у віртуальному просторі. Місце зустрічі» проводилось з метою виявити
Планування в просторі станів iconГенетичні основи двовекторності розвитку, саморозвитку та корекції психосоматичних станів Академік апн україни
Генетичні основи двовекторності розвитку, саморозвитку та корекції психосоматичних станів
Планування в просторі станів iconОбраз України у електоральному просторі: динаміка, константи, прогноз Образ Украины в электоральном пространстве: динамика, константы, прогноз
Факторний аналіз виборів народних депутатів України 2006 року. Вперше за роки незалежності Україна настільки дезінтегрована у електоральному...
Планування в просторі станів iconВсеукраїнський форум представників органів студентського самоврядування «нові законодавчі ініціативи та болонський процес в українському освітньому просторі»
Реєстраційна анкета учасника всеукраїнського студентського форуму «нові законодавчі ініціативи та болонський процес в українському...
Планування в просторі станів iconРеферату : Планування сім’ї Розділ : Різне Планування сім’ї
Погіршення репродуктивного здоров’я населення особливої уваги заслуговують питання планування сім’ї як резерву в зниженні материнської...
Планування в просторі станів iconОперативне планування маріуш Земба Зміст Вступ Оперативне планування
Планування це процес визначення цілей організації та засобів їх досягнення. Під час цього процесу ми визначаємо, що, коли і як потрібно...
Планування в просторі станів iconEcofin. Org. Ua середньострокове бюджетне планування в Швеції
Швеції. Основні елементи реформи включали прийняття багаторічного планування і здійснення бюджетного процесу «згори вниз». Багаторічне...
Планування в просторі станів iconПланування як визначення змісту І засобів діяльності
П. Бачило, Б. А. Гаєвська, Л. І. Даниленко, Ю. А. Конаржевський, Ф. І. Хміль та інші. За даними дослідження Г. В. Єльникової, майже...
Планування в просторі станів iconШановні колеги! Маємо честь запросити Вас 21-22 листопада 2013 року в
«Нові горизонти анестезіології, інтенсивної терапії критичних станів та лікування болю»
Планування в просторі станів iconПолітика Єс в інформаційному просторі України

Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©gua.convdocs.org 2000-2015
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов