طراحی الگوریتم تقسیم و غلبه با جاوا(۲۷۰۷)

---

شرح پروژه

سلام

پروژه تقسیم و حل طراخی الگوریتم ¼ دارم

سوال سختی بهتون دادند… برای این سوال باید یک سری پیش فرض ها رو بدونی مثل این که چه طور با استفاده از چند نقطه یک شکل محدب بسازیم و چه طور تشخیص بدیم چه نقاطی داخل این شکل محدب قرار می گیرند و چه نقاطی نه. برای این کار صفحات ۴۴ تا ۴۹ پی دی افی که می فرستم رو بخون یکم سخته فهمش ولی خب چاره ای نیست. اما فعلا الگوریتم اصلی رو اول خوب بفهمش بعد برو سر کتابه.

الگوریتم اصلی: توی این سوال ما یک سری نقطه داریم که سه مولفه دارند x و y و ارزش نقطه مورد نظر. برای حلش به روش تقسیم و حل باید اون ها رو بر اساس مولفه‌ی x یا y مرتب کنیم و بعد به دو دسته تقسیمشون می کنیم و برای هر کدوم شکل محدبی که مجموع ارزش نقطه های آن، از نصف ارزش مجموع کل نقاط زیر مسئله (و نه تمام نقاط مسئله) بیشتر هست رو پیدا کنیم. فرض می کنیم که این کار انجام شده. یعنی ما یک شکل محدب سمت چپ داریم و یک شکل محدب سمت راست. حالا برای این که شکل محدب کلی رو بدست بیاوریم باید این دو شکل را با هم ترکیب کنیم. اول تمام ترکیب های ۳ نقطه ای را که از ترکیب نقاط شکل محدب سمت چپ و راست هستند را بدست می آوریم مثلا دو نقطه از شکل سمت چپ و یک نقطه از شکل سمت راست را با هم ترکیب می کنیم تا یک مثلث بوجود بیاید حالا چک می کنیم که آیا نقطه ای از بقیه کل نقاط در این شکل هست یاد نه و اگر بود ارزشش را با ارزش سه نقطه قبلی جمع می کنیم در صورتی که از نصف مجموع ارزش کل نقاط بیشتر بود یک کاندیدای جواب است. تمام حالت های سه تایی را محاسبه می کنیم و در صورتی که چند تا از آنها کاندیدای جواب بودند شکلی را انتخاب می کنیم که کمتر از بقیه نقطه دارد. اگر دو شکل دارای تعداد یکسانی نقطه بودند هر کدام ارزش بیشتری داشتند را انتخاب می کنیم و اگر هیچ شکلی از ترکیب سه نقطه کاندیدای جواب نبود. یک گام جلوتر می رویم و ۴ نقطه را با هم ترکیب می کنیم و این کار را تا جایی که تمام نقاط شکل محدب سمت چپ و راست را در ترکیب کنیم ادامه می دهیم. 

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

و حالا یک سری نکات:

۱) از ترکیب سه نقطه یا بیشتر ما حتما می توانیم یک شکل محدب بسازیم. 

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

۳) چند مثال با این روش حل کنید تا روند کار دستت بیاد.

۴) برای بهتر فهمیدن روش تقسیم و حل بهتره این دو تا مثال همون کتاب یعنی تعیین نزدیک ترین زوج نقطه در فضای یک بعدی و دو بعدی رو بخون. صفحات ۴۲ تا ۴۴.

دد لاین پروژمون ۱۸ ام فروردینه

تا اون موقع حاضر میشه

این پروژه شامل 1 فایل مهم است، لطفا قبل از ارسال پیشنهاد حتما نسبت به بررسی این فایل اقدام فرمایید.

مهارت ها و تخصص های مورد نیاز

---

---