Оптимізація алгоритмів пошуку

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

МІНІСТЕРСТВО ОСВІТИ

Державна освітня установа вищої професійної освіти "Воронезький державний технічний університет"

Радіотехнічний факультет

Кафедра радіотехніки

Спеціальність 210302 "Радіотехніка"

Оптимізація алгоритмів пошуку

Виконав студент гр. РТ-041 Д.С. Четкін

Перевірив доцент кафедри В.П. Литвиненко

Воронеж 2007

Зміст

Введення

1. Розробка оптимального дихотомічного алгоритму пошуку при равновероятного розподілу ймовірностей і числі подій М = 16

2. Розробка оптимального алгоритму пошуку для експоненціального закону розподілу ймовірностей при М = 16

3. Розробка оптимального алгоритму пошуку експоненціального закону розподілу при числі вимірювань від N = 15 до N = log2M

4. Розробка оптимального алгоритму пошуку для 9-го варіанту розподілу при числі вимірювань від N = 1 до 15

Висновок

Список літератури

Введення

Скритність характеризує витрати (часу, коштів), необхідні для виявлення реасобитія із заданою вірогідністю (ймовірністю правильного рішення, довірчою ймовірністю ).

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

Безліч Х з відповідним законом розподілу ймовірностей розбивається на дві підмножини і (Верхній індекс - номер розбиття). Двійковий вимірювач проводить двійкове вимір, виявляючи, в якому підмножині знаходиться реасобитіе (його слід). Потім підмножина, в якому виявлено реасобитіе (на рис.2.1. Це ), Знову розбивається на дві підмножини і і виявляється слід реасобитія в одному з них. Процедура закінчується, коли у виділеному підмножині виявляється одна подія. Пошук може бути послідовним і дихотомічним. У першому алгоритмі ( ) Проводиться послідовний перебір станів від першого до останнього, поки не зустрінеться реасобитіе.

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

Існує кілька способів мінімізації двійкових пошукових процедур. Прикладами можуть служити методи Циммермана-Хафмена і Шеннона-Фоно. Оптимізувати алгоритм можна за різними параметрами з урахуванням вартості вимірювання і без. У даній лабораторній роботі досліджували оптимізацію дихотомічного алгоритму пошуку за найменшою величиною середньої скритності.

1. Розробка оптимального дихотомічного алгоритму пошуку при равновероятного розподілу ймовірностей і числі подій М = 16

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

У даному випадку найбільш оптимальним алгоритмом пошуку є алгоритм розроблений за принципом Шеннона-Фано. Даний метод передбачає вихідне безліч елементів із заданим розподілом розбити на дві підмножини з номерами 0 і 1 так, щоб ймовірності попадання в них були максимальні близькі (в ідеалі навпіл). Потім кожен з отриманих підмножин окремо розбивається на дві підмножини з тією ж умовою та номерами з 00,01,10,11. Розбиття закінчується коли всі елементи підмножини будуть мати тільки по одному елементу.

У результаті розроблено оптимальний алгоритм пошуку для равновероятного закону розподілу ймовірностей.

Проведемо розрахунок потенційної скритності для равновероятного закону розподілу ймовірностей:

(1)

У результаті для даного випадку:

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

2. Розробка оптимального алгоритму пошуку для експоненціального закону розподілу ймовірностей при М = 16

Виберіть експоненційний розподіл ймовірностей подій виду , , - Нормуючий множник, при тому ж , Що і в пункті 1. Визначте оптимальний алгоритм пошуку, поставте його на набірному полі, проведіть моделювання, визначте потенційну скритність.

Спочатку залишимо дерево пошуку таким же, що в попередньому пункті. «Print Screen» програми «Poisk» для даного випадку для експоненціального закону розподілу.

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

Доказ використання послідовного алгоритму пошуку. Для цього використовується метод Циммермана-Хаффмена. Даний метод оптимізації складається з двох етапів: «Заготівельні операції» і «Зчитування». Більш докладно про це йдеться в книзі [1].

Так як показник ступеня більше 1, а це задовольняє нерівності:

Де λ - показник ступеня розподілу ймовірностей, рівний 1, то для даного випадку оптимальним є послідовний алгоритм пошуку.

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

3. Розробка оптимального алгоритму пошуку експоненціального закону розподілу при числі вимірювань від N = 15 до N = log2M

Для експоненційного розподілу ймовірностей з пункту 2 послідовно зменшуючи максимальне число вимірювань від до , Розробіть оптимальні алгоритми пошуку і за результатами моделювання визначте відповідні значення середнього числа вимірів .

При N = 15 з попереднього пункту оптимальним є послідовний алгоритм пошуку і для нього значення середнє значення двійкових вимірювань визначається так само як і для потенційної скритності. Значення Rcp представлено в таблиці 1.

Таблиця 1 - Залежність середнього числа вимірів

від числа вимірювань при оптимальних алгоритмах пошуку

Т N

33

44

55

66

77

88

99

110

111

112

113

114

115

До R сер

ннельзя


4


2 2.875

22.4 062

22. 20 листопада

22 .0956

22 .0343

.2.0077

22.0038

22.0013

12.0003

11,9998

11.9997

Далі при N = 14.

Проведемо розрахунок потенційної скритності для кожного випадку за формулою 1:

При числі вимірювань рівному 3-м, розробити алгоритм пошуку неможливо, так це не задовольняє умові реалізованим пошуку, а саме:

(2)

У результаті побудований графік залежності середнього числа вимірювань від числа вимірів представлений на рисунку 8.

Рисунок 8 - Залежність середнього числа вимірювань від числа вимірів для експоненціального закону розподілу ймовірності

4. Розробка оптимального алгоритму пошуку для 9-го варіанту розподілу при числі вимірювань від N = 1 до 15

Для свого варіанту розподілу ймовірностей при числі подій розробіть оптимальний алгоритм пошуку, побудуйте дерево пошуку, поясніть його форму, чим вона обумовлена?

На набірному полі задайте оптимальний повний алгоритм пошуку. Послідовно виключаючи останні вимірювання (до ), Розгляньте залежність середнього числа вимірів , Ймовірності неповного рішення і залишковою скритності від тривалості пошуку . Результати представлені в таблиці 2.

Таблиця 2 - Залежність середнього числа вимірів,

залишкової скритності, ймовірності невизначеності від числа вимірів

n

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

R




4

3.775

4.325

4.725

5.1625

5.375

5.5

5.65

5.7

5.7625

5.8

5.8

P неоп

0.55

0.7625

0.875

0

0

0

0

0

0

0

0

0

0

0

0

S ост


0 .8 01

0.785

0.791

0.802

0.814

0.826

0.837

0.848

0.858

0.868

0.877

0.885

0.893

0.901

У даній таблиці S ост вважалося при довірчій ймовірності 0.9. «Print Screen» програми «Poisk» при різних значеннях числа вимірів представлений на малюнках 8-11.

При числі вимірювань менше 4-х з'являється ймовірність неповного рішення, пов'язана з тим, що неможливо перевірити всі події. У результаті доводиться перевіряти не всі, оптимальним варіантом буде перевірка найбільш ймовірних подій. «Print Screen» програми «Poisk» при числі вимірювання менше 3-х представлена ​​на малюнку 12.

Побудуємо графік залежності потенційної скритності від числа виміру, який представлений на малюнку 13.

Малюнок 13 - Залежність середнього числа вимірювань від числа вимірів для 9-го закону розподілу ймовірності

Рисунок 14 - Залежність ймовірності неповного рішення від числа вимірів для 9-го закону розподілу ймовірності

Далі потрібно провести розрахунок залишкової скритності від числа вимірів.

(3)

(4)

Довірчу ймовірність будемо міняти в межах 0.7 ÷ 0.9. У результаті отриманий графік залежності залишкової скритності від числа вимірів, який представлений на малюнку 15.

Ност (P дов) P дов = 0.9

Рисунок 15 - Залежність залишкової прихованості при значеннях довірчої ймовірності 0.7 ÷ 0.9

З представленого вище графіка можна зробити висновок, що P дов слід вибирати близьким до одиниці, це призведе до зменшення залишкової скритності, проте не завжди таке можливо.

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

Рисунок 16 - Залежність залишкової прихованості при значеннях числа вимірів 4,8,16

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

Висновок

У даній роботі були проведені дослідження оптимізації дихотомічного алгоритму пошуку за допомогою програми Poick. Проведено порівняння з послідовним алгоритмом. Досліджено вид КСН при рівномірному, експоненційному і заданому за варіантом розподілі подій. Напрацьовано навички у поводженні з програмою Poick.

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

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

Правильність роботи програми Poisk потверджений за допомогою розрахунків проведених у пакеті програм Matcard 2001.

Список літератури

1. Основи теорії скритності: навчальний посібник для студентів спеціальності 200700 «Радіотехніка» денної форми навчання / Черкаський національний технічний університет; Сост.З.М. Канівський, В.П. Литвиненко, Г.В. Макаров, Д.А. Максимов; під редакцією З.М. Канівського. Воронеж, 2006. 202с.

2. Методичні вказівки до лабораторних робіт «Дослідження алгоритмів пошуку» з дисципліни «Основи теорії скритності» для студентів спеціальності 200700 «Радіотехніка» денної форм7 навчання / Воронезький державний технічний університет; сост.З.М. Канівський, В.П. Литвиненко. Воронеж, 2007.54с.

3. СТП ВДТУ 005-2007. Курсове проектування. Організація, порядок, оформлення розрахунково-пояснювальної записки та графічної частини.

Додати в блог або на сайт

Цей текст може містити помилки.

Комунікації, зв'язок, цифрові прилади і радіоелектроніка | Курсова
44.2кб. | скачати


Схожі роботи:
Складання алгоритмів пошуку несправностей
Порівняльний аналіз ефективності та складності алгоритмів пошуку елементів у масивах
Оптимізація Методи багатовимірного пошуку
Алгоритми сортування пошуку найкоротшого шляху в графі та пошуку покриття близького до найкоротшому
Алгоритми сортування пошуку найдовшого шляху в зваженому графі та пошуку покриття близького до найкоротшому
Теорія алгоритмів
Типи алгоритмів
Програмування допоміжних алгоритмів
Виконавець алгоритмів людина
© Усі права захищені
написати до нас