جستجو سهتایی
جستجو سهتایی
در علوم کامپیوتر رویه ی جستجو ترنری مهارتی برای پیدا کردن مقدار بیشینه یا کمینه در توابع أکید است. در این رویه مشخص میکنیم که مقدار بیشینه یا کمینه تابع نمیتواند در یک سوم ابتدا یا انتهای دامنه ی تابع وجود داشته باشد. سپس همین شیوه را بر روی دو سوم باقیمانده به کار میبریم. جستجو سهتایی نمومهای از روش الگوریتم تقسیم و حل است(الگوریتم جستجو را ببینید.)Ternary search[پیوند مرده]
تابع[ویرایش]
فرض کنید ما به دنبال بیشینۀ هستیم و می دانیم این مقدار بین و قرار دارد. برای این که الگوریتم قابل اعمال باشند، یک مقدار باید وجود داشته باشد به طوری که:
- به ازای همۀ مقادیر و ، که داریم
- به ازای همۀ مقادیر و ، که داریم
الگوریتم[ویرایش]
تابع اکید را روی بازۀ در نظر بگیرید. دو نقطه ی و را در این بازه انتخاب میکنیم. بنابراین در این صورت سه حالت وجود دارد :
- اگر، مقدار بیشینه نمیتواند دربازۀ سمت چپ واقع شود-- . این بدان معنی است که مقدار بیشینه در فاصله قرار دارد.
- اگر، مقدار بیشینه نمیتواند دربازۀ سمت راست واقع شود-- . این بدان معنی است که مقدار بیشینه در فاصله قرار دارد.
- اگر، این جستجو باید در بازۀ انجام شود. این حالت را میتونیم به هر یک از حالتهای قبل برای ساده شدن رویه نسبت دهیم.
این فرایند تا زمانی ادامه پیدا میکند که بازۀ حاصل از مقدار ثابت از پیش تعیین شده کوچکتر شود.
انتخاب نقاط و :
- m1 = l + (r-l)/3
- m2 = r - (r-l)/3
زمان اجرا[ویرایش]
T(n) = T(2/3 * n) + c (Θ(log n
رویۀ بازگشتی[ویرایش]
def ternarySearch(f, left, right, absolutePrecision):
#left and right are the current bounds; the maximum is between them
if (right - left) <absolutePrecision:
return (left + right)/2
leftThird = (2*left + right)/3
rightThird = (left + 2*right)/3
if f(leftThird)> f(rightThird):
return ternarySearch(f, leftThird, right, absolutePrecision)
else:
return ternarySearch(f, left, rightThird, absolutePrecision)
درخت جستجوی سهتایی[ویرایش]
درخت جستجوی سهتایی یکی از جالبترین دادهساختارهادر زمینه دانش خوداست، زیرا این درخت ذخیرهسازی بهینه را با سریع پیدا کردن ترکیب میکندو توانایی جستجوی پیشوندرا نیز دارد.
قسمتی از نظریه[ویرایش]
درخت جستجو سه تایی کمی پیچیدهتر از درخت جستجو دوتایی است. علاوه بر درخت جستجوی دودویی، اشاره گر سومی در هر گره وجود دارد. زمانی که بر روی درخت حرکت میکنیم، این اشارهگرهنگامی که مقداری که مقایسه میشود؛ با مقدار گره برابر باشد، استفاده میگردد.در نتیجه این درخت سه اشارهگر چپ، راست، و برابر دارد. که در شکل زیر مشاهده میکنید.
شکل زیر درخت جستجو سه تایی رشتههای "as", "at", "cup", "cute", "he", "i" and "us" را نشان میدهد:
c \ | / a u h | / / / t t e u \ | \| | s p e i s
پیادهسازی[ویرایش]
پیادهسازی تابع search :
def search(string)
return false unless (string && !string.empty? && self.value)
head, tail = string.partition
if head <self.value
return @left.search(string) if @left
elsif head == self.value
return true if !tail && self.ending?
return @equal.search(tail) if @equal
elsif head> self.value
return @right.search(string) if @right
end
end
پیادهسازی کلاس string :
def search(string)class String
def partition
[head, tail]
end
# First character.
def head
(self.length>= 1) ? self[0].chr : nil
end
# Cut the first character from the string and return the tail.
def tail
(self.length>= 2) ? self[1..-1] : nil
end
end
پیادهسازی کلاس درخت جستجوی سهتایی :
class Tst
def initialize
@left = @equal = @right = nil
@ending = false
end
def insert(string)
raise ArgumentError unless string.is_a?(String)
head, tail = string.partition
if self.value.nil? # self.value ?
self.value = head # self.value ?
end
if head <self.value
@left = Tst.new unless @left
@left.insert(string)
elsif head == self.value
if tail
@equal = Tst.new unless @equal
@equal.insert(tail)
else
self.ending_here()
end
elsif head> self.value
@right = Tst.new unless @right
@right.insert(string)
end
end
def search(string)
return false unless (string && !string.empty? && self.value)
head, tail = string.partition
if head <self.value
return @left.search(string) if @left
elsif head == self.value
return true if !tail && self.ending?
return @equal.search(tail) if @equal
elsif head> self.value
return @right.search(string) if @right
end
end
alias :<<:insert
alias :[] :search
protected
def value
@value
end
def value=(value)
raise ArgumentError unless acceptable?(value)
@value = value
end
def acceptable?(value)
value.is_a?(String) && value.length == 1
end
def ending_here
@ending = true
end
def ending?
@ending
end
end