Задача за търговския пътник, навигация на роботи, задачи за планиране и конструиране (асемблиране) на сложни обекти и др



Дата23.02.2017
Размер47.07 Kb.
#15561
ТипЗадача
Лекция 3: Търсене на път до определена цел

Примерни задачи от реалния свят: намиране на път (при routing в компютърни мрежи, при планиране на пътувания с автомобилен/самолетен транспорт и др.), задача за търговския пътник, навигация на роботи, задачи за планиране и конструиране (асемблиране) на сложни обекти и др.

Характеристики на алгоритмите за търсене:

• пълнота

• оптималност

• сложност o по време ≈ брой изследвани възли o по памет ≈ максимален размер на фронта

Необходимост от избягване на повторения и зацикляне.

Параметри на търсенето:

• дълбочина на “най-плитката” цел – d (или максимална “дълбочина” на пространството/графа на състоянията – m)

• коефициент на разклонение (разклоненост) на ГС – b

Методи за неинформирано ("сляпо") търсене

Обща характеристика: пълно изчерпване по твърда (фиксирана отнапред) стратегия. Прилагат се, когато липсва специфична информация за предметната област и оценяващата функция може само да провери дали дадено състояние е целево или не е. Програмна реализация: чрез използване на работна памет (списък Open/frontier/fringe на т. нар. открити възли или списък от натрупани/изминати пътища, започващи от началния възел – нарича се още фронт на търсенето).

Общ алгоритъм за неинформирано търсене

Тръгва се от началния възел, като на всяка стъпка фронтът на търсенето се разширява в посока към неизследваните възли, докато се достигне до целеви възел.

Начинът, по който се разширява фронтът, както и правилата за избор на конкретен елемент на фронта, от който ще продължи неговото разширяване, определят стратегията на търсене (search strategy).

(рисува се вълна в/у дърво)

Неинформирано търсене в дърво Неформално описание на общия алгоритъм

function TREE-SEARCH( problem, strategy) returns a solution, or failure

initialize the search tree using the initial state of problem

loop do


if there are no candidates for expansion then return failure

choose a leaf node for expansion according to strategy

if the node contains a goal state then return the corresponding solution

else expand the node and add the resulting nodes to the search tree



Реализация – представяне на възлите от графа (дървото)

на състоянията

В следващите дефиниции на функции за търсене (написани на псевдокод) ще предполагаме, че всеки възел от ГС е структура от данни с 5 компонента: STATE: състоянието от пространството, на което съответства

разглежданият възел PARENT: възелът от ГС, като наследник на който е генериран

разглежданият възел ACTION: операторът, с помощта на който е бил генериран

разглежданият възел

PATH-COST: цената (традиционно означавана с g(n)) на пътя от началното състояние до състоянието, съответно на разглеждания възел (в съответствие с указателите към родителските възли)

DEPTH: броят на стъпките, от които е съставен пътят от началното състояние до състоянието, съответно на разглеждания възел



Пример: задача за 8-те плъзгащи се плочки (the 8-puzzle problem)

Състояния: разположения (конфигурации) на 8-те плочки Оператори: премествания на празното поле (left, right, up, down) Проверка за достигане на целта: проверка за съвпадение с

даденото целево състояние Цена на пътя: 1 за всяко преместване

• Всяко състояние (state) представя конкретна конфигурация на плочките;

• Всеки възел от ГС (node) се представя като структура от данни, която съдържа компоненти (полета), описващи състоянието, родителя, използвания оператор, цената на съответната част от пътя и дълбочината на вложение;

• Функцията EXPAND генерира нови възли, като за целта попълва съответните компоненти (полета) и в частност използва функцията SUCCESSOR-FN за създаване на съответните състояния.



Формално описание на общия алгоритъм за неинформирано

търсене в дърво

function TREE-SEARCH( problem, jrm^e) returns a solution, or failure fringe <— lNSERT(MAKE-NoDE(lNiTiAL-STATE[pn?b/em]), fringe) loop do

if fringe is empty then return failure

node <— REMOVE- FRONT(fringe)

if GOAL- TEST[problem]( STATE [node]) then return SOLUTION( node)

fringe <— INS ЕКГАЬЬ( EXPAND (node, problem), fringe)

function EXPAND( node, problem) returns a set of nodes successors <— the empty set for each action, result in SuccESSOR-FN[prcMem](STATE[n0de]) do

s«— a new NODE

PARENT- NODE[

PATH-COST[S] <— PATn-CosT[node] + STEP-COST(node, action, s)

DEPTH [S] <— DEPTH[node] + 1

add s to successors return successors



Описание на действието на използваните функции:

• FIRST(list) връща първия елемент на list

• REMOVE-FRONT(list) връща FIRST(list) и го изтрива от list

• INSERT(element, list) добавя element към list и връща получения списък

• INSERTALL(elements, list) добавя множество от елементи към даден списък и връща като резултат получения списък

• SOLUTION(node) връща като резултат поредицата от оператори, довели от началното до целевото състояние (в съответствие с указателите към родителските възли)

Забележка. Функцията TREE-SEARCH се изпълнява със стойност на аргумента fringe, равна на празен списък.

Неинформирано търсене в граф

Формално описание на общия алгоритъм за неинформирано

търсене в граф

function GRAPH-SEARCH(problem, fringe) returns a solution, or failure

closed

fringe «- lNSERT(MAKE-NODE(lNiTiAL-STATE[proMem]), fringe)

loop do

if fringe is empty then return failure node-<^REMOVE-FRONT( fringe)



if GOAL- TEST [prob Jem] (STATE [node]) then return SOLUTION (node) if STATE [node] is not in closed then add STATE [node] to closed fringe«— INSERTALL(EXPAND( node, problem), fringe)

Стратегии за неинформирано търсене

1. Изчерпване (търсене) в дълбочина (depth-first search) -добавяне на новите възли (новия възел) в началото на списъка Open/fringe.

fringe = стек (LIFO, put successors at front)

Търсенето е евтино (линейно по отношение на необходимата памет), но не е нито пълно, нито оптимално (пълно е, когато графът на състоянията е краен или поне не съществуват безкрайно дълги ациклични пътища в него).

Построяване на пътя като списък от последователни

състояния

• Фронтът на търсенето е списък от пътища (отначало е списък от един път, който включва само началното състояние).

• При търсенето в дълбочина фронтът се обработва като стек.

• Ако фронтът има вида [p1, p2, … , pn], то:

o Избира се p1. Ако p1 е довел до целта, край.

o Пътищата p11, p12, … , p1k, които разширяват p1, се добавят в началото на фронта (преди p2), т.е. фронтът придобива вида [p11, p12, … , p1k, p2, … , pn]. Преминава се към следващата стъпка от цикъла.


Вариант 1: търсене в дълбочина до определено ниво (depth-bound search, depth-limited search).

Вариант 2: итеративно търсене по нива (iterative deepening).



2. Изчерпване (търсене) в широчина (breadth-first search) -добавяне на новите възли в края на списъка Open/fringe.

fringe = опашка (FIFO, put successors at end)

Търсенето е пълно (когато всеки възел от ГС има краен брой наследници) и оптимално, но е скъпо (експоненциално по отношение на необходимата памет).

Построяване на пътя като списък от последователни

състояния

• Фронтът на търсенето е списък от пътища (отначало е списък от един път, който включва само началното състояние).

• При търсенето в широчина фронтът се обработва като опашка.

• Ако фронтът има вида [p1, p2, … , pn], то: o Избира се p1. Ако p1 е довел до целта, край. o Пътищата p11, p12, … , p1k, които разширяват p1, се добавят в

края на фронта (след pn), т.е. фронтът придобива вида [p2, … , pn, p11, p12, … , p1k]. Преминава се към следващата стъпка от цикъла.

Вариант: търсене с равномерна цена на пътя (uniform-cost search) - сортиране на списъка Open/fringe според цената на изминатия път.

Оценка на сложността. Пространствената сложност (сложността по памет) на търсенето в дълбочина е О(bm), докато пространствената сложност на търсенето в широчина е О(bd+1). Времевата сложност на търсенето в дълбочина е О(bm), а времевата сложност на търсенето в широчина е О(bd+1). При задачи, които имат много решения, търсенето в дълбочина може да бъде по-бързо от търсенето в широчина, тъй като има добър шанс да се намери решение след изследване на малка част от цялото ПС.

Търсенето в ограничена дълбочина (търсенето в дълбочина до определено ниво) има сложност, подобна на тази на търсенето в дълбочина (изисква О(bl) време и О(bl) памет, където l е максималната дълбочина на изследване). Итеративното търсене по нива има времева сложност О(bd) и пространствена сложност О(bd), където където d е максималната дълбочина на изследване. Това е най-предпочитаният метод за търсене, когато ПС е с голям размер и няма никаква информация за дълбочината на решението.



Резюме на алгоритмите за неинформирано търсене

Означения:

b - коефициент на разклонение на ГС d - дълбочина на най-плитката цел

m - максимална дълбочина на ГС (може да бъде ∞) l - максимална дълбочина на изследване



C* - цена на оптималния път (предполага се, че всички стъпки имат цена ≥ ε, ε>0)


Сподели с приятели:




©obuch.info 2024
отнасят до администрацията

    Начална страница