دور و مسیر اویلری

تعاریف :

گراف G را اویلری می گوئیم اگر و فقط اگر همبند باشد و درجه تمام رئوس آن زوج باشد .

گراف G را نیمه اویلری می گوئیم اگر و فقط اگر همبند باشد و حداکثر 2 رأس درجه فرد داشته باشد .

مسیر بسته ای که که از یک رأس شروع شده و از تمامی یال های گراف دقیقا یکبار می گذرد و به نقطه شروع باز می گردد را دور اویلری گوئیم .

مسیری که از یک رأس شروع شده و از تمامی یال های گراف دقیقا یکبار می گذرد و در نقطه ای دیگر متوقف می شود ، مسیر اویلری گوئیم .

برای پیدا کردن دور(مسیر) اویلری در یک راف ، کافیست شرط اویلری بودن رو چک کنیم .

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

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

برای بدست آوردن دور(مسیر) الگوریتم خطی نسبت به تعداد یالها( (O(E ) وجود داره .

الگوریتم :

با کمک DFS گراف را پیمایش می کنیم . هر بار که از روی یک یال گذشتیم ، یال مورد نظر رو از گراف حذف می کنیم . زمان بازگشت از DFS رأس فعلی رو به مسیر اضافه می کنیم .

نکته : تو گراف اویلری ، تو هر راس نحوه انتخاب یال بعدی مهم نیست .

نکته : تو گراف های نیمه اویلری ، تو هر راس حداکثر 2 بار DFS فراخوانی میشه .

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

به اضافه کردن این دور به ابتدای مسیری که قبلا پیدا کرده بودیم ، یک مسیر اویلری برای گراف پیدا کردیم .

به عنوان مثال اگر در گراف زیر از نقطه 1 شروع کنیم و به رأس 2 بریم ، مسیر اولیه پیدا شده ولی هنوز یال استفاده نشده وجود داره . لذا دوباره از 1 شروع می کنیم و دور اویلری گراف باقیمونده رو پیدا می کنیم و به اول مسیر قبلی اضافه می کنیم .

1 --- 2

| \

|   \

3 --- 4

مسیر اویلری این گراف میشه :

1 3 4 1 2

کد :

int path[N], len = 0;
void DFS( int x )
{
    for( int i = 0 ; i < N ; i ++ )
        if( mat[x][i] > 0 )
        {
            mat[x][i] --;
            mat[i][x] --;
            DFS( i );
        }
    path[ len ++ ] = x;
}

برای بدست آوردن دور(مسیر) کافیه از main تابع رو برای یه نقطه شروع خوب ( رأس دلخواه در گراف اویلری و رأس فرد در گراف نیمه اویلری ) فراخوانی کنید .

بعد از اجرای DFS ، اگر مسیر شامل E|  + 1| رأس بود ، path شامل دور(مسیر) مورد نظر است .

در غیر این صورت گراف ناهمبند است لذا دور(مسیر) اویلری نداریم .

101 - Domino

لینک سوال

مفهوم سوال

سوال یه سری دومینو به ما میده و می خواد همه ی اونها رو طوری پشت سر هم بچینیم که عدد های مجاور در دومینو ها برابر باشه .

دومینو یک قطعه مستطیل شکل با ابعاد 2*1 فرض شده که روش 2 عدد بین 0 تا 6 نوشته شده .

ترتیب و جهت اصلی دومینو هارو داریم . همچنین می تونیم یه دومینو رو برعکس کنیم و بعد ازش استفاده کنیم .

به عنوان خروجی ترتیب و جهت نهایی دومینو ها یا No Solution رو از ما می خواد .

حل :

برنامه نویسی پویا - Dynamic Programming

سلام

DP روشی است که بر دو مبنای ، رابطه بازگشتی و نقطه شروع بنا شده .

این طور که برای حل سعی می کنیم مساله رو به زیر مساله های کوچک تر تقسیم کنیم و بعد از جواب های بدست اومده جواب مساله کلی رو بدست بیارم .

تا اینجای کار هیچ فرقی بین DP و روش "تقسیم و حل ( غلبه )" (Divide & Conquer ) نیست .

اما وجه تمایز این دو رویکرد در اینه که تو مسائل DP جواب زیر مساله هایی که حل کردیم رو نگه می داریم ( معمولا تو یه آرایه ) و بعد تو تکرار های بعدی از این مقادیر استفاده می کنیم ( برای جلوگیری از محاسبه دوباره ) .

برای اینکه این کار ما مفید باشه باید زیر مساله های تکراری داشته باشیم ، وگرنه خود D&C می تونه مساله رو حل کنه .

به عنوان مثال تابع فاکتوریل ( Factorial ) رو در نظر بگیرید .

یه همچنین تابعی میشه :

int Factorial ( int n )

{

    if( n < 2 )

        return 1;

    return n * Factorial( n-1 );

}

تو همین تابع ساده فرض کنید می خوایم 5! رو بدست بیاریم . تمام مقادیر 1! و 2! و 3! و 4! و 5! ساخته میشن و از بین میرن .

حالا اگر دوباره مثلا 6! رو بخوایم حساب کنیم ، دوباره باید همه مقادیر قبلی رو محاسبه کنیم و ...

حالا اگر مقدار 5! که قبلا محاسبه کرده بودیم رو جایی نگه می داشتیم چی ؟

برای محاسبه 6! فقط کافی بود مقداری که قبلا محاسبه کردیم رو استخراج کنیم و جواب رو بدست بیاریم . توجه داشته باشید که با این کار از 4 بار فراخوانی تابع جلوگیری کردیم .

برای مقادیر بزرگتر و مسائل پیچیده تر این کار فوق العاده کمک می کنه .

چجوری این کارو انجام بدیم ؟

تابع رو یکم تغییر می دیم :

int DP[100] = {0};

int Factorial ( int n )

{

    if( n < 2 )

        return 1;

    if( DP[n] != 0 )

        return DP[n];

    return DP[n] = n * Factorial( n-1 );

}

تو این حالت اگر DP[n] = 0 باشه ، یعنی هوز مقدارش رو حساب نکردیم پس مجبوریم تابع رو برای n-1 فراخوانی کنیم .

اگر DP[n] != 0 بود ، یعنی قبلا این تابع فراخوانی شده بوده و مقدارش حساب شده پس کافیه مقدار DP[n] رو برگردونیم . ( تو این حالت از فراخوانی زیرمساله های تکراری جلوگیری کردیم . )

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

تو حل مسائل DP باید برای حل تابع بازگشتی ارائه بدید . این توابع یه سری ورودی مستقل دارند و یه سری ورودی وابسته . برای اینکه بین زیر مساله های مختلف تمایز قائل بشیم باید طوری متغیر های مستقل رو انتخاب کنیم که اولا تمامی زیرمسائل رو شامل بشه و ثانیا زیر مساله ها با هم تداخل نداشته باشند .

برای ذخیره سازی زیر مسائل معمولا یه آرایه به اسم DP می گیریم که به تعداد ورودی های مستقل بُعد داره و هر بعد از اون یه اندازه بازه ای که اون ورودی می تونه تغییرات داشته باشه اندازه داره و تو هر سلول از این آرایه جواب متناظر با اون سلول قرار می گیره .

زمان مقدار دهی اولیه ، به هر سلول عددی رو نظیر می کنیم که هیچ وقت جواب تابع نباشه ( معمولا -1 )

مثلا تو تابع بالا ، فرض کردیم که مقادیر N! رو برای N < 100 نیاز داریم . پس ورودی تابع عددی بین 0 تا 99 خواهد بود و لذا اندازه DP رو 100 در نظر گرفتیم .

به عنوان مثالی پیچیده تر "ترکیب r تایی از n عضو" رو در نظر بگیریم .( n < 100 )

می دونیم این مقدار رو با ( C( n , r  نشون میدن . 

برای این مقدار رابطه بازگشتی زیر رو ارائه میدیم :

C( n , r ) = C( n-1 , r ) + C( n-1 , r-1 )

الان میبینیم که جواب مساله به دو متغیر مستقل ، وابسته شده پس برای ذخیره کردن زیرمساله ها به یه آرایه دوبعدی نیاز داریم . لذا برای محاسبه به صورت زیر عمل می کنیم .

int DP[100][100];

for( int i = 0 ; i < 100 ; i ++ )

{

    DP[i][0] = DP[i][i] = 1;

    for( int j = 1 ; j < i ; j ++ )

        DP[i][j] = DP[i-1][j] + DP[i-1][j-1];

}

همین طور میشه برای سوال های پیچیده تر این کار رو کرد .

انواع DP :

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

1. روش بالا به پایین : تو این روش هر زمان که احتیاج به زیر مساله کوچکتری داشتیم ، مقدارش رو محاسبه می کنیم . این روش معمولا با تابع بازگشتی( از نظر مفهوم برنامه نویسی ) پیاده سازی میشه . برای مثال اول ( فاکتوریل ) از این تکنیک استفاده کردیم .

خوبی : این تکنیک از نظر فهمیدن و نوشتن کد ساده است .

بدی : 

کدش طولانی میشه .

چون از تابع بازگشتی استفاده می کنیم ، احتیاج به مقدار زیادی از stack داریم . برای تابع های بزرگ یا توابعی که عمق زیادی دارند نمیشه ازش استفاده کرد .( معمولا Stack Over Flow ) میشه .

اصطلاحا به تکنیکی که تو مثال اول استفاده کردیم ، Memoization یا به اختصار Memoize هم میگیم .

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

تو مثال دوم ( ترکیب ) از این تکنیک استفاده کردیم .

خوبی : کدش کوتاهه و debug کردنش راحته .

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

برای شروع چند یه سوال ساده از این مبحث کنید بد نیست .

سوال 11703 از سایت UVa

علاوه بر این مطلب خوندن مطالب این مقاله و حل سوالاتی که توش مطرح کرده توصیه میشه .

اگر موردی هست که به نظرتون جا افتاده یا ... بگید تا اضافه کنم .