Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Зведення до дискретного масиву даних




End

Begin

 

s.parent:= nil; // s is a node for the start

 

s.g:= 0; // s is the start node

 

s.h:= GoalDistEstimate(s); s.f = s.g + s.h;

 

push s on Open

 

while Open is not empty do begin

pop node n from Open

 

if n is a goal node then begin

construct path

 

result:= true; // success

exit;

 

end;

 

for each successor n’ of n do begin

newg:= n.g + cost(n,n’);

 

if (n’ is in Open or Closed) and n’.g <= newg

then continue;

 

n’.parent:= n; n’.g:= newg;

 

n’.h:= GoadDistEstimate(n’); n’.f:= n’.g + n’.h;

 

if n’ is in Closed then remove n’ from Closed; if

n’ is not in Open then push n' on Open;

 

end;

 

push n on Closed

end;

 

result:= false; // no path found

 

 


Алгоритм A* має декілька цікавих властивостей:

 

– він гарантовано знаходить найкоротший (оптимальний) шлях, якщо евристична оцінка h (n) прийнятна у тому розумінні, що вона ніколи не більша від істинної відстані до цілі;

– кількість обчислень евристичної функції мінімальна. Це означає, що ніякий інший алгоритм, що використовує ту ж саму функцію h (n),не обробить менше вузлів,ніж алгоритмA*.

 

Приклад роботи алгоритму A* для розглянутої задачі подано на рис. 9.7.

 

Рис. 9.7. Результат роботи алгоритмуA*

 

9.7. Різні форми задання простору пошуку

 

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

 

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

 

 


Найбільш очевидним підходом буде відобразити інформацію про об’єкти на двовимірний масив даних. У цьому разі комірки карти, де об’єктів зовсім немає, можуть розглядатися як вільні, а ті комірки, які зайняті об’єктами повністю або частково, як непрохідні (рис. 9.8, б). Єдиним недоліком такого підходу є велика кількість елементів у просторі пошуку.

Задання об’єктів вершинами у зоні прямої видимості

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

Метод опуклих багатокутників

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

 

 


 

 

 

a б в

 

 

г д е

 

Рис. 9.8. Перешкоди в суцільному просторі та методи перетворення простору пошуку:

а – перешкоди в суцільному просторі; б – зведення до дискретного масиву даних;

в – задання об’єктів вершинами у зоні прямої видимості; г – метод опуклих багатокут-ників; д – метод послідовного розбиття простору; е – метод узагальнених циліндрів

 

Метод послідовного розбиття простору

 

Зменшуючи крок дискретизації під час перетворення простору пошуку до дискретного вигляду можна отримати будь-яку наперед задану точність подання перешкод, але необмежено зростаючу кількість елементів у просторі пошуку. Збільшуючи ж крок, точність подання перешкод може виявитись незадовільною. Компромісним розв’язанням може стати метод адаптивного розбиття простору. Під час

 


першого проходу крок дискретизації вибирають досить великим. Надалі «подрібнюються» тільки ті елементи, які частково містять перешкоди. Результат такого адаптивного розбиття показано на рис. 9.8, д.

 

Метод узагальнених циліндрів

 

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

 

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

 

 


СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

 

1. Вороновский Г. К. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности [Текст] / Г. К. Вороновский, К. В. Махотило, С. Н. Петрашев, С. А. Сергеев. – Харьков: Основа, 1997. – 112 с. – Библиогр.: с. 78–81. – 800 экз. – ISBN 5–7768–0293–8.

 

2. Уськов А. А. Интеллектуальные технологии управления:искус-ственные нейронные сети и нечеткая логика [Текст] / А. А. Уськов, А. В. Кузьмин. – М.: Горячая линия – Телеком, 2004. – 143 с. – Биб

лиогр.: с. 124–141. – 1000 экз. – ISBN 5–93517–181–3.

 

3. Рутковская Д. Нейронные сети,генетические алгоритмы и не-четкие системы [Текст] / Д. Рутковская, М. Пилиньский, Л. Рутковский. – М.: Горячая линия – Телеком, 2004. – 452 с. – Библиогр.:

 

с. 379–380. – 1500 экз. – ISBN 5–93517–103–1.

 

4. P. Wasserman. Neural computing: theory and practice / VanNostrand Reinhold, New-York, 1989.

 

5. J. S. Albus and A.M. Meystel. Engineering of Mind: AnIntroduction to the Science of Intelligent Systems / Wiley, New York, 2001.

 

6. J. S. Albus and A. M. Meystel. Intelligent Systems: Architecture,Design, and Control / Wiley, New York, 2002.

 

7. A. P. Engelbrecht. Computational Intelligence: An Introduction /Wiley, Chichester, U.K., 2002.

 

8. R. Babuska. Fuzzy Modeling for Control / Kluwer AcademicPublishers, Boston, 1998.

9. L. Fausett. Fundamentals of Neural Networks: Architectures,Algorithms and Applications / Prentice Hall, Englewood Cliffs, NJ, 1997

 

 


10. S. Haykin. Neural Networks: A Comprehensive Foundation /

Macmillan, New York, 1994.

11. C. R. Reeves and J.W. Rowe. Genetic Algorithms Principles and

Perspectives: A Guide to GA Theory / Kluwer, Boston, 1997.

12. R. A. Aleev and R. R. Aleev. Soft Computing and its Applications /

World Scientific, Singapore, 2001.

13. L. A. Zadeh. Fuzzy sets / Information and Control, 8:338-353,

1965.

14. H. Bandemer and S. Gottwald. Fuzzy Sets, Fuzzy Logic Fuzzy

Methods with Applications / John Wiley & Sons, Chichester, 1995.

15. R. J. Schalkoff. Artificial Neural Networks / McGraw-Hill, New

York, 2002.

16. A. B. Badiru and J. Y. Cheung. Fuzzy Engineering Expert Systems

with Neural Network Applications / John Wiley, New York, NY, 2002.

 

 





Поделиться с друзьями:


Дата добавления: 2014-11-16; Просмотров: 467; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.01 сек.