پروژه طراحي الگوريتم

---

شرح پروژه

اين پروژه يکي از تمرينات کتاب الگوريتم است که انرا نيز ضميمه کردم-سوال 30 از فصل 6 اين کتاب است توضيح بيشتر در مورد اين سوال: ومسئله بازسازي درخت تکامل با حداکثر صرفهجويي يا همون Reconstructing evolutionary trees by maximum parsimony يک مسئله معروف ژنتيک است که اگر يک جستجو ميکرديد ميتونستيد مسئله را بفهميد. بريم سراغ صورت مسئله، مسئله از اين قرار است که ما n تا رشته به طول k داريم که هر رشته از حروف {A,G,C,T} تشکيل شده است. پس تکليف ورودي مشخص شده که به اينصورت است: Input: n , k s1,s2,…,sn حالا قرار است با اين رشته ها درخت تکامل را بسازيم به طوري که برگها همان رشتههاي s1,…,sn باشند (منتها جهت راهنمايي ترتيب برگها لزوما با ترتيب ورودي يکي نيست و برگها لزوما در يک سطح قرار ندارند) گرههاي مياني و ريشه هم رشتههايي به طول k هستند. که اين گرههاي مياني بايستي طوري انتخاب شوند هزينه مجموع بالهاي کل درخت حداقل شود(ارتفاع درخت مهم نيست هزينه مهم است.) هزينه هر يال برابر تعداد کاراکترهاي متفاوت دو رشته مربوط به دو راس آن است. مثلا هزينه يال (ACCT,AGCA) برابر 2 است. پس تکليف خروجي هم مشخص شد : Output: Tree //يا به صورت گرافيکي بيان شود يا به صورت ليست يالها بيان شود که بتوان درخت حاصل را کامل استنتاج کرد Cost هزينه درخت ( مجموع هزينه يالها) به عنوان مثال : n=5 و k=7 و cost=12 البته مطمئن نيستم که درخت زير حداقل هزينه را دارد فقط به عنوان يک نمونه از درهت رسم شده که درک کنيد درخت تکامل يعني چي؟ روي هريال هزينه آن توشته شده است. ( درضمن لازم نيست هر رشته شامل هر چهار تا کاراکتر قد شده باشد حتي يک رشته ممکن است همه کاراکترهاي آن يکسان باشد.)

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

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

---

---