2014/2, стр. 107 - 128

ДВУМЕРНИ МАСИВИ: АЛГОРИТМИ ЗА ТЪРСЕНЕ И ЕКСПЕРИМЕНТИ

Резюме: В статията се разглеждат алгоритми за търсене в числени 2D частично наредени масиви, т.е. масиви, чиито елементи са ненамаляващи по редове и колонки. Накратко са разгледани четири известни алгоритъма, единият от които е алгоритъмът за търсене Saddleback. Описан е и един нов алгоритъм, наречен алгоритъм за търсене чрез концентрични подмасиви. Основната идея на алгоритъма е конструирането на редица от подмасиви с намаляващи размери на редовете и колонките, като всеки следващ подмасив на редицата се съдържа в предшестващия го подмасив. По този начин, ако търсеното число се съдържа в първоначалния масив, то числото се съдържа и във всеки подмасив на редицата, последният от които съдържа само един елемент със стойност, равна на търсеното число. Всичките пет алгоритъма са реализирани в средата за програмиране Microsoft Visual C++. Извършени са експерименти, в които са измерени времената за изпълнението им за разнообразни стойности на броя на редовете и колонките в масивите. Част от резултатите от проведените експерименти са дадени в няколко таблици и са илюстрирани със съответни графики. Най-добри времена от функциите, реализиращи съответните алгоритми, са получени от алгоритъма за търсене с концентрични подмасиви.

Ключови думи: search in 2D arrays, 2D partially ordered arrays, Saddleback algorithm, empirical analysis

1. Въведение

1.1. Основна задача

В тази статия се разглеждат алгоритми за търсене в числени двумерни масиви, (2D масиви), с M реда и N колонки, M и N са цели положителни числа. Предполага се, че елементите на масивите са ненамаляващи числени редици по редове и колонки, т.е. ако а е такъв масив, тогава са в сила следните две свойства:

− Наредба по редове: a[i][j] ≤ a[i][j+1], за всяко i = 1, 2, …, M и 1 ≤ j < N.

− Наредба по колонки: a[i][j] ≤ a[i+1][j], за всяко j = 1, 2, …, N и 1 ≤ i < M.

Определение. 2D масив, за елементите на който са в сила горните две свойства, ще наричаме частично нареден масив. Частните случаи на 2D масиви с размерност 1xN и Mx1, т.е. едномерните наредени масиви, също ще наричаме частично наредени масиви. За частично нареден масив приемаме и масива с размери 1x1, т.е. масив от един елемент.

Основна задача [Търсене в частично нареден масив] Нека a да е 2D частично нареден масив, а x число от базовия тип данни на масива. Да се построи алгоритъм, с който се търси елемент от масива със стойност x, т.е. алгоритъм, с който се търсят индекси p и q на масива, 1 ≤ p ≤ M , 1 ≤ q ≤ N, такива че a[p][q] = x или да се констатира, че в масива не съществува елемент със стойност x.

В някакъв смисъл формулираната задача е обобщение на задачата за търсене в нареден едномерен масив, в който случай задачата е перфектно решена с метода „Разделяй и владей“, а съответният алгоритъм е познат като „Двоично търсене“.

1.2. Свойства на 2D частично наредените масиви

Частично наредените 2D масиви притежават редица свойства. По-долу са по-сочени само тези от тях, които са в основата на алгоритмите за търсене, разгледани в тази статия.

Нека а е произволен 2D частично нареден масив, а x е произволно число от базовия тип на масива. В сила са следните свойства:

P1. Ако x е елемент от масива, то a[1][1] ≤ x ≤ a[M][N]. Ще акцентираме две очевидни, но важни следствия, които многократно се използват по-нататък:

− a[1][1] е най-малкото число в масива, а a[M][N] – най-голямото;

− Ако x < a[1][1] или x > a[M][N], тогава x не е елемент на a.

P2. Ако a[M-1][N-1] < x < a[M][N], тогава x може да бъде елемент на масива само ако е в последия ред и/или колонка.

P3. Всяка правоъгълна област от 2D частично нареден масив е също 2D частично нареден масив, който по-нататък ще бъде наричан подмасив.

P4. Елементите на всеки диагонален ред, успореден на „главния диагонал“, са в ненамаляваща последователност. Понятието главен диагонал, когато масивът не е квадратен (M  N), е интуитивно ясно.

Доказателствата следват непосредствено. Ще докажем само свойствo P1.

Доказателство. Ако x е елемент от масива, тогава съществува поне една двойка индекси p и q, 1 ≤ p ≤ M, 1 ≤ q ≤ N, такива, че x = a[p][q]. Можем да запишем следната редица от неравенства:

a[1][1] ≤ a[p][1] ≤ a[p][q] ≤ a[p][N] ≤ a[M][N]

1.3. Литературна справка

Формулираната по-горе задача е математическа, която в по-общ вид е изследвана още през 70-те години (Agarwal&Sharir, 1988; Linial&Saks, 1985), но публикации се срещат и сега (Bird, 2006; Bird, 2010)1. С приложенията си в различни области, като например в компютърната графика и изчислителната геометрия, тази задача става още по-атрактивна. Разработени са разнообразни алгоритми за решението й, а програмни реализации и коментари към тях, срещани в Internet, се публикуват и днес.2,3

Особен интерес се проявява към алгоритъма, наречен Saddleback, известен отпреди 40 години. Ръкописен материал за него се съдържа в архива на E. Dijkstra.1,4 В него той пише “The origin of the algorithm is unnkown; its name has been invented by David Gries”. В свои публикации, книги и лекционни материали5 D. Gries разглежда този алгоритъм и днес алгоритъмът е един от класическите примери, които се представят в университетски курсове по алгоритми и формални методи за доказване на коректността на програми. Вече не е лесно да се посочат разнообразните идеи на модификации на алгоритъма Saddleback. Той е намерил място и в колекцията от „перли по проектиране на функционални алгоритми“ на Richard Bird (2006; 2009).

Някои основни и добре познати идеи за алгоритми за търсене в 2D частично наредени масиви са разгледани накратко в т. 2. Представен е и един нов алгоритъм, описан в т. 3. В т. 4 е описана процедура за генериране на 2D частично наредени масиви, които се използват в т. 5 за експериментите с разгледаните алгоритми.

2. Известни алгоритми за решаване на основната задача

При словесното описание на алгоритмите индексите на масивите започват от 1, а не от 0, както това е при езиците C/C++. Означенията на променливите и параметрите са унифицирани по следния начин:

− а – име на частично нареден 2D масив с размерност MxN, M – брой редове и N – брой колонки;

− x е число, което се търси в 2D масива;

− [a..b] – интервал от индекси в масива а, посочващи поредни номера на редове или колонки , a ≤ b. Например с [r1..r2] е означен интервалът от редове на масива от r1 до r2 включително.

− r, r1, r2, p, p1, p2 – индекси от интервала [1..M], посочващи пореден номер на ред от а;

− c, c1, c2, q, q1, q2 – индекси от интервала [1..N], посочващи пореден номер на колонка от а.

Реализизацията на всички алгоритми е извършена в среда на програмиране Microsoft Visuаl С++ 2010.

2.1. Алгоритъм „Saddleback“

Търсенето на елемент от масива със стойност x в алгоритъма Saddleback започва с елемента a[r][c], който се намира в последния ред (r = М), първа колонка (c = 1). Ако a[r][c] = x, елементът е намерен и търсенето завършва. Ако a[r][c] < x, търсеният елемент не може да бъде в тази колонка и търсенето продължава в следващата колонка (c + 1). В противен случай, т.е. ако a[r][c] > x, търсеният елемент не може да бъде в този ред и се тества елементът от същата колонка, но от предходния ред (r – 1). Кодът на функцията, реализираща този алгоритъм, е даден по-долу:

Лесно се съобразява, че реализацията на алгоритъма Saddleback може да се опише и като се започне от най-горния десен елемент на масива (индекси [1][N]), а придвижването ще се извършва надолу (нарастване на номера на реда) и наляво (намаляване на номера на колонката).

2.2. Последователно-двоично търсене по редове (стълбове)

Понеже редовете (колонките) на частично наредените масиви са наредени едномерни масиви, то за всеки от тях може да се приложи алгоритъмът за двоично търсене. Това означава обединение на последователното търсене с двоичното търсене в една процедура, която накратко е наречена последователно-двоично търсене. Следва описанието на алгоритъма като функция (alg2), в която съществено се изполва функцията bSearchR за двоично търсене в произволен ред r от масива а, r = 1, 2, …, M.

Функцията bSearchR ще се изпълни не повече от M пъти, което означава, че времето за изпълнение на тази функция е constxMxlg(N). Същата идея може да се приложи и по колонки. Една предварителна проверка за стойностите на M и N ще реши кой от двата варианта да бъде използван в конкретния случай – търсене по редове или търсене по колонки.

2.3. Двумерен вариант на двоичното търсене

В този алгоритъм „средният“ елемент ще бъде някъде в „средата“ на масива с индекси [M/2][N/2]. Чрез средния елемент масивът се „разбива“ на четири подмасива, всеки от които е частично нареден масив (свойство P3). Един пример е даден на фиг. 1, в който M = 9, N = 10, M/2 = 4, N/2 = 5. Средният елемент в масива е а[4][5] = 19, а четирите области A, B, C и D са определени с номерата на двойките индекси по редове и колонки, както следва: подмасив A: ([1..4], [1..5]), подмасив B: ([1..4], [6..10]), подмасив C: ([5..9], [1..4]) и подмасив D: ([5..9], [6..10]).

Интересни за разглеждане са следните случаи:

a) Ако a[M/2][N/2] = x, елементът е намерен и търсенето завършва с успех. b) Ако x < a[M/2][N/2], търсеният елементът не може да бъде в подмасив D. (свойство P1) и търсенето трябва да продължи в подмасивите A, B и C.

c) Ако a[M/2][N/2] < x, търсеният елементът не може да бъде в подмасив A (свойство P1) и търсенето следва да продължи в подмасивите B, C и D.

d) Този процес на „разбиване“ на подмасиви продължава до намирането на търсения елемент или до достигане на подмасив, в който единият или и двата му размера са равни на нула.

Специално ще отбележим, че подмасивите B и C присъстват и в двата случая b) и c), което трябва се има предвид при реализацията на алгоритъма (alg3Rec). Параметрите r1, r2, c1и c2 се използват като индекси, с които на всяка стъпка се определят подмасивите A, B, C и D на текущия масив.

bool alg3(int a[][N], int x)

Началните стойности на параметрите r1, r2, c1 и c2, с които функцията alg3Rec се изпълнява, са съответно [r1..r2] = [0..М-1] и [c1..c2] = [0..N-1]. Те определят границите на първоначалния масив.

2.4. Алгоритъм за търсене в средния ред на масива

Вместо да се избира елемент в средата на масива, търсенето в този алгоритъм започва с двоично търсене в средния ред на масива. След това се определя подходящата средна колонка. Ето основните стъпки в алгоритъма:

1. Извършва се търсене в средния ред r = [M/2] на масива. Ако търсеният елемент е намерен, търсенето завършва с успех.

2. Ако търсеният елемент не е в ред r, тогава:

− Ако a[r][1] > x търсенето продължава в подмасив A1, определен от редове [r1, r-1].

− Ако a[r][N] < x търсенето продължава в подмасив A2, определен от редове [r+1, r2].

3. Ако търсеният елемент не е в ред r, но в него има позиция q, такава че:

a[r][q] < x < a[r][N]. В този случай търсенето продължава в два подмасива B и C.

− Масивът B е определен с редове [r1, r-1] и колонки [q+1, c2].

− Масивът C e с редове [r1+1, r2] и колонки [c1, q].

4. За всеки от подмасивите A1, A2, B и C търсенето продължава от т. 1.

По-долу следва кодът на рекурсивната функция с име alg4Rec, реализираща алгоритъма. Параметрите r1, r2, c1и c2 се използват като индекси, с които на всяка стъпка се определят подмасивите A и B на текущия масив.

Началните стойности на параметрите r1, r2, c1и c2, с които функцията alg4Rec се изпълнява, са съответно [r1..r2] = [0..М-1] и [c1..c2] = [0..N-1].

3. Алгоритъм за търсене чрез редица от концентрични подмасиви

Водеща идея в този алгоритъм е конструирането на редица от подмасиви с намаляваща размерност, която има следните две свойства:

− [C1] Всеки подмасив от редицата, с изключение на първоначалния, изцяло се съдържа в предхождащия го. Тази е и причината редицата от подмасиви да бъде наречена редица от концентрични масиви.

− [C2] Ако първоначалният масив съдържа елемент с търсената стойност x, то този елемент се съдържа във всеки подмасив от редицата.

Тъй като размерността на всеки следващ подмасив в редицата е намаляваща, то поне една от размерностите на всеки следващ подмасив от редицата ще е по-малка от съответната размерност на предхождащия го подмасив. Като следствие от това и от свойствата C1 и C2, редицата от подмасиви ще клони към подмасив, съдържащ само един елемент. Стойността на този елемент ще определи крайния резултат от търсенето. Ако стойността му е равна на x, търсенето завършва с успех. В противен случай първоначалният масив не съдържа елемент с търсената стойност.

3.1. Построяване на редицата от концентрични подмасиви

В алгоритъма, представен по-долу, процедурата за двоично търсене се прилага четирикратно за определянето на всеки следващ подмасив от редицата.

1. Началният масив (подмасив) съдържа редовете [r1..r2] = [1..M] и колонките [c1..c2] = [1..N].

2. В интервала от редовете [r1..r2] и колонката c1 се търси ред с номер p1 такъв, че елементът a[p1][c1] да е равен на x или a[p1][c1] да е най-голямото число в колонката c1, което да не е по-голямо от x (фиг. 2).

3. В реда p1 между колонките [c1..c2] се търси колонка q1 такава, че a[p1]

[q1] да е равен на x или a[p1][q1] да е най-голямото число в колонката q1, което не е по-голямо от x. По този начин се определят номерата на реда r2 = p1 и на колонката c1 = q1 на новия подмасив.

4. В интервала от колонките [c1..c2] и в реда r1 се търси колонка с номер q2 такава, че елементът a[r1][q2] да е равен на x или a[r1][q2] да е най-голямото число в реда r1, което не е по-голямо от x.

5. В колонката q2 между редовете [r1..p] се търси ред p2 такъв, че a[p2][q2] да е равен на x или a[p2][q2] да е най-голямото число в колонката q2, което не е по-голямо от x. По този начин се определя номерът на горния ред r1 = p2 и номерът на дясната колонка c2 = q2 на новия подмасив.

От стъпки 2 и 3 на алгоритъма се определя долният ляв елемент на новия подмасив: ред r2 = p1 - 1 и колонка c1 = q1 + 1. От стъпки 4 и 5 се определя горният десен елемент на новия подмасив: ред r1 = p2 + 1 и колонка c2 = q2 - 1.

С описаната процедура от текущия подмасив се отстраняват областите, несъдържащи търсения елемент. Търсенето ще продължи в нов подмасив, в който е възможно да се съдържа търсеният елемент. Фиг. 2 илюстрира опеделянето на новия подмасив. Маркираната област от масива е новият подмасив от редицата.

Ясно е, че конструираният нов масив е подмасив на дадения. Ще докажем, че ако x е елемент на първоначалния масив, то той се съдържа и в подмасива.

Доказателство. Начинът, по който са пресметнати p1, q1 и p2, q2, елеминира търсенето в подмасивите ([r1..r2] [c1..q1]) и ([r1..p2][c1..c2]).

В сила са и следните неравенства:

a[p1][c1] < x < a[p1+1][c1] ≤ a[i][j] за i = p1+1, p1+2, . . ., M; j = 1, 2, . . ., N.

Първите две неравенства следват от избора на p1, а последното – от свойство P1. Аналогично могат да се запишат и неравенствата:

a[r1][q2] < x < a[r1][q2+1] ≤ a[i][j] за i = 1, 2, . . ., M; j = q2+1, q2+2, . . ., N.

С тези две системи от неравенства се елиминират подмасивите, определени с интервалите от индекси ([p1+1..r2][c1..c2]) и ([r1..r2][q2+1..c2]). Всичко това показва, че ако търсеният елемент x е в първоначалния масив, той остава и във всеки следващ подмасив на редицата.

Следва кодът на функцията alg5, реализираща описания алгоритъм. Както се вижда, централна роля в нея играят функциите за двоично търсене по редове bSearchR и по колонки bSearchC. Всяка от тези функции се прилага по два пъти за определянето на координатите на всеки следващ подмасив от редицата. 3.2. Програмен код на алгоритъма bool alg5(int a[][N], int x)

4. Обратна на основната задача

За извършването на експерименти с представените алгоритми е необходимо да се генерират 2D частично наредени масиви със случайни числа. Това налага решаването на още една задача.

4.1. Дефиниция и алгоритъм на задачата

Задача. Дадени са целите положителни числа M, N, p, q, x, y и z, за които са изпълнени следните условия: 1 ≤ p ≤ M, 1 ≤ q ≤ N и y ≤ x ≤ z. Да се генерира 2D масив a с размерност MxN, имащ свойствата:

− Масивът а е частично нареден, a eлементите му са случайни цели числа в интервала [y .. z].

− a[1][1] = y, a[M][N] = z и a[p][q] = x.

Всеки 2D масив може да се разглежда като едномерен, в който редовете (колонките) на двумерния масив се поставят една след друга, т.е. след елементите на първия ред следват елементите на втория и т.н. Пресмятането на позицията (индекса) k на елемент от едномерния масив, съответен на елемент от двумерния масив с индекси [p][q], може да се извърши с линейна функция, която ще зависи от p, q и N. Тук трябва да се има предвид, че индексът на първия елемент в езиците C/C++ е нула. Тогава общият вид на функцията address, с която се пресмята адресът на елемента a[p][q] в едномерното представяне на двумерния масив, ще бъде:

k = address(p, q, N) = Np + q

Като се използват направените по-горе уточнения, решението на задачата може да се формулира така:

1. Дефинира се едномерен масив b с MxN елемента;

2. Генерират се MxN случайни числа в интервала [y..z] като елементи на масива масива b.

3. Масивът b се сортира в нарастващ ред на елементите му.

4. Масивът b се разглежда като едномерно представяне на двумерния масив a по редове.

Определеният по този начин масив a с помощта на едномерния масив b е частично нареден, защото масивът b е сортиран. Това означава, че: b[k1] ≤ b[k2] за k1≤ k2, т.е. 2D масивът a е нареден по редове и по колонки.

Остава нерешен още един въпрос – елементът a[p][q] трябва да e със стойност x. Това лесно се постига, като интервалът от индекси [0 .. MN-1] се раздели на две части [0.. Np + q -1] и [Np + q, MN -1]. За елементите от масива b с индекси от първия интервал ще се генерират случайни числа в интервала [y .. x], а за елементите от втория интервал ще се генерират случайни числа в интервала [x .. z].

4.2. Програмен код за генериране на 2D частично наредени масиви

Генерирането на случайни числа – елементи на частично нареден 2D масив, се извършва с трите функции, чиито дефиниции следват по-долу.

5. Експерименти. Измерване на времето със синтетично генерирани частично наредени 2D масиви

С разработените алгоритми са направени разнообразни експерименти за пресмятане на времето им за изпълнение. Част от тези данни са представени по-долу в таблици и графики. Дадена е и частта от управляващия модул на програмата, с която са извършени експериментите. Основни параметри на експериментите са различните стойности на размерностите M и N на масивите. Те включват и трите случая: M < N, M > N и M = N. За всички тези случаи са извършени два основни вида експерименти, когато търсеното число е елемент на масива и когато търсеното число не е елемент на масива. Времената за изпълнение на всички алгоритми са получени от изпълнението им с едни и същи 2D частично наредени масиви и едни и същи числа x за търсене в тях. Максималният размер на масивите, с които са извършени изпълненията, е 250,000 елемента. За всяка двойка (M, N) са генерирани по 10 масива. За стойност на числото x, което се търси, е използван всеки един от елементите на масива. Това означава, че всеки от алгоритмите е изпълнен общо 10xMxN пъти при търсенето, което е завршвало с успех за всяка двойка (M, N). Същият брой експерименти е извършен и в случаите, при които числото не е елемент на масива.

Графичната илюстрация на времената за изпълнение на алгоритмите за определени стойности на M и N е получена в средата на програмиране MATLAB.6 5.1. Текст на управляващия модул на програмата

Петте алгоритъма са реализирани като функции с еднакви сигнатури. Това позволява да се разглеждат като масив от функции {alg1, alg2, alg3, alg4, alg5}. С това се постига унифицирано обръщение към всички функции с единствен оператор. Той се намира в тялото на най-вътрешния цикъл на управляващия модул.

5.2. Резултати от проведените експерименти

Част от извършените експерименти са обобщени в няколко таблици и графики. В експеримент 1 стойността на M е фиксирана на 250 реда, а броят на колонките се изменя от 100 до 1000 със стъпка 100 (Табл. 1). При експеримент 2 броят на колонките N е фиксиран и е равен на 250, а броят на редовете се променя от 100 до 1000 със стъпка 100 (Табл. 2). Може да се забележи, че и в двата експеримента алгоритмите 1, 4 и 5 имат сходни времена за едни и същи стойности на MxN. Вижда се също, че алгоритмите 2 и 3 дават големи отклонения при експеримент 2 (M > N) спрямо тези от експеримент 1, което е очаквано.

На фиг. 3 графично са илюстрирани времената от експериментите 1 и 2, но само на три от алгоритмите (1, 4 и 5). Времената за изпълнение на всички алгоритми в двата случая се различават, особено тези на Алгоритми 2 и 3 (Табл.1, 2), но съотношенията на времената между всичките алгоритми и в двата случая се запазват.

При експеримент 3 са измерени времената на петте алгоритъма при M = N с начална стойност 100, крайна стойност 500 и стъпка 50 в случая, когато търсеният елемент е елемент на масива (Табл. 3). Същият експеримент е извършен и в случая, когато търсеното число не е елемент на масива. Графично резултатите от двата експеримента са представени на фиг. 4. Поради голямата разлика във времената на Алгоритми 2 и 3 по отношение на останалите е използвана логаритмична скала по оста Oy. В лявата графика е представен случаят, когато търсеното число е елемент на масива, а дясната показва случая, когато числото не е елемент на масива. Въпреки че се забелязва известно нарастване на времената във втория случай, съотношението на времената между отделните алгоритми се запазава.

Интересно е да се разгледат и резултатите от Табл. 4, в която има няколко екстремални случая, като например М = 1, N = 250000. В този случай двумерният масив се изражда в едномерен, състоящ се само от един ред. Аналогичен е и другият случай, при който масивът се изражда само в една колонка, M = 250000 и N = 1.

Във всички разгледани случаи Алгоритъм 5 се е изпълнил за най-кратко време. Изпълненията му не са повлияни от това, дали M < N, M > N или M =N. Това му поведение се запазва и в случаите, когато двумерният масив е с големи различия в стойностите на M и N, включително и при израждането на двумерния масив до едномерен. От Табл. 4 се вижда, че времената на Алгоритъм 1 са твърде високи при големи разлики в стойностите на M и N. Интересни, но не изненадващи, са резулатите на Алгоритъм 2. При M = 1 и N = 250000 времето му за изпълнение е най-добро от всички алгоритми за всички случаи на MxN = 250000. Направените по-горе коментари към времевите характеристики на разгледаните алгоритми не са математически обосновани. Те са основават на данните, по-лучени експериментално, но резултатите от експериментите са достатъчно ясни, за да подсказват идеи за формулиране на хипотези, валидността на които следва да бъде доказана.

6. Проект в развитие

Като близки до основната задача, разгледана в статията, могат да се формулират редица други задачи за частично наредени масиви. Списък от шест такива задачи е даден по-долу. За всяка от тях се иска проектиране и разработка на съответен алгоритъм. Времевата характеристика на алгоритмите не е без значение. Реализирането на алгоритмите на определен език за програмиране и извършването на съответни експерименти ще внесе допълнителна яснота относно практическата им стойност.

Задача 1. Свойство P2 дава идея за алгоритм, който започва с разглеждането на най-големия елемент на масива, a[M][N]. Ето основните случаи, които трябва да се разглеждат в този алгоритъм:

a) Ако a[M][N] = x, елементът е намерен и търсенето завършва с успех.

b) Ако x > a[M][N], масивът не съдържа елемент със стойност x и търсенето завършва с неуспех (съгласно P1).

c) Ако a[M-1][N-1] = x, елементът е намерен и търсенето завършва с успех. d) Ако a[M-1][N-1] < x, търсенето има смисъл да продължи само в M-тия ред и N-та колонка (съглано P2).

e) Ако x < a[M-1][N-1], търсенето продължава в подмасива на първоначалния масив, в който са отстранени последният ред и последната колонка. Новият подмасив е 2D частично нареден (съгласно P3).

Да се постри алгоритъм по описаната идея и да се извършат екперименти, подобни на описаните.

Задача 2. Тази задача е обобщение на задача 1, в която се прилага и свойство P4. На фиг. 5 и 6 са дадени два случая на правоъгълни масиви (M ¹ N), в които с права линия са посочени елементите от диагонала, започващ от елемента с индекси [M][N]. Съгласно свойство P4 всички елементи от диагонала са наредени в ненамаляващ ред. В случай че масивът е квадратен, посочените диагонали представляват главния диагонал в съответния масив.

Ето основните случаи, които трябва да се разгледат:

a) Ако a[M][N] = x, елементът е намерен и търсенето завършва с успех.

b) Ако x > a[M][N], масивът не съдържа елемент със стойност x и търсенето завършва с неуспех (съгласно P1).

c) Ако случаите a) и b) не са в сила, тогава се прилага двоично търсене в диагоналния ред за намиране на елемент със стойност x. Ако такъв елемент се намери, търсенето завършва с успех. Ако няма такъв елемент, тогава се търси елемент, чиято стойност е най-голямата в диагонала, но не по-голяма от x. На двете фигури това е защрихованият елемент. Ако индексите му са [p][q], тогава търсенето продължава в подмасивите [p+1..M][1..N] и [1..p] [q+1..N], за които се прилaга процедурата от по-горе.

d) Елементът с индекси [1][1] и защрихованият елемент определят подмасив, в който със сигурност няма елемент със стойност x.

Да се постри алгоритъм по описаната идея и да се извършат екперименти, подобни на описаните в т. 5.

Задача 3. Да се построи алгоритъм, с който се намира най-малкото число в 2D частично нареден масив, което не е елемент на масива.

Задача 4. Да се построи алгоритъм за намиране на всичките елементи на 2D частично нареден масив с дадена стойност.

Задача 5. Да се построи алгоритъм, с който се пресмята броят на елементите в 2D частично нареден масив, които са в даден инервал.

Задача 6. Да се построи алгоритъм за търсене в 3D частично нареден масив.

БЕЛЕЖКИ

1. Dijkstra E. (1985) The Saddleback Search. Note EWD-934. Available at http:// www.cs.utexas.edu/users/EWD/index09xx.html

2. Gidney C. Searching a Sorted Matrix Faster. http://twistedoakstudios.com/blog/ Post5365_searching-a-sorted-matrix-faster

3. Searching a 2D Sorted Matrix (Parts I, II, and III)

http://leetcode.com/2010/10/searching-2d-sorted-matrix.html

4. E. Dijkstra е удостоен през 1972 г. с Turing Award (присъждана от ACM) за фундаментален принос в областта на езиците за програмиране.

5. Gries D. Saddleback Search.

http://www.cs.geneseo.edu/~baldwin/math-thinking/saddleback.html

http://www.cs.cornell.edu/Courses/cs6110/2012sp/notes/griesLectureOnAlgorithms. pdf

6. MATLAB. Latest Release R2013b. http://www.mathworks.com/

ЛИТЕРАТУРА

Agarwal, P. & Sharir, M. (1998). Efficient Algorithms for Geometric Optimization. ACM Computing Surveys, vol. 30, No. 4, 412 – 458

Bird, R. (2006). Improving saddleback search: a lesson in algorithm design. Mathematics of Program Construction. Springer, LNCS 4014, 82 – 89.

Bird R. (2010). Improving on saddleback search. Pearls of Functional Algorithm Design. Cambridge University Press, 12 – 20.

Linial, N & Saks, M. (1985). Searching ordered structures. Journal of Algorithms. Vol 6, Issue 1, 86 – 103. are implemented in the programming environment of Microsoft Visual C++. Additional experiments were conducted to find out the respective execution time for each of these five algorithms by selecting a variety of values for the number of rows and columns. Some of the obtained results are presented in tables, included in the text of the paper, and are also accompanied by the corresponding charts. The best values for the execution time are established for the search algorithm through concentric subarrays.