ورود به حساب ثبت نام جدید فراموشی کلمه عبور
برای ورود به حساب کاربری خود، نام کاربری و کلمه عبورتان را در زیر وارد کرده و روی “ ورود به حساب” کلیک کنید.





اگر فرم ثبت نام برای شما نمایش داده نمیشود، اینجا را کلیک کنید.









اگر فرم بازیابی کلمه عبور برای شما نمایش داده نمیشود، اینجا را کلیک کنید.





نمایش نتایج: از 1 به 2 از 2
  1. #1
    sina
    sina
    Guest

    تکنیکهای طراحی الگوریتم - روش سیری ناپذیر

    روش سیری ناپذیر (Greedy Method) معمولا" برای حل مسایل بهینه سازی (Optimization Problems) مورد استفاده قرار می*گیرد. این مسایل غالبا" دارای تعدادی ورودی (کاندیدا) هستند که باید زیر مجموعه*ای بهینه از آنها را برای رسیدن به شرطی خاص بدست آورد. بر اساس نوع مسئله، روش سیری ناپذیر به هر کاندیدا عددی نسبت می*دهد و بهترین ورودی را بر اساس بزرگترین یا کوچکترین عدد نسبت داده شده به آنها انتخاب می*کند.

    لازم به ذکر است که:

    روش سیری ناپذیر همیشه به یک جواب بهینه (مناسبترین جواب) نمی*رسد و گاهی فقط تقریبی از جواب را بدست می*آورد.
    حتی برای مسائلی که دقیقا" با این روش قابل حل هستند، ممکن است تعیین درستی این روش امری دشوار باشد.

    در این روش روال الگوریتم به این صورت است که از بین کاندیداهای ورودی (C)، تک به تک بهترین کاندیدا را انتخاب کرده (Select) و در صورتی که اضافه کردن کاندیدای انتخاب شده به مجموعه کاندیداهای از پیش انتخاب شده (S) بتواند مجموعه جواب محتملی ایجاد کند (Feasible)، آن را به مجموعه اضافه می*کنیم. عمل انتخاب کاندیداها را وقتی متوقف می*کنیم که یا دیگر کاندیدایی وجود نداشته نباشد یا اینکه مجموعه جواب محتمل بتواند به عنوان مجمومه جواب مسئله (Solution) قبول شود.

    همانگونه که در ابتدا گفته شد٬ تابع Select با استفاده از یک روال عینی (Objective Function) بهترین کاندیدا را انتخاب می*کند.

    function Select(C: set of condidates) return cadidate

    function Feasible(S: set of candidates) return boolean

    function Solution(S: set of candidates) return boolean



    function Gready(C: set of condidates) return set of condidates

    var

    S: set of condidates;

    x: candidate;

    begin

    S := {} /* S is the set in which we construct solutions */

    while not Solution(S) and (C <> {}) loop

    X := Select(C)

    C := C - {x}

    if Feasible(S union {x}) then

    S := S union {X}

    end if

    end loop

    if Solution(S) then

    return S

    else

    return {}

    end if

    end Gready



    مثال:

    می خواهیم بقیه پول مشتری را با کمترین تعداد پول خرد بپردازیم.

    در این مثال مجموعه جواب احتمالی (Feasible) آن مجموعه از پول خردهاست که جمع آنها کمتر یا برابر با مقدار پولی باشد که قرار است به مشتری برگردانده شود. و مجموعه جواب مسئله (Solution) مجموعه*ای از پول خردهاست که جمع آنها دقیقا" برابر با مقدار پول برگشتی مشتری است.

    بدیهی است برای داشتن کمترین تعداد پول خرد، بهترین انتخاب٬ انتخاب بزرگترین پول خرد است. این همان چیزی است که به آن روال عینی (Objective Function) گفتیم و تابع Select براساس آن پیاده سازی می*شود.

    function FindCoinChanges(C: coin_set; /* واحدهای پول خرد */

    K: integer) /* پولی که قرار است به مشتری برگردانده شود */

    return coin_set; /* پول خردهای جواب */

    var

    S: coin_set; /* پول خردهایی که تا کنون انتخاب شده*اند */

    Sum: iteger; /* مجموع پول خردهایی که تا کنون انتخاب شده*اند */

    X: integer;

    begin

    S := {};

    Sum := 0;

    while not (Sum = K) /* SOLUTION */ and (C <> {}) loop

    X := select the largest coin in C /* SELECT */

    C := C - {X};

    if (Sum + X <= K) /* FEASIBLE */ then

    S := S + {X}

    Sum := Sum + X

    end if

    end loop

    if (Sum = K) /* SOLUTION */ then

    return S

    else

    return {}

    end if

    end FindCoinChanges;


    با فرض داشتن پول خردهای 1 و 5 و 10 ریالی، الگوریتم هواره بهترین جواب را بر می*گرداند. اما اگر پول خرد 12 ریالی را به این مجموعه اضافه کنیم، الگوریتم الزاما"بهترین جواب را پیدا نخواهد کرد.

    به عنوان مثال:

    15 = 12 + 1 + 1 + 1


    در صورتیکه بهترین جواب عبارت است از:

    15 = 10 + 5


    در حالتی حتی ممکن است الگوریتم علارقم وجود جواب، قادر به پیدا کردن جواب نباشد. فرض کنید پول خوردهایی که داریم 2 و 3 و 5 ریالی باشند:

    6 = 5 + ?


    در صورتیکه جوابی به صورت زیر موجود است:

    6 = 3 + 3
  2. 1
  3. #2
    raziehkia
    كاربر عادي
    تاریخ عضویت
    2013 May
    نوشته ها
    1
    0
    0
    سلام یه مسئله الگوریتم دارم کی میتونه برام حل کنه؟
نمایش نتایج: از 1 به 2 از 2

اطلاعات موضوع

کاربرانی که در حال مشاهده این موضوع هستند

در حال حاضر 1 کاربر در حال مشاهده این موضوع است. (0 کاربران و 1 مهمان ها)

موضوعات مشابه

  1. ( مشکل ) خطا در اجرای برنامه مدیریت پایگاه بسیج
    توسط i3ooter در انجمن برنامه نویسی در 6 VB
    پاسخ: 21
    آخرين نوشته: 2014-09-15, 05:52 PM
  2. خبر کشورهای آسیایی بالاترین سرعت اینترنت را دارند
    توسط Prof.MohammadGh در انجمن تازه‌های دنیای کامپیوتر و فناوری
    پاسخ: 0
    آخرين نوشته: 2012-10-20, 10:56 AM
  3. پاسخ: 0
    آخرين نوشته: 2012-07-29, 03:55 AM
  4. 3ساعت بسیار زیبای jQuery
    توسط vahid4251 در انجمن طراحی وب (Web Design)
    پاسخ: 0
    آخرين نوشته: 2012-02-13, 04:13 PM

کلمات کلیدی این موضوع

مجوز های ارسال و ویرایش

  • شما نمیتوانید موضوع جدیدی ارسال کنید
  • شما امکان ارسال پاسخ را ندارید
  • شما نمیتوانید فایل پیوست کنید.
  • شما نمیتوانید پست های خود را ویرایش کنید
  •  

Content Relevant URLs by vBSEO 3.6.0 RC 2