موضوع مقاله: درج کردن حریصانه | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درج کردن حریصانه | مقدمه: در رایانش توزیع‌شده و نظریه گراف هندسی، برازش حریصانه، یک روند اختصاص دادن مختصات راس‌های یک شبکهٔ مخابراتی است که قابلیت مسیریابی جغرافیایی حریصانه برای مسیر دادن پیام‌ها در داخل شبکه را فراهم می‌کند. | ## بخش 1: درج کردن حریصانه | اگرچه برازش حریصانه برای استفاده در حسگر شبکه‌های بی‌سیم پیشنهاد شده‌است، که در آن راس‌ها در فضای فیزیکی مکان‌دهی شده‌اند، این مکان‌های موجود می‌توانند با مکان‌های داده‌شده توسط برازش حریصانه تفاوت داشته‌باشند، که در بعضی از موارد می‌تواند نقاطی از یک فضای مجازی‌ای از یک بعد بالاتر یا در یک هندسه نااقلیدسی باشند. از این دید، برازش حریصانه را می‌توان مانند یک روش کشیدن گراف در نظر گرفت، که در آن یک گراف انتزاعی (شبکهٔ ارتباطات) در یک فضای هندسی برازش می‌شود. پیش‌رفت‌های بعدی نشان‌داده‌اند که تمام شبکه‌ها دارای برازش حریصانه با مختصات فشرده راس‌ها در هندسه هذلولوی هستند، که بعضی گراف‌ها، شامل گراف‌های چندضلعی، در فضای دوبعدی دارای برازش حریصانه‌اند، و این‌که گراف‌های حلقه-واحد، در فضاهای اقلیدسی بعدهای متوسط با عوامل کشش کم، دارای برازش حریصانه‌اند. تعاریف در مسیریابی حریصانه، یک پیام از یک راس مبدأ s به یک راس مقصد t، با یک سری قدم در بین راس‌های میانی سفر می‌کند، که هر کدام از آن قدم‌ها، پیام را به یک راس مجاور می‌دهد که به t نزدیک‌تر است. | ## بخش 2: درج کردن حریصانه | اگر پیام به یک راس میانی x برسد که راس مجاور نزدیک‌تری به t نداشته‌باشد، پس نمی‌توان پیش‌رفت کرد، و روند مسیریابی حریصانه شکست می‌خورد. یک برازش حریصانه، برازشی است از گراف داده‌شده، با ویژگی‌ای که این‌گونه شکست غیرممکن باشد. به طوری که در هر برازش این گراف، دو برگ وجود دارند که زاویهٔ بین آن‌ها، کمترمساوی ۶۰ درجه‌اند، که نتیجه می‌شود که حداقل یکی از این دو راس، راس مجاوری که به راس دیگر نزدیک‌تر باشد ندارند. در فضاهای اقلیدسی با بعدهای بالا، گراف‌های بیش‌تری دارای برازش حریصانه‌اند؛ برای مثال، ستارهٔ شش‌پر در فضای سه‌بعدی دارای برازش حریصانه است، به‌طوری که راس میانی در مرکز و برگ‌ها هر کدام در فاصلهٔ واحد از مرکز در شش جهت بردار نشان هستند. | ## بخش 3: درج کردن حریصانه | البته، در هر فضا با بعد ثابت، گراف‌هایی هستند که نمی‌توانند حریصانه برازش شوند؛ زمانی که n, از عدد تماس یک فضا، بیش‌تر باشد، ستارهٔ nپر دارای برازش حریصانه نیست.دیوید اپشتاین، مایکل گودریچ "مسیریابی هندسی حریص با استفاده از هندسه هیپربولیک" برازش‌های هیپربولیک و فشرده برخلاف فضای دوبعدی، هر شبکه در فضای هذلولوی دارای برازش حریصانه است. اثبات اصلی این نتیجه، توسط رابرت کلاینبرگ، نیازمند این بود که مکان راس‌ها، با دقت بالا مشخص شوند،رابرت کلاینبرگ، "مسیر جغرافیایی با استفاده از فضای هذلولی" ولی متعاقباً نشان داده شده بود که، با استفاده از تجزیهٔ سنگین مسیر از یک درخت پوشای شبکه، ممکن است که هر راس را، با استفاده از تعداد نمایی‌ای از بیت‌ها در هر نقطه، به‌صورت فشرده نمایش داد. در عوض، گراف‌هایی وجود دارند که در فضای دوبعدی دارای برازش حریصانه‌اند، ولی در این برازش‌ها نیازمند تعداد چندجمله‌ای‌ای از بیت‌ها برای مختصات دکارتی هر نقطه‌اند.پاتریزیو انجلینی، ژوسپ دی‌باریستا، فابریزیو فراتی، "نقشه‌های حریص مختصر همیشه وجود ندارد"لی شاو، استرلزوف، سان، "اختصاری از مسیریابی حریصانه در فضای دوبعدی" حالت‌های خاص گراف‌ها درخت‌ها برای درخت‌هایی که برازش حریضانه دارند، زمان به‌دست آوردن این برازش در زمان خطی است.مارتین نولنبرگ، رومن پروتکین، "برازش حریصانهٔ اقلیدسی درختان" برای گراف‌های کلی‌تر، برخی از الگوریتم‌های برازش حریصانه، مانند الگوریتم کلاینبرگ، اول درخت پوشای گراف مورد نظر را پیدا می‌کند، و سپس برازش حریصانهٔ آن را می‌سازد. | ## جمع‌بندی | با این حال، گراف‌هایی وجود دارند که در فضای دوبعدی دارای برازش حریصانه‌اند، ولی هیچ درخت پوشایی از آن دارای برازش حریصانه نیست.تامسون لایتون، آنکور مویترا، "بعضی نتایج بر روی جزییات حریصانه در فضاهای متریک" گراف‌های مسطح پاپادیمیتریو و راتاژاک، حدس زده‌بودند که تمام گراف‌های پلی‌هدرال (یک گراف مسطح 3 راس)، دارای برازش حریصانه در فضای دوبعدی‌اند.