close
دانلود فیلم
فروش پروژه پیمایش گراهام با نرم افزار MATLAB
پنجشنبه 23 آذر 1396

ADS [A1]




در اين سایت
در كل اينترنت
اطلاعات کاربری

عضو شويد

نام کاربری :
رمز عبور :

فراموشی رمز عبور؟

عضویت سریع
نام کاربری :
رمز عبور :
تکرار رمز :
ایمیل :
نام اصلی :
کد امنیتی : * کد امنیتیبارگزاری مجدد
کدهای اختصاصی
آخرین ارسال های انجمن

  • ترجمه متون انگلیسی شما با قیمتی استثنایی کلیک کنید
  • پروژه خود را برای ما ارسال کنید تا ذقیق تر به خواسته خود برسید
  • كد: 1098

    عنوان پروژه: فروش پروژه پیمایش گراهام با نرم افزار MATLAB

    قالب بندی: m

    دسته: كامپيوتر - MATLAB

    قيمت: 20.000 تومان

    قابليت اجرا در نرم افزار: MATLAB

    شرح مختصر:

    فروش پروژه پیمایش گراهام با نرم افزار MATLAB

    عكس خروجی برنامه

    برای خريد اين پروژه با شماره ۰۹۳۸۸۱۱۶۱۶۲

    يا آدرس ایمیل  smyt1338@gmail.com در تماس باشيد.


     

     

     

     

      پیمایش گراهام روشی است برای محاسبه پوش محدب مجموعه متناهی از نقاط صفحه که پیچیدگی زمانی آن O(n logn) است. این الگوریتم به افتخار رونالد گراهام که نسخهٔ اصلی الگوریتم را در ۱۹۷۲ منتشر کرد نامگذاری شده است. این الگوریتم تمامی راس‌های مرزی پوش محدب به صورت مرتب می‌یابد.

     

     

    الگوریتم

    اولین گام در این الگوریتم یافتن نقطه‌ای با کمترین y است. اگر چند نقطه با کمترین y وجود داشت، در این مجموعه نقطه با کمترین x انتخاب خواهد شد. این نقطه را P می‌نامیم. این مرحله به اندازه (O(n زمان می‌برد که n تعداد نقاط می‌باشد.

    سپس مجموعه نقاط باید بر حسب افزایش زاویه‌ای که آنها و نقطه P با محور X می‌سازند، مرتب شوند. از هر الگوریتم مرتب‌سازی برای این این مرحله می‌توان استفاده کرد به عنوان مثال مرتب‌سازی هرمی که پیچیدگی زمانی آن (O(n log n است.

    برای افزایش سرعت محاسبه لازم نیست زاویهٔ واقعی که این نقاط با محور X می‌سازند محاسبه شود در عوض، محاسبه کسینوس این زاویه کافیست.

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

    گراهام.png

    بازهم برای تعیین اینکه آیا سه نقطه تشکیل یک چرخش به چپ را می‌دهند یا چرخش به راست، نیازی نیست زاویه واقعی میان دو پاره خط محاسبه شود و در واقع می‌توانید تنها با حسابی ساده به این هدف برسید. برای سه نقطه (x1,y1)، (x2,y2)و (x3,y3)، محاسبه جهت ضرب خارجی دو برداری که با نقاط (x1,y1) , (x2,y2)و (x1,y1), (x3,y3)تعریف می‌شوداز طریق تعیین علامت عبارت (x2 − x1)(y3 − y1) − (y2 − y1)(x3 − x1)میسر است. اگر این عبارت صفر شد نقاط هم راستا هستند. اگر مثبت شد نقاط یک گردش به چپ و در غیر اینصورت یک گردش به راست را تشکیل می‌دهند.

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

    پیچیدگی زمانی

    مرتب سازی نقاط دارای پیچیدگی زمانی (O(n logn می‌باشد. در حالی که ممکن است به نظر برسد پیچیدگی زمانی حلقه از O(n2) می‌باشد. زیرا برای هر نقطه به عقب برمی گردد تا چک کند آیا هر یک از نقاط قبلی چرخش به راست ایجاد می‌کنند، اما در واقع از (O(n می‌باشد زیرا هر نقطه در نهایت از هر جهت چه گردش به راست و چه گردش به چپ، دو بار در نظر گرفته می‌شود. هر نقطه فقط یک بار به عنوان نقطه (x2,y2)در گردش به چپ در نظر گرفته می‌شود (زیرا الگوریتم به سراغ نقطه (x3,y3) بعد از آن می‌رود), و هم چنین به عنوان نقطه (x2,y2)در گردش به راست (زیرا نقطه (x2,y2) حذف می‌شود). بنابراین پیچیدگی زمانی کلی برابر است با (O(n logn.

    شبه کد

    ابتدا تعریف

    # Three points are a counter-clockwise turn if ccw > 0, clockwise if
    # ccw < 0, and collinear if ccw = 0 because ccw is a determinant that
    # gives the signed area of the triangle formed by p1, p2 and p3.
    function ccw(p1, p2, p3):
        return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x)
    

    سپس نتایج در آرایه points ذخیره می‌شود.

    let N           = number of points
    let points[N+1] = the array of points
    swap points[1] with the point with the lowest y-coordinate
    sort points by polar angle with points[1]
    
    # We want points[0] to be a sentinel point that will stop the loop.
    let points[0] = points[N]
    
    # M will denote the number of points on the convex hull.
    let M = 2
    for i = 3 to N:
        # Find next valid point on convex hull.
        while ccw(points[M-1], points[M], points[i]) <= 0:
              # Check if first points are collinear, if so ignore unnecessary points.
              if M is 2:
                      swap points[M] with points[i]
                      i += 1
              else
                      M -= 1
    
        # Update M and swap points[i] to the correct place.
        M += 1
        swap points[M] with points[i]
    

    این شبه کد از کتاب Sedgewick and Wayne's Algorithms چاپ چهارم گرفته شده‌است


    برچسب : [Post_Tags_Title] ,
    نویسنده : سید محمد
    ارسال نظر برای این مطلب

    نام
    ایمیل (منتشر نمی‌شود) (لازم)
    وبسایت
    :) :( ;) :D ;)) :X :? :P :* =(( :O @};- :B /:) :S
    نظر خصوصی
    مشخصات شما ذخیره شود ؟ [حذف مشخصات] [شکلک ها]
    کد امنیتی
    آمار سایت
    آمار مطالب
    کل مطالب : 1200
    کل نظرات : 113
    آمار کاربران
    افراد آنلاین : 2
    تعداد اعضا : 119

    آمار بازدید
    بازدید امروز : 319
    باردید دیروز : 602
    گوگل امروز : 1
    گوگل دیروز : 2
    بازدید هفته : 2,254
    بازدید ماه : 9,549
    بازدید سال : 237,588
    بازدید کلی : 730,057
    خبرنامه
    براي اطلاع از آپدیت شدن سایت در خبرنامه سایت عضو شويد تا جديدترين مطالب به ايميل شما ارسال شود

    جستجو