تعدادی کامپیوتر در یک فضای دوبعدی هستند، اگر همۀ کامپیوترها با یک سیم، به یک دستگاه وصل شوند، دستگاه در چه نقطه ای قرار بگیرد تا طول سیم حداقل باشد؟

Question

سلام و وقت بخیر

تعدادی کامپیوتر در یک فضای دو بعدی پراکنده هستند. همۀ این کامپیوترها قرار است به‌وسیلۀ یک سیم، مستقیم به یک دستگاه وصل بشوند.

1. دستگاه در چه نقطه‌ای قرار بگیرد تا مقدار سیم مورد نیاز برای ارتباط بین کامپیوترها و دستگاه حداقل باشد؟ (آیا میانگین نقاط $x$ و میانگین نقاط $y$ می‌تواند نقطۀ بهینه باشد؟)
2. اگر سیم‌ها فقط بتوانند موازی با محورهای اصلی ($x,y$) کشیده شوند، دراین حالت محل بهینۀ دستگاه کجا خواهد بود؟
3. اگر کامپیوترها در دو طبقه با ارتفاع $z$ پراکنده باشند، محل بهینۀ دستگاه کجا می‌تواند باشد؟

Comments

سوال جالبی است ترجیح می دادم هر مورد بعنوان یه سوال جداگانه مطرح می شد.خوشحالم از اینکه اولین امتیاز به اولین فعالیت شما دادم.ورودتان به جمع مون تبریک می گم.

---

@mahdi411 می‌توانستید ابتدا فقط مورد ۱ را بپرسید و با پاسخی که می‌گرفتید، به موردهای بعدی خودتان فکر می‌کردید و اگر نمی‌توانستید حل کنید یک مورد دیگر را می‌پرسیدید و به همین طریق. همیشه سعی کنید خودتان فکر کنید و تلاش کنید نه اینکه کل سوال‌هایتان را بگذارید و منتظر فکرکردنِ دیگران باشید! بعلاوه هیچ چیزی پیرامون اینکه خودتان پیش از گذاشتن پرسش در این سایت چه کارهایی برای حل آن انجام دادید یا چه چیزی را متوجه نمی‌شوید ننوشته‌اید! همیشه باید تلاش خودتان را اشاره کنید.

Answer 1

نکته: تابع زیر با فرض $a_i\leq a_{i+1} $ در نظر بگیرید $$f(x) = \sum _{i=1}^n|x-a_i| $$ در حالت $n=2k $ مینیمم f در بازه $x\in[a_k, a_{k+1}] $ اتفاق می افتد. و در حالت $n=2k-1 $ مینیمم f در نقطه $x=a_k $ اتفاق می افتد.

جواب مورد2) فرض کنیم مکان n کامپیوتر در صفحه به مختصات \begin{bmatrix}a_i\\b_i\end{bmatrix} و مکان نقطه مورد نظر \begin{bmatrix}x\\y\end{bmatrix} باشد آنگاه تابع فاصله به صورت زیر است. $$f(x, y) = \sum _{i=1}^n(|x-a_i|+|y-b_i|) $$ $$= \sum _{i=1}^n|x-a_i|+ \sum _{i=1}^n|y-b_i| $$ می نیمم تابع برابر با مجموع می نیمم های دو مجموع(سیگما)، با توجه به نکته بالا در حالت n=2k تابع در سطح مستطیلی ( $a_i $ ها را بصورت صعودی مرتب کرده و با $c_i $ نمایش می دهیم به طور متشابه برای $b_i $ ها که با d نمایش می دهیم.) $$x\in[ c_k, c_{k+1}]\quad y \in[d_k, d_{k+1}] $$ به می نیمم خود می رسد.

و در حالت $n=2k-1 $ با توجه به نکته بالا f در نقطه زیر مینیمم می شود. \begin{bmatrix}c_k \\d_k \end{bmatrix}

در نتیجه شیوه کار به این صورت است که در راستای افقی از بین مولفه های دوم، نقطه (1یا2 نقطه) وسط را پیدا کنید و خط افقی از آن نقطه (ها) رسم کنید همین کار برای راستای قائم برای مولفه های اول نیز انجام می دهیم در این صورت به یک سطح مستطیلی یا پاره خط یا نقطه خواهیم رسید که جواب مسئله می باشد.

توجه کنید که می توان به فضای سه بعدی تعمیم داد.

Answer 2

در حالتی که 4 کامپیوتر داشته باشیم و هیچ سه تای آنها روی یک خط قرار نداشته باشند محل برخورد اقطار چهارضلعی ایجاد شده پاسخ است.

Comments

اگر سیگما زیر رادیکال باشه راه حل درسته ولی بنظرم سیگما زیر رادیکال نمی باشه؟ لطفا بررسی کنید

---

حالا  dدرست شده یعنی سیکما را از زیر رادیکال خارج کردید اما حالا در نحوه مشتق گیری مشکل وجود داره؟

---

به چه دلیل می نیمم d و e معادلند؟

---

دونقطه یکی در مبدا و دیگر در مکان 1 روی محور xها در نظر بگیرید مکان دستگاه را با تعریف  d و e  بدست آورید به دو جواب متفاوت می رسید چطور ممکنه این دو معادل باشند؟

---

اگر 4 کامپیوتر به ترتیب در مکان‌های A, B, C, D باشند آنگاه محل برخورد(اشتراک) قطرها(پاره خط) AC وBD جواب می باشد. (در صورت وجود اشتراک)
چند حالت اتفاق می افتد
حالت اول) اگر 4ضلعی محدب باشه، همانطور که اشاره کردید نقطه تلاقی قطرها آن جواب است.

حالت دوم) فقط سه نقطه مثلاA, B, C  در یه راست باشندآنگاهB محل برخورد است و جواب می باشه.

حالت سوم) هر 4 نقطه در یک راسته باشه آنگاه مکان‌های اشتراک پاره خط BC می باشد که محل قرار دادن دستگاه است.

*)توجه کنید که برای چهار ضلعی غیر محدب عنوان نکردم چون  اشتراک قطرها تهی است، به نظرم راسی که سبب غیر محدب شدن آن شد جواب می باشه.