Назад | Содержание| Вперёд Часть 2 ПР...

Назад | Содержание| Вперёд

Часть 2

ПРОЛОГ

В ИСКУССТВЕННОМ ИНТЕЛЛЕКТЕ

Рис. 9. 1. Сортировкасписка процедурой быстрсорт.

встав( X, [Y |УпорСпис], [Y | УпорСпис1]):-

больше( X, Y), !,

встав( X, УпорСпис, УпорСпис1).

встав( X, УпорСпис, [X| УпорСпис] ).

Процедуры сортировки пузырек и вставсортпросты, но не эффективны. Из этих двух процедурпроцедура со вставками более эффективна, однакосреднее время, необходимое для сортировки спискадлиной n процедурой вставсорт,возрастает с ростом n пропорционально n². Поэтому для длинных списковзначительно лучше работает алгоритм быстройсортировки, основанный на следующей идее(рис. 9.1):

Для того, чтобы упорядочить непустой список L, необходимо:

(1) Удалить из списка L какой-нибудь элемент Х иразбить оставшуюся часть на два списка,называемые Меньш и Больш,следующим образом: все элементы большие, чем X, принадлежат списку Больш, остальные- списку Меньш.

(2) Отсортировать список Меньш,результат - список УпорМеньш.

(3) Отсортировать список Больш,результат - список УпорБольш.

(4) Получитьрезультирующий упорядоченный список какконкатенацию списков УпорМеньш и [Х | УпорБольш].

Заметим, что если исходный список пуст, торезультатом сортировки также будет пустойсписок. Реализация быстрой сортировки на Прологепоказана на рис. 9.2. Здесь в качестве элемента X, удаляемого из списка, всегда выбираетсяпросто голова этого списка. Разбиение на двасписка запрограммировано как отношение счетырьмя аргументами:

разбиение( X, L,Больш, Меньш).

Временная сложность нашего алгоритма зависитот того, насколько нам повезет при разбиениисортируемого списка. Если списки всегдаразбиваются на два списка примерно равной длины,то процедура сортировки имеет временнуюсложность порядка nlogn, где n -длина исходного списка. Если же, наоборот,разбиение всегда приводит к тому, что один изсписков оказывается значительно больше другого,то сложность будет порядка n². Анализ показывает, что, к счастью, средняяпроизводительность быстрой сортировки ближе клучшему случаю, чем к худшему.

Программу, показанную на рис. 9.2, можноусовершенствовать, если реализовать операциюконкатенации более эффективно. Напомним, чтоконкатенация

быстрсорт( [ ], [ ] ).

быстрсорт( [X |Хвост], УпорСпис) :-

разбиение( X, Хвост, Меньш, Больш),

быстрсорт( Меньш, УпорМеньш),

быстрсорт( Больш, УпорБольш),

конк( УпорМеньш, [X | УпорБольш], УпорСпис).

разбиение( X, [ ], [ ], [ ]).

разбиение( X, [Y |Хвост], [Y | Меньш], Больш ) :-

больше( X, Y), !,

разбиение( X, Хвост, Меньш, Больш).

разбиение( X, [Y |Хвост], Меньш, [Y | Больш] ) :-

разбиение( X, Хвост, Меньш, Больш).

конк( [ ], L, L).

конк( [X | L1], L2, [X | L3] ):-

конк( L1, L2, L3 ).

Рис. 9. 2. Быстраясортировка.

становится тривиальной операцией послеприменения разностного представления списков,введенного в гл. 8. Для того, чтобы использоватьэту идею в нашей процедуре сортировки, нужнопредставить встречающиеся в ней списки в формепар вида A-Z следующим образом:

УпорМеньшимеет вид A1-Z1

УпорБольш имеетвид A2-Z2

Тогда конкатенации списков

УпорМеньш и [Х | УпорБольш]

будет соответствовать конкатенация пар

A1-Z1 и [ Х | A2]-Z2

В результате мы получим

А1-Z2, причем Z1 = [ Х | А2]

Пустой список представляется парой Z-Z.Систематически вводя изменения в программу рис.9.2, мы получим более эффективный способреализации процедуры быстрсорт,показанный на рис. 9.3 под именем

быстрсорт( Спис,УпорСпис) :-

быстрсорт2( Спис, УпорСпис-[ ] ).

быстрсорт2( [ ], Z-Z).

быстрсорт2( [X |Хвост], A1-Z2) :-

разбиение( X, Хвост, Меньш, Больш),

быстрсорт2( Меньш, А1-[Х | A2] ),

быстрсорт2( Больш, A2-Z2).

Рис. 9. 3. Болееэффективная реализация процедуры быстрсорт

с использованием разностногопредставления списков. Отношение

разбиение( Х, Спис, Меньш, Больш)определено, как на рис. 9.2.

быстрсорт2. Здесь, как и раньше,процедура быстрсорт использует обычноепредставление списков, но в действительностисортировку выполняет более эффективнаяпроцедура быстрсорт2, использующаяразностное представление. Эти две процедурысвязаны между собой, соотношением

быстрсорт( L, S) :-

быстрсорт2( L, S-[ ] ).

Упражнения

9. 5. Напишите процедуруслияния двух упорядоченных списков в один третийсписок. Например:

?- слить( [2, 5, 6, 6,8], [1, 3, 5, 9], L).

L = [1, 2, 3, 5, 5, 6, 6, 8, 9]

9. 6. Программы сортировки,показанные на рис. 9.2 и 9.3, отличаются друг отдруга способом представления списков. Первая изних использует обычное представление, в то времякак вторая - разностное представление.Преобразование из одного представления в другоеочевидно и может быть автоматизировано. Введитев программу рис. 9.2 необходимые изменения, чтобыпреобразовать ее в программу рис. 9.3.

9. 7. Наша программа быстрсортв случае, когда исходный список уже упорядоченили почти упорядочен, работает оченьнеэффективно. Проанализируйте причины этогоявления.

9. 8. Существует еще однахорошая идея относительно механизма сортировкисписков, позволяющая избавиться от недостатковпрограммы быстрсорт, а именно: разбитьсписок на два меньших списка, отсортировать их, азатем слить вместе. Итак, для того, чтобыотсортировать список L, необходимо

разбить L на два списка L1 и L2 примерно одинаковой длины;

произвести сортировку списков L1 и L2,получив списки S1 и S2;

слить списки S1 и S2, завершив на этом сортировку списка L.

Реализуйте этот принцип сортировки и сравнитеего эффективность с эффективностью программы быстрсорт.

Посмотреть ответ

Назад | Содержание| Вперёд

Оглавление