الگوریتم امروز

وبلاگ تخصصی الگوریتم

الگوریتم امروز

وبلاگ تخصصی الگوریتم

وبلاگ علمی و مخصوص مباحث الگوریتمی است.
نظر خصوصی نگذارید چون جواب نمی‌دهم نظر عمومی بگذارید بدون نام هم که باشد همانجا جواب می‌دهم.

بایگانی

محاسبه کوچکترین توپ محیطی

شنبه, ۲۳ فروردين ۱۳۹۳، ۰۱:۲۱ ب.ظ

*روش افزایشی

هر بار یک نقطه را اضافه می‌کنیم و توپ محیطی را حساب می‌کنیم تا شامل همه نقاط شود. این کار را با استفاده از این نکته که هر نقطه جدید حتما روی محیط می‌افتد انجام می‌دهیم.

حالا باید ضریب تقریب آن را به دست بیاوریم. دایره جواب بهینه را در نظر می‌گیریم. فاصله‌ی مرکز دایره i-ام تا نقطه i-ام برابر شعاع دایره i-ام است و اگر آن را امتداد دهیم قسمت دیگر حداکثر سه برابر این قسمت است. می‌دانیم طول وتر از قطر کمتر است پس از اینجا ضریب تقریب ۳/۲ به دست می‌آید.

؟؟ چرا سه نقطه‌ی pi,ci,c(i-1) هم‌خط اند؟

*روش تکراری

یک نقطه دلخواه بر می‌داریم و به مجموعه Q اضافه می‌کنیم. دایره محیطی Q را به دست می‌آوریم و دورترین نقطه به آن از بین نقاط اولیه (به مرکز دایره) را به Q اضافه می‌کنیم و این کار را ادامه می‌دهیم تا توپ شامل همه‌ی نقاط شود.


موافقین ۰ مخالفین ۰ ۹۳/۰۱/۲۳
سپیده آقاملائی

نظرات  (۰)

هیچ نظری هنوز ثبت نشده است

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی