Алгоритмы сортировки, поиска длиннейшего пути во взвешенном графе и поиска покрытия, близкого к кратчайшему (стр. 2 из 4)
2.5 Контрольные примеры решения задачи с помощью алгоритма сортировки простыми включениями
Пример сортировки массива, отсортированного случайным образом.
Пусть задан такой массив из восьми элементов: (32,43,2,30,82,8,5,52) (см. Таб. 1).
| Начальные ключи | 32 | 43 | 02 | 30 | 82 | 08 | 05 | 52 |
| i = 2 | 32 | 43 | 02 | 30 | 82 | 08 | 05 | 52 |
| i = 3 | 02 | 32 | 43 | 30 | 82 | 08 | 05 | 52 |
| i = 4 | 02 | 30 | 32 | 43 | 82 | 08 | 05 | 52 |
| i = 5 | 02 | 30 | 32 | 43 | 82 | 08 | 05 | 52 |
| i = 6 | 02 | 08 | 30 | 32 | 43 | 82 | 05 | 52 |
| i = 7 | 02 | 05 | 08 | 30 | 32 | 43 | 82 | 52 |
| i = 8 | 02 | 05 | 08 | 30 | 32 | 43 | 52 | 82 |
Пошаговое решение:
Шаг 1:
1) i=2;
2) x=43; a[0]=43; j=1;
3) x > a[j]=32;
3.2) a[2]= 43;
4) i=3; i ≤ n=8 → п. 2;
Шаг 2:
2)x=2; a[0]=2; j=2;
3) x < a[j]=43;
3.1) a[3]=43; j=1; → п. 3;
3) x < a[j]=32;
3.1) a[2]=32; j=0; → п. 3;
3) x = a[j];
3.2) a[1]=2;
4) i=4; i<n → п. 2;
Шаг 3:
2) x=30; a[0]=30; j=3;
3) x < a[j]=43;
3.1) a[4]=43; j=2; → п. 3;
3) x < a[j]=32;
3.1) a[3]=32; j=1; → п. 3;
3) x > a[1]=2
3.2) a[2]=30;
4) i=5; i<n → п. 2;
Шаг 4:
2) x=82; a[0]=82; j=4;
3) x > a[j];
3.2) a[5] = 82;
4) i=6; i<n → п. 2;
Шаг 5:
2) x=8; a[0]=8; j=5;
3) x < a[j]=82;
3.1) a[6]=82; j=4; → п. 3;
3) x < a[j]=43;
3.1) a[5]=43; j=3; → п. 3;
3) x < a[j]=32;
3.1) a[4]=32; j=2; → п. 3;
3) x < a[j]=30;
3.1) a[3]=30; j=1; → п. 3;
3) x > a[j]=2;
3.2) a[2]=8;
4) i=7; i<n → п. 2;
Шаг 6:
2) x=5; a[0]=5; j=6;
3) x < a[j]=82;
3.1) a[7]=82; j=5; → п. 3;
3) x < a[j];
3.1) a[6]=43; j=4; → п. 3;
3) x < a[j]=32;
3.1) a[5]=32; j=3; → п. 3;
3) x < a[j]=30;
3.1) a[4]=30; j=2; → п. 3;
3) x < a[j]=8;
3.1) a[3]=8; j=1; → п. 3;
3) x > a[j]=2;
3.2) a[2]=5;
4) i=8; i≤n → п. 2;
Шаг 7:
2) x=52; a[0]=52; j=7;
3) x < a[j]=82;
3.1) a[8]=82; j=6; → п. 3;
3) x > a[j]=43;
3.2) a[7]=52;
4) i=9; i>n→ конец алгоритма.
Таким образом, имеем 21 пересылку элементов и 20 сравнений.
Пример сортировки уже отсортированного массива.
Пусть задан такой массив из восьми элементов: (2,5,8,30,32,43,52,82).
Пошаговое решение:
Шаг 1:
1) i=2;
2) x=5; a[0]=2; j=1;
3) x > a[j]=2;
3.2) a[2]=5;
4) i=3; i<n → п. 3;
Шаг 2:
2) x=8; a[0]=8; j=2;
3) x > a[j]=5;
3.2) a[3]=8;
4) i=4; i<n → п. 3;
Шаг 3:
2) x=30; a[0]=30; j=3;
3) x > a[j]=8;
3.2) a[4]=30;
4) i=5; i<n → п. 3;
Шаг 4:
2) x=32; a[0]=32; j=4;
3) x > a[j]=30;
3.2) a[5]=32;
4) i=6; i<n → п. 3;
Шаг 5:
2) x=43; a[0]=43; j=5;
3) x > a[j]=32;
3.2) a[6]=43;
4) i=7; i<n → п. 3;
Шаг 6:
2) x=52; a[0]=52; j=6;
3) x > a[j]=43;
3.2) a[7]=52;
4) i=8; i≤n → п. 3;
Шаг 7
2) x=82; a[0]=82; j=7;
3) x > a[j]=52;
3.2) a[8]=82;
4) i=9; i>n →конецалгоритма.
Таким образом получили 7 пересылок и 7 сравнений.
Пример сортировки массива, отсортированного в обратном порядке.
Пусть задан такой массив из восьми элементов: (82,52,43,32,30,8,5,2).
Пошаговое решение:
Шаг 1:
1) i=2;
2) x=52; a[0]=52; j=1;
3) x< a[j]=52;
3.1) a[2]=82; j=0; → п. 3;
3) x=a[j];
3.2) a[1]=52;
4) i=3; i<n → п. 2;
Шаг 2:
2) x=43; a[0]=43; j=2;
3) x < a[j]=82;
3.1) a[3]=82; j=1; → п. 3;
3) x < a[j]=52;
3.1) a[2]=52; j=0; → п. 3;
3) x = a[j];
3.2) a[1]=43;
4) i=4; i<n → п. 2;
Шаг 3:
2) x=32; a[0]=32; j=3;
3) x < a[j]=82;
3.1) a[4]=82; j=2; → п. 3;
3) x < a[j]=52;
3.1) a[3]=52; j=1; → п. 3;
3) x < a[j]=43;
3.1) a[2]=43; j=0; → п. 3;
3) x=a[j];
3.2) a[1]=32;
4) i=5; i<n → п. 2;
Шаг 4:
2) x=30; a[0]=30; j=4;
3) x < a[j]=82;
3.1) a[5]=82; j=3; → п. 3;
3) x < a[j]=52;
3.1) a[4]=52; j=2; → п. 3;
3) x < a[j]=43;
3.1) a[3]=43; j=1; → п. 3;
3) x < a[j]=32;
3.1) a[2]=32; j=0; → п. 3;
3) x=a[j];
3.2) a[1]=30;
4) i=6; i<n → п. 2;
Шаг 5:
2) x=8; a[0]=8; j=5;
3) x < a[j]=82;
3.1) a[6]=82; j=4; → п. 3;
3) x < a[j]=52;
3.1) a[5]=52; j=3; → п. 3;
3) x < a[j]=43;
3.1) a[4]=43; j=2; → п. 3;
3) x < a[j]=32;
3.1) a[3]=32; j=1; → п. 3;
3) x < a[j]=30;
3.1) a[2]=30; j=0; → п. 3;
3) x=a[j];
3.2) a[1]=8;
4) i=7; i<n → п. 2;
Шаг 6:
2) x=5; a[0]=5; j=6;
3) x < a[j]=82;
3.1) a[7]=82; j=5; → п. 3;
3) x < a[j]=52;
3.1) a[6]=52; j=4; → п. 3;
3) x < a[j]=43;
3.1) a[5]=43; j=3; → п. 3;
3) x < a[j]=32;
3.1) a[4]=32; j=2; → п. 3;
3) x < a[j]=30;
3.1) a[3]=30; j=1; → п. 3;
3) x < a[j]=8;
3.1) a[2]=8; j=0; → п. 3;
3) x=a[j];
3.2) a[1]=5;
4) i=8; i<n → п. 2;
Шаг 7:
2) x=2; a[0]=2; j=7;
3) x < a[j]=82;
3.1) a[8]=82; j=6; → п. 3;
3) x < a[j]=52;
3.1) a[7]=52; j=5; → п. 3;
3) x < a[j]=43;
3.1) a[6]=43; j=4; → п. 3;
3) x < a[j]=32;
3.1) a[5]=32; j=3; → п. 3;
3) x < a[j]=30;
3.1) a[4]=30; j=2; → п. 3;
3) x < a[j]=8;
3.1) a[3]=8; j=1; → п. 3;
3) x < a[j]=5;
3.1) a[2]=5; j=0; → п. 3;
3) x=a[j];
3.2) a[1]=2;
4) i=9; i>n → конецалгоритма.
Таким образом, имеем 35 сравнений и 35 пересылок.
3. Алгоритм покрытия по методу «Построение одного кратчайшего покрытия»
3.1 Математическое описание задачи и методов её решения
Пусть
-опорное множество. Имеется множествоподмножеств
множества B ( 
). Каждому подмножеству 
сопоставлено число 
, называемой ценой. Множество 
называется решением задачи о покрытии, или просто покрытием, если выполняется условие 
, при этом цена 
. Термин «покрытие» означает, что совокупность множеств 
содержит все элементы множества В, т.е. «покрывает» множество BБезизбыточным называется покрытие, если при удалении из него хотя бы одного элемента оно перестает быть покрытием. Иначе – покрытие избыточно.
Покрытие Р называется минимальным, если его цене
- наименьшая среди всех покрытий данной задачи.Покрытие Р называется кратчайшим, если l– наименьшее среди всех покрытий данной задачи.
Удобным и наглядным представлением исходных данных и их преобразований в задаче о покрытии является таблица покрытий. Таблица покрытий – это матрица Т отношения принадлежности элементов множеств
опорному множеству В. Столбцы матрицы сопоставлены элементам множества В, строки – элементам множестваА:
Нули в матрице Tне проставляются.
Имеются следующие варианты формулировки задачи о покрытии:
1. Требуется найти все покрытия. Для решения задачи необходимо выполнить полный перебор всех подмножеств множества А.
2. Требуется найти только безубыточные покрытия. Не существует простого и эффективного алгоритма, не требующего построения всех избыточных покрытий: хорошо, если уменьшается их количество. (Используется граничный перебор либо разложение по столбцу в ТП).
Требуется найти одно безизбыточное покрытие. Решение задачи основано на сокращении таблицы.
Задачи о покрытии могут быть решены точно (при небольшой размерности) либо приближенно (см. [2]).
Для нахождения точного решения используются такие алгоритмы.
1) Алгоритм полного перебора. (Основан на методе упорядочения перебора подмножеств множества А).
2) Алгоритм граничного перебора по вогнутому множеству. (Основан на одноименном методе сокращения перебора).
3) Алгоритм разложения по столбцу таблицы покрытия. Основан на методе сокращения перебора, который состоит в рассмотрении только тех строк таблицы покрытия, в которых имеется «1» в выбранном для разложения столбце.
4) Алгоритм сокращения таблицы покрытия. Основан на методе построения циклического остатка таблицы покрытия, для которого далее покрытие строится методами граничного перебора либо разложения по столбцу.
Приближенное решение задачи о покрытии основано на следующем соображении. Если даже сокращенный перебор приводит к очень трудоемкому процессу решения, то для получения ответа приходится отказываться от гарантий построения оптимального решения (минимального либо кратчайшего); однако целесообразно получить не самый худший результат – хотя бы безызбыточное покрытие, удовлетворяющее необходимому условию. При этом в ущерб качеству можно значительно упростить процесс решения.
Для случая построения одного кратчайшего покрытия используется алгоритм построения циклического остатка таблицы покрытий и множества ядерных строк.
3.2 Словесное описание алгоритма и его работы
0) Считаем исходную таблицу покрытий текущей, а множество ядерных строк – пустым.
1) Находим ядерные строки, запоминаем множество ядерных строк. Текущую таблицу покрытий сокращаем, вычеркивая ядерные строки и все столбцы, покрытые ими.
2) Вычеркиваем антиядерные строки.
3) Вычеркиваем поглощающие столбцы.
4) Вычеркиваем поглощаемые строки.
5) Если в результате выполнения пунктов с 1 по 4 текущая таблица покрытий изменилась, снова выполняем пункт 1, иначе преобразование заканчиваем.
Поэтому алгоритм работы следующий:
1) ввод числа строк и столбцов таблицы покрытия;
2) ввод таблицы покрытия;
3) поиск ядерных строк. Если их нет, то п. 4. Иначе, запоминаем эти ядерные строки. Ищем столбцы, покрытые ядерными строками. Вычеркиваем все ядерные строки и столбцы, покрытые ими.
4) вычеркивание антиядерных строк. Переход в п. 5.
6) вычеркивание поглощающих столбцов.
7) вычеркивание поглощаемых строк.
8) если в результате преобразований таблица покрытий изменилась, выполняем пункт 3. Иначе – вывод множества покрытия, конец алгоритма.
3.3 Выбор структур данных
Из анализа задачи и ее данных видно, что алгоритм должен работать с таблицей покрытия и с некоторыми переменными, которые представлены ниже (все переменные целого типа):