مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

این صفحه فقط خواندنی است. شما می‌توانید متن صفحه را مشاهده کنید، اما نمی‌توانید آن را تغییر دهید. اگر فکر می‌کنید که مشکلی رخ داده است، مدیر ویکی را در جریان بگذارید.

====== جستجوی نزدیک‌ترین همسایه ======
هدف پیدا کردن نزدیک‌ترین نقطه به نقطه‌ی داده شده است. پیاده‌سازی از این الگوریتم در [[آماده‌سازی:کدهای_آماده|کدهای آماده]] وجود دارد.
===== درخت $kd$ =====
در این قسمت درخت $kd$ را معرفی می‌کنیم که تعمیمی از درخت جستجوی دودویی (یک بعدی) به $k$ بعد است.

برای ساخت این درخت یک بعد را انتخاب می‌کنیم و نقاط را بر اساس میانه‌شان در آن بعد دو قسمت می‌کنیم. سپس این کار را در بعد دیگری روی هر کدام از فرزندان این گره انجام می‌دهیم.

زمان ساخت درخت $kd$ با مرتب‌سازی در هر مرحله $O(n\log^2 n)$ است.

جستجوی نزدیک‌ترین همسایه روی درخت $kd$:

مشابه درخت جستجوی دودویی درخت را از ریشه به برگ طی می‌کنیم. این برگ را به عنوان بهترین جواب فعلی در نظر می‌گیریم. مسیر را به سمت ریشه برمی‌گردیم و اگر جواب بهتر شد، فرزند دیگر آن گره را هم بررسی می‌کنیم.
متوسط زمان این کار $O(\log n)$ است.

از این درخت برای جستجوی بازه‌ای هم می‌توان استفاده کرد.

[[http://en.wikipedia.org/wiki/K-d_tree|مطالب بیشتر در مورد درخت $kd$]]

مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

ابزار کاربر

ابزار سایت

ابزار صفحه