جستجو سه‌تایی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

جستجو سه‌تایی

در علوم کامپیوتر رویه ی جستجو ترنری مهارتی برای پیدا کردن مقدار بیشینه و یا کمینه در توابع أکید است. در این رویه مشخص می‌کنیم که مقدار بیشینه یا کمینه تابع نمی‌تواند در یک سوم ابتدا یا انتهای دامنه ی تابع وجود داشته باشد. سپس همین شیوه را بر روی دو سوم باقی‌مانده به کار می‌بریم. جستجو سه‌تایی نمومه‌ای از روش الگوریتم_تقسیم_و_حل است(الگوریتم جستجو را ببینید.)Ternary search

تابع[ویرایش]

فرض کنید ما به دنبال بیشینه‌ی f(x) و می دانیم این مقدار بین A و B قرار دارد. برای این که الگوریتم قابل اعمال باشند، یک مقدارxباید وجود داشته باشد به طوری که :

  • به ازای همه‌ی مقادیر a و b، که A \le a<b \le x داریم f(a)<f(b)
  • به ازای همه‌ی مقادیر a و b، که x \le a<b \le B داریم f(a)>f(b)

الگوریتم[ویرایش]

تابع اکید f(x) را روی بازه‌ی [l,r] در نظر بگیرید. دو نقطه ی m_1 و m_2 را در این بازه انتخاب می‌کنیم. بنابراین l \le m_1<m_2 \le rدر این صورت سه حالت وجود دارد :


  • اگرf(m_1)<f(m_2)، مقدار بیشینه نمی‌تواند دربازه‌ی سمت چپ واقع شود-- [l,m_1]. این بدان معنی است که مقدار بیشینه در فاصله [m_1,r] قرار دارد.
  • اگرf(m_1)>f(m_2)، مقدار بیشینه نمی‌تواند دربازه‌ی سمت راست واقع شود-- [m_2,r]. این بدان معنی است که مقدار بیشینه در فاصله [l,m_2] قرار دارد.
  • اگرf(m_1)=f(m_2)، این جستجو باید در بازه‌ی انجام شود. این حالت را می‌تونیم به هر یک از حالت‌های قبل برای ساده شدن رویه نسبت دهیم.

این فرایند تا زمانی ادامه پیدا می‌کند که بازه‌ی حاصل از مقدار ثابت از پیش تعیین شده کوچکتر شود.

انتخاب نقاط m_1 و m_2 :

  • m1 = l + (r-l)/3
  • m2 = r - (r-l)/3

Ternary search

زمان اجرا[ویرایش]

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)

Ternary search

درخت جستجوی سه‌تایی[ویرایش]

درخت جستجوی سه‌تایی یکی از جالب‌ترین داده‌ساختارهادر زمینه دانش خوداست، زیرا این درخت ذخیره‌سازی بهینه را با سریع پیدا کردن ترکیب می‌کندو توانایی جستجوی پیشوندرا نیز دارد.

قسمتی از نظریه[ویرایش]

درخت جستجو سه تایی کمی پیچیده‌تر از درخت جستجو دوتایی است. علاوه بر درخت جستجوی دودویی، اشاره گر سومی در هر گره وجود دارد. زمانی که بر روی درخت حرکت می‌کنیم، این اشاره‌گرهنگامی که مقداری که مقایسه می‌شود؛ با مقدار گره برابر باشد، استفاده می‌گردد.در نتیجه این درخت سه اشاره‌گر چپ، راست، و برابر دارد. که در شکل زیر مشاهده می‌کنید.

شکل زیر درخت جستجو سه تایی رشته‌های "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

[۱]

منابع[ویرایش]

پیوند به بیرون[ویرایش]