من علاقه مند هستم كه درستي الگوريتم هاي زير را به كمك منطق بازي ها ثابت كنم. دانشجويان علاقه مند به من مراجعه كنند
فرض كنيم مي خواهيم كه يك كيك عادلانه بين n نفر تقسيم شود. الگوريتمهاي زير نمونه اي از الگوريتم هاي چند عاملي براي n=3 هستند.
تعريف: گوييم يك تقسيم كيك بين n عامل عادلانه است هرگاه هر عامل باور داشته باشد كه حداقل يك nام كيك به او رسيده است.
الگوريتم زير عادلانه بودن تقسيم را برآورده ميكند.
1- ابتدا بازيكن 1 كيك را به دو قسمت مساوي از لحاظ خود تقسيم ميكند (فرض كنيد a1,a2 )
2- بازيكن 2 يكي از دو قسمت را كه از لحاظ خود از ديگري بزرگتر است براي خود بر ميدارد (فرض كنيد a2 را برداشته است)
3- بازيكن 1 قسمت خود را به 3 قسمت مساوي از لحاظ تقسيم ميكند (فرض كنيد a11,a12,a13)
4- بازيكن 2 قسمت خود را به 3 قسمت مساوي از لحاظ خود تقسيم ميكند (فرض كنيد a21,a22,a23)
5- بازيكن 3 از 3 قسمت a11,a12,a13 بزرگترين قسمت از لحاظ خود را برمي دارد. (فرض كنيد a12)
6- بازيكن 3 از 3 قسمت a21,a22,a23 بزرگترين قسمت از لحاظ خود را برمي دارد. (فرض كنيد a21 )
بعد از انجام الگوريتم بازيكن 1 قسمتهاي a11,a13، بازيكن 2 قسمتهاي a22,a23 و بازيكن 3 قسمتهاي a12,a21 را خواهد داشت.
تعريف: گوييم يك تقسيم كيك بين n عامل از حسادت آزاد است هرگاه هيچ عاملي به عاملي ديگر حسادت نكند.
الگوريتم زير به يك تقسيم حسادت آزاد منجر ميشود. خوب بود اگر نويسنده پاياننامه بتواند بصورت فرمال اين موضوع را ثابت كند.
1. بازيكن اول كيك را به سه قسمت a1,a2,a3 از لحاظ خود مساوي تقسيم ميكند.
2. بازيكن دوم سه قسمت تقسيم شده را از لحاظ خود از بزرگ به كوچك مرتب ميكند. فرض كنيد a1>a2>a3 . سپس تكهe>=0 را طوري از a1 جدا ميكند كه a'1=a1-e=a2 شود.
3. بازيكن سوم از بين تكههاي a'1,a2,,a3 تكه بزرگتر از لحاظ را انتخاب ميكند و براي خود بر ميدارد.
4. اگر بازيكن سوم را a'1 بر ندارد a'1 به بازيكن دوم داده ميشود و تكه ديگر باقيمانده (از سه تكه a'1,a2,,a3) به بازيكن اول داده ميشود. اگر بازيكن سوم a'1 را بردارد، بازيكن دوم از بين دو قسمت ديگر بزرگترين را از لحاظ خود انتخاب ميكند و براي خود بر ميدارد. تكه ديگر باقيمانده نيز به بازيكن اول داده ميشود.
5. بعد از اجراي 4، يا بازيكن دوم يا بازيكن سوم a'1 را دارد. آن بازيكني كه a'1 را دارد بازيكن P1 و بازيكن ديگر (از بين بازيكنهاي دوم و سوم) را بازيكن P2 بناميد.
6. بازيكن P2 قسمت e را به سه قسمت از لحاظ خود مساوي تقسيم ميكند و بازيكن P1 ، بازيكن اول و بازيكن P2 به ترتيب هر يك، يك قسمت را براي خود بر ميدارد.
تا آنجا كه من ميدانم الگوريتم حسادت آزاد براي تقسيم بين n>=5 عامل هنوز معرفي نشده است. اين موضوع ميتواند به عنوان يك پژوهش در نظر گرفته شود كه آيا منطق به پيدا كردن اين الگوريتمها كمك كند. آيا ميتوان وجود يا عدم وجود اين الگوريتمها را ثابت كرد.
اين وبلاگ نظريه سيستم ها دانشكده علوم رياضي دانشگاه صنعتي شريف است. رياضيات پيچيدگي هاي علوم زيادي را از جمله مكانيك و الكترونيك حل كرده است. اكنون اميد مي رود كه رياضيات بتواند افسار گسيختگي علوم انساني چون جامعه شناسي، قانون گذاري، و سياست را مهار كند. منطق بازي ها (مبتني بر نظريه بازي ها)؛ منطق تكليف، و منطق شناختي نمونه هايي از ابزارها رياضي هستند كه مي توانند در توصيف و درستيابي سيستم هاي چند عاملي (اجتماعي) نقش بازي كنند. در درس نظريه سيستم ها، براي عامل چهار ويژگي: آگاهي، رقابت، ائتلاف و تعهد را در نظر مي گيريم. هر عامل با توجه به اين ويژگي ها سعي بر رفع نيازهاي خود دارد.اقليدس رياضيات (خواص و روابط) اشيا ساكن را صورتبندي كرد، نيوتن رياضيات اشيا متحرك، و حالا بشر مي خواهد رياضيات اشيا هوشمند را صورتبندي كند.
۱۳۸۷ بهمن ۳۰, چهارشنبه
اشتراک در:
نظرات پیام (Atom)
۳ نظر:
من الگوریتم تقسیم عادلانه را برای 4 نفر به این صورت طراحی کردم. ببینید درسته؟
6 مرحله اول مانند الگوریتم برای 3 نفر است. یعنی حالا نفر اول a11 و a13 (روی هم A)، نفر دوم a22 و a23 (روی هم B)و نفر سوم a12 و a21(به ترتیب C و D) را دارد.A+B+C+Dِ=1
7- نفر اول هر کدام از قسمت های خود را به2 قسمت مساوی از نظر خودش تقسیم میکند. یعنی:a111وa112وa131وa132
8-نفر دوم نیز همینکار را می کند.
یعنی:a221وa222وa231وa232
9-نفر سوم نیز هر کدام از قسمت های خود را به 4 قسمت مساوی تقسیم می کند. یعنی:a121وa122وa123وa124 a211وa212وa213وa214
10- حال نفر چهارم یک قسمت از کیکهای نفر اول و یک قسمت از کیکهای نفر دوم برمی دارد و دو قسمت از کیکهای نفر سوم بر می دارد به این صورت که یک قسمت از 4 تیکه اول یعنی a12 ها و یک قسمت از 4 تیکه دوم یعنی a21 ها.
به این ترتیب واضح است که به هرکدام 1/4 می رسد. حال چرا این تقسیم عادلانه است؟
نفر اول و دوم راضی اند چون از نظر خوددشان قسمت ها مساوی بوده.
نفر سوم راضی است چون همانطور که قبلا دیدیم از نظر او 1/3 < a12+a21 پس
3/4a12 + 3/4a21 > 1/4
و نفر چهارم راضی است چون از نظر خودش از نفر اول بیشتر ازA/4 و از نفر دوم بیشتر از B/4 و از نفر سوم بیشتر از C/4+D/4 برداشته،پس در کل بیشتر از 1/4 برداشته.
ممنونم از نظرت. شما در آخر روش نشان دادي كه تقسيم عادلانه است درحالي كه هدف ما بيشتر از اينه. بايد تقسيم حسادت آزاد باشه. بطور كلي طراحي الگوريتم براي تقسيم عادلانه دشوار نيست با تعداد كمتري مرحله هم امكان پذير است.
ارسال یک نظر