از پارسکدرز بیشترین بهره را ببرید و رویای کاری خود را زندگی کنید.
چهارده سال پیش منتشر شده
تعداد بازدید: 2396
کد پروژه: 2441
شرح پروژه
. معرفي
درختان جستجوي دودويي ساختمان دادهاي براي جستجوي يک بعدي ميباشند. اين ساختمان داده براي جستجوي عناصر کوچکتر يا مساوي value-max و بزرگتر يا مساوي value-min مناسب ميباشد. در اين پروژه شما بايد ساختمان داده جديدي با نام kd-tree بسازيد که جستجوي با ابعاد بيشتر را انجام دهد.
تأکيد اين پروژه بر روي جستجوهاي 2-بعدي ميباشد. شما بايد kd-tree دوبعدي را پيادهسازي نماييد که در واقع گسترش درخت جستجوي دودويي به دو بعد ميباشد. به عنوان مثال فرض کنيد ميخواهيد نقاطي درون يک صفحه را جستجو کنيد به طوريکه مختصات اين نقاط بين [x-min,x-max] و [y-min,y-max] باشد. در اينگونه مسائل kd-tree دو بعدي ميتواند راه حل مناسبي باشد.
2. درختان Kd-tree
ساخت يک kd-tree: مجموعه P شامل n نقطه در يک فضاي دوبعدي را در نظر بگيريد. هر نقطه piP توسط مختصاتش (xi,yi) مشخص مي شود. ايده اصلي اين است که ابتدا نقطه ها را بر اساس محور xها به دو قسمت تقسيم کنيم، سپس هر قسمت را بر اساس محور yها تقسيم کنيم، مجددا هر قسمت را بر اساس محور xها تقسيم کنيم وهمينطور الي آخر. در ريشه با يک خط عمودي، P را به دو قسمت مساوي تقسيم مي کنيم. نقاطي که در سمت راست اين خط هستند تشکيل زيردرخت سمت راست ريشه را خواهند داد و نقاطي که در سمت چپ اين خط هستند تشکيل زير درخت سمت چپ ريشه را خواهند داد. اين دو زير مجموعه را به ترتيب P-right و P-left مي ناميم. مجددا P-right را توسط يک خط افقي به دو زير مجموعه تقسيم مي کنيم. نقاطي که بالاي اين خط هستند تشکيل زير درخت راست فرزند راست ريشه را خواهند داد و نقاطي که پايين اين خط هستند تشکيل زير درخت چپ فرزند راست ريشه را خواهند داد. همين روند را براي زيرمجموعه P-left تکرار مي کنيم. به طور کلي در گره هاي با عمق زوج هر گره را با يک خط عمودي به دو قسمت تقسيم مي کنيم و در گره هاي با عمق فرد هر گره را با يک خط افقي به دو قسمت تقسيم مي کنيم. اين روند را تا جايي ادامه مي دهيم که تعداد گره هاي هر زير مجموعه برابر با c نقطه يا کمتر شود. هنگامي که اين اتفاق بيفتد يک گره برگ مي سازيم که تمام نقاط زيرمجموعه نهايي راشامل شود. توجه داشته باشيد که گره هاي مياني هيچ نقطه اي را ذخيره نمي کنند. شکل زير مثالي با c=1 را نشان ميدهد.
براي تضمين توازن، در هر گره مياني اگر عمق زوج باشد خط عمودي از نقطه ميانه xها و اگر عمق فرد باشد خط افقي از نقطه ميانه yها خواهد گذشت. براي انجام اين کار، فرض کنيد n تعداد نقاط زيرمجموعه مورد نظر باشد و نقاط با توجه به مقدار xشان ذخيره شده اند، بنابراين xi
زیرساخت:
windows xp
c++
microsoft visual stodio 2005
قابل تحویل:
این پروژه شامل 2 فایل مهم است، لطفا قبل از ارسال پیشنهاد حتما نسبت به بررسی این فایل اقدام فرمایید.
مهارت ها و تخصص های مورد نیاز
بودجه
5,000 تومان تا 100,000 تومان
مهلت برای انجام
8روز
وضعیت مناقصه
بسته
درباره کارفرما
عضویت چهارده سال پیش
قادر به انجام این پروژه هستید؟
مهلت ارسال پیشنهاد قیمت برای این پروژه تمام شده است
به رایگان یک حساب کاربری بسازید
مهارتها و تخصصهای خود را ثبت کنید، رزومه و نمونهکارهای خود را نشان دهید و سوابق کاری خود را شرح دهید.
به شیوهای که دوست دارید کار کنید
برای پروژههای دلخواه در زمان دلخواه پیشنهاد قیمت خود را ثبت کنید و به فرصتهای شغلی منحصر به فرد دسترسی پیدا کنید.
با اطمینان دستمزد دریافت کنید
از زمان شروع کار تا انتهای کار به امنیت مالی شما کمک خواهیم کرد. وجه پروژه را از ابتدای کار به امانت در سایت نگه خواهیم داشت تا تضمین شودکه بعد از تحویل کار دستمزد شما پرداخت خواهد شد.
میخواهید شروع به کار کنید؟
یک حساب کاربری بسازید
بهترین مشاغل فریلنسری را پیدا کنید
رشد شغلی شما به راحتی ایجاد یک حساب کاربری رایگان و یافتن کار (پروژه) متناسب با مهارتهای شما
است.
پیدا کردن کار (پروژه)
تماشای دمو روش کار