Login lub e-mail Hasło   

Algorytmy wyszukujące - wyszukiwanie interpolacyjne

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/al(...)ex.html
Wyszukiwanie interpolacyjne jest ulepszeniem przedstawionego w poprzednim rozdziale algorytmu wyszukiwania binarnego . Nadaje się ono dla zbiorów uporządkowanych o lini...
Wyświetlenia: 7.709 Zamieszczono 03/11/2006

Wyszukiwanie interpolacyjne jest ulepszeniem przedstawionego w poprzednim rozdziale algorytmu wyszukiwania binarnego. Nadaje się ono dla zbiorów uporządkowanych o liniowym rozkładzie elementów. W algorytmie wyszukiwania binarnego partycję zbioru dzieliliśmy zawsze w połowie i tam poszukiwaliśmy danego elementu. Tymczasem możemy skorzystać z własności zbiorów uporządkowanych liniowo i wyliczyć prawdopodobną pozycję elementu wg wzoru:

   d[ ]  - przeszukiwany zbiór
isr = ip +    (w - d[ip]) (ik - ip)   
d[ik] - d[ip]
  
w  - poszukiwana wartość
ip  - indeks pierwszego elementu partycji
ik  - indeks ostatniego elementu partycji
isr  - wyznaczona, przypuszczalna pozycja   

We wzorze stosujemy dzielenie całkowitoliczbowe (pozycja nie może przecież być ułamkowa !).

Powyższy wzór wyprowadzamy z prostej proporcji. Jeśli zbiór posiada liniowy rozkład elementów, to odległość wartości poszukiwanej w od d[ip] jest w przybliżeniu proporcjonalna do liczby elementów pomiędzy ip a isr:

ip ... isr   ...   ...   ...   ik
                           
                           
d[ip] ... w   ...   ...   ...   d[ik]

Skoro tak, to zachodzi przybliżona proporcja:

isr - ip    w - d[ip] , mnożymy obustronnie przez ik - ip
ik - ip d[ik] - d[ip]
isr - ip   (w - d[ip]) (ik - ip) , dodajemy obustronnie ip
d[ik] - d[ip]
isrip +    (w - d[ip]) (ik - ip)   , zaokrąglamy do wartości całkowitej i otrzymujemy wzór końcowy
d[ik] - d[ip]

Aby zrozumieć zaletę tego sposobu wyznaczania pozycji, przyjrzyjmy się poniższemu przykładowi, gdzie wyliczyliśmy pozycję wg wzoru z poprzedniego rozdziału oraz wg wzoru podanego powyżej. Poszukiwany element zaznaczono kolorem czerwonym:

nr pozycji 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
elementy 10 11 13 13 15 16 18 19 20 22 22 23 25 27 27 28 29 30 32
binarnie isr =                   X                  
interpolacyjnie isr =         X                            

Binarne wyznaczenie pozycji:

isr =     ip + i    =    1 + 19    =    20    = 10
 2  2 2

Interpolacyjne wyznaczenie pozycji:

isr = ip +    (w - d[ip]) (ik - ip)     = 1 +   (15 - 10) (19 - 1)    = 1 +   5 18    = 1 +   90   = 1 + 4 = 5
d[ik] - d[ip] 32 - 10 22 22

Metoda interpolacyjna wyznacza pozycję zwykle dużo bliżej poszukiwanego elementu niż metoda binarna (w przykładzie trafiamy za pierwszym razem). Zauważ, iż w metodzie binarnej nie korzystamy zupełnie z wartości elementów na krańcach dzielonej partycji, czyli działamy niejako na ślepo. Natomiast metoda interpolacyjna wyznacza położenie w zależności od wartości elementów zbioru oraz wartości poszukiwanego elementu. Działa zatem celowo dostosowując się do zastanych w zbiorze warunków. Stąd jej dużo większa efektywność.

Po wyznaczeniu położenia isr pozostała część algorytmu jest bardzo podobna do wyszukiwania binarnego.

Wyszukiwanie interpolacyjne posiada klasę czasowej złożoności obliczeniowej równą O(log log n), zatem wyszukuje znacząco szybciej w zbiorach o liniowym rozkładzie elementów niż wyszukiwanie binarne o klasie O(log n).

Dane wejściowe

n - ilość elementów w przeszukiwanym zbiorze.  n N
d[ ] - posortowany rosnąco zbiór danych. Indeksy elementów rozpoczynają się od 1. Dodatkowo żądamy, aby zbiór posiadał liniowy rozkład elementów.
w - wartość poszukiwanego elementu. Typ elementu taki sam jak typ elementów zbioru.

Dane wyjściowe

p - pozycja elementu w zbiorze, p C,   1 p n - element znaleziony,  p = 0 - element nie znaleziony

Zmienne pomocnicze

ip - zawiera indeks pierwszego elementu w partycji. ip C
ik - zawiera indeks ostatniego elementu w partycji, ik C
isr - zawiera indeks środkowego elementu, isr C
krok 1: ip 1;  ik n;  p 0
krok 2: Dopóki d[ip] w d[ik]: wykonuj kroki 3...5
krok 3:
   isr = ip +    (w - d[ip]) (ik - ip)   
d[ik] - d[ip]
krok 4:     Jeśli w = d[isr], to p isr i zakończ algorytm
krok 5:     Jeśli w > d[isr], to ip isr + 1.  Inaczej ik isr - 1
krok 6: Zakończ algorytm

Algorytm wyszukiwania interpolacyjnego jest bardzo podobny do algorytmu wyszukiwania binarnego. Różnice zaznaczyliśmy szarym kolorem symboli blokowych.

Inny jest warunek kontynuacji pętli wyszukującej - wykonuje się ona dotąd, dopóki poszukiwana wartość wpada w zakres partycji od d[ip] do d[ik].

Druga różnica występuje przy wyznaczaniu pozycji isr. W wyszukiwaniu binarnym pozycja ta znajdowała się w środku partycji zbioru. W wyszukiwaniu interpolacyjnym staramy się ustalić położenie poszukiwanego elementu na podstawie jego wartości oraz wartości krańców partycji. Zakładamy oczywiście, iż elementy są w miarę równomiernie rozłożone w obrębie partycji.

Po wyznaczeniu pozycji isr reszta algorytmu jest identyczna jak przy wyszukiwaniu binarnym - sprawdzamy, czy poszukiwany element znajduje się na wyliczonej pozycji. Jeśli tak, zwracamy w zmiennej p tę pozycję i kończymy algorytm. W przeciwnym razie za nową partycję wyznaczamy lewą lub prawą część partycji względem isr w zależności od relacji poszukiwanego elementu z elementem zbioru leżącym na pozycji isr i kontynuujemy pętlę warunkową.

Jeśli pętla warunkowa zakończy się w sposób naturalny, to poszukiwanego elementu w zbiorze nie ma. W takim przypadku pozycja p ma wartość 0 i tę wartość zwracamy jako wynik negatywny przy zakończeniu algorytmu.


   
   
   

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

 
       

Program generuje 100 pseudolosowych liczb z zakresu od 0 do 99. Następnie losowana jest wartość od 0 do 99 i poszukiwana w zbiorze za pomocą wyszukiwania interpolacyjnego. Znaleziony element jest odpowiednio oznaczany. Dodatkowo program zlicza i wypisuje ilość wykonań pętli warunkowej w algorytmie.

Efekt uruchomienia programu
Wyszukiwanie interpolacyjne
---------------------------
(C)2006 mgr Jerzy Wałaszek

0 1 2 2 3 5 6 8 8 9 10 11 11 13 14 15 15 15 15 16
20 21 25 25 25 26 26 26 28 29 29 30 30 31 31 32 33 33 33 34
35 35 35 38 40 41 42 42 (48) 49 49 49 50 52 53 54 55 56 58 58
58 60 61 63 64 65 65 65 65 66 67 68 68 68 69 71 74 74 78 78
80 81 81 81 81 81 82 83 84 85 85 86 86 89 92 92 96 98 98 99

Ilość prób = 1

Element w = 48 jest na pozycji nr 49

KONIEC. Naciśnij dowolny klawisz...

// Wyszukiwanie interpolacyjne
//-----------------------------
// (C)2006 mgr Jerzy Wałaszek
// I LO w Tarnowie
//----------------------------

program intersearch;

{$APPTYPE CONSOLE}

const

N = 100; // Liczba elementów w zbiorze
M = 99; // Maksymalna wartość elementu

var
d : array[1..N] of integer;
w,i,ip,ik,isr,p,l : integer;

begin
writeln('Wyszukiwanie interpolacyjne');
writeln('---------------------------');
writeln('(C)2006 mgr Jerzy Walaszek');
writeln;

// Generujemy zbiór pseudolosowy

randomize;
for i := 1 to N do d[i] := random(M + 1);

// Zbiór sortujemy rosnąco

for i := N - 1 downto 1 do
begin

w := d[i]; ip := i + 1;
while (ip <= N) and (w > d[ip]) do
begin

d[ip - 1] := d[ip]; inc(ip);
end;
d[ip - 1] := w;
end;

// Generujemy poszukiwany element

w := random(M + 1);

// Szukamy elementu w

ip := 1; ik := N; p := 0; l := 0;
while (d[ip] <= w) and (w <= d[ik]) do
begin

isr := ip + (w - d[ip]) * (ik - ip) div (d[ik] - d[ip]);
inc(l);
if w = d[isr] then
begin

p := isr; break;
end
else if
w > d[isr] then
ip := isr + 1
else
ik := isr - 1;
end;

// Prezentujemy wyniki

for i := 1 to N do
if
i = p then write('(',d[i]:2,')') else write(d[i]:3,' ');
writeln;
writeln('Ilosc prob = ',l);
writeln;
write('Element w = ',w);
if p > 0 then
writeln(' jest na pozycji nr ',p)
else
writeln(' w zbiorze nie wystepuje.');
writeln;

// Gotowe

writeln('Nacisnij klawisz Enter...');
readln;
end.
// Wyszukiwanie interpolacyjne
//-----------------------------
// (C)2006 mgr Jerzy Wałaszek
// I LO w Tarnowie
//----------------------------

#include <iostream>
#include <iomanip>

using namespace std;

const int N = 100; // Liczba elementów w zbiorze
const int M = 99; // Maksymalna wartość elementu

int main(void)
{
int d[N + 1],w,i,ip,ik,isr,p,l;

cout << "Wyszukiwanie interpolacyjne\n"
"---------------------------\n"
"(C)2006 mgr Jerzy Walaszek\n\n"
;

// Generujemy zbiór pseudolosowy

srand((unsigned)time(NULL));
for(i = 1;i <= N; i++) d[i] = rand() % (M + 1);

// Zbiór sortujemy rosnąco

for(i = N - 1; i >= 1; i--)
{
w = d[i]; ip = i + 1;
while((ip <= N) && (w > d[ip]))
{
d[ip - 1] = d[ip]; ip++;
}
d[ip - 1] = w;
}

// Generujemy poszukiwany element

w = rand() % (M + 1);

// Szukamy elementu w

ip = 1; ik = N; p = l = 0;
while((d[ip] <= w) && (w <= d[ik]))
{
isr = ip + (w - d[ip]) * (ik - ip) / (d[ik] - d[ip]);
l++;
if(w == d[isr])
{
p = isr; break;
}
else if(w > d[isr]) ip = isr + 1; else ik = isr - 1;
}

// Prezentujemy wyniki

for(i = 1; i <= N; i++)
if(i == p)
cout << "(" << setw(2) << d[i] << ")";
else
cout << setw(3) << d[i] << " ";
cout << "\nIlosc prob = " << l << "\n\nElement w = " << w;
if(p)
cout << " jest na pozycji nr " << p << endl;
else
cout << " w zbiorze nie wystepuje.\n";
cout << endl;

// Gotowe

system("pause"); return 0;
}
' Wyszukiwanie interpolacyjne
'-----------------------------
' (C)2006 mgr Jerzy Wałaszek
' I LO w Tarnowie
'----------------------------

Module Module1

Sub Main()
Const N = 100 ' Liczba elementów w zbiorze
Const M = 99 ' Maksymalna wartość elementu

class="i">Dim d(N), w, i, ip, ik, isr, p, l As Integer

Console.WriteLine("Wyszukiwanie interpolacyjne")
Console.WriteLine("---------------------------")
Console.WriteLine("(C)2006 mgr Jerzy Wałaszek")
Console.WriteLine()

' Generujemy zbiór pseudolosowy

Randomize()
For i = 1 To N : d(i) = Int(Rnd(1) * (M + 1)) : Next

' Zbiór sortujemy rosnąco

For i = N - 1 To 1 Step -1
w = d(i) : ip = i + 1
While (ip <= N) AndAlso (w > d(ip))
d(ip - 1) = d(ip) : ip += 1
End While
d(ip - 1) = w
Next

' Generujemy poszukiwany element

w = Int(Rnd(1) * (M + 1))

' Szukamy elementu w

ip = 1 : ik = N : p = 0 : l = 0
While (d(ip) <= w) AndAlso (w <= d(ik))
isr = ip + (w - d(ip)) * (ik - ip) \ (d(ik) - d(ip))
l += 1
If w = d(isr) Then
p = isr : Exit While
ElseIf w > d(isr) Then
ip = isr + 1
Else
ik = isr - 1
End If
End While

' Prezentujemy wyniki

For i = 1 To N
If i = p Then
Console.Write("({0,2})", d(i))
Else
Console.Write(" {0,2} ", d(i))
End If
Next

Console.WriteLine()
Console.WriteLine("Ilość prób = {0}", l)
Console.WriteLine()
Console.Write("Element w = {0}", w)
If p > 0 Then
Console.WriteLine(" jest na pozycji nr {0}", p)
Else
Console.WriteLine(" w zbiorze nie występuje.")
End If

' Gotowe

Console.WriteLine()
Console.WriteLine("KONIEC. Naciśnij dowolny klawisz...")
Console.ReadLine()

End Sub

End Module
# -*- coding: cp1250 -*-
# Wyszukiwanie interpolacyjne
#-----------------------------
# (C)2006 mgr Jerzy Wałaszek
# I LO w Tarnowie
#----------------------------

import random

N = 100 # Liczba elementów w zbiorze
M = 99 # Maksymalna wartość elementu

d = []

print "Wyszukiwanie interpolacyjne"
print "---------------------------"
print "(C)2006 mgr Jerzy Walaszek"
print

# Generujemy zbiór pseudolosowy

for i in range(N): d.append(random.randint(0, M))

# Zbiór sortujemy rosnąco

d.sort()

# Generujemy poszukiwany element

w = random.randint(0, M)

# Szukamy elementu w

ip, ik, p, l = 0, N - 1, -1, 0
while (d[ip] <= w) and (w <= d[ik]):
isr = ip + (w - d[ip]) * (ik - ip) // (d[ik] - d[ip])
l += 1
if w == d[isr]:
p = isr
break
elif w > d[isr]:
ip = isr + 1
else:
ik = isr - 1

# Prezentujemy wyniki

for i in range(N):
if i == p:
print "(%2d)" % d[i],
else:
print " %2d " % d[i],
print
print
print
"Ilosc prob =", l
print
print "Element w =", w,
if p >= 0:
print "jest na pozycji nr", p + 1
else:
print "w zbiorze nie wystepuje."
print

# Gotowe

raw_input("Nacisnij klawisz Enter...")
<html>
<head>
</head>
<body>
<div align=
"center">
<form style="BORDER-RIGHT: #ff9933 1px outset; PADDING-RIGHT: 4px;
BORDER-TOP: #ff9933 1px outset; PADDING-LEFT: 4px;
PADDING-BOTTOM: 1px; BORDER-LEFT: #ff9933 1px outset;
PADDING-TOP: 1px; BORDER-BOTTOM: #ff9933 1px outset;
BACKGROUND-COLOR: #ffcc66"
name="frmInterSearch">
<h4 id=
"out_t0" style="text-align: center">Wyszukiwanie interpolacyjne</h4>
<p style=
"TEXT-ALIGN: center">
(C)2006 mgr Jerzy Wałaszek<br>
I LO w Tarnowie
</p>
<hr>
<p style=
"TEXT-ALIGN: center">
<input type=
"button" value="Szukaj" name="B1" onclick="main();">
</p>
<p style=
"TEXT-ALIGN: center" id="t_out">...</p>
</form>

<script language=
javascript>

// Wyszukiwanie interpolacyjne
//----------------------------
// (C)2006 mgr Jerzy Wałaszek
// I LO w Tarnowie
//----------------------------

function main()
{
var N = 100; // Liczba elementów w zbiorze
var M = 99; // Maksymalna wartość elementu
var d = new Array(N + 1);
var w,i,ip,ik,isr,p,l,t;

// Generujemy zbiór pseudolosowy

for(i = 1; i <= N; i++) d[i] = Math.floor(Math.random() * (M + 1));

// Zbiór sortujemy rosnąco

for(i = N - 1; i >= 1; i--)
{
w = d[i]; ip = i + 1;
while((ip <= N) && (w > d[ip]))
{
d[ip - 1] = d[ip]; ip++;
}
d[ip - 1] = w;
}

// Generujemy poszukiwany element

w = Math.floor(Math.random() * (M + 1));

// Szukamy elementu w

ip = 1; ik = N; p = l = 0;
while((d[ip] <= w) && (w <= d[ik]))
{
isr = ip + Math.floor((w - d[ip]) * (ik - ip) / (d[ik] - d[ip]));
l++;
if(w == d[isr])
{
p = isr; break;
}
else if(w > d[isr]) ip = isr + 1; else ik = isr - 1;
}

// Prezentujemy wyniki

t = "";
for(i = 1; i <= N; i++)
if(i == p)
t += " <b><font color=red>(" + d[i] + ")</font></b>";
else
t += " &nbsp;" + d[i] + "&nbsp;";
t += "<br><br>Ilość prób = " + l + "<br><br>Element w = " + w;
if(p > 0)
t += " jest na pozycji nr " + p;
else
t += " w zbiorze nie wystepuje";

// Gotowe

document.getElementById("t_out").innerHTML = t;
}

</script>
</div>
</body>
</html>
 
Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Podobne artykuły


7
komentarze: 1 | wyświetlenia: 6262
16
komentarze: 5 | wyświetlenia: 9006
9
komentarze: 0 | wyświetlenia: 2784
49
komentarze: 18 | wyświetlenia: 64976
12
komentarze: 3 | wyświetlenia: 29779
37
komentarze: 9 | wyświetlenia: 28519
11
komentarze: 2 | wyświetlenia: 33152
18
komentarze: 11 | wyświetlenia: 9267
7
komentarze: 1 | wyświetlenia: 34648
17
komentarze: 4 | wyświetlenia: 14181
15
komentarze: 5 | wyświetlenia: 32761
13
komentarze: 2 | wyświetlenia: 22961
12
komentarze: 2 | wyświetlenia: 18506
11
komentarze: 1 | wyświetlenia: 86405
 
Autor
Artykuł




Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska