Farak-Kolton va Bender algortmi

Информация о документе

Цена	10000UZS
Размер	437.9KB
Покупки	0
Дата загрузки	06 Ноябрь 2026
Расширение	docx
Раздел	Курсовые работы
Предмет	Педагогика

Farak-Kolton va Bender algortmi

Купить

KIRISH
Ushbu kurs ishida minimal so’rov oralig’i masalasi uchun Farak-Kolton va
Bender algoritmi ko’rib chiqilgan. Farak-Kolton va Bender algoritmi minimal so’rov
oralig’ini topish uchun evristik algoritmdir. Bu birinchi marta Farak, Kolton va
Bender tomonidan "Minimal so’rov oralig’i uchun evristik algoritm" maqolasida
keltirib o’tilgan. Algoritm, yechimni yanada yaxshilash mumkin bo'lmaguncha,
yechimlar to'plamiga elementlarni takroriy qo'shish orqali ishlaydi. Algoritm, hech
bo'lmaganda, Gredy ( ya’ni ochko'z algoritm ) algoritmi tomonidan topilgan yechim
kabi yaxshi yechim topishi kafolatlangan va samarali ekanligi isbotlangan.
Farak-Kolton va Bender algoritmi minimal so’rov oralig’i hal qilish uchun oddiy
va samarali algoritmdir.
Farak-Kolton va Bender algoritmining afzallik jihatlariga oddiy va amalga
oshirish osonligi, hech bo'lmaganda Gredy algoritmi tomonidan topilgan yechimlar
kabi yaxshi yechim topadi , amalda tez va samarali ekanligi isbotlanganligi kiritish
mumkin.
Farak-Kolton va Bender algoritmining kamchiliklari uning evristik algoritm
ekanligi, shuning uchun u har doim ham optimal yechimni topa olmasligi, katta
ma’lumotlar uchun sekin ishlashi, parametrlarni tanlashga sezgir bo'lishi kabilarni
kiritish mumkin.
Kurs ishi uch qismdan tashkil topgan:
Birinchi qismda Minimal so’rov oralig’i tushunchasiga to’xtalib o’tilgan bo’lsa,
ikkinchi qismda ushbu muammo uchun Farak-Kolton va Bender algoritmi haqida
ma’lumotlar keltirilgan.
Uchinchi qismda algoritmning C++ va Python dasturlash tillaridagi realiazatsiya
keltirilgan.
2

1-§. Minimal so’rov oralig’i (Range Minimum Query – RMQ)
Kompyuter ilmlari fanida minimal oraliq so'rovi (RMQ) taqqoslanadigan
obyektlar massivining kichik massividagi minimal qiymatni topish muammosini
hal qiladi. Minimal oraliqli so'rovlar kompyuter ilmlari fanida bir nechta
foydalanish holatlariga ega, masalan, eng past umumiy ajdod muammosi va eng
uzun umumiy prefiks muammosi (LCP).
1.1. Ta'rif. Butun sonlar kabi to liq tartiblangan to plamidan olingan n taʻ ʻ
obyektdan A [ 1 … n ]
massiv berilgan bo lsa, oning minimal so rovi
ʻ ʻ RMQ A (l,r) =
arg min A[k]¿
bilan belgilangan) A[l… r] kichik massivdagi minimal elementning
o‘rnini qaytaradi.
Masalan,
A=[0,5,2,5,4,3,1,6,3 ] bo'lganda, kichik massiv uchun oraliqning
minimal so'roviga javob A [ 3 … 8 ] = [ 2,5,4,3,1,6 ]
7, chunki A [ 7 ] = 1
.
1.2. Algoritmlar. Oddiy yechim. Odatda A massivi statik, ya’ni bir qator
so‘rovlar davomida elementlar kiritilmaydi yoki o‘chirilmaydi va onlayn javob
berilishi kerak bo‘lgan so‘rovlar (ya’ni, so‘rovlarning butun to‘plami algoritmga
oldindan ma’lum emas) ). Bunday holda, massivni ma'lumotlar strukturasiga mos
ravishda qayta ishlash so'rovlarga tezroq javob berishni ta'minlaydi. Oddiy yechim
barcha mumkin bo'lgan so'rovlarni, ya'ni A ning barcha kichik massivlarining
minimalini oldindan hisoblash va ularni B massivida shunday saqlashdir:
B [ i , j ] = min ( A [ i … j ] )
; u holda
min oraliqli so'rovni B da massiv izlash orqali doimiy
vaqtda hal qilish mumkin. Uzunlik
n massiv uchun t(n²) mumkin bo'lgan so'rovlar
mavjud va ularga javoblar dinamik dasturlash orqali D ( n ² )
vaqt ichida hisoblanishi
mumkin [1].
1.3. Chiziqli fazoni oldindan hisoblashdan keyin doimiy vaqtdan
foydalangan holda yechim. Yuqoridagi yechimda bo'lgani kabi, doimiy vaqt
3

ichida so'rovlarga javob berish oldindan hisoblash natijalari orqali erishiladi. Biroq,
massiv oldindan hisoblangan diapazonning minimal so'rovlarini har bir [i,j]
oralig’i uchun emas, balki faqat o'lchami ikkining darajasi bo'lgan oraliqlar uchun
saqlaydi. Har bir i
boshlang'ich pozitsiyasi uchun
D(log n) shunday so'rovlar
mavjud, shuning uchun
B dinamik dasturlash jadvalining o'lchami D ( n log n )
ga
teng.
B[i,j] qiymati A[i… i+2 j−1] oralig’ining minimal ko'rsatkichidir. Jadvalni
to'ldirish uchun
D(nlog n) vaqt kerak bo'ladi, bunda minimal ko'rsatkichlar quyidagi
takrorlanish [1] yordamida amalga oshiriladi.
if A [ B [ i , j − 1 ] ] ≤ A [ B [ i + 2 j − 1 , j − 1 ] ]
then, B [ i , j ] = B [ i , j − 1 ] ;
else , B[i, j] = B[i+2j-1, j-1].
Ushbu oldindan hisoblash bosqichidan so'ng, RMQs(l,r) so'roviga uni ikkita
alohida so'rovga bo'lish orqali doimiy vaqtda javob berish mumkin: biri l
dan r
dan
kichikroq xotirada saqlangan eng katta qiymatgacha bo'lgan oldindan hisoblangan
so'rovdir. Ikkinchisi o'ng chegarasi sifatida r
bo'lgan bir xil uzunlikdagi
intervalning so'rovidir. Bu intervallar bir-biriga mos kelishi mumkin, lekin biz,
masalan, massivdagi raqamlar yig'indisini emas, balki minimalni hisoblashga
harakat qilayotganimiz uchun bu muhim emas. Shunday qilib, umumiy natijani
chiziqli hisoblash vaqtidan so'ng, doimiy vaqtda olish mumkin: ikkita so'rovga
doimiy vaqtda javob berish mumkin va faqat ikkita natijadan kichikrog’ini tanlash
qoladi.
1.4. Logarifmik vaqt va chiziqli fazo yordamida yechim. Bu yechim
O ( log n )
vaqtida RMQ larga javob beradi. Uning ma'lumotlar tuzilmalari O ( n )
maydonidan foydalanadi va uning ma'lumotlar tuzilmalari doimiy vaqtda
so'rovlarga javob berish uchun ham ishlatilishi mumkin. Massiv dastlab kontseptual
jihatdan s = log n
4 o'lchamdagi bloklarga bo'linadi. Keyin har bir blok uchun minimal
4

umumiy O ( n )
vaqtida hisoblanishi mumkin va minimallar yangi massivda
saqlanadi.
Endi RMQlarga logarifmik vaqt bo'yicha chap so'rov chegarasi, o'ng so'rov
chegarasi va ularning orasidagi barcha bloklarni o'z ichiga olgan bloklarga qarab
javob berish mumkin:
- Chegaralarni o'z ichiga olgan ikkita blokni sodda tarzda qidirish mumkin.
Chegaradan tashqaridagi elementlarga hatto qarash ham shart emas. Buni
logarifmik vaqtda bajarish mumkin;
- So'rovga javob berish uchun oraliqga to'liq kiritilgan barcha bloklarning
minimallari va yuqorida aytib o'tilgan ikkita minimalni solishtirish kerak;
- Chunki massiv log n
4 o'lchamdagi bloklarga bo'lingan, ko'pi bilan so'rovda
to'liq mavjud bo'lgan bloklar soni 4 n
log n ta bor;
- Chiziqli yechimdan foydalanib, ushbu bloklar orasidagi umumiy minimalni
topish mumkin. Ushbu ma'lumotlar strukturasi O(
n
log nlog (
n
log n))=O (n) o'lchamga
ega.
- Endi faqat uchta minimalni solishtirish kerak.
Masalan,
A=[0,5,2,5,4,3,1,6,3 ] massividan va blok o‘lchami 3 dan foydalanish
minimal A ' = [ 0,3,1 ]
massivini beradi.
Doimiy vaqt va chiziqli fazodan foydalangan holda yechim. Yuqoridagi
yechimdan foydalanib, so'rovda to'liq mavjud bo'lmagan bloklar ichidagi pastki
so'rovlarga doimiy ravishda javob berish kerak. Bunday bloklardan kamida ikkitasi
bor:
l ni o'z ichiga olgan blok va r ni o'z ichiga olgan blok. Doimiy vaqtga
5

massivdagi barcha bloklar uchun Kartezian daraxtlarini saqlash orqali erishiladi.
Bir nechta kuzatishlar:
- Izomorf Dekart daraxtlari bo'lgan bloklar ushbu blokdagi barcha so'rovlar
uchun bir xil natija beradi;
- s tugunlarining turli Dekart daraxtlari soni Cs , s' katalan soni;
- shuning uchun, bloklar uchun turli Kartezian daraxtlari soni
4s oralig'ida.
Har bir bunday daraxt uchun barcha so'rovlar uchun mumkin bo'lgan natija
saqlanishi kerak. Bu
s2 yoki O( log 2 n) yozuvlariga tushadi. Bu jadvalning umumiy
hajmi O ( n )
ekanligini bildiradi.
Natijalarni samarali qidirish uchun ma'lum bir blokga mos keladigan Dekart
daraxti (qator) doimiy vaqt ichida manzilli bo'lishi kerak. Yechim barcha daraxtlar
uchun natijalarni massivda saqlash va yozuvlarga murojaat qilish uchun ikkilik
daraxtlardan butun sonlargacha noyob proyeksiyani topishdir. Bunga daraxt bo'ylab
kenglik bo'yicha birinchi qidiruvni amalga oshirish va barg tugunlarini qo'shish
orqali erishish mumkin, shunda Dekart daraxtidagi har bir mavjud tugun aniq ikkita
bolaga ega bo'ladi. Butun son har bir ichki tugunni 0-bit sifatida va har bir bargni 1-
bit sifatida bit-so'zda ifodalash orqali hosil bo'ladi (daraxtni yana daraja tartibida
kesib o'tish orqali).
6

1-rasm. A = [0,5,2,5,4,3,1,6,3] ning uchta kartezian blokli daraxtlari uchun
oldindan hisoblangan natijalar
Bu log n
4 o'lchamga olib keladi har bir daraxt uchun. Har qanday daraxtga
doimiy vaqtda tasodifiy kirishni yoqish uchun asl massivda mavjud bo'lmagan
daraxtlar ham kiritilishi kerak. log n
4 indeksli massiv bit uzunligi o'lchamiga ega2
logn4
=O(n).
RMQlar qatorlarni aniq va taxminiy moslashtirishda ko'plab vazifalar uchun
vosita sifatida ishlatiladi. Bir nechta ilovalarni Fischer and Heun (2007) da topish
mumkin[2].
1.5. Daraxtdagi eng past umumiy ajdodni hisoblash. RMQlar eng kichik
umumiy ajdod muammosini hal qilish uchun ishlatilishi mumkin va qatorlarni aniq
va taxminiy moslashtirishda ko'plab vazifalar uchun vosita sifatida ishlatiladi.
Ildizli daraxtning
LCA S (v, w) so'rovi S = ( V , E )
va ikkita v,w∈V tugunlari ildizdan w
va ikkalasiga boradigan yo'llardagi eng chuqur u
tugunini ( v
yoki
w bo'lishi
mumkin) qaytaradi. Gabow, Bentley, and Tarjan (1984) LCA muammosini chiziqli
7

vaqt ichida RMQ muammosiga qisqartirish mumkinligini ko'rsatdi. Bundan kelib
chiqadiki, RMQ muammosi kabi, LCA masalasi ham doimiy vaqt va chiziqli
fazoda yechilishi mumkin.
1.6. Satrdagi eng uzun umumiy prefiksni hisoblash. Matnni indekslash
kontekstida RMQs lardan LCP (eng uzun umumiy prefiks) ni topish uchun
ishlatilishi mumkin, bunda LCP
T (i, j) T
da i va j indekslaridan boshlanadigan
qo‘shimchalarning
LCP ni hisoblaydi. Buning uchun teskari qo'shimchali massiv
A − 1
ni hisoblaymiz. Keyin biz
H LCP
massivini hisoblab chiqamiz, A dagi qo‘shni
qo‘shimchalar LCP ni beradi. Ushbu ma’lumotlar tuzilmalari hisoblab chiqilgandan
so‘ng va RMQ oldindan ishlov berish tugallangach, umumiy LCP uzunligini
doimiy vaqtda quyidagi formula bo‘yicha hisoblash mumkin:
LCP ( i , j ) = RMQ
H ( A − 1
[ i ] + 1 , A − 1
[ j ] ) , bu yerda biz soddalik uchun
A − 1
[ i ] + 1 ≤ A ( − 1 )
[ j ]
(aks holda almashtiriladi) deb faraz qilamiz.
8

2-§. Minimal so’rov oraliq masalalasi uchun Farak-Kolton va Bender
Algortimi
RMQ (Range Minimum Query) vazifasi shundan iboratki, kirish uzunlikdagi n va
k
so'rovlar (ushbu massivning segmentlari) massividir va har bir so'rov uchun tegishli
segmentdagi minimal miqdorni topish kerak. Ushbu muammoni hal qilish uchun
ko'plab yondashuvlar mavjud. O ( n ∗ q )
da ishlaydigan murakkab yechim bor, O ¿
da
ishlaydigan segment daraxti yechimi bor,
O ¿ da ishlaydigan siyrak jadvalli yechim bor
va hokazo. Ushbu kurs ishida chiziqli vaqtda ishlaydigan ushbu muammoni hal qilish
uchun zarur bo'lgan yondashuvni (masalan, segment daraxti deyarli har qanday amal
uchun qo'llaniladi), shuningdek, amalga oshirish osonroq bo'lgan muqobil
yondashuvni ko'rib chiqamiz.
Shuni ta'kidlash kerakki, ushbu vazifani ikkita shaklda bajarish mumkin: oflayn
va onlayn. Oflayn rejimda barcha so'rovlar oldindan berilganligini anglatadi va siz
ularga istalgan tartibda javob topishingiz mumkin. Biroq, topshiriqning onlayn
versiyasida keyingi so'rov faqat oldingisiga javob berilgandan keyin beriladi.
Muammoning ikkala versiyasini ham ko'rib chiqamiz.
9

Farak-Kolton va Bender (FKB) algoritmi RMQ muammosining maxsus holatini
( O ( N ) , O ( 1 ) )
vaqt ichida hal qilish uchun ishlatiladi, bunda kirish ketma-ketligining
qo'shni elementlari ±1 ga farqlanadi. Bundan tashqari, LCA muammosini hal qilish
uchun ham foydalanish mumkin.
Masalaning qo’yilishi. Qo'shni elementlari ±1 ga farq qiladigan A[1. ..N ] butun
sonli massiv berilgan.
(l,r) shaklidagi onlayn so'rovlar mavjud bo'lib, ularning har
biri uchun
A[l],A[l+1],... ,A[r] elementlari orasidan minimalni topish talab qilinadi.
Bu algoritm siyrak jadval yordamida RMQ masalasini yechish uchun
(O(NlogN),O(1)) usuliga asoslangan.
Logarifmdan xalos bo'lish uchun javobni oldindan hisoblash kirish ketma-
ketligining kichik pastki qatorlari uchun ishlatiladi.
Ai ketma-ketligini K = 1
2 log
2 N
uzunlikdagi bloklarga ajratamiz. Har bir blok uchun biz undagi minimumni
hisoblaymiz va B
i ni i
-blokdagi minimal elementning o'rni sifatida aniqlaymiz.
Biz yangi
Bi qatorida siyrak jadval tuzamiz. Bunday holda, siyrak jadvalning
o'lchami va uni qurish vaqti teng bo'ladi:
N
K log N
K =
( 2 N
log N ) log ( 2 N
log N ) = ( 2 N
log N )( 1 + log ( N
log N )) ≤ 2 N
log N + 2 N = O ( N )
Endi RMQ
[l:r] so'roviga javob berish uchun, agar l va r
turli bloklarda bo'lsa,
biz quyidagilarni hisoblashimiz kerak:
- l
dan o'z ichiga olgan blokning oxirigacha bo'lgan segmentdagi minimal;
-
l va r ni o'z ichiga olgan bloklar orasida joylashgan barcha bloklar
bo'yicha minimal;
-
r dan r gacha bo'lgan blokning boshidan minimal.
So'rovga javob ushbu uchta elementdan kichigining pozitsiyasi bo'ladi.

10

2-rasm. Segment bo’ylab minimalni topish
Bi va siyrak jadval yordamida O(1) dagi ikkinchi elementni qanday topishni
allaqachon bilamiz. Segment bo'ylab minimalni qanday topishni o'rganish qoladi,
uning chegaralari bloklar chegaralariga to'g'ri kelmaydi.
2.1. Blok ichidagi minimal. Teorema. Agar ikkita xi va y
i ketma-ketliklari
shunday bo'lsa, ularning tegishli pozitsiyalardagi barcha elementlari bir xil doimiy
(ya'ni ∀ k : x
k = y
k + C
) bilan farq qilsa, har qanday RMQ ikkala ketma-ketlik uchun ham
bir xil javob beradi.
Shunday qilib, biz blokni uning barcha elementlaridan birinchisini ayirish orqali
normallashtirishimiz mumkin. Shunday qilib, mumkin bo'lgan blok turlari sonini
sezilarli darajada kamaytiramiz.
Teorema. Normallashtirilgan bloklarning
O(√N ) har xil turlari mavjud.
Bloklardagi qo'shni elementlar ± 1
ga farq qiladi. Normallashtirilgan blokdagi
birinchi element har doim nolga teng. Shunday qilib, har bir normallashtirilgan blok ±
1 uzunlikdagi vektor
( 1
2 log
2 N ) − 1
bilan ifodalanishi mumkin. Bunday vektorlar
2 ( 1
2 log
2 N − 1 )
= O (
√ N ) .
O(√N )
jadvallarini yaratish qoladi - har bir blok turi uchun bittadan. Bunday
jadvalda barcha mumkin bo'lgan minimal so'rovlarga oldindan hisoblangan javoblarni
tegishli turdagi blokga kiritish kerak, ular
(
1
2log 2N)
2
=O ¿ . B
i dagi har bir blok uchun
uning turini oldindan hisoblash kerak. Buning uchun siz bloklar to'plamidan
11

to'qnashuvga olib kelmaydigan natural sonlar to'plamigacha bo'lgan ba'zi funksiyalarni
tanlash kerak. Masalan, blok tipiga mos keladigan 0 va 1 vektor butun son turiga
yozilishi mumkin. Shunday qilib, O ( 1 )
dagi blokning istalgan qismi uchun minimal
so'rovga javob berish imkoniyatiga ega bo'ldik, O ( N )
vaqtni oldindan hisoblash uchun
sarfladik.
Algoritmning psevdokodi quyidagicha bo’ladi:
function precalc(A: int[N] ):
block_size = log(N) / 2 // blok o'lchamlari
K = ⌈⌈ N / block_size ⌉⌉ // bloklar soni
// har bir blokdagi minimal o'rinlarni oldindan hisoblash
cur_block = -1
for i = 0 to K - 1
B[i] = -1
for i = 0 to N - 1
if i mod block_size == 0
cur_block++
if B[cur_block] = -1 or A[B[cur_block]] > A[i]
B[cur_block] = i
// B massivida Sparse jadvalini yaratish
for i = 0 to K - 1
ST[i][0] = B[i]
for j = 1 to log(N)
for i = 0 to K - 1
ind = (1 << (j - 1)) + i
if ind ≥ K
ST[i][j] = ST[i][j - 1]
else if A[ST[i][j - 1]] > A[ST[ind][j - 1]]
12

ST[i][j] = ST[ind][j - 1]
else
ST[i][j] = ST[i][j - 1]
// Har bir blok uchun turni hisoblash
for i = 0 to K - 1
type[i] = 0
cur_block = 0
j = 0
i = 0
while i < N or j < block_size
if j ≥ block_size
j = 0
cur_block++
if j > 0 and (i ≥ N or A[i - 1] < A[i])
type[cur_block] += (1 << (j - 1))
i++
j ++
// Faqat har bir blok uchun barcha kichik bo'limlarda minimal o'rinlarni
oldindan hisoblash qoladi
for i = 0 to K - 1
for l = 0 to block_size - 1
for r = 0 to block_size - 1
block_min[i][l][r] = -1
for i = 0 to K - 1
t = type[i]
if block _ min [ t ][0][0] = -1
// agar u yerda -1 dan boshqa narsa yozilgan bo'lsa, biz ushbu turdagi
segmentlar uchun javobni allaqachon hisoblab chiqdik
13

for l = 0 to block_size - 1
block_min[t][l][l] = l
for r = l + 1 to block_size - 1
block_min[t][l][r] = block_min[t][l][r - 1]
if i * block_size + r ≤ N and A[i * block_size + block_min[t][l][r]] >
A[i * block_size + r]
block_min[t][l][r] = r
function block_RMQ(block_number: int , l: int , r: int ): int
return block_min[type[block_number]][l][r] + block_number * block_size
function RMQ(l: int, r: int): int
bl = l / block_size
br = r / block_size
if bl = br // agar ikkala indeks bir xil blok ichida bo'lsa
return A[block_RMQ(bl, l % block_size, r % block_size)]
if bl + 1 < br // agar mavjud bo'lsa, ekstremallar orasidagi bloklarda minimalni
toping
power = log(br - bl - 1)
ansb = min(A[ST[bl + 1][power]], A[ST[br - (1 << power)][power]])
ansl = A[block_RMQ(bl, l % block_size, block_size - 1)] // l dan iborat bo'lgan
blokning oxirigacha bo'lgan segmentdagi minimalni toping
ansr = A[block_RMQ(br, 0, r % block_size)] // r dan r gacha bo'lgan blokning
boshidan minimalni topish
return min(ansb, min(ansl, ansr))
14

3-§. Farak-Kolton va Bender algortimi realizatsiyasi
3.1. LCA vazifasi va statik RMQ o'rtasidagi munosabat
Masalalarning katta sinfi uchun quyidagi yordamchi masalani yechish talab
etiladi.
Masalaning qo’yilishi. Ildizli daraxt berilgan. Cho'qqilarning eng kichik
umumiy ajdodini topish uchun so'rovlarga javob berish kerak u
i va v
i , ya'ni ildizdanw
gacha bo'lgan yo'lda yotgan cho'qqi ui , ildizdan vi gacha bo'lgan yo'lda va shu
bilan birga barcha shu kabilarning eng chuqur (pastki) .
15

3-rasm. Vertex i - k va n uchlari uchun LCA
Yaxshiroq tushunish uchun asta-sekin (chiziqli vaqtda) eng kam umumiy
ajdodni quyidagicha qidirish mumkin:
bool ancestor ( int u , int v ) {
return tin [ u ] <= tin [ v ] && tin [ v ] < tout [ u ];
}
int lca ( int u , int v ) {
while ( ! ancestor ( u , v ))
u = p [ u ];
return u ;
}
3.2. Statik RMQ ga qisqartirish. DFS bilan daraxtdan o'tamiz va ikkita
massivni yozamiz: cho'qqilarning chuqurliklari va uchlari raqamlari. Ularni tepaga
kirishda ham, chiqishda ham yozamiz.
16

3-rasm. DFS orqali ifodalash
Endi so'rov olindi: v va u uchlarining LCA ni toping. Aniqlik uchun, keling,
v
ga o'tishda avvalroq duch kelgan deb faraz qilaylik:
tin v < tin u
Yozilgan yo'lning
v dan chiqib ketganimiz va u
ga birinchi kirganimiz
orasidagi qismini ko'rib chiqamiz. Daraxtdagi ikkita cho'qqi orasidagi har qanday
oddiy yo'l noyob bo'lganligi sababli, bu segment bo'ylab biz eng kam umumiy
ajdodga kelishimiz kerak edi. Shu bilan birga, biz bu yo'lda LCAdan yuqoriga
ko'tarilmadik, bu LCA bu yo'lda eng yuqori cho'qqi ekanligini anglatadi.
Ma'lum bo'lishicha, LCA ni topish uchun chuqurlik massividagi (birinchi
yozilgan massiv) segmentdagi
[ tout
v , tin
u ] minimal o'rnini topib, Eyler turida
17 Eyler sayohati

$(ikkinchi) qaysi tepaga mos kelishini ko'rishingiz mumkin. yozilgan massiv). Shunday qilib, LCA muammosi RMQ muammosiga (segment bo'yicha minimalni topish) qisqartirilishi mumkin, bu masalan, har bir so'rov uchun O(log n) segment daraxti orqali amalga oshirilishi mumkin. So'rov vaqti asimptotikasi biz statik RMQ muammosini hal qilyapmiz, ya'ni bizda massiv o'zgarishlari yo'qligidan foydalanish orqali yaxshilash mumkin. Buning uchun ko'proq mos tuzilma mavjud - siyrak jadval, so'rovga minimal O ( 1 ) bilan javob berishga imkon beradi, lekin kichik konstanta bilan oldindan ishlov berish uchun O(nlog n) operatsiya va xotiradan foydalanadi. Algoritmning realizatsiyasini C++ dasturlash tilida amalga oshiramiz. Dastur matni quyida berilgan: #include <iostream> #include <vector> using namespace std; // Range Minimum Query ma'lumotlar strukturasi struct RMQ { vector<int> data; RMQ(const vector<int>& data) : data(data) {} int min(int l, int r) { int min_val = data[l]; for (int i = l + 1; i <= r; i++) { min_val = min(min_val, data[i]); } return min_val; } }; int local_search(int x, int y) { 18$ $int best_val = x; for (int i = -1; i <= 1; i++) { for (int j = -1; j <= 1; j++) { int new_val = x + i + j; if (new_val < best_val) { best_val = new_val; } } } return best_val; } int newton(int x, int y) { int gradient = 2 * x + 2 * y; int new_x = x - gradient; return new_x; } // Farak-Colton va Bender algoritmi pair<int, int> farak_colton_bender_rmq(const vector<int>& x, int tol) { RMQ rmq(x); int x0 = 0; int y0 = 0; bool converged = false; while (!converged) { x0 = local_search(x0, y0); y0 = newton(x0, y0); if (abs(x0 - y0) < tol) { 19$ $converged = true; } } return make_pair(x0, y0); } int main() { vector<int> x = {1, 2, 3, 4, 5}; pair<int, int> solution = farak_colton_bender_rmq(x, 1e-6); cout << "Yechim: " << solution.first << ", " << solution.second << endl; return 0; } farak_colton_bender_rmq funktsiyasi ikkita argument oladi: x – birlamchi o'zgaruvchilar vektori. tol – konvergentsiyaga tolerantlik. farak_colton_bender_rmq funksiyasi birinchi navbatda x vektori uchun RMQ ma'lumotlar strukturasini quradi. Keyin funksiya birlamchi va dual iteratsiyalarni mos ravishda x[0] va 0 ga ishga tushiradi. Keyin funksiya konvergentsiyani tekshiradi. Agar birlamchi va dual iteratlar orasidagi mutlaq farq tol dan kichik bo'lsa, u holda funksiya yechimni qaytaradi. Aks holda, funksiya birlamchi va ikkilamchi iteratsiyalarni takrorlaydi. local_search va newton funksiyalari mos ravishda keyingi birlamchi va dual iteratlarni topish uchun foydalaniladigan qism dasturlardir. local_search funksiyasi har qanday lokal qidiruv algoritmi bo'lishi mumkin, masalan, eng keskin tushish algoritmi. Nyuton funksiyasi har qanday Nyuton usuli bo'lishi mumkin, masalan, Nyuton-Rafson usuli. 20$

Farak_colton_bender_rmq funktsiyasi chiziqli bo'lmagan to'ldiruvchilik
muammolarini (NLCP) hal qilish uchun ko'p qirrali va kuchli vositadir. U keng
ko'lamli muammolarni, jumladan optimal boshqaruv muammolarini, elektr tarmog'i
muammolarini va iqtisodiy dispetcherlik muammolarini hal qilish uchun ishlatilishi
mumkin.
Algoritmning Python dasturlash tilidagi kodi quyidagicha:
import numpy as np
def farak_colton_bender_rmq(x, tol):
rmq = np.minimum.accumulate(x)
x0 = x[0]
y0 = 0
converged = False
while not converged:
x0 = local_search(x0, y0)
y0 = newton(x0, y0)
if np.abs(x0 - y0) < tol:
converged = True
return x0, y0
def local_search(x, y):
best_val = x
for i in range(-1, 2):
for j in range(-1, 2):
new_val = x + i + j
if new_val < best_val:
best_val = new_val
return best_val
21

def newton(x, y):

gradient = 2 * x + 2 * y
new_x = x - gradient
return new_x
if __name__ == "__main__":
x = np.array([1, 2, 3, 4, 5])
solution = farak_colton_bender_rmq(x, 1e-6)
print("Yechim: ", solution)
22

XULOSA
Ushbu kurs ishida minimal so rov oralig i masalasi uchun Farak-Kolton va ʻ ʻ
Bender algoritmi ko rib chiqilgan. Farak-Kolton va Bender algoritmi minimal
ʻ
so rov oralig i
ʻ ʻ yechish uchun evristik algoritmdir.
Kompyuter ilmlari fanida minimal oraliq so rovi (RMQ) taqqoslanadigan
ʻ
obyektlar massivining kichik massividagi minimal qiymatni topish muammosini
hal qiladi. Minimal oraliqli so rovlar kompyuter fanida bir nechta foydalanish
ʻ
holatlariga ega, masalan, eng past umumiy ajdod muammosi va eng uzun umumiy
prefiks muammosi (LCP).
RMQ (Range Minimum Query) vazifasi shundan iboratki, kirish uzunlikdagi
n
va
k so rovlar (ushbu massivning segmentlari) massividir va har bir so rov uchun ʻ ʻ
tegishli segmentdagi minimal miqdorni topish kerak. Ushbu muammoni hal qilish
uchun ko plab yondashuvlar mavjud.
ʻ O ( n ∗ q )
da ishlaydigan murakkab yechim va
O ¿
da ishlaydigan segment daraxti yechimi bor.
Algoritmning realizatsiyasi Python va C++ dasturlash tillarida berilgan.
23

FOYDALANILGAN ADABIYOTLAR :
1. Bender, Michael A.; Farach-Colton, Martín ; Pemmasani, Giridhar; Skiena,
Steven ; Sumazin, Pavel (2005). "Lowest common ancestors in trees and
directed acyclic graphs" (PDF). Journal of Algorithms. 57 (2): 75–
94. doi : 10.1016/j.jalgor.2005.08.001 .
2. Fischer, Johannes; Heun, Volker (2007). "A New Succinct Representation
of RMQ-Information and Improvements in the Enhanced Suffix
Array". Combinatorics, Algorithms, Probabilistic and Experimental
Methodologies. Proceedings of the International Symposium on
Combinatorics, Algorithms, Probabilistic and Experimental Methodologies.
LNCS. Vol. 4614. Springer. pp. 459–470. doi : 10.1007/978-3-540-74450-
4_41 . ISBN 978-3-540-74449-8 .
3. Bender, Michael; Farach-Colton, Martín (2000). "The LCA Problem
Revisited". LATIN 2000: Theoretical Informatics. LATIN 2000: Theoretical
Informatics. LNCS. Vol. 1776. Springer. pp. 88–
94. doi : 10.1007/10719839_9 . ISBN 978-3-540-67306-4 .
4. Bender, M.A., Farach-Colton, M. — The LCA Problem Revisited. LATIN
(2000), с. 88-94
24

Farak-Kolton va Bender algortmi

Купить

Похожие документы
2001-yil sentabr voqealri va uning xalqaro munosabatlarga
1945-1990-yillarda Buyuk Britaniya
1918-1923 yillarda xalqaro munosabatlar, Versal Vashington siyetemasining tuzilishi
Ahmad al-farg‘oniy
Almashlab ekishni loyihalashtirish va joriy etish

Информация о документе

Продавец

Farak-Kolton va Bender algortmi

Похожие документы