• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Швидке сортування quick

Метод вставки

Метод пухирця

Додавання елементу без дублювання

Minimum(X, Y, M).

Поелементне введення-виведення списку.

Введення-виведення списку як терма.

При цьому способі список розглядається як один терм.

Наприклад, процедура:

pr:-write('Уведіть список L:'),nl,

read(L),nl,

write('Список L='),

tab(2), write(L),nl.

При виклику мети

?-pr.

вона буде виконуватися в такий спосіб:

Уведіть список L:

[a,b,c,d].

Список L= [a,b,c,d]

Даний спосіб може бути організований за допомогою рекурсивно визначених процедур.

read_list([X|T]):-write('Введіть елемент: '),

read(X),

X\==end,!,

read_list(T).

end - терм , що означає кінець списку.

read_list([]).

write_list([]):-nl.

write_list([H|T]):-write(H),

tab(2),

write_list(T).

Тоді після виклику мети:

?-read_list(L),nl,write('Список='),nl, write_list(L).

Виникає наступний діалог:

Введіть елемент: a.

Введіть елемент: b.

Введіть елемент: c.

Введіть елемент: d.

Введіть елемент: end.

Список= a b c d

Лекція 5

Відсікання. Сортування списків.

Зміст

5.1. Відсічення

5.1.1. Графічна ілюстрація дії cut

5.1.2. Приклад дії cut

5.1.3. Застосування cut при виборі альтернатив

5.1.4. Формальний опис дії відсічення

5.2. Застосування відсічення

5.2.3. Класифікація

5.2.4. Відсічення в чисельній рекурсії

5.2.5. Зауваження при використанні відсічення

5.3. Сортування списків

5.3.1. Метод наївного сортування

5.1 Відсікання.

У процесі обчислення мети пролог проводить перебір варіантів, відповідно до встановленого порядку. Мети виконуються послідовно, одна за одною, а у випадку невдачі відбувається відкіт до попередньої мети (backtracing).

Однак для підвищення ефективності виконання програми, часто потрібно втрутитися в перебір, обмежити його, виключити деякі мети.

Для цієї мети в пролог уведена спеціальна конструкція cut - "відсікання", що позначається як "!"

(Читається "cut", "кат").

Cut підказує прологу "закріпити" усі рішення попередній появі його в пропозиції. Це означає, що якщо потрібно бектрекінг, то він приведе до невдачі (fail) без спроби пошуку альтернатив.

5.1.1 Графічна ілюстрація дії cut.

Графічно дію cut можна показати за допомогою box-представлення логічного висновку.

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

G:-A,B,C.

виглядає в такий спосіб:

Тобто. пошук альтернатив виробляється для всіх цілей: G,A,B,C. Замінимо B на cut:

Графічна ілюстрація дії cut.

Дія cut полягає в скасуванні пошуку альтернатив для цілей A,G, що стоять після "!".

5.1.2 Приклад дії cut.

Нехай база даних виглядає наступним чином

data(one).

data(two).

data(three).

Процедура для перевірки:

cut_test_a(X):- data(X).

cut_test_a('last clouse').

Ціль:

?- cut_test_a(X),nl,write(X).

one;

two;

three;

last_clouse;

no

Тепер поставимо cut у правило:

cut_test_b(X):- data(X),!.

cut_test_b('last clouse').

Ціль:

?-cut_test_b(X),nl,write(X).

one;

no

Відбувається зупинка бектрекінгу для лівого data і батьківського

cut_test_b(X).

Тепер помістимо cut між двома цілями.

cut_test_з(X,Y):- data(X),

/ !,data(Y).

cut_test_з('last clouse').

Тепер бектрекінг не буде для лівого data і батьківського cut_test_b(X),але буде для правого data, що стоїть після !.

?-cut_test_з(X,Y),nl,write(X-Y).

one-one;

one-two;

one-tree;

no

5.1.3 Застосування cut при виборі альтернатив.

Розглянемо функцію Y(X):

На пролозі це запишеться через бінарне відношення f(X, Y).

Процедура виглядає:

f(X, 0):- X < 3.

f(X, 2):- 3 =< X, X < 6.

f(X, 4):- 6 =< X.

Поставимо запитання:

?-f(1,Y),Y>2.

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

Як забрати неефективність?

Треба використовувати відсікання-cut.

Перепишемо

f( X, 0):-X<3, !.

f(X, 2):- 3=<X, X<6, !.

f(X, 4):-6 =<X, !.

! указує, що повернення з цієї точки проводити не треба.

Що відбудеться тепер?

Для мети

?-f(1, Y), Y>2.

no

Після виконання мети X<3 мета Y>2, не досягається, але відкіт не може відбутися, тому що стоїть cut.

У такий спосіб скорочується перебір.

Аналогічно для мети

?-f(5, Y), Y=0.

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

Після вилучення ! декларативний зміст не зміниться.

Таке застосування cut називають "зеленим відсіканням".

"Зелені відсікання" лише відкидають ті шляхи обчислення, що не приводять до нових рішень.

Бувають і "червоні відсікання", при вилученні яких міняється декларативний зміст програми.

5.1.4 Формальний опис дії відсікання.

Розглянемо пропозицію

Н:-B1, B2,..., Bm, !,..., Bn.

Ця пропозиція активізується, коли деяка ціль G, буде зіставлятися з H.

Тоді G називають метою-батьком.

Якщо B1, B2,..., Bm виконані, а після !, наприклад у Bi, i>m, відбулася невдача і потрібно вибрати

альтернативні варіанти, то для B1, B2,..., Bm такі альтернативи більше не розглядаються і усе виконання

закінчиться невдачею. Крім цього G буде зв'язана з головою H, і інші пропозиції процедури в увагу не

приймаються.

Тобто. відсікання в тілі пропозиції відкидає всі пропозиції , розташовані після цієї пропозиції.

Формальна дія відсікання описується так:

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

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

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

альтернативи на проміжку між метою-батьком і сut закінчуються невдачею.

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

5.2 Застосування відсікання.

Читайте також:

1. Багатофазне сортування
2. Багатофазне сортування
3. Контроль-сортування (дефектація).
4. Медичне сортування та медична евакуація при НС
5. МЕДИЧНЕ СОРТУВАННЯ.
6. Оскiльки ще важливiшим стає швидке реагування, спроможнiсть iнформацiйних систем збирати та iнтегрувати iнформацiю паралельно щодо всiх функцiй бiзнесу є виключно важливою.
7. Порозрядне сортування для списків.
8. Сортування
9. Сортування - це процес, який дозволяє впорядкувати множину подібних даних у порядку зростання або убування.
10. Сортування вибором
11. Сортування вибором
12. Сортування вибором.

Переглядів: 786