Големина на текста:
1.1Комбинаторни проблеми
Комбинаторният проблем P=(S,f) е оптимизационен проблем, за който е дефинирано
крайно множество от обекти S и обектна функция f:-> S IR+, която присвоява съответна
стойност на цената за всеки от обектите s S. Целта е да се открие обект с минимална
стойност на цената. В общия случай обектите са цели числа, подмножество от точки в
списък, пермутации на точки или граф-структури. Комбин проблеми: Проблем на
търговския пътник (TSP) Проблеми за планиране (scheduling) Проблеми за
разпределение (assignment) Времеви графици (timetabling) Проблеми за подреждане
1.2. а) Алгоритми за комбинаторно търсене. Паралелизация
Комбинаторно търсене – процес на намиране на едно или повече оптимални или
субоптимални решения в дефинирано пространство на проблема. Приложения:
проектиране на МГИС при минимална площ, заемана от връзките, планиране на
движенията на ръцете на робот при минимално изминато разстояние, доказване на
тереми, игри.
Алгоритми, отговарящи на въпроса съществува ли решение на оптимизационни
проблеми – “да” или “не”;
• Алгоритми, решаващи оптимизационни проблеми – намират решение, което намира
минимум или максимум на стойността на функция на обекта;
При всички случаи коренът на дървото представя оригиналния проблем;
• Дълбочината и вида му зависят от решавания проблем;
• Възел от тип “AND” – проблем или подпроблем, който се решава тогава и
само тогава, когато всичките му деца са решени;
• Възел от тип “OR” – проблем или подпроблем, който се решава когато някое от децата
има решение;
AND дърво – решението на проблема се намира като се комбинират решенията
на всички подпроблеми (алгоритми “разделяй-и-владей”);
• OR дърво – решението на проблема се намира когато поне един от проблемите
е решен (търсене с обратен ход или търсене с клони и граници);
• AND/ OR дърво - дървета на игри.
1.2.б) Алгоритми за комбинаторно търсене с обратен ход. Паралелизация
Метод за решаване на комбинаторни оптимизационни проблеми, който се
основава на обхождане по дълбочина (depthfirst search) за разглеждане на
алтернативите;
• Генерират се децата на основния проблем (корена) и се избира едно от тях за да
продължи търсенето;
• Тази методология се повтаря рекурсивно за всеки избран възел;
• При достигане на възел, който не може да бъде разширен (dead end), или ако всички
поддървета на детето са вече разгледани, управлението се връща на предходния възел
(backtrack – обратен ход).
Ако средният фактор на разклонение на дървото на пространството на търсене е
b, търсенето в дърво с дълбочина k изисква разглеждането в най-лошия случай на
~?(bk) брой възли: 1+b+b
2
+…+b
k
= (b
k+1
– b/b-1)+1= ?(b
k
)
Търсенето с обратно обхождане в дървото на пространството на търсене изисква
експоненциално време в най-лошия случай:
• Необходимата памет нараства линейно с дълбочината на търсенето
1.2.в) Алгоритми за комбинаторно търсене по метода на клоните и границите.
Паралелизация
Вариант на търсенето с обратен ход:
• Анализира се информацията за оптималността на частичните решения, като се
избягват решенията, които не могат да бъдат оптимални
• Пример: решаване на пъзела на Сам Лойд с минимален брой ходове – оптимизационен
проблем.
За представяне на позициите, които могат да бъдат получени от първоначалното
разположение на плочките върху дъската използваме дърво на пространството на
търсене:
• Използваме метода “breadth-first search”
• Целта е да се разгледат минимален на брой ходове
• За всяка конфигурация определяме минималният брой ходове, които са необходими за
решаване на пъзела
Последователният алгоритъм предполага изграждането на приоритетна опашка
за неразгледаните проблеми:
• За мултикомпютърните платформи централизираната приоритетна опашка е
неефективна.
• Ако един процесор осъществява операциите над приоритетната опашка – тясно място.
• Една приоритетна опашка не дава възможност за мащабиране.
Всеки процесор трябва да поддържа собствена опашка на неразгледаните
подпроблеми:
• През всяка итерация всеки процес премахва от приоритетната си опашка подпроблема
с най-малка долна граница
• Ако подпроблемът не е възел на решение, то той се разделя на b подпроблема, които се
вмъкват в приоритетната му опашка
• Не съществува синхронизация между процесите
От време на време даден процес изпраща неразгледани подпроблеми на друг
процес
• В началото процес 0 съдържа първо- началния си проблем в приоритетната си опашка.
• Приоритетните опашки на другите процеси са празни и те престояват.
• Процес 0 разпределя неразгледаните подпроблеми, рекурсивно новите подпроблеми се
разпределят, и т.н.
1.2.г) Комбинаторно търсене в дървета на игри. Паралелизация
Най-успешните компютърни програми за игри с двама играчи като шах,
например, се основават на алгоритми за търсене, които изчерпват всички възможни
ходове:
• Тези алгоритми разглеждат възможни последователности от ходове и контраходове,
оценяват колко е желателна съответната конфигурация в играта, и осъществяват
обратен ход на търсене в дървото за определяне на най-успешния първоначален ход

Това е само предварителен преглед

За да разгледате всички страници от този документ натиснете тук.

Теми по метаевристика

Лекционни материали по дисциплината Матаевристика....
Изпратен от:
hafizey
на 2013-10-01
Добавен в:
Лекции
по Технологично проектиране
Статистика:
5 сваляния
виж още
 
 
Онлайн тестове по Технологично проектиране
Тест по компютърно проектиране на технологични процеси за 4-ти курс
изпитен тест по Технологично проектиране за Студенти от 4 курс
Изпитен тест по компютърно проектиране на технологични процеси за студенти 4-ти курс. Съдържа 30 въпроса, някои от които имат повече от един верен отговор.
(Лесен)
30
4
1
5 мин
13.02.2014
Тест по Проектиране и разработване на мултимедийни продукти
тематичен тест по Технологично проектиране за Студенти
Тестът се състои от 50 въпроса, всеки от които има само един верен отговор. Специализиран е в областта на проектирането и създаването на мултимедийни продукти. Може да послужи за подготовка както на студенти, така и на всички, които се занимават в областта.
(Лесен)
50
13
1
7 мин
10.10.2016
» виж всички онлайн тестове по технологично проектиране

Теми по метаевристика

Материал № 1023920, от 01 окт 2013
Свален: 5 пъти
Прегледан: 141 пъти
Предмет: Технологично проектиране, Технически науки
Тип: Лекция
Брой страници: 54
Брой думи: 1,608
Брой символи: 10,069
Цена: 5.00 лв. Закупи материала
Докладвай
Последно видяха материала
Сродни търсения