سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه شظرنج

[daneshvar.amrollahi]

مکانی برای بحث درمورد سوال زیر:


حرکات اسب در صفحه شظرنج - گراف و الگوریتم - ۱۵ امتیازی

برنامه ای بنوسید که با گرفتن یک عدد n، مشخص کند که آیا می توان با شروع از خانه ای دلخواه در یک صفحه شظرنج n*n، تنها با حرکات اسب و عدم ورود به خانه ی تکراری (مراجعه شده)، به همه ی خانه ها راه یافت یا خیر؟ (خیلی به اردر برنامه توجه نکنید - الگوریتم برنامه مورد نظر است)

تاپیک مربوطه: http://www.sampadia.com/forum/index.php/topic,106140.0.html

مدت زمان پاسخ گویی به سوال: ۴ روز

*ویرایش:
۱ - ارائه ی راه حل به کمک هر مبحثی (ترکیبیات، گراف، الگوریتم یا ...) بلامانع است و در این زمینه هیچ محدودیتی ندارید!

۲- امتیاز این سوال از ۱۰ به ۱۵ تغییر یافت. ۵ نمره ی دیگر مربوط به کد سوال است. یعنی هر که بتواند کد این سوال را بنویسد، از امتیاز کامل ۱۵ برخوردار خواهد شد. در غیر این صورت با ارائه راه حل تئوری، می تواند ۱۰ امتیاز کسب کند.

×علی[میم] : با تشکر ویژه بابت استارتی که به مسابقه زدی !!!!!

 

[Anita H]

پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

فرض کن صفحه ی شطرنج یه گراف باشه که خونه های اون متناظر با راسهای گراف هستن و دو راس(خونه) به هم یال دارن اگر و فقط اگر بشه با مهره ی اسب و با یه حرکت از اون دو تا خونه به همدیگه رفت!‌(پیچیده گفتم )
حالا از یه خونه شروع میکنیم dfs میزنیم میریم جلو
(الآن باس توضیح بدم چرا الگوریتم درسته؟ واضحه دیگه )
اردرش هم احتمالن ان دو هست چون از هر خونه ی ارایه فقط یه بار میگذریم

ویرایش: آقا غلط کردم، سوالو اشتباه فهمیده بودم کلن، اردر این الگوریتم n^4 هست یحتمل

 

[daneshvar.amrollahi]

پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

فرض کن صفحه ی شطرنج یه گراف باشه که خونه های اون متناظر با راسهای گراف هستن و دو راس(خونه) به هم یال دارن اگر و فقط اگر بشه با مهره ی اسب و با یه حرکت از اون دو تا خونه به همدیگه رفت!‌(پیچیده گفتم )
حالا از یه خونه شروع میکنیم dfs میزنیم میریم جلو
(الآن باس توضیح بدم چرا الگوریتم درسته؟ واضحه دیگه )
اردرش هم احتمالن ان دو هست چون از هر خونه ی ارایه فقط یه بار میگذریم

آره میدونم توضیحش سخته. اصلا ماهیت dfs همینه مگه نه؟‌ اگر بتونید دقیق تر بگید چه بهتر...

روی اردرش بیشتر فکر کن. اگر واقعا اردر n^2 باشه، یعنی اگر کدش نوشته بشه و تا 10000 بهش ورودی بدیم، زیر ۱ ثانیه جواب میده. چون تا ۱۰ به توان ۸ عملیات زیر ۱ ثانیه میتونه انجام بشه. آیا همچنین چیزی امکان داره؟

 

[rezaezio]

پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

فرض کن صفحه ی شطرنج یه گراف باشه که خونه های اون متناظر با راسهای گراف هستن و دو راس(خونه) به هم یال دارن اگر و فقط اگر بشه با مهره ی اسب و با یه حرکت از اون دو تا خونه به همدیگه رفت!‌(پیچیده گفتم )
حالا از یه خونه شروع میکنیم dfs میزنیم میریم جلو
(الآن باس توضیح بدم چرا الگوریتم درسته؟ واضحه دیگه )
اردرش هم احتمالن ان دو هست چون از هر خونه ی ارایه فقط یه بار میگذریم

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

نکته : منظورم این نبود که مساله مورد نظر تاپیک الگوریتم چندجمله ای نداره !! سوتفاهم نشه "

 

[daneshvar.amrollahi]

پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

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

خود دور همیلتونی رو نمی خوایم! یعنی این که اول به کدوم خونه بره و بعدش به کجا و ... .
فقط میخواهیم ببینیم آیا این گراف دور هملیتونی دارد یا نه ( که با dfs زدن میشه حل کرد ). شاید راه های دیگری هم داشته باشد...

 

[rezaezio]

پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

خود دور همیلتونی رو نمی خوایم! یعنی این که اول به کدوم خونه بره و بعدش به کجا و ... .
فقط میخواهیم ببینیم آیا این گراف دور هملیتونی دارد یا نه ( که با dfs زدن میشه حل کرد ). شاید راه های دیگری هم داشته باشد...

بررسی وجود دور همیلتونی تو یک گراف دلخواه هم الگوریتم چند جمله ای نداره، داره ؟!
+ این مساله جواب داره از (O(1 !

 

[daneshvar.amrollahi]

پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

بررسی وجود دور همیلتونی تو یک گراف دلخواه هم الگوریتم چند جمله ای نداره، داره ؟!
+ این مساله جواب داره از (O(1 !

یعنی یه الگوریتمی هست که دور هملیتونی توی گراف پیدا می کنه (از اردر ۱) ؟

آره دیگه در واقع انگار داریم می پرسیم: گراف صفحه شظرنج n*n، همیلتونی هستش یا نه...

الگوریتم چند جمله ای چیه؟ یه توضیح می دیدید؟

*ویرایش: متن سوال رو اصلاح کردم. میتونید دوباره بخونید : هر کسی میتونه با هر الگوریتم و ابزاری، اینجا پاسخ بنویسه! ممکنه چند تا راه حل داشته باشیم!

 

[rezaezio]

پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

یعنی یه الگوریتمی هست که دور هملیتونی توی گراف پیدا می کنه (از اردر ۱) ؟

آره دیگه در واقع انگار داریم می پرسیم: گراف صفحه شظرنج n*n، همیلتونی هستش یا نه...

الگوریتم چند جمله ای چیه؟ یه توضیح می دیدید؟

نه باو !
توی یه گراف عمومی، مساله پیدا کردن دور همیلتونی و یا حتی بررسی وجود دور همیلتونی، در زمان چند جمله‌ای تا حالا حل نشده !!!!
ولی گفتم که واسه مساله‌ی تاپیک، یعنی بررسی وجود دور همیلتونی در گراف خاص صفحه شطرنج، میشه راه گفت از (O(1 !!!!

الگوریتم چند جمله‌ای یعنی الگوریتمی که اردرش، چند جمله‌ای بر حسب n باشه ! مثلا (O(n ^ 2 ، یا (O(n ^ 3
ولی بعضی الگوریتم ها اُردرشون نمایی هست ! مثلا از اُردر دو به توان n ! ویا اُردر n فاکتوریل !!!!

++ فک کنم تاپیکُ ریختیم به هم ! اگه چیزیو نفهمیدی خصوصی بگو

×علی[میم] : بسیار درخواست میشه ، خصوصی نرین ، عمومی بحث کنین یخ ملت باز شه !!!!

 

[daneshvar.amrollahi]

پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

نه باو !
توی یه گراف عمومی، مساله پیدا کردن دور همیلتونی و یا حتی بررسی وجود دور همیلتونی، در زمان چند جمله‌ای تا حالا حل نشده !!!!
ولی گفتم که واسه مساله‌ی تاپیک، یعنی بررسی وجود دور همیلتونی در گراف خاص صفحه شطرنج، میشه راه گفت از (O(1 !!!!

الگوریتم چند جمله‌ای یعنی الگوریتمی که اردرش، چند جمله‌ای بر حسب n باشه ! مثلا (O(n ^ 2 ، یا (O(n ^ 3
ولی بعضی الگوریتم ها اُردرشون نمایی هست ! مثلا از اُردر دو به توان n ! ویا اُردر n فاکتوریل !!!!

++ فک کنم تاپیکُ ریختیم به هم ! اگه چیزیو نفهمیدی خصوصی بگو

مشکلی نیست. بحث های عمومی هستند و به درد همه می خورن! تاپیک به هم نریخته.

صورت سوال هم که گراف کلی نیست . گراف صفحه شطرنج موردنظر هستش. اگر برای جواب این سوال، کسی الگوریتمی از (O(1 گفتش (با توضیحات) احتمالا میشه بهترین جواب!

 

[Anita H]

‌

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

+یکی منو از سردرگمی دربیاره

خطاب به پایینی: باو مشکل من اصلن اردر 1 و این حرفا نیست، مشکل من اون قسمتی از حرفه دیمنه که میگه باید دنبال دور همیلتونی بگردیم.

 

[daneshvar.amrollahi]

پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

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

+یکی منو از سردرگمی دربیاره

یه راهش همون dfs هستش که گفتید. اما آقای سلطانی میگن برای گراف این سوال، میشه با اردر ۱ فهمید هملیتونی هستش یا نه که اگر باشه، یعنی میشه به همه ی خونه ها رفت.

 

[rezaezio]

پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

ببین آقا الان یه گراف ساختیم، که راس هاش خونه های صفحه شطرنج هستن و دو راس به هم یال دارن اگر و فقط اگر با یه حرکت اسب بتونیم بین خانه های این دو راس حرکت کرد !

حالا توی این گراف دنبال چی هستیم ؟ مگه دنبال مسیر همیلتونی نمیگردیم ؟ آیا میشه تو یه گراف ساده مسیر همیلتونی در زمان چند جمله‌ای پیدا کرد ؟

 

[Anita H]

پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

ببین آقا الان یه گراف ساختیم، که راس هاش خونه های صفحه شطرنج هستن و دو راس به هم یال دارن اگر و فقط اگر با یه حرکت اسب بتونیم بین خانه های این دو راس حرکت کرد !

حالا توی این گراف دنبال چی هستیم ؟ مگه دنبال مسیر همیلتونی نمیگردیم ؟ آیا میشه تو یه گراف ساده مسیر همیلتونی در زمان چند جمله‌ای پیدا کرد ؟

آره!
نه ممکن نیست

پ.ن: خب اول نوشته بودی دنبال دور همیلتونی بگردیم

 

[daneshvar.amrollahi]

پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

میدونم مسابقه به اتمام نرسید و این تنها سوالش بود!

مهلتش که تموم شده!

بیاید اینم کدش!

http://paste.ubuntu.com/8096669/

 

[Anita H]

پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

میدونم مسابقه به اتمام نرسید و این تنها سوالش بود!

مهلتش که تموم شده!

بیاید اینم کدش!

http://paste.ubuntu.com/8096669/

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

 

[daneshvar.amrollahi]

پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

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

چرا فکر کنم. میگید پیداکردن مسیر هملیتونی الگوریتم دیگه ای داره؟
من با این dfs نوشتم! اگر ایرادی داره بگید!

بعد مگه فرقی میکنه از کدوم خونه شروع کنه؟