طراحی سایت و برنامه نویسی

آموزش طراحی سایت و برنامه نویسی

طراحی سایت و برنامه نویسی

آموزش طراحی سایت و برنامه نویسی

خطایابی نرم افزار — پادکست پرسش و پاسخ

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

پادکست پیرامون خطایابی نرم افزار

00:00

02:56

ذخیره کردن این فایل صوتی: لینک دانلود

نسخه نوشتاری

یکی از موضوعات مهمی که من همیشه در دوره‌های آموزشی برنامه‌نویسی، در آموزش‌های گوناگون، در هر کلاس درسی و به طور کلی در هر جایی که فرصت بوده به آن اشاره می‌کنم این است که کاربر با هر نرم‌افزاری که کار می‌کند – مثلا «متلب» (MATLAB) یا هر کامپایلری – ممکن است در هر جا خطایی به کاربر نمایش داده می‌شود. این متن خطا مهم‌ترین چیزی است که فرد باید در آن لحظه بخواند. خیلی وقت‌ها پاسخ کاربر و پاسخ اشکال موجود، در همان‌جا است. یعنی مثلا در متن خطا گفته شده این کار را باید انجام دهید و واقعا با انجام همان کار مشکل حل می‌شود.

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

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

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

برای دانلود کردن و شنیدن دیگر پادکست‌های دکتر سید مصطفی کلامی هریس در مجله فرادرس، روی این لینک [+] کلیک کنید.

منبع: فرادرس

مشاوره شنبه 29 تیر 1398 ساعت 14:15

0 نظر

آرگومان های پیش فرض در ++C — به زبان ساده

در این مقاله با معنی آرگومان های پیش فرض و روش استفاده از آن‌ها و اعلان‌های ضروری برای کاربردشان آشنا می‌شوید. در برنامه‌نویسی ++C می‌توانید مقادیر پیش‌فرض را برای پارامترهای تابع ارائه کنید.

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

Overload در تابع های ++C — راهنمای کاربردی

کار کردن با آرگومان‌های پیش‌فرض

آرگومان های پیش فرض

مثال

در ادامه به یک مثال در همین رابطه می‌پردازیم.

آرگومان پیش‌فرض

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// ++C Program to demonstrate working of default argument
#include <iostream>
using namespace std;
void display(char = '*', int = 1);
int main()
{
    cout << "No argument passed:\n";
    display();
    
    cout << "\nFirst argument passed:\n";
    display('#');
    
    cout << "\nBoth argument passed:\n";
    display('$', 5);
    return 0;
}
void display(char c, int n)
{
    for(int i = 1; i <= n; ++i)
    {
        cout << c;
    }
    cout << endl;
}

خروجی

No argument passed:
*

First argument passed:
#

Both argument passed:
$$$$$

در برنامه فوق، می‌توانید مقدار پیش‌فرض انتساب یافته به آرگومان‌ها را ببینید:

1
void display(char = '*', int = 1);

در ابتدا، تابع ()display بدون ارسال هیچ پارامتری فراخوانی می‌شود. در این حالت، تابع ()display از هر دو آرگومان c = * و n = 1 استفاده می‌کند.

سپس در دفعه دوم تنها آرگومان نخست با استفاده از تابع ارسال می‌شود. در این حالت، تابع از مقدار پیش‌فرض نخست ارسالی استفاده نمی‌کند. بدین ترتیب از پارامتر واقعی ارسالی به عنوان آرگومان نخست # = c استفاده می‌کنیم و مقدار پیش‌فرض n=1 به عنوان آرگومان دوم می‌گیرد.

زمانی که ()display برای بار سوم فراخوانی می‌شود، هر دو آرگومان ارسال می‌شوند، آرگومان‌های پیش‌فرض مورد استفاده قرار نمی‌گیرند. بنابراین مقدار $ = c و n=5 استفاده می‌شوند.

خطاهای رایج هنگام استفاده از آرگومان پیش‌فرض

1
void add(int a, int b = 3, int c, int d = 4);

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

1
void add(int a, int b = 3, int c, int d);

تابع فوق نیز کامپایل نخواهد شد. شما باید مقادیر پیش‌فرض را برای هر آرگومان پس از b ذکر کنید.

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

1
void add(int a, int b, int c, int d = 4);

مهم نیست که از آرگومان‌های پیش‌فرض چگونه استفاده می‌کنید، چون یک تابع باید همواره طوری نوشته شود که تنها یک منظور را اجرا کند.

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

منبع: فرادرس

مشاوره شنبه 29 تیر 1398 ساعت 14:12

0 نظر

آشنایی با آپاچی اسپارک (Spark) و پایتون — راهنمای مقدماتی

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

مقدمه‌ای بر آپاچی اسپارک

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

اغلب افراد دچار این سوءتفاهم هستند که اسپارک جایگزینی برای هادوپ (Hadoop) است، اما باید بدانند که اسپارک تنها یک رقیب برای فریمورک map-reduce هادوپ محسوب می‌شود. بدین ترتیب با توجه به سریع‌تر بودن اسپارک یکی از کوتاه‌ترین مسیرهای یادگیری را برای توسعه‌دهندگان دارد و با در نظر گرفتن این نکته که از سوی شرکت‌های بزرگی در بازار استفاده می‌شود، یک مهارت ساده و مؤثر جهت ارتقا در رزومه هر توسعه‌دهنده‌ای به حساب می‌آید.

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

آپاچی اسپارک

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

نکته قابل توجه

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

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

1. نصب لوکال

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

اگر زمان برایتان مهم است و حوصله سر و کله زدن با نصب موارد مختلف را ندارید، بهتر است از دردسر دوری کنید و به گزینه‌های 2 و 3 این مقاله مراجعه نمایید.

آن چه برای نصب لوکال نیاز دارید یک نرم‌افزار Virtual Box، سیستم اوبونتو و زمان و صبر به مقدار کافی است.

Virtual Box (+) اپلیکیشنی است که امکان اجرای یک رایانه مجازی روی سیستم را به شما می‌دهد. این جایی است که ما اوبونتو، یک سیستم عامل مبتنی بر لینوکس و اسپارک را نصب خواهیم کرد. اگر هم اینک از سیستم اوبونتو استفاده می‌کنید می‌توانید این مرحله را رد کنید.
نرم‌افزار Virtual Box را از این لینک (+) دانلود کنید و میزبان را بسته به سیستم عامل خود ویندوز یا OS X انتخاب نمایید. زمانی که دانلود پایان یافت، روی فایل دابل کلیک کنید و با پیگیری دستورالعمل‌ها و تنظیمات پیش‌فرض آن را نصب کنید.

در ادامه به این لینک (+) بروید و اوبونتو را دانلود کنید. البته اوبونتو دسکتاپ ترجیح بیشتری دارد. پس از این مرحله، باید یک فایل دانلود شده iso. در اختیار داشته باشید.

بدین ترتیب می‌توانید به اپلیکیشن Virtual box بروید. این نرم‌افزار در ابتدا اساساً خالی است. می‌توانید با کلیک کردن روی دکمه New یک ماشین مجازی جدید به آن اضافه کنید. برای این ماشین یک نام تعیین کرده، گزینه Linux را انتخاب کنید و در ادامه Next را بزنید.

آپاچی اسپارک

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

در وهله دوم نوبت به هارد دیسک می‌رسد. این گزینه را نیز می‌توانید روی مقدار پیشنهادشده 8 گیگابایت رها کنید و گزینه ایجاد یک ماشین مجازی جدید را کلیک کنید و VDI (یعنی ایمیج دیسک ویرچوال باکس) را در پنجره نوع فایل هارد دیسک انتخاب نمایید و next را بزنید.

در وهله سوم نوبت به فضای ذخیره‌سازی می‌رسد. شما می‌توانید اندازه با تخصیص دینامیک یا ثابت را انتخاب کنید. اندازه ثابت پیشنهاد می‌شود، چون سرعت ورودی/ خروجی بهتری دارد. 20 گیگابایت می‌تواند مقدار مناسبی باشد. در ادامه روی Create کلیک کنید.

آپاچی اسپارک

زمانی که روی Create کلیک کردید، ایجاد ماشین کمی طول می‌کشد. زمانی که ماشین مجازی آماده شد، می‌توانید به صفحه اصلی ویرچوال باکس بازگردید، چنان که می‌بینید ماشین جدیدی که تنظیم کردیم اینک ایجاد شده است.

آپاچی اسپارک

به صورت پیش‌فرض این ماشین خاموش است، اما می‌توانید آن را با دو بار کلیک کردن روشن کنید. در طی نخستین زمان روشن شدن از شما خواسته می‌شود که دیسک آغازین را انتخاب کید. این امر مهمی است و جایی است که به ایمیج Ubuntu.iso که قبلاً دانلود کرده‌اید اشاره می‌کنید. فایل Ubuntu.iso را انتخاب کرده و روی start کلیک کنید. بدین ترتیب اوبونتو روی ماشین مجازی نصب می‌شود. در این مسیر گزینه‌های نصب زیادی در اختیار شما قرار می‌گیرند و می‌توانید آن را سفارشی‌سازی کرده و یا مقادیر پیش‌فرض را حفظ کنید. در هر صورت مشکلی وجود ندارد و در انتها یک سیستم عامل آماده به کار در اختیار شما قرار می‌گیرد که البته از نوع مجازی است.

نخستین کاری که باید درون ماشین مجازی انجام دهید این است که مطمئن شود پایتون از قبل نصب شده است. به این منظور به اپلیکیشن ترمینال اوبونتو بروید و عبارت python3 را وارد کرده و اینتر کنید. بدین ترتیب یک خروجی مانند تصویر زیر باید مشاهده کنید:

آپاچی اسپارک

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

سپس قصد داریم یک سری نرم‌افزارها را نصب کنیم که برای اجرای اسپارک روی ماشین مجازی ضروری هستند.

Jupyter Notebook

نصب ژوپیتر نت‌بوک یکی از ساده‌ترین روش‌ها برای تعامل با پایتون و نوشتن کد خوب محسوب می‌شود. به این منظور روی همان ترمینال یا یک پنجره جدید، دستور زیر را وارد کنید:

pip3 install jupyter

این دستور باید سیستم ژوپیتر نت‌بوک را نصب کند. زمانی که کار پایان یافت، می‌توانید با وارد کردن دستور زیر در ترمینال آن را تست کنید:

jupyter notebook

بدین ترتیب اینترفیس ژوپیتر نت‌بوک در یک مرورگر باز می‌شود. این امر نشان می‌دهد که نصب نت‌بوک کامل بوده است.

جاوا

اکنون نوبت به نصب جاوا رسیده است که برای اجرای اسپارک ضروری است. در یک پنجره ترمینال دیگر این دستورها را یکی پس از دیگری وارد کنید:

sudo apt-get update
sudo apt-get install default-jre

نخستین دستور مکانیسم apt-get ما را به‌روزرسانی خواهد کرد و پس از آن جاوا با استفاده از دستور دوم نصب می‌شود.

اسکالا

به طور مشابه اسکالا را نیز نصب می‌کنیم.

sudo apt-get install scala

برای تست کردن این نکته که آیا نصب موفق بوده است یا نه می‌توانید دستور زیر را وارد کنید که به نسخه اسکالای نصب شده اشاره می‌کند:

scala –version

نصب Py4j

اکنون نوبت به نصب یک کتابخانه پایتون رسیده است که جاوا و اسکالا را به پایتون وصل می‌کند:

pip3 install py4j

اسپارک و هادوپ

اکنون که به انتها رسیده‌ایم باید اسپارک و هادوپ را نصب کنیم. به این منظور به این لینک (+) بروید و نسخه اسپارک را مستقیماً دانلود کنید. مطمئن شوید که این گام را روی ماشین مجازی انجام می‌دهید تا مستقیماً روی آن دانلود شود.

یک ترمینال جدید باز کنید و مطمئن شوید که در همان مکانی قرار دارید که فایل‌ها دانلود شده بودند. می‌توانید به پوشه صحیح cd کرده و دستور زیر را اجرا کنید (توجه داشته باشید که نام فایل بسته به نسخه اسپارک مورد استفاده می‌تواند متفاوت باشد):

sudo tar -zxvf spark-2.1.0-bin-hadoop2.7.tgz

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

export SPARK_HOME=’home/ubuntu/spark-2.1.0-bin-hadoop2.7'
export PATH=@SPARK_HOME:$PATH
export PYTHONPATH=$SPARK_HOME/python:$PYTHONPATH
export PYSPARK_DRIVER_PYTHON=”jupyter”
export PYSPARK_DRIVER_PYTHON_OPTS=”notebook”
export PYSPARK_PYTHON=python3

اگر در تمام طول این مسیر با ما همراه بوده و دستورها را اجرا کرده باشید، اینک همه چیز آماده شده است. یک پنجره ترمینال باز کنید و به مسیر زیر cd کنید:

cd /spark-2.1.0-bin-hadoop2.7/python

زمانی که در دایرکتوری صحیح قرار گرفتید، ژوپیتر نت‌بوک را باز کنید:

jupyter notebook

اکنون باید مرورگر خود را ببینید که با سیستم ژوپیتر نت‌بوک باز شده است. یک نت‌بوک جدید پایتون ایجاد کنید و در یک سلول خالی دستور زیر را وارد کرده و Ctrl+Enter بزنید.

import pyspark

اسپارک

اینک ماشین مجازی ما به همراه اسپارک نصب شده آماده است و می‌توانیم کار خود را آغاز کنیم.

2. Databricks

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

با این که Databricks به منظور استفاده از سوی شرکت‌هایی که به سمت کلان‌داده و محاسبات توزیع یافته حرکت می‌کنند طراحی شده است، اما یک نسخه کامیونیتی نیز دارد که برای منظور ما مناسب است.

برای شروع کار به این لینک (+) بروید و در نسخه کامیونیتی ثبت نام کنید. شما باید آدرس ایمیل خود را اعتبارسنجی کنید تا بتوانید برای نخستین بار وارد شوید. زمانی که این کار را انجام دادید امکان کار با محیط نت‌بوک پایتون که از قبل نصب شده را خواهید یافت.

Spark

هنگامی که لاگین کردید، روی Create a Blank Notebook کلیک کنید تا کار را آغاز کنید. در این هنگام یک ژوپیتر نت‌بوک عرضه می‌شود که می‌توان کد پایتون را در هر سلول آن وارد کرده و به صورت مستقل اجرا کرد.

Databricks برای اسپارک ساخته شده است و نیازی به نگرانی در مورد نصب موارد اضافی وجود ندارد. شما می‌توانید بی‌درنگ عبارت spark را در سلول نخست وارد کنید و با زدن کلیدهای Ctrl+Enter یا دکمه پخش کوچک در سمت راست سلول آن را اجرا کنید:

Spark

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

نکته: ابزار Databricks به دلایل مختلف جالب است و مهم‌تر از همه این که مخزن داده عظیمی ارائه می‌کند که با استفاده از آن می‌توانید همه قدرتش را مورد آزمایش قرار دهید.

برای بررسی اجمالی آن چه که Databricks ارائه می‌کند، باید با استفاده از دستور magic به «file system» مربوط به Databricks بروید. در یک سلول جدید عبارت fs% را وارد کنید و سپس ls را وارد کرده و سلول را اجرا کنید. بدین ترتیب مسیرهای dbfs را به صورت فهرست‌بندی شده مشاهده می‌کنید:

Spark

سپس روی ls /databricks-datasets/ کلیک کنید تا همه مجموعه داده‌های موجود را ببینید. اگر به هر کدام از آن‌ها علاقه‌مند هستید می‌توانید به سادگی از آن‌ها در کد خود استفاده کنید. برای نمونه ما داده‌های ساده people/people.json/ را دوست داریم و می‌خواهیم از آن در کد خود استفاده کنیم. این کار به صورت زیر میسر است:

data = spark.read.json(“/databricks-datasets/samples/people/people/.json”)

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

3. Google Colab

Google Colaboratory (+) یک محیط رایگان ژوپیتر نت‌بوک است که شباهت زیادی به Databricks دارد و به طور کامل روی کلود اجرا می‌شود، اما همه شهرت آن از این ناشی نمی‌شود که یک سیستم رایگان نت‌بوک است، بلکه بخش عمده آن ناشی از ارائه GPU رایگان است. بله درست شنیده‌اید، Colab امکان استفاده رایگان از GPU را فراهم می‌سازد. این یک پیشنهاد عالی برای افرادی است که می‌خواهند یادگیری ماشین را بیاموزند. البته این موضوع مجزایی است و با موضوع مقاله ما که معرفی اسپارک است ارتباط مستقیمی ندارد.

برای استفاده از Google Colab به یک مرورگر وب، یک اتصال اینترنتی خوب و یک حساب گوگل نیاز دارید. به این لینک (+) بروید و از طریق حساب گوگل وارد شوید تا صفحه‌ای برای ایجاد «New Python 3 Notebook» مشاهده کنید. در ادامه یک نت‌بوک بسازید.

این مرحله ما را وارد سرزمین آشنایی می‌کند که یک نت‌بوک پایتون یا یک سلول خالی است. Google Colab برخلاف Databricks آماده استفاده با اسپارک است و از این رو نیازی به همان تنظیمات اندک آغازین هم نداریم. اگر pyspark را در سلول خالی اجرا کنید با خطایی به صورت زیر مواجه خواهید شد.

اسپارک

در ادامه این خطا را اصلاح می‌کنیم. Google Colab هم شبیه به یک ماشین مجازی و هم یک نت‌بوک عمل می‌کند. دستور زیر را در یک سلول خالی وارد کرده و با زدن Ctrl+Enter جاوا را نصب می‌کنیم:

!apt install openjdk-8-jdk-headless -qq > /dev/null

با استفاده از علامت (!) در ابتدای دستور آن را در یک پوسته (Shell) اجرا می‌کنیم و نشان می‌دهیم که یک کد پایتون نیست. اینک اسپارک و هادوپ را دانلود می‌کنیم.

!wget -q http://www-eu.apache.org/dist/spark/spark-2.3.3/spark-2.3.3-bin-hadoop2.7.tgz

زمانی که دانلود پایان یافت، می‌توانید با اجرای ls -l! همانند یک پوسته لینوکسی در عمل ببینید که آیا فایل دانلود شده یا نه.

اسپارک

چنان که می‌بینید فایل با فرمت یک فایل zip دانلود شده، پس باید آن را از حالت فشرده خارج کنیم:

!tar xf spark-2.3.3-bin-hadoop2.7.tgz

اکنون قبل از شروع به کار با اسپارک باید چند کار دیگر نیز انجام دهیم که تنظیم متغیرهای جاوا و اسپارک به صورت زیر است:

import os
os.environ[“JAVA_HOME”] = “/usr/lib/jvm/java-8-openjdk-amd64”
os.environ[“SPARK_HOME”] = “/content/spark-2.3.3-bin-hadoop2.7”

این همه کاری است که برای راه‌اندازی نیاز داریم. اکنون به بررسی کد نمونه زیر می‌پردازیم:

اسپارک

کد فوق با ایجاد یک SparkSession جدید اقدام به مقداردهی اسپارک می‌کند و سپس یک فریم داده جدید اسپارک به صورت on fly با استفاده از list comprehension پایتون می‌سازد و در نهایت فریم داده نمایش می‌یابد. آن را در یک سلول جدید امتحان کنید.

سخن پایانی

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

منبع: فرادرس

مشاوره شنبه 29 تیر 1398 ساعت 14:11

0 نظر

یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده

«مسیر همیلتونی» (Hamiltonian Path) در یک گراف غیر جهت‌دار، مسیری است که در آن هر «راس» (Vertex) دقیقا یک‌بار مشاهده می‌شود. یک «دور همیلتونی» یا «مدار همیلتونی» (Hamiltonian Cycle | Hamiltonian Circuit)، یک مسیر همیلتونی است که در آن از آخرین راس به اولین راس یک «یال» (Edge) وجود دارد. در ادامه، روشی جهت بررسی اینکه آیا در یک گراف داده شده، دور همیلتونی وجود دارد یا خیر بررسی می‌شود. همچنین، در صورت وجود دور، مسیر آن را چاپ می‌کند. در واقع، با استفاده از یک روش ساده و یک روش «پس‌گرد» (Backtracking)، بررسی می‌شود که آیا در یک گراف دور همیلتونی وجود دارد یا خیر و در صورت وجود، مسیر در خروجی چاپ می‌شود. ورودی و خروجی تابع لازم برای این کار به صورت زیر هستند.

یافتن دور همیلتونی در گراف

برای یافتن دور همیلتونی در گراف، به طور کلی به صورت زیر عمل می‌شود.

ورودی:

یک آرایه دوبُعدی [graph[V][V که در آن V تعداد راس‌ها در گراف و [graph[V][V «ماتریس همسایگی» (Adjacency Matrix) گراف است. مقدار [graph[i][j در صورت وجود یک یال مستقیم از راس i به راس j برابر با یک و در غیر این صورت، [graph[i][j برابر با صفر است.

خروجی:

یک آرایه [path[V باید حاوی یک مسیر همیلتونی باشد. [path[i باید راس i در مسیر همیلتونی را نمایش دهد. همچنین، کد باید مقدار false را در صورت عدم وجود دور همیلتونی در گراف، بازگرداند.

برای مثال، دور همیلتونی در گراف زیر به صورت {۰ ،۳ ،۴ ،۲ ،۱ ، ۰} است.

(0)--(1)--(2)
|    / \   |
|    / \   | 
|    / \   |
(3)-------(4)

گراف زیر حاوی هیچ دور همیلتونی نیست.

(0)--(1)--(2)
|    / \   |
|    / \   | 
|    / \   |
(3)       (4)

الگوریتم ساده (Naive Algorithm)

الگوریتم ساده‌ای که در زیر ارائه شده، همه پیکربندی‌های ممکن برای راس‌ها را ارائه می‌کند و پیکربندی که محدودیت های داده شده را ارضا می‌کند، باز می‌گرداند. به تعداد !n، پیکربندی ممکن وجود دارد.

1
2
3
4
5
6
7
8
9
10
11
while there are untried conflagrations
{
   generate the next configuration
   if ( there are edges between two consecutive vertices of this
      configuration and there is an edge from the last vertex to 
      the first ).
   {
      print this configuration;
      break;
   }
}

یافتن دور همیلتونی با الگوریتم پس‌گرد (Backtracking Algorithm)

این الگوریتم یک آرایه مسیر خالی می‌سازد و راس ۰ را به آن اضافه می‌کند. در ادامه، دیگر راس‌ها را با آغاز از راس ۱ به آرایه اضافه می‌کند؛ اما پیش از اضافه کردن یک راس، بررسی می‌کند که آیا با راس پیشین اضافه شده مجاور است یا خیر و همچنین، بررسی می‌کند که راس، پیش از این به آرایه اضافه نشده باشد. اگر چنین راسی پیدا شود، یال به عنوان بخشی از راهکار اضافه می‌شود. اگر راس پیدا نشود، مقدار false بازگردانده می‌شود.

پیاده‌سازی الگوریتم پس‌گرد برای مساله یافتن دور همیلتونی در گراف

در ادامه، پیاده‌سازی الگوریتم پس‌گرد برای مساله یافتن دور همیلتونی در گراف در زبان‌های برنامه‌نویسی گوناگون ارائه شده است.

++C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
/* C++ program for solution of Hamiltonian  
Cycle problem using backtracking */
#include <bits/stdc++.h> 
using namespace std; 
  
// Number of vertices in the graph  
#define V 5  
  
void printSolution(int path[]);  
  
/* A utility function to check if  
the vertex v can be added at index 'pos'  
in the Hamiltonian Cycle constructed  
so far (stored in 'path[]') */
bool isSafe(int v, bool graph[V][V],  
            int path[], int pos)  
{  
    /* Check if this vertex is an adjacent  
    vertex of the previously added vertex. */
    if (graph [path[pos - 1]][ v ] == 0)  
        return false;  
  
    /* Check if the vertex has already been included.  
    This step can be optimized by creating 
    an array of size V */
    for (int i = 0; i < pos; i++)  
        if (path[i] == v)  
            return false;  
  
    return true;  
}  
  
/* A recursive utility function  
to solve hamiltonian cycle problem */
bool hamCycleUtil(bool graph[V][V],  
                  int path[], int pos)  
{  
    /* base case: If all vertices are  
    included in Hamiltonian Cycle */
    if (pos == V)  
    {  
        // And if there is an edge from the  
        // last included vertex to the first vertex  
        if (graph[path[pos - 1]][path[0]] == 1)  
            return true;  
        else
            return false;  
    }  
  
    // Try different vertices as a next candidate  
    // in Hamiltonian Cycle. We don't try for 0 as  
    // we included 0 as starting point in in hamCycle()  
    for (int v = 1; v < V; v++)  
    {  
        /* Check if this vertex can be added  
        // to Hamiltonian Cycle */
        if (isSafe(v, graph, path, pos))  
        {  
            path[pos] = v;  
  
            /* recur to construct rest of the path */
            if (hamCycleUtil (graph, path, pos + 1) == true)  
                return true;  
  
            /* If adding vertex v doesn't lead to a solution,  
            then remove it */
            path[pos] = -1;  
        }  
    }  
  
    /* If no vertex can be added to  
    Hamiltonian Cycle constructed so far,  
    then return false */
    return false;  
}  
  
/* This function solves the Hamiltonian Cycle problem  
using Backtracking. It mainly uses hamCycleUtil() to  
solve the problem. It returns false if there is no  
Hamiltonian Cycle possible, otherwise return true  
and prints the path. Please note that there may be  
more than one solutions, this function prints one  
of the feasible solutions. */
bool hamCycle(bool graph[V][V])  
{  
    int *path = new int[V];  
    for (int i = 0; i < V; i++)  
        path[i] = -1;  
  
    /* Let us put vertex 0 as the first vertex in the path. 
    If there is a Hamiltonian Cycle, then the path can be  
    started from any point of the cycle as the graph is undirected */
    path[0] = 0;  
    if (hamCycleUtil(graph, path, 1) == false )  
    {  
        cout << "\nSolution does not exist";  
        return false;  
    }  
  
    printSolution(path);  
    return true;  
}  
  
/* A utility function to print solution */
void printSolution(int path[])  
{  
    cout << "Solution Exists:"
            " Following is one Hamiltonian Cycle \n";  
    for (int i = 0; i < V; i++)  
        cout << path[i] << " ";  
  
    // Let us print the first vertex again 
    // to show the complete cycle  
    cout << path[0] << " ";  
    cout << endl; 
}  
  
// Driver Code  
int main()  
{  
    /* Let us create the following graph  
        (0)--(1)--(2)  
        | / \ |  
        | / \ |  
        | / \ |  
        (3)-------(4) */
    bool graph1[V][V] = {{0, 1, 0, 1, 0},  
                        {1, 0, 1, 1, 1},  
                        {0, 1, 0, 0, 1},  
                        {1, 1, 0, 0, 1},  
                        {0, 1, 1, 1, 0}};  
      
    // Print the solution  
    hamCycle(graph1);  
      
    /* Let us create the following graph  
    (0)--(1)--(2)  
    | / \ |  
    | / \ |  
    | / \ |  
    (3) (4) */
    bool graph2[V][V] = {{0, 1, 0, 1, 0},  
                         {1, 0, 1, 1, 1},  
                         {0, 1, 0, 0, 1},  
                         {1, 1, 0, 0, 0},  
                         {0, 1, 1, 0, 0}};  
  
    // Print the solution  
    hamCycle(graph2);  
  
    return 0;  
}  
  
// This is code is contributed by rathbhupendra 

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/* C program for solution of Hamiltonian Cycle problem 
   using backtracking */
#include<stdio.h> 
  
// Number of vertices in the graph 
#define V 5 
  
void printSolution(int path[]); 
  
/* A utility function to check if the vertex v can be added at 
   index 'pos' in the Hamiltonian Cycle constructed so far (stored 
   in 'path[]') */
bool isSafe(int v, bool graph[V][V], int path[], int pos) 
{ 
    /* Check if this vertex is an adjacent vertex of the previously 
       added vertex. */
    if (graph [ path[pos-1] ][ v ] == 0) 
        return false; 
  
    /* Check if the vertex has already been included. 
      This step can be optimized by creating an array of size V */
    for (int i = 0; i < pos; i++) 
        if (path[i] == v) 
            return false; 
  
    return true; 
} 
  
/* A recursive utility function to solve hamiltonian cycle problem */
bool hamCycleUtil(bool graph[V][V], int path[], int pos) 
{ 
    /* base case: If all vertices are included in Hamiltonian Cycle */
    if (pos == V) 
    { 
        // And if there is an edge from the last included vertex to the 
        // first vertex 
        if ( graph[ path[pos-1] ][ path[0] ] == 1 ) 
           return true; 
        else
          return false; 
    } 
  
    // Try different vertices as a next candidate in Hamiltonian Cycle. 
    // We don't try for 0 as we included 0 as starting point in in hamCycle() 
    for (int v = 1; v < V; v++) 
    { 
        /* Check if this vertex can be added to Hamiltonian Cycle */
        if (isSafe(v, graph, path, pos)) 
        { 
            path[pos] = v; 
  
            /* recur to construct rest of the path */
            if (hamCycleUtil (graph, path, pos+1) == true) 
                return true; 
  
            /* If adding vertex v doesn't lead to a solution, 
               then remove it */
            path[pos] = -1; 
        } 
    } 
  
    /* If no vertex can be added to Hamiltonian Cycle constructed so far, 
       then return false */
    return false; 
} 
  
/* This function solves the Hamiltonian Cycle problem using Backtracking. 
  It mainly uses hamCycleUtil() to solve the problem. It returns false 
  if there is no Hamiltonian Cycle possible, otherwise return true and 
  prints the path. Please note that there may be more than one solutions, 
  this function prints one of the feasible solutions. */
bool hamCycle(bool graph[V][V]) 
{ 
    int *path = new int[V]; 
    for (int i = 0; i < V; i++) 
        path[i] = -1; 
  
    /* Let us put vertex 0 as the first vertex in the path. If there is 
       a Hamiltonian Cycle, then the path can be started from any point 
       of the cycle as the graph is undirected */
    path[0] = 0; 
    if ( hamCycleUtil(graph, path, 1) == false ) 
    { 
        printf("\nSolution does not exist"); 
        return false; 
    } 
  
    printSolution(path); 
    return true; 
} 
  
/* A utility function to print solution */
void printSolution(int path[]) 
{ 
    printf ("Solution Exists:"
            " Following is one Hamiltonian Cycle \n"); 
    for (int i = 0; i < V; i++) 
        printf(" %d ", path[i]); 
  
    // Let us print the first vertex again to show the complete cycle 
    printf(" %d ", path[0]); 
    printf("\n"); 
} 
  
// driver program to test above function 
int main() 
{ 
   /* Let us create the following graph 
      (0)--(1)--(2) 
       |   / \   | 
       |  /   \  | 
       | /     \ | 
      (3)-------(4)    */
   bool graph1[V][V] = {{0, 1, 0, 1, 0}, 
                      {1, 0, 1, 1, 1}, 
                      {0, 1, 0, 0, 1}, 
                      {1, 1, 0, 0, 1}, 
                      {0, 1, 1, 1, 0}, 
                     }; 
  
    // Print the solution 
    hamCycle(graph1); 
  
   /* Let us create the following graph 
      (0)--(1)--(2) 
       |   / \   | 
       |  /   \  | 
       | /     \ | 
      (3)       (4)    */
    bool graph2[V][V] = {{0, 1, 0, 1, 0}, 
                      {1, 0, 1, 1, 1}, 
                      {0, 1, 0, 0, 1}, 
                      {1, 1, 0, 0, 0}, 
                      {0, 1, 1, 0, 0}, 
                     }; 
  
    // Print the solution 
    hamCycle(graph2); 
  
    return 0; 
}

پایتون

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
# Python program for solution of 
# hamiltonian cycle problem 
  
class Graph(): 
    def __init__(self, vertices): 
        self.graph = [[0 for column in range(vertices)]\ 
                            for row in range(vertices)] 
        self.V = vertices 
  
    ''' Check if this vertex is an adjacent vertex  
        of the previously added vertex and is not  
        included in the path earlier '''
    def isSafe(self, v, pos, path): 
        # Check if current vertex and last vertex  
        # in path are adjacent 
        if self.graph[ path[pos-1] ][v] == 0: 
            return False
  
        # Check if current vertex not already in path 
        for vertex in path: 
            if vertex == v: 
                return False
  
        return True
  
    # A recursive utility function to solve  
    # hamiltonian cycle problem 
    def hamCycleUtil(self, path, pos): 
  
        # base case: if all vertices are  
        # included in the path 
        if pos == self.V: 
            # Last vertex must be adjacent to the  
            # first vertex in path to make a cyle 
            if self.graph[ path[pos-1] ][ path[0] ] == 1: 
                return True
            else: 
                return False
  
        # Try different vertices as a next candidate  
        # in Hamiltonian Cycle. We don't try for 0 as  
        # we included 0 as starting point in in hamCycle() 
        for v in range(1,self.V): 
  
            if self.isSafe(v, pos, path) == True: 
  
                path[pos] = v 
  
                if self.hamCycleUtil(path, pos+1) == True: 
                    return True
  
                # Remove current vertex if it doesn't  
                # lead to a solution 
                path[pos] = -1
  
        return False
  
    def hamCycle(self): 
        path = [-1] * self.V 
  
        ''' Let us put vertex 0 as the first vertex  
            in the path. If there is a Hamiltonian Cycle,  
            then the path can be started from any point 
            of the cycle as the graph is undirected '''
        path[0] = 0
  
        if self.hamCycleUtil(path,1) == False: 
            print "Solution does not exist\n"
            return False
  
        self.printSolution(path) 
        return True
  
    def printSolution(self, path): 
        print "Solution Exists: Following is one Hamiltonian Cycle"
        for vertex in path: 
            print vertex, 
        print path[0], "\n"
  
# Driver Code 
  
''' Let us create the following graph 
      (0)--(1)--(2) 
       |   / \   | 
       |  /   \  | 
       | /     \ | 
      (3)-------(4)    '''
g1 = Graph(5) 
g1.graph = [ [0, 1, 0, 1, 0], [1, 0, 1, 1, 1],  
             [0, 1, 0, 0, 1,],[1, 1, 0, 0, 1],  
             [0, 1, 1, 1, 0], ] 
  
# Print the solution 
g1.hamCycle(); 
  
''' Let us create the following graph 
      (0)--(1)--(2) 
       |   / \   | 
       |  /   \  | 
       | /     \ | 
      (3)       (4)    '''
g2 = Graph(5) 
g2.graph = [ [0, 1, 0, 1, 0], [1, 0, 1, 1, 1],  
           [0, 1, 0, 0, 1,], [1, 1, 0, 0, 0],  
           [0, 1, 1, 0, 0], ] 
  
# Print the solution 
g2.hamCycle(); 
  
# This code is contributed by Divyanshu Mehta 

جاوا

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
/* Java program for solution of Hamiltonian Cycle problem 
   using backtracking */
class HamiltonianCycle 
{ 
    final int V = 5; 
    int path[]; 
  
    /* A utility function to check if the vertex v can be 
       added at index 'pos'in the Hamiltonian Cycle 
       constructed so far (stored in 'path[]') */
    boolean isSafe(int v, int graph[][], int path[], int pos) 
    { 
        /* Check if this vertex is an adjacent vertex of 
           the previously added vertex. */
        if (graph[path[pos - 1]][v] == 0) 
            return false; 
  
        /* Check if the vertex has already been included. 
           This step can be optimized by creating an array 
           of size V */
        for (int i = 0; i < pos; i++) 
            if (path[i] == v) 
                return false; 
  
        return true; 
    } 
  
    /* A recursive utility function to solve hamiltonian 
       cycle problem */
    boolean hamCycleUtil(int graph[][], int path[], int pos) 
    { 
        /* base case: If all vertices are included in 
           Hamiltonian Cycle */
        if (pos == V) 
        { 
            // And if there is an edge from the last included 
            // vertex to the first vertex 
            if (graph[path[pos - 1]][path[0]] == 1) 
                return true; 
            else
                return false; 
        } 
  
        // Try different vertices as a next candidate in 
        // Hamiltonian Cycle. We don't try for 0 as we 
        // included 0 as starting point in in hamCycle() 
        for (int v = 1; v < V; v++) 
        { 
            /* Check if this vertex can be added to Hamiltonian 
               Cycle */
            if (isSafe(v, graph, path, pos)) 
            { 
                path[pos] = v; 
  
                /* recur to construct rest of the path */
                if (hamCycleUtil(graph, path, pos + 1) == true) 
                    return true; 
  
                /* If adding vertex v doesn't lead to a solution, 
                   then remove it */
                path[pos] = -1; 
            } 
        } 
  
        /* If no vertex can be added to Hamiltonian Cycle 
           constructed so far, then return false */
        return false; 
    } 
  
    /* This function solves the Hamiltonian Cycle problem using 
       Backtracking. It mainly uses hamCycleUtil() to solve the 
       problem. It returns false if there is no Hamiltonian Cycle 
       possible, otherwise return true and prints the path. 
       Please note that there may be more than one solutions, 
       this function prints one of the feasible solutions. */
    int hamCycle(int graph[][]) 
    { 
        path = new int[V]; 
        for (int i = 0; i < V; i++) 
            path[i] = -1; 
  
        /* Let us put vertex 0 as the first vertex in the path. 
           If there is a Hamiltonian Cycle, then the path can be 
           started from any point of the cycle as the graph is 
           undirected */
        path[0] = 0; 
        if (hamCycleUtil(graph, path, 1) == false) 
        { 
            System.out.println("\nSolution does not exist"); 
            return 0; 
        } 
  
        printSolution(path); 
        return 1; 
    } 
  
    /* A utility function to print solution */
    void printSolution(int path[]) 
    { 
        System.out.println("Solution Exists: Following" + 
                           " is one Hamiltonian Cycle"); 
        for (int i = 0; i < V; i++) 
            System.out.print(" " + path[i] + " "); 
  
        // Let us print the first vertex again to show the 
        // complete cycle 
        System.out.println(" " + path[0] + " "); 
    } 
  
    // driver program to test above function 
    public static void main(String args[]) 
    { 
        HamiltonianCycle hamiltonian = 
                                new HamiltonianCycle(); 
        /* Let us create the following graph 
           (0)--(1)--(2) 
            |   / \   | 
            |  /   \  | 
            | /     \ | 
           (3)-------(4)    */
        int graph1[][] = {{0, 1, 0, 1, 0}, 
            {1, 0, 1, 1, 1}, 
            {0, 1, 0, 0, 1}, 
            {1, 1, 0, 0, 1}, 
            {0, 1, 1, 1, 0}, 
        }; 
  
        // Print the solution 
        hamiltonian.hamCycle(graph1); 
  
        /* Let us create the following graph 
           (0)--(1)--(2) 
            |   / \   | 
            |  /   \  | 
            | /     \ | 
           (3)       (4)    */
        int graph2[][] = {{0, 1, 0, 1, 0}, 
            {1, 0, 1, 1, 1}, 
            {0, 1, 0, 0, 1}, 
            {1, 1, 0, 0, 0}, 
            {0, 1, 1, 0, 0}, 
        }; 
  
        // Print the solution 
        hamiltonian.hamCycle(graph2); 
    } 
} 
// This code is contributed by Abhishek Shankhadhar

سی شارپ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
// C# program for solution of Hamiltonian  
// Cycle problem using backtracking 
using System; 
  
public class HamiltonianCycle 
{ 
    readonly int V = 5; 
    int []path; 
  
    /* A utility function to check  
    if the vertex v can be added at  
    index 'pos'in the Hamiltonian Cycle 
    constructed so far (stored in 'path[]') */
    bool isSafe(int v, int [,]graph, 
                int []path, int pos) 
    { 
        /* Check if this vertex is  
        an adjacent vertex of the 
        previously added vertex. */
        if (graph[path[pos - 1], v] == 0) 
            return false; 
  
        /* Check if the vertex has already  
        been included. This step can be 
        optimized by creating an array 
        of size V */
        for (int i = 0; i < pos; i++) 
            if (path[i] == v) 
                return false; 
  
        return true; 
    } 
  
    /* A recursive utility function 
    to solve hamiltonian cycle problem */
    bool hamCycleUtil(int [,]graph, int []path, int pos) 
    { 
        /* base case: If all vertices  
        are included in Hamiltonian Cycle */
        if (pos == V) 
        { 
            // And if there is an edge from the last included 
            // vertex to the first vertex 
            if (graph[path[pos - 1],path[0]] == 1) 
                return true; 
            else
                return false; 
        } 
  
        // Try different vertices as a next candidate in 
        // Hamiltonian Cycle. We don't try for 0 as we 
        // included 0 as starting point in in hamCycle() 
        for (int v = 1; v < V; v++) 
        { 
            /* Check if this vertex can be  
            added to Hamiltonian Cycle */
            if (isSafe(v, graph, path, pos)) 
            { 
                path[pos] = v; 
  
                /* recur to construct rest of the path */
                if (hamCycleUtil(graph, path, pos + 1) == true) 
                    return true; 
  
                /* If adding vertex v doesn't  
                lead to a solution, then remove it */
                path[pos] = -1; 
            } 
        } 
  
        /* If no vertex can be added to Hamiltonian Cycle 
        constructed so far, then return false */
        return false; 
    } 
  
    /* This function solves the Hamiltonian  
    Cycle problem using Backtracking. It  
    mainly uses hamCycleUtil() to solve the 
    problem. It returns false if there 
    is no Hamiltonian Cycle possible,  
    otherwise return true and prints the path. 
    Please note that there may be more than  
    one solutions, this function prints one  
    of the feasible solutions. */
    int hamCycle(int [,]graph) 
    { 
        path = new int[V]; 
        for (int i = 0; i < V; i++) 
            path[i] = -1; 
  
        /* Let us put vertex 0 as the first 
        vertex in the path. If there is a  
        Hamiltonian Cycle, then the path can be 
        started from any point of the cycle  
        as the graph is undirected */
        path[0] = 0; 
        if (hamCycleUtil(graph, path, 1) == false) 
        { 
            Console.WriteLine("\nSolution does not exist"); 
            return 0; 
        } 
  
        printSolution(path); 
        return 1; 
    } 
  
    /* A utility function to print solution */
    void printSolution(int []path) 
    { 
        Console.WriteLine("Solution Exists: Following" + 
                        " is one Hamiltonian Cycle"); 
        for (int i = 0; i < V; i++) 
            Console.Write(" " + path[i] + " "); 
  
        // Let us print the first vertex again 
        //  to show the complete cycle 
        Console.WriteLine(" " + path[0] + " "); 
    } 
  
    // Driver code 
    public static void Main(String []args) 
    { 
        HamiltonianCycle hamiltonian = 
                                new HamiltonianCycle(); 
        /* Let us create the following graph 
        (0)--(1)--(2) 
            | / \ | 
            | / \ | 
            | /     \ | 
        (3)-------(4) */
        int [,]graph1= {{0, 1, 0, 1, 0}, 
            {1, 0, 1, 1, 1}, 
            {0, 1, 0, 0, 1}, 
            {1, 1, 0, 0, 1}, 
            {0, 1, 1, 1, 0}, 
        }; 
  
        // Print the solution 
        hamiltonian.hamCycle(graph1); 
  
        /* Let us create the following graph 
        (0)--(1)--(2) 
            | / \ | 
            | / \ | 
            | /     \ | 
        (3)     (4) */
        int [,]graph2 = {{0, 1, 0, 1, 0}, 
            {1, 0, 1, 1, 1}, 
            {0, 1, 0, 0, 1}, 
            {1, 1, 0, 0, 0}, 
            {0, 1, 1, 0, 0}, 
        }; 
  
        // Print the solution 
        hamiltonian.hamCycle(graph2); 
    } 
} 
  
// This code contributed by Rajput-Ji

خروجی:

Solution Exists: Following is one Hamiltonian Cycle
 0  1  2  4  3  0

Solution does not exist

توجه به این نکته لازم است که قطعه کد بالا، همیشه دورهایی که از صفر شروع می‌شوند را چاپ می‌کند. نقطه شروع نباید اهمیتی داشته باشد، زیرا یک دور می‌تواند از هر راسی آغاز شود. افرادی که قصد تغییر دادن نقطه شروع را دارند، باید دو تغییر در کد بالا اعمال کنند. تغییر «;path[0] = 0» به «;path[0] = s» که در آن، s نقطه شروع جدید است. همچنین، باید حلقه «(++for (int v = 1; v < V; v» در ()hamCycleUtil، به «(++for (int v = 0; v < V; v» تغییر پید

منبع: فرادرس

مشاوره جمعه 28 تیر 1398 ساعت 15:53

0 نظر

توسعه یک اپلیکیشن MacOS ساده — از صفر تا صد

مشاوره جمعه 28 تیر 1398 ساعت 15:52

0 نظر

332
1
...
44
45
صفحه 46
47
48
...
67

طراحی سایت و برنامه نویسی

ابر برجسب

جدیدترین یادداشت‌ها

بایگانی

جستجو

خطایابی نرم افزار — پادکست پرسش و پاسخ

پادکست پیرامون خطایابی نرم افزار

نسخه نوشتاری

آرگومان های پیش فرض در ++C — به زبان ساده

کار کردن با آرگومان‌های پیش‌فرض

مثال

خطاهای رایج هنگام استفاده از آرگومان پیش‌فرض

آشنایی با آپاچی اسپارک (Spark) و پایتون — راهنمای مقدماتی

مقدمه‌ای بر آپاچی اسپارک

نکته قابل توجه

1. نصب لوکال

جاوا

اسکالا

نصب Py4j

اسپارک و هادوپ

2. Databricks

3. Google Colab

سخن پایانی

یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده

یافتن دور همیلتونی در گراف

ورودی:

خروجی:

الگوریتم ساده (Naive Algorithm)

یافتن دور همیلتونی با الگوریتم پس‌گرد (Backtracking Algorithm)

پیاده‌سازی الگوریتم پس‌گرد برای مساله یافتن دور همیلتونی در گراف

++C

C

پایتون

جاوا

سی شارپ

توسعه یک اپلیکیشن MacOS ساده — از صفر تا صد