Histograms

به مساله ی زير توجه کنيد: “يک سری مستطيل با عرض واحد و ارتفاع های مختلف داريم که کنار هم قرار گرفته اند. الگوريتمی پيشنهاد دهيد که مساحت بزرگترين مستطيلی که درون اين مستطيل ها جا می شود را پيدا کند.” (برای امتحان کردن روش های مختلف حل اين مساله، سعی کنيد مساله ی ZJU #1985 را حل کنید.) مثلا در شکل زير، مستطيلی که مساحت آن جواب مساله است با رنگ سبز مشخص شده است.

ساده ترين راه حلی که به ذهن می رسد اين است که به ازای هر مستطيل فرض کنيم که مستطيل نتيجه هم ارتفاع با آن است و ببينيم با اين ارتفاع چقدر می توانيم به سمت راست و چپ برويم. ولی پيچيدگی زمانی اين راه حال در بدترين حالت می باشد که چندان مطلوب نيست.

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

دفعه ی اولی که اين مساله را سر امتحان ميان ترم درس طراحی الگوريتم ها ديدم، اين راه حل به ذهنم رسيد:

فرض کنيد می خواهيم جواب را برای مستطيل a-ام تا b-ام پيدا کنيم. اين مستطيل ها را از وسط به دو قسمت تقسيم می کنيم. جواب يا کاملا در قسمت سمت چپ است يا کاملا در قسمت سمت راست يا اينکه قسمتی از آن در سمت راست است و قسمتی از آن در سمت چپ. دو حالت اول را به صورت بازگشتی پيدا می کنيم و برای پيدا کردن بهترين جواب در حالت سوم، به روش زير عمل می کنيم:

در هر مرحله مستطيل را با ارتفاع جاری گسترش می دهيم. حالا، از سمت چپ و راست به دو مستطيل مختلف مماس می شود. ارتفاع جاری را به ماکزيمم ارتفاع اين دو مستطيل تغيير می دهيم و ادامه می دهيم. در هر مرحله مساحت مستطيل جاری را پيدا کرده و جواب را بروز می کنيم. اين کارها را تا زمانی انجام می دهيم که از سمت چپ به مستطيل a-ام و از سمت راست به مستطيل b-ام برسيم.

برای اينکه منظور من را دقيق تر بفهميد، به pseudo-code زير توجه کنيد:

def FindLargestRectangle(a, b):
   if a == b:
      return Heights[a]
   mid = (a+b) / 2
   Result = max(FindLargestRectangle(a, mid), FindLargestRectangle(mid+1, b))
   Left = mid
   Right = mid+1
   CurrentHeight = min(Heights[Left], Heights[Right])
   while Left != a or Right != b do:
      if Left == a:
         # We cannot go to left anymore
         Right += 1
         CurrentHeight = min(CurrentHeight, Heights[Right])
      elif Right == b:
         # We cannot go to right anymore
         Left -= 1
         CurrentHeight = min(CurrentHeight, Heights[Left])
      elif Heights[Left-1] >= CurrentHeight:
         # We can go to Left with CurrentHeight
         Left -= 1
      elif Heights[Right+1] >= CurrentHeight:
         # We can go to right with CurrentHeight
         Right += 1
      else:
         # Choose the next CurrentHeight
         CurrentHeight = max(Heights[Left-1], Heights[Right+1])
      Result = max(Result, (Right - Left + 1) * CurrentHeight)
   end
   return Result
 
print FindLargestRectangle(0, len(Heights)-1)

رابطه ی بازگشتی پیچیدگی زمانی این الگوریتم:

که اگر آن را حل کنيم، بدست می آوريم که پيچيدگی زمانی اين الگوريتم از مرتبه ی می باشد.

ايده ی اين روش اين است که عريض ترين مستطيلی که هم ارتفاع با يکی از مستطيل ها باشد بازه ای شامل مستطيل هايي با ارتفاع های بزرگتر مساوی اين ارتفاع می باشد.

مستطيل ها را به ترتيب ارتفاع بررسی می کنيم. در هر مرحله يک سری بازه داريم (که در ابتدا خالی است) و در هر مرحله بازه ی مستطيلی که بررسی می شود را به اين بازه های اضافه می کنيم. (منظورم از بازه، بازه ای از محور x ها است که هر مستطيل اشغال می کند. مثلا برای سمت چپ ترين مستطيل، اين بازه [0,1]، برای بعدی [1,2] و … می باشد.)

پس از اضافه کردن بازه ی مستطيل جاری، ممکن است اين بازه از سمت چپ يا از سمت راست به يک بازه ای که قبلا اضافه شده بچسبد، يا اينکه دو بازه را به هم بچسباند، يا اينکه يک بازه ی جديد ايجاد کند. به هر حال بازه ای که پس از اضافه کردن بازه ی مستطيل جاری شامل بازه ی مستطيل جاری می باشد، عريض ترين بازه ای است که هم ارتفاع با اين مستطيل می تواند باشد.

(البته استثنا در مورد مستطيل های هم ارتفاعی که عريض ترين بازه يشان يکسان است وجود دارد، ولی چون بالاخره چنين بازه ای بعد از اضافه کردن آخرين مستطيل بوجود می آيد، خللی در درستی الگوريتم ما ايجاد نمی کند.)

اميدوارم توانسته باشم ايده ی اين روش را خوب توضيح بدهم.

برای نگهداری بازه ها، از دو آرايه با نام های Left و Right که طول آن ها N (که N تعداد مستطيل ها می باشد) استفاده می کنيم که مقدار اوليه ی عناصر آن ها 1- می باشد. برای يک بازه عضو متناظر با سمت راست ترين عضو آن بازه در آرايه ی Right انديس سمت چپ ترين عضو آن بازه را نگه داری می کند و عضو متناظر با سمت چپ ترين عضو آن بازه در آرايه ی Left انديس سمت راست ترين عضو آن بازه را نگه داری می کند. چون هميشه ما فقط با دو سر بازه کار داريم، مقاديری که در اعضای متناظر با ساير اعضای آرايه نگه داری می شود برای ما اهميتی ندارد. در اين صورت، pseudo-code الگوريتم فوق به صورت زير خواهد بود:

def FindLargestRectangle():
   Result = 0
   SortedArray = [0, 1, … , N-1]
   SortedArray.SortUsingHeights() # This can be done in O(N*log(N))
   for i in 0 .. N-1:
      CurrentLeft  = SortedArray[i]
      CurrentRight = SortedArray[i]
      if CurrentRight < N-1 and Right[CurrentRight + 1] != -1:
         # if there is another range in the right side of current range,
         # then extend current range
         CurrentRight = Right[CurrentRight + 1]
      if CurrentLeft > 0 and Left[CurrentLeft - 1] != -1:
         # if there is another range in the left side of current range,
         # then extend current range
         CurrentLeft  = Left[CurrentLeft - 1]
      # Update Result
      Result = Max(Result, (CurrentRight - CurrentLeft + 1) * Heights[SortedArray[i]])
      # Update Range Arrays
      Right[CurrentLeft] = CurrentRight
      Left[CurrentRight] = CurrentLeft
   end for
   return Result
 
print FindLargestRectangle()

پيچيدگی زمانی اين الگوريتم از مرتبه ی می باشد.