حل جدول سودوکو؟
- شروع کننده موضوع khoshi
- تاریخ شروع
parsa_spy
کاربر فوق‌حرفه‌ای
- ارسال‌ها
- 1,161
- امتیاز
- 443
- نام مرکز سمپاد
- علامه حلی تهران
- شهر
- تهران
- سال فارغ التحصیلی
- 1390
- مدال المپیاد
- مدال طلای المپیاد کامپیوتر
- دانشگاه
- صنعتی شریف
- رشته دانشگاه
- نرم افزار
پاسخ : حل جدول سودوکو؟
سودوکو الگوریتم چندجمله ای نداره! باید از backtrack استفاده کنی. اگه از bound و branch های مناسب استفاده کنی توی backtrack برنامه خیلی سریع جواب می ده.
سودوکو الگوریتم چندجمله ای نداره! باید از backtrack استفاده کنی. اگه از bound و branch های مناسب استفاده کنی توی backtrack برنامه خیلی سریع جواب می ده.
parsa_spy
کاربر فوق‌حرفه‌ای
- ارسال‌ها
- 1,161
- امتیاز
- 443
- نام مرکز سمپاد
- علامه حلی تهران
- شهر
- تهران
- سال فارغ التحصیلی
- 1390
- مدال المپیاد
- مدال طلای المپیاد کامپیوتر
- دانشگاه
- صنعتی شریف
- رشته دانشگاه
- نرم افزار
پاسخ : حل جدول سودوکو؟
backtrack یه جوری شیوه حل مساله هست! کلا یک شیوه، برای به جواب رسیدن توی مساثل NP هست!
توضیحش واقعا سخته اینجا! وقتی می خوان backtrack رو دقیق توضیح بدن، راحت 2-3 جلسه می تونه طول بکشه. کلی پیش زمینه لازم داره!
خلاصش اینکه نمی شه اینجا توضیح داد! از یکی از معلم های کامپیوتر ( اگه المپیاد بود بهتر) مدرستون بخواه که واست توضیح بده.
backtrack یه جوری شیوه حل مساله هست! کلا یک شیوه، برای به جواب رسیدن توی مساثل NP هست!
توضیحش واقعا سخته اینجا! وقتی می خوان backtrack رو دقیق توضیح بدن، راحت 2-3 جلسه می تونه طول بکشه. کلی پیش زمینه لازم داره!
خلاصش اینکه نمی شه اینجا توضیح داد! از یکی از معلم های کامپیوتر ( اگه المپیاد بود بهتر) مدرستون بخواه که واست توضیح بده.
princess
کاربر نیمه‌فعال
- ارسال‌ها
- 11
- امتیاز
- 7
- نام مرکز سمپاد
- فرزانگان تهران
- شهر
- تهران
- مدال المپیاد
- کامپیوتر ریاضی
- دانشگاه
- امیرکبیر
- رشته دانشگاه
- علوم کامپیوتر
پاسخ : حل جدول سودوکو؟
به زبون ساده تر خواستی: backtrack میشه امتحان کردن همه ی حالت ها، با branch & bound میشه با حذف حالت هایی که می دونیم به جواب نمی رسن!
واسه این که مثلا همین سودوکو رو حل کنی می تونی یه تابع بازگشتی بنویسی که هر بار یه ماتریس ( همون جدول سودوکویی که تا اینجا حل کردی ) رو به عنوان ورودی می گیره و یه عنصر بهش اضافه می کنه و دوباره خودش رو صدا می کنه. تهش دو تا اتفاق ممکنه بیفته : یا جدول حل میشه ( ابراز شادی ) یا دیگه نمی شه عنصری بهش اضافه کرد که ما عنصر فعلی ( که اضافه کرده بودیم ) رو حذف می کنیم و یکی دیگه به جاش می ذاریم. و همین داستان رو ادامه می دیم.
کلا این مدل الگوریتم سه قسمت داره: 1-چک کردن این که به جواب رسیدیم 2- پیدا کردن حالت هایی که می تونیم ادامه بدیم اونا رو 3- گذاشتن هر کدوم از حالت های مساله ی قبل
حالا این branch and bound میاد می گه تو به یه ترتیب خوبی این راس ها رو برو که زودتر بفهمی دیگه نباید ادامه بدی یا یه چیز اضافه ای ( bound ) رو حساب کن که بفهمی کدوم راه دیگه به جواب نمی رسه. تو این مساله الآن چیزی به ذهنم نمی رسه! سودوکو ام هم خوب نیست..
به زبون ساده تر خواستی: backtrack میشه امتحان کردن همه ی حالت ها، با branch & bound میشه با حذف حالت هایی که می دونیم به جواب نمی رسن!
واسه این که مثلا همین سودوکو رو حل کنی می تونی یه تابع بازگشتی بنویسی که هر بار یه ماتریس ( همون جدول سودوکویی که تا اینجا حل کردی ) رو به عنوان ورودی می گیره و یه عنصر بهش اضافه می کنه و دوباره خودش رو صدا می کنه. تهش دو تا اتفاق ممکنه بیفته : یا جدول حل میشه ( ابراز شادی ) یا دیگه نمی شه عنصری بهش اضافه کرد که ما عنصر فعلی ( که اضافه کرده بودیم ) رو حذف می کنیم و یکی دیگه به جاش می ذاریم. و همین داستان رو ادامه می دیم.
کلا این مدل الگوریتم سه قسمت داره: 1-چک کردن این که به جواب رسیدیم 2- پیدا کردن حالت هایی که می تونیم ادامه بدیم اونا رو 3- گذاشتن هر کدوم از حالت های مساله ی قبل
حالا این branch and bound میاد می گه تو به یه ترتیب خوبی این راس ها رو برو که زودتر بفهمی دیگه نباید ادامه بدی یا یه چیز اضافه ای ( bound ) رو حساب کن که بفهمی کدوم راه دیگه به جواب نمی رسه. تو این مساله الآن چیزی به ذهنم نمی رسه!
سودوکو ام هم خوب نیست..stevendeljoo
داماد مسعودی
- ارسال‌ها
- 1,351
- امتیاز
- 2,642
- نام مرکز سمپاد
- شهید بهشتی نیشابور
- شهر
- نیشابور
- سال فارغ التحصیلی
- 1391
- مدال المپیاد
- ندارم
- دانشگاه
- امیرکبیر
- رشته دانشگاه
- برق
پاسخ : حل جدول سودوکو؟
اینا سریعه؟؟؟؟؟؟؟
اینا که تقریبا آزمون و خطاست همش!
فک کنم بتونی ی سیستم امتیاز دهی خوب برای پرکردن خونه ها تعریف کنی
اول از همه آرایه تو تحلیل کن .ببین هرخونه چه اعدادی رو قبول میکنه(باتوجه به سطر و ستون و بلاکش)بعد همشو تو ی رشته بریز که مثلا هروقت به *رسیدیم توش یعنی به مشخصات خونه ی بعد وارد شدیم تو هرقسمتIوJخونه و اعداد ممکن رو بریز و جدا کن
بعد شروع کن به امتیاز دادن
اگه به جمع بندی درستی نرسیدی با توجه به خونه های سطر و ستونو بلاکش هم امتیاز بده
ی چیزی مث احتمال
درصد امکان بده!
اینا سریعه؟؟؟؟؟؟؟
اینا که تقریبا آزمون و خطاست همش!
فک کنم بتونی ی سیستم امتیاز دهی خوب برای پرکردن خونه ها تعریف کنی
اول از همه آرایه تو تحلیل کن .ببین هرخونه چه اعدادی رو قبول میکنه(باتوجه به سطر و ستون و بلاکش)بعد همشو تو ی رشته بریز که مثلا هروقت به *رسیدیم توش یعنی به مشخصات خونه ی بعد وارد شدیم تو هرقسمتIوJخونه و اعداد ممکن رو بریز و جدا کن
بعد شروع کن به امتیاز دادن
اگه به جمع بندی درستی نرسیدی با توجه به خونه های سطر و ستونو بلاکش هم امتیاز بده
ی چیزی مث احتمال
درصد امکان بده!
BLACK HOLE
کاربر فوق‌حرفه‌ای
- ارسال‌ها
- 826
- امتیاز
- 2,199
- نام مرکز سمپاد
- فرزانگان امين
- شهر
- اصفهان
- سال فارغ التحصیلی
- 1392
- مدال المپیاد
- نجوم
- دانشگاه
- University of Alberta
- رشته دانشگاه
- Computer Science
پاسخ : حل جدول سودوکو؟
NPچیه دیگه؟
معلم‌های کامپیوتر میدونن؟
اگه فقط برنامه نویسی خونده باشن؟
مشکل ۲تا شد!به نقل از پارسا :backtrack یه جوری شیوه حل مساله هست! کلا یک شیوه، برای به جواب رسیدن توی مساثل NP هست!
توضیحش واقعا سخته اینجا! وقتی می خوان backtrack رو دقیق توضیح بدن، راحت 2-3 جلسه می تونه طول بکشه. کلی پیش زمینه لازم داره!
خلاصش اینکه نمی شه اینجا توضیح داد! از یکی از معلم های کامپیوتر ( اگه المپیاد بود بهتر) مدرستون بخواه که واست توضیح بده.
NPچیه دیگه؟
معلم‌های کامپیوتر میدونن؟
اگه فقط برنامه نویسی خونده باشن؟
parsa_spy
کاربر فوق‌حرفه‌ای
- ارسال‌ها
- 1,161
- امتیاز
- 443
- نام مرکز سمپاد
- علامه حلی تهران
- شهر
- تهران
- سال فارغ التحصیلی
- 1390
- مدال المپیاد
- مدال طلای المپیاد کامپیوتر
- دانشگاه
- صنعتی شریف
- رشته دانشگاه
- نرم افزار
پاسخ : حل جدول سودوکو؟
NP مخفف Non Polynomial هست. به دسته مسائلی گفته می شه برای حلشون الگوریتم هایی از زمان چندجمله ای وجود نداره ( تعریفش این نیست در اصل، ولی همین رو می شه فرض کرد الان! مشکلی ایجاد نمی کنه)
حالا لازمه که شما ما مفهومی به نام "اُردِر" آشنایی داشته باشید، تا این تعریف رو متوجه بشید.
احتمال خیلی زیاد باید معلم های کامپیوتر بدونند! فکر می کنم که جزو واحدهای دانشگاهشون، طراحی الگوریتم هم وجود داره، که فکر می کنم این چیزا رو توش گفتن حتما.
اگه معلم المپیاد کامپیوتر (معلم الگوریتم) دارید حتما می دونه! از اون بپرس.
به نقل از ..AndromedA.. :مشکل ۲تا شد!
NPچیه دیگه؟
معلم‌های کامپیوتر میدونن؟
اگه فقط برنامه نویسی خونده باشن؟
NP مخفف Non Polynomial هست. به دسته مسائلی گفته می شه برای حلشون الگوریتم هایی از زمان چندجمله ای وجود نداره ( تعریفش این نیست در اصل، ولی همین رو می شه فرض کرد الان! مشکلی ایجاد نمی کنه)
حالا لازمه که شما ما مفهومی به نام "اُردِر" آشنایی داشته باشید، تا این تعریف رو متوجه بشید.
احتمال خیلی زیاد باید معلم های کامپیوتر بدونند! فکر می کنم که جزو واحدهای دانشگاهشون، طراحی الگوریتم هم وجود داره، که فکر می کنم این چیزا رو توش گفتن حتما.
اگه معلم المپیاد کامپیوتر (معلم الگوریتم) دارید حتما می دونه! از اون بپرس.
BLACK HOLE
کاربر فوق‌حرفه‌ای
- ارسال‌ها
- 826
- امتیاز
- 2,199
- نام مرکز سمپاد
- فرزانگان امين
- شهر
- اصفهان
- سال فارغ التحصیلی
- 1392
- مدال المپیاد
- نجوم
- دانشگاه
- University of Alberta
- رشته دانشگاه
- Computer Science
پاسخ : حل جدول سودوکو؟
شما این چیز هارو از کجا یاد گرفتید که من هم برم از پایه یاد بگیرم؟
خوب پس سوال رو کلی تر می‌کنیم!به نقل از پارسا :
شما این چیز هارو از کجا یاد گرفتید که من هم برم از پایه یاد بگیرم؟
parsa_spy
کاربر فوق‌حرفه‌ای
- ارسال‌ها
- 1,161
- امتیاز
- 443
- نام مرکز سمپاد
- علامه حلی تهران
- شهر
- تهران
- سال فارغ التحصیلی
- 1390
- مدال المپیاد
- مدال طلای المپیاد کامپیوتر
- دانشگاه
- صنعتی شریف
- رشته دانشگاه
- نرم افزار
پاسخ : حل جدول سودوکو؟
المپیاد کامپیوتر
به نقل از ..AndromedA.. :خوب پس سوال رو کلی تر می‌کنیم!
شما این چیز هارو از کجا یاد گرفتید که من هم برم از پایه یاد بگیرم؟
المپیاد کامپیوتر
BLACK HOLE
کاربر فوق‌حرفه‌ای
- ارسال‌ها
- 826
- امتیاز
- 2,199
- نام مرکز سمپاد
- فرزانگان امين
- شهر
- اصفهان
- سال فارغ التحصیلی
- 1392
- مدال المپیاد
- نجوم
- دانشگاه
- University of Alberta
- رشته دانشگاه
- Computer Science
پاسخ : حل جدول سودوکو؟
حدس میزدم... B-)
خوب حالا از روی چه کتابی اینا رو خوند اید؟
به نقل از پارسا :المپیاد کامپیوتر
حدس میزدم... B-)
خوب حالا از روی چه کتابی اینا رو خوند اید؟
parsa_spy
کاربر فوق‌حرفه‌ای
- ارسال‌ها
- 1,161
- امتیاز
- 443
- نام مرکز سمپاد
- علامه حلی تهران
- شهر
- تهران
- سال فارغ التحصیلی
- 1390
- مدال المپیاد
- مدال طلای المپیاد کامپیوتر
- دانشگاه
- صنعتی شریف
- رشته دانشگاه
- نرم افزار
پاسخ : حل جدول سودوکو؟
معلم درس داد!
پ.ن : موضوع منحرف داره می شه. ادامه سوالاتتون رو توی پ.خ بپرسید. ممنون.
به نقل از ..AndromedA.. :حدس میزدم... B-)
خوب حالا از روی چه کتابی اینا رو خوند اید؟
معلم درس داد!
پ.ن : موضوع منحرف داره می شه. ادامه سوالاتتون رو توی پ.خ بپرسید. ممنون.
maziar
مازیمون
- ارسال‌ها
- 1,962
- امتیاز
- 6,836
- نام مرکز سمپاد
- علامه حلی
- شهر
- تهران، استانبول، کوالالامپور، اُسلو!
- دانشگاه
- Universitetet i Oslo
- رشته دانشگاه
- ریاضی، CS، نانو الکترونیک
پاسخ : حل جدول سودوکو؟
خب اگه اشتباه نكنم حل سودوكو جواب چند جمله اي نداره
و ما با يه مساله NP-Complete طرف هستي
پس تعجبي نداره كه بري سراغ راه هايي كه با توان رابطه دارن
يعني اكسپوننشيال بايد باشه
پس دنبال راه كوتاه از نظر زماني نباش
دنبال ساده كردن راه باش
خب ببين تو همه چيز رو بايد امتحان كني و بعد مي بيني تعداد خيلي زيادي از راه ها حذف ميشن
و خب اين جا مهم اينه كه تو بتون خيلي زود راه هايي كه اهميت خاصب ندارن و حتمن غلط هستن حذف كني
خب مي توني درباره مسائل اين مدلي مي توني به سوال هايي مثل vertex cover independent set يه نگاهي بندازي ايده هايه خوبي بهت ميدن
خب اگه اشتباه نكنم حل سودوكو جواب چند جمله اي نداره
و ما با يه مساله NP-Complete طرف هستي
پس تعجبي نداره كه بري سراغ راه هايي كه با توان رابطه دارن
يعني اكسپوننشيال بايد باشه
پس دنبال راه كوتاه از نظر زماني نباش
دنبال ساده كردن راه باش
خب ببين تو همه چيز رو بايد امتحان كني و بعد مي بيني تعداد خيلي زيادي از راه ها حذف ميشن
و خب اين جا مهم اينه كه تو بتون خيلي زود راه هايي كه اهميت خاصب ندارن و حتمن غلط هستن حذف كني
خب مي توني درباره مسائل اين مدلي مي توني به سوال هايي مثل vertex cover independent set يه نگاهي بندازي ايده هايه خوبي بهت ميدن