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

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

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

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

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

بایگانی

۱۰۴ مطلب با موضوع «هندسه پیشرفته» ثبت شده است

*روش افزایشی

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

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

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

*روش تکراری

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


۰ نظر موافقین ۰ مخالفین ۰ ۲۳ فروردين ۹۳ ، ۱۳:۲۱
سپیده آقاملائی

۰ نظر موافقین ۰ مخالفین ۰ ۲۳ فروردين ۹۳ ، ۱۱:۳۰
سپیده آقاملائی

عمرمون بر فناست اگه اینها رو ندونیم! :)

http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic1/lectureNotes/lec13/lec13.pdf

http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic1/lectureNotes/lec16/lec16.pdf

http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic1/lectureNotes/lec18/lec18.pdf

http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic1/lectureNotes/lec15/lec15.pdf

مرجع:

http://stellar.mit.edu/S/course/6/fa07/6.895/materials.html

دلیل اینکه در هندسه محاسباتی پیشرفته است روش‌های merge and reduce و مثل آن است که در این درس آمده است.

۰ نظر موافقین ۰ مخالفین ۰ ۲۳ فروردين ۹۳ ، ۱۱:۰۲
سپیده آقاملائی

(اولش هندسه محاسباتی مقدماتی هم دارد. شما از بقیه اش بخونید!)

http://people.csail.mit.edu/indyk/6.838/

۰ نظر موافقین ۰ مخالفین ۰ ۲۳ فروردين ۹۳ ، ۱۰:۲۱
سپیده آقاملائی

الگوریتم‌های جلسه قبل از مرتبه O(dn) بودند یعنی برای ابعاد بالا قابل استفاده نیستند. پس یک بار دیگر عملکرد الگوریتم‌های جلسه قبل را بررسی می‌کنیم.

فرض کنید همان طور که با پیدا کردن دورترین نقطه از نقطه فعلی الگوریتم دوم را از روی الگوریتم اول به دست ‌آوردیم کار را ادامه می‌دادیم. اگر نقاط بیشتری را درگیر حل مسأله کنیم و دورترین نقطه از آنها را پیدا کنیم مجموعه‌ای از جواب‌ها را داریم که هر کدام در یک جهت نقاط را در بر‌می‌گیرند (جواب مسأله هستند). پس اگر تعداد جهت‌های مناسب با فاصله‌ی مناسب انتخاب کنیم می‌توانیم جواب مسأله را با تقریب خوبی به دست بیاوریم. یک راه این کار در نظر گرفتن نقاط با فاصله یکسان روی سطح کره است و دیگری در نظر گرفتن جهت با وصل کردن مرکز مکعب به وسط هر خانه توری. چون سطح مطرح شده است از مرتبه‌ی d-1 یک بر اپسیلون است.

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

ما عمل مقیاس کردن را در روش توری انجام دادیم و روش تصویر کردن جهتی را هم الآن بررسی کردیم. می‌توانیم این دو را ترکیب کنیم چون خروجی الگوریتم توری یک مجموعه نقاط است و می‌توان مجدداً روی آنها الگوریتم دیگری اجرا کرد. با این کار تقریب مورد نظر به هم نمی‌خورد چون نقاط درون یک خانه‌ی توری از نظر زاویه به هم نزدیک هستند. در غیر این صورت باید ضریب تقریب‌ها را جمع می‌کردیم و ضریب تقریب دو برابر می‌شد.

چون تقریب در واقع به توری وابسته است، به جای اینکه ابتدا نقاط سطح توری را به دست بیاوریم بعد آنها را رند کنیم می‌توانیم از روی توری جواب مسأله را هم تقریب بزنیم. یعنی دورترین نقطه را از هر نقطه توری در هر ابرصفحه حساب کنیم. این کار باعث می‌شود نقاطی که می‌دانیم جزو جواب نیستند را در نظر نگیریم. برای این کار به صورت افزایشی تعداد ابعاد را زیاد می‌کنیم و هر بار نقاطی را که نسبت به نقاط قبلی دورترین هستند نگه می‌داریم. در خود مقاله گفته است که نقاط دیاگرام ورونوی گسسته دوگان دورترین نقاط در جهت‌های داده شده هستند.

من الآن دارم مقاله را می‌خوانم و حس می‌کنم این‌ها هیچ ربطی به مطالب مقاله ندارند.

۰ نظر موافقین ۰ مخالفین ۰ ۲۲ فروردين ۹۳ ، ۱۰:۱۳
سپیده آقاملائی

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

روش اول که پیدا کردن دورترین نقطه است از اینجا به ذهن می‌رسد که ماکسیمم فاصله هر دو نقطه قطر را می‌دهد. برای اثبات تقریب باید به ازای هر نقطه p از نقاط اولیه ثابت کنیم که دو نقطه‌ی جواب (مثلا a و b) تقریبی از قطر می‌دهند.

ALG < OPT < c*ALG

max(pa,pb) < ab < pa+pb < 2*max(pa,pb)

یعنی اگر ماکسیمم فاصله‌ از هر نقطه دلخواهی را به عنوان جواب برگردانیم ۲-تقریب جواب بهینه است.

این معادل زدن یک دایره به مرکز p و شعاع دورترین نقطه از آن است. می‌دانیم دورترین نقطه روی محیط می‌افتد (چون فاصله‌اش تا مرکز برابر شعاع دایره است). دورترین نقطه از این نقطه را هم پیدا می‌کنیم و به مرکز آن و شعاع این نقطه جدید (مثلا q) دایره می‌زنیم. همه‌ی نقاط درون اشتراک این دو دایره می‌افتند. در یک حالت نقطه‌ی q روی دایره‌ی اول می‌افتد (بدترین حالت در روش قبلی) و وقتی ما ماکسیمم این دو جواب را برمی‌گردانیم به جواب بهینه می‌رسیم چون حداکثر فاصله‌ی دو نقطه از قطر دایره کمتر است. یعنی بدترین حالت روش قبلی تبدیل به بهترین حالت روش جدید شده است. اما بدترین حالت روش فعلی چیست؟ اینکه فاصله‌ها برابر باشند. در این صورت دایره دوم از مرکز دایره‌ی اول عبور می‌کند و مرکز خودش هم روی محیط دایره اول است. (پس دو دایره مساوی داریم.) حداکثر فاصله‌ی دو نقطه در این حالت عمود منصف بین‌المرکزین است که رادیکال ۳ برابر بین‌المرکزین است.

می‌خواهیم دقت بیشتری داشته باشیم. برای حل این مشکل از مقیاس دادن استفاده می‌کنیم، یعنی مثلا دورتر می‌ایستیم و نقاط نزدیک به هم را یکی می‌بینیم. این کار را با استفاده از توری انجام می‌دهیم. بعد از اینکه جواب را در مقیاس بالاتر به دست آوردیم نزدیک‌تر می‌شویم و جواب را بهتر می‌کنیم. (مثل عمل zoom). برای این کار از یک تقریب قبلی (مثل دو الگوریتمی که گفته شد) استفاده می‌کنیم بعد یک توری با کمک کوچکترین جعبه محیطی می‌سازیم که اندازه‌ی خانه‌های آن اپسیلون برابر تقریب قطر است و نقاط را به نزدیک‌ترین گوشه توری رند می‌کنیم. حالا طبق تقریبی که از قطر به دست آورده‌ایم می‌دانیم تعداد خانه‌های توری که واقعاً به کار می‌روند در هر بعد از یک بر اپسیلون کمتر است پس کلاً تعداد نقاط جدید ما یک بر اپسیلون به توان d خواهد بود. (d تعداد ابعاد است.)

حالا الگوریتم brute force را روی این نقاط جدید که تعداد کمی دارند (همان طور که گفته شد وابسته به اپسیلون است.) اجرا می‌کنیم که مرتبه‌ی n^2 است و زمان ما همچنان خطی بر حسب n و یک بر اپسیلون خواهد بود. (PTAS) زمان خطی مربوط به رند کردن نقاط به توری است که با یک کف گرفتن (جزء صحیح) انجام می‌شود.

ضریب تقریب آن رادیکال d برابر عرض هر خانه (=قطر هر خانه) خواهد بود که چون تعداد ابعاد را از قبل می‌دانیم می‌توانیم به هر اپسیلون دلخواهی برسیم.

در این توری می‌دانیم که نقاطی که درون مکعب می‌افتند تاثیری در محاسبه‌ی قطر ندارند پس با در نظر گرفتن نقاط روی سطح آن می‌توانیم توان یک بر اپسیلون را در محاسبه‌ی تعداد نقاط یکی کم کنیم.

۰ نظر موافقین ۰ مخالفین ۰ ۲۲ فروردين ۹۳ ، ۰۹:۲۰
سپیده آقاملائی
مرجع: کتاب هندسه محاسباتی موازی Akl S.G., Lyons K.
البته کتاب قدیمی است و نتایج هم احتمالاً قدیمی اند!
۰ نظر موافقین ۰ مخالفین ۰ ۲۱ فروردين ۹۳ ، ۰۲:۱۰
سپیده آقاملائی

مرجع: http://cs-wwwarchiv.cs.unibas.ch/lehre/ws06/cs342/slides/6_en_SimilaritySearch_2.pdf

یعنی باید دایره حول نقطه کوئری را بزرگتر می‌گرفتیم (همان طور که در قسمت‌های بعدی سوال گفته شده است)‌ و بعد با شماره‌گذاری خانه‌های نزدیک‌تر با اعداد کمتر به جواب می‌رسیدیم.

(سوال اول تمرین این سری هندسه را هم غلط حل کردم. البته قسمت اولش رو چون بعدی ها رو مستقل ثابت کردم ولی احتمالاً نمره‌ی هیچ کدوم رو نمی‌گیرم.)

۰ نظر موافقین ۰ مخالفین ۰ ۲۰ فروردين ۹۳ ، ۲۲:۵۱
سپیده آقاملائی

منبع: http://sarielhp.org/teach/1999/course.html


۰ نظر موافقین ۰ مخالفین ۰ ۲۰ فروردين ۹۳ ، ۲۲:۳۵
سپیده آقاملائی

روی جواب تمرین هندسه اصلاحیه داده شد.

۰ نظر موافقین ۰ مخالفین ۰ ۱۹ فروردين ۹۳ ، ۱۲:۱۸
سپیده آقاملائی