Payamvdn/NorthPersian_fa_wiki huggingface dataset:
قرار می گیرند نیز formula_13 هزینه می برد، پس در کل تا اینجا از formula_13 هزینه کرده ایم. به طور دلخواه نقاط با کمترین و بیشترین مجموع x,y و نقاط با کمترین و بیشترین تفاضل x,y را نیز می توانند به چهار ظلعی قبلی اضافه شوند تا این نقاط بر روی هم یک ۸ ظلعی محدب را به وجود آورند که نقاط درون آن به راحتی می توانند حذف شوند. اگر نقاط ورودی به صورت رندم انتخاب شوند آنگاه برای کلاسی گسترده از تابع های چگالی احتمال، این دور انداختن بعضی از نقاط در پیش پردازش باعث می شود که الگوریتمی که اجرا می شود دارای پیچیگی زمانی باشد که امید ریاضی آن خطی باشد، حتی اگر در بدترین حالت از formula_23 باشد. مسئله پوش محدب برخط و داینامیک. در بحثهای بالا فرض بر آن است که تمامی نقاط از قبل به ما داده شده است. اما ممکن است کسی به این دو حالت بپردازد. درج یک نقطه به تعداد ضلع های پوش محدب حداکثر یک واحد اضافه می کند در حالی که عمل حذف می تواند یک پوش سه راسی را به یک پوش n-۱ راسی تبدیل کند. در نوع برخط با اضافه شدن هر نقطهformula_24 هزینه شده که به طور مجانبی بهینه است. در نوع داینامیک هر عملیات درformula_25 انجام می شود. به دست آوردن پو
ش محدب چندضلعی ساده. McCallum و Avis اولین نفراتی بودند که پوش محدب برای یک چندظلعی ساده با رأس های را درformula_13) ساختند. ایدهٔ اصلی بسیار ساده است. چپترین نقطه روی پوش محدب می باشد و ما آن را با formula_27 مشخص می کنیم. دومین نقطه را نیز به عنوان کاندیدی برای راس پوش فرض می کنیم. در هر مرحله به سه راس متوالی نگاه می کنیم که دو تای اول به عنوان رأس های موقت پوش اختصاص داده شده اند و راس سوم هنوز پردازش نشده است که ما آن ها را به صورتformula_28 مشخص می کنیم. اگر زاویهٔ بین آن ها محدب بود انگاه formula_29 و این سه تایی با یک انتقال یک راسی سه تایی بعدی را مشخص می کند. اما اگر زاویهٔ ایجاد شده مقعر باشد آنگاه نقطه میانی(formula_30) پاک شده و این تست برای سه تایی formula_31 تا تکرار می کنیم تا این که یا به زاویهٔ محدب رسیده یا این که به و بعد از نقطهٔ بعدی به سه تایی برای تست شدن اضافه می شود و این روند تکرار می شود. هر چند که در تعدادی از مقالاتی که در گذشته انتشار یافته اند از امکان خود متقاطع شدن چند ضلعی در حین حذف رءوس صحبت شده که دلیلی بر نامعتبر بودن روند این الگوریتم می باشد. خوشبختانه، این مورد نیز به
صورت کارا مدیریت می شود. بعداً Tor و Middleditch و به صورت مستقل Melkman رویکردی ساده تر با پیچیدگی زمانی یکسان ارائه کردند. بعدهای بالاتر. شماری از الگوریتم ها برای سه بعد وجود دارد، همچنین برای بعدهای دلخواه: نگاه کنید به:https://web.archive.org/web/20070609032115/http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html برای مجموعه ای محدود از نقاط در سه بعد پوش محدب به صورت یک چند وجهی محدب می باشد یا به طور کلی یک چندوجهی محدب برای هر تعداد بعد، که رأس های آن زیر مجموعه ای از رأس های ورودی می باشد. نمایش آن به سادگی نمایش در بعد نمی باشد. در بعدهای بالاتر حتی اگر رأس های این چند وجهی معلوم باشند. ساختن وجههای آن کاری بدیهی نیست. همچنین دوگان این مسئله نیز این چنین است یعنی پیدا کردن رأس ها از روی وجه ها. سایز خروجی می تواند به صورت نمایی از سایز ورودی بیشتر باشد، حتی در شرایطی که سایز خروجی و ورودی قابل مقایسه باشد الگوریتم های ارائه شده برای بعدهای بالاتر حساس به خروجی نیستند.
در نظریه گراف، قضیه ویزینگ (به نام وادیم ویزینگ نامگذاری شده که آن را در سال ۱۹۶۴ منتشر کرد) بیان می کند که یال های هر گراف ساده را می توان با حداکثر یکی بیشتر از بیشترین درجه رئوس گراف رنگ کرد. همواره حداقل رنگ لازم است، بنابراین گراف های ساده را می توان به دو رده افراز کرد: گراف های «ردهٔ اول» آنهایی هستند که رنگ، برای رنگ آمیزی آن ها کافی است و گراف های «ردهٔ دوم» آن هایی هستند که رنگ، برای رنگ آمیزی آن ها لازم است. مثال ها. هنگامی که است، گراف خود یک تطابق است که هیچ دو یال مجاوری ندارد و عدد رنگی یالی آن یک است. پس، تمام گراف های با جزء گرافهای ردهٔ اول هستند. هنگامی که است، گراف اجتماع مجموعه های مجزای مسیرها و دورها است. اگر همهٔ دورها زوج باشند، آن ها می توانند ۲-رنگ پذیر یالی باشند با تغییر تناوبی دو رنگ، پیرامون هر دور. هر چند، اگر حداقل یک دور فرد وجود داشته باشد، هیچ ۲-رنگ آمیزی یالی ممکن نیست. پس، یک گراف با جزء گراف های ردهٔ اول است اگر و تنها اگر دوبخشی باشد. قضیهٔ ویزینگ در حالت کلی برای گراف های چندگانه برقرار نمی باشد. برای مثال، گراف چندگانهٔ حاصل از مضاعف کردن هر یال یک مثلث، بیشینه درجهٔ
چهار دارد اما نمی توان آن را با کمتر از شش رنگ، رنگ آمیزی کرد. رده بندی گراف ها. چندین نویسنده شرایطی را برای رده بندی برخی گراف ها به ردهٔ اول یا ردهٔ دوم ارائه کرده اند اما رده بندی کاملی ارائه نشده است. برای مثال اگر مجموعهٔ رئوس با بیشینه درجهٔ در گراف یک مجموعه مستقل باشد، یا به طور کلی تر زیرگراف القایی این رئوس یک جنگل باشد، آنگاه باید جزء گراف های ردهٔ اول باشد. اردوش و ویلسون (۱۹۷۷) نشان دادند که تقریباً همهی گراف ها جزء ردهٔ اول هستند. پس، در مدل اردوش-رنیِ گراف های تصادفی، که تقریباً تمام گراف های -راسی برابر هستند، را احتمال کشیده شدن یک گراف -راسی از توزیع گراف های ردهٔ اول تعریف می کنیم، در نتیجه اگر به بینهایت میل کند به یک نزدیک می شود. برای حدود بهتری که به یک همگرا باشد، به رجوع شود. گراف های مسطح. ویزینگ (۱۹۶۵) نشان داد که هر گراف مسطح جزو گراف های ردهٔ اول است اگر بیشترین درجهٔ رئوس گراف حداقل هشت باشد. در مقابل او مشاهده کرد که به ازاء هر بیشترین درجهٔ بین دو تا پنج، گراف مسطحی وجود دارد که جزو گراف های ردهٔ دوم باشد. برای درجهٔ دو، هر دور فردی چنین گراف است و برای درجهٔ سه و چهار و پنج گ
راف های مورد نظر از اجسام افلاطونی با جایگزین کردن یک یال به جای دو یال مجاور می توانند ساخته شوند. در حدس گراف های مسطح ویزینگ، ویزینگ (۱۹۶۵) بیان می کند که گراف های سادهٔ مسطح که بیشترین درجهٔ رئوس آن ها شش یا هفت است، جزء گراف های ردهٔ اول هستند، و این موارد ممکن باقی مانده را تمام می کند. سندرز و ژاو (۱۹۶۵) با نشان دادن ردهٔ اول بودن تمام گراف های مسطح با بیشترین درجهٔ رئوس هفت، تقریباً حدس گراف های مسطح ویزینگ را اثبات کردند. بنابراین، تنها حالت حدس که حل نشده باقی مانده این است که بیشترین درجه، شش باشد. این حدس شامل دلایلی برای حدس رنگ آمیزی کامل گراف است. گراف های مسطح ردهٔ دوم که با زیربخش های اجسام افلاطونی ساخته می شوند منظم نیستند: آن ها رئوس درجهٔ دو دارند همانطور که رئوس با درجهٔ بالاتر دارند. قضیه چهاررنگ، روی رنگ آمیزی راسی گراف های مسطح، معادل این گزاره است که هر گراف ۳-منظمِ مسطحِ بدون یال برشی جزء گراف های ردهٔ اول هستند (تایت ۱۸۸۰). این گزاره بعد از اثبات قضیه چهار رنگ توسط اپل و هاکن (۱۹۷۶) درست شناخته شد. گراف های روی رویه های غیرمسطح. در سال ۱۹۶۹، برانکو گرانبام حدس زد که تمام گراف های ۳
-منظم با برازش چندوجهی روی هر خمینهٔ جهت دار دو بعدی مانند چنبره، باید جزو گراف های ردهٔ اول باشد. در این زمینه، برازش چندوجهی یک برازش گراف است که در آن هر ناحیه از برازش از نظر توپولوژیکی یک دیسک است و به طوری که گرافِ دوگانِ برازش ساده است، بدون حلقه و یال چندگانه. در صورت درست بودن، این حدس یک تعمیم قضیهٔ چهار رنگ است که توسط تایت، نشان داده شد معادل این گزاره است که گراف های ۳-منظم با برازش چندوجهی روی یک کره، جزء رده اول هستند. اگرچه کُچُل (۲۰۰۹) نشان داد که حدس غلط است اگر اسنارکی که دارای برازش چندوجهی بر روی رویهٔ جهت دار بالادسته وجود داشته باشد. بر این اساس، او همچنان نشان داده است که دانستن اینکه برازش چندوجهی جزو گراف ها ردهٔ اول است، ان پی کامل است. الگوریتم ها. میسرا و گرایز (۱۹۹۲) یک الگوریتم با زمان چندجمله ای برای رنگ آمیزی هر گراف با رنگ ارائه کردند، که بیشینه درجهٔ گراف است. پس، الگوریتم برای گراف های ردهٔ دوم از تعداد رنگ های بهینه استفاده می کند، و حداکثر یکی بیشتر از تعداد رنگ های مورد نیاز برای همهٔ گراف ها. الگوریتم آن ها از روشی یکسان با اثبات اصلی ویزینگ برای قضیه اش پیروی می کند: ا
ین الگوریتم از یک گراف رنگ نشده شروع می کند، و سپس به طور مکرر راهی را برای رنگ آمیزی دوباره گراف پیدا می کند تا تعداد یال های رنگ شده را یک عدد افزایش دهد. به طور خاص تر، فرض کنید که یک یال رنگ نشده در یک گراف نیمه رنگ شده باشد. الگوریتم میسرا و گرایز ممکن است به عنوان ساخت یک شبه جنگل جهت دار (یک گراف که هر رأس آن حداکثر یک یال خارج شونده دارد.) روی همسایه های تفسیر شود: برای هر همسایهٔ از ، الگوریتم یک رنگ را می یابد که توسط هیچ یک از یال های مجاور استفاده نشده است، رأس را می یابد (در صورت وجود) که یال رنگ را دارد و را به عنوان یک یال به اضافه می کند. دو حالت وجود دارد: با برخی از ساختمان داده های ساده برای پیگیری رنگ هایی استفاده شده و قابل استفاده در هر رأس، می توان ساختن و گام های رنگ آمیزی دوباره الگوریتم را با زمان پیاده سازی کرد، که تعداد رئوس گراف ورودی است. چون در هر تکرار این گام ها تعداد یال های رنگ شده یکی افزایش می یابد، باید این گام ها را بار تکرار کرد، پس زمان مجموع برابر است با . در یک گزارش فنی منتشر نشده، گابو و همکاران (۱۹۸۵) ادعای ارائهٔ یک محدودیت زمانی formula_1 سریع تر را برای مسئلهٔ
رنگ آمیزی یکسان با رنگ را کردند. تاریخچه. در هر دو گوتین و تافت (۲۰۰۰) و سافیر (۲۰۰۸)، ویزینگ اشاره کرد که کارش انگیخته شده توسط یکی از قضایای شانون (۱۹۴۹) است که نشان می دهد گراف های چندگانه می توانند با حداکثر رنگ، رنگ آمیزی شوند. هر چند حالا قضیه ویزینگ جزء مواد استاندارد بسیاری از کتاب های نظریه گراف است، ویزینگ در ابتدا برای انتشار نتایجش مشکل داشت، و مقاله اش در یک مجلهٔ گمنام به نام Diskret. Analiz. چاپ شد.
مسئله کوله پشتی، یکی از مسائل مورد مطالعه در بهینه سازی ترکیبیاتی است که در بعضی موارد در زندگی واقعی نیز کاربرد دارد. به همین دلیل تعدادی از حالات خاص یا حالات کلی آن مورد آزمایش قرار گرفته است. چیزی که در تمام نسخه های این مسئله مشترک است، وجود مجموعه ای با n عضو است، که هر عضو با اندیس j که formula_1، یک ارزش formula_2 و وزن formula_3 دارد. متغیر دودویی تصمیم formula_4 برای انتخاب کردن اشیا به کار میرود. هدف برداشتن تعدادی از اعضا است، به طوری که ارزش کلشان بیشینه شود و در عین حال بیشینه مجموع وزن اشیا انتخاب شده از formula_5 تجاوز نکند. در حالت کلی، این ضرایب در عددی ضرب می شوند (مقیاس می شوند) تا به اعداد صحیح تبدیل شوند و همیشه فرض می شود که این ضرایب عدد طبیعی هستند. مسئله کوله پشتی در ساده ترین شکل به صورت زیر است: formula_6 را بیشینه کنید، به طوری که formula_7،formula_8،formula_9. کلی سازی مستقیم. یک شکل رایج این مسئله این است که هر عضو بتواند چندین بار انتخاب شود. مسئله کوله پشتی محدود برای هر عضو formula_10، یک کران بالای formula_11 (که می تواند یک عدد صحیح مثبت یا بی نهایت باشد.) که تعداد دفعاتی ا
ست که عضو formula_10ام انتخاب شده است را مشخص می کند: formula_6 را بیشینه کنید، به طوری که formula_7، formula_15 و formula_4 برای هر formula_10 عددی صحیح است. مسئله کوله پشتی نامحدود (که گاهی اوقات مسئله کوله پشتی صحیح نیز خوانده می شود) برای تعداد تکرارهای یک عضو کران بالایی قرار نمی دهد: formula_6 را بیشینه کنید، به طوری که formula_7 و formula_20، formula_21 برای هر j عددی صحیح است. در سال 1975 لوکر ثابت کرد که نوع نامحدود مسئله ان پی کامل است. هر دو نوع محدود و نامحدود این مسئله یک FPTAS دارند (در اصل شبیه به همان است که در مسئله کوله پشتی 0-1 استفاده شد). اگر اعضا در "k" دسته که با formula_22 نشان داده می شوند طبقه بندی شوند، و دقیقاً از هر کلاس یک عضو انتخاب شود آنگاه با مسئله کوله پشتی چند گزینه ای روبرو هستیم: formula_23 را بیشینه کنید، به طوری که formula_24 ؛ formula_25، برای هر formula_26 و formula_27، برای هرformula_26 و هر formula_29. اگر برای هر عضو ارزش و وزنش یکسان باشند، با مسئله جمع زیرمجموعه ها روبرو هستیم (اغلب مسئله تصمیم که متناظر با آن است به جای آن داده می شود): formula_6 را بیشینه کنید،
به طوری که formula_31، formula_8. اگر "n" عضو و "m" کوله پشتی با ظرفیت formula_33 داشته باشیم،با مسئله کوله پشتی چندگانه روبرو هستیم: formula_34 را بیشینه کنید، به طوریکه formula_35، برای هر formula_36 و formula_37، برای هر formula_1 و formula_27، برای هر formula_1 و هر formula_36. به عنوان یک حالت خاصِ مسئله کوله پشتی چندگانه، هنگامی که ارزش ها با وزن ها برابر و همه صندوق ها حجم برابر داشته باشند، با مسئله حاصل جمع زیرمجموعه های چندگانه روبرو هستیم: مسئله کوله پشتی درجه دوم: formula_42 را بیشینه کنید، به طوری که formula_7، formula_8 برای هر formula_1. مسئله کوله پشتی مجموعه-اجتماع(SUKP): SUKP توسط Kellerer و همکارانش ( در صفحه 423) همانطور که در ادامه آمده تعریف شده است: مجموعه formula_46 شامل formula_47 عضو و formula_48 شامل formula_49 عضو داده شده است، هر عضو formula_10 به یک زیرمجموعه formula_51 از مجموعه formula_52 مربوط میشود. برای هرformula_53 ، عضو formula_10ام ارزش نامنفی formula_2 دارد، و برای هر formula_56 ، عضو formula_57 ام وزن نامنفی formula_58 دارد. وزن کلی یک مجموعه از اعضا برابر با مجموع وزن
اعضای متناظر آن در مجموعه است. هدف پیدا کردن زیرمجموعه ای از عضوها است که وزن کلی آن از حجم کوله پشتی بیشتر نشود و ارزش بیشینه را داشته باشد. محدودیت چندگانه. اگر بیشتر از یک محدودیت وجود داشته باشد (برای مثال هم محدودیت حجمی و هم محدودیت وزنی داشته باشیم، در حالی که حجم و وزن هر شی هیچ رابطه ای با یکدیگر ندارند)، به مسئلهٔ کوله پشتی با شرایط چندگانه، مسئله کوله پشتی چند بعدی، یا مسئله کوله پشتی m- بعدی می رسیم (توجه کنید که "بُعد" در این جا هیچ ارتباطی به شکل اشیا ندارد). این مسئله انواع 0-1، محدود و نامحدود دارد که نوع نامحدود آن در زیر نشان داده شده است: formula_6 را بیشینه کنید، به طوریکه formula_60 ، برای هر formula_61 formula_62، formula_4 برای هر formula_64 عددی صحیح باشد. در حدود سال 1980 نشان داده شد که نوع 0-1 مسئله (برای هر formula_65 ثابت) ان پی کامل است و به طور قویتر FPTAS ندارد مگر اینکه P = NP. انواع محدود و نامحدود مسئله نیز (برای هرformula_65 ثابت) درجه سختی مشابه دارند. برای هر formula_65 ثابت، این مسائل یک (مشابه مسئله کوله پشتی اصلی) و یک PTAS دارند. مسئله های مشابه کوله پشتی. اگر ارزش ه
مهٔ اشیا یک باشد می توانیم تلاش کنیم تا تعداد اشیایی که کوله پشتی را کاملاً پر می کنند، کمینه کنیم: formula_68 را کمینه کنید، به طوریکه formula_69 و formula_8، formula_71. اگر تعدادی جعبه (با سایز یکسان) داشته باشیم و هدف قرار دادن همهٔ n شی در حداقل تعداد جعبه ممکن باشد به مسللهٔ (بسته بندی جعبه ها) می رسیم که با متغیرهای شاخص مدل می شود و formula_72 است اگر و تنها اگر جعبهٔ "i"م استفاده شود: formula_73 را کمینه کنید، به طوریکه formula_74، formula_75 و formula_76، formula_77 و formula_78، formula_75 و formula_27، formula_81. مسئلهٔ مشابه مسئلهٔ است، اما از آن جا که نمونه های عملی انواع کمتری از اعضا دارند، اغلب از فرمول دیگری استفاده می شود. عضو "j"م formula_82 مرتبه نیاز است، هر الگویی از اعضا که برای یک کوله پشتی مناسب باشد یک متغیر formula_83 دارد("m" الگو وجود دارد) و الگوی "i" عضو "j" را formula_84 بار استفاده می کند: formula_85 را کمینه کنید، به طوریکه formula_86 برای هر formula_1 و formula_88 برای هر formula_89. اگر برای مسئله کوله پشتی چندگزینه ای که در آن ها چند انتخاب وجود دارد، این محدودیت که در آ
ن سایز هر زیرمجموعه "n" باشد را اضافه کنیم و محدودیت بر روی وزن کلی را حذف کنیم، به مسئلهٔ assignment می رسیم که مسئلهٔ پیدا کردن یک بیشینه نیز است: formula_90 را بیشینه کنید، به طوریکه formula_76 برای هر formula_1 و formula_93 برای هر formula_94 و formula_27 برای هر formula_26 و برای هر formula_29. در مسئله کوله پشتی با چگالی بیشینه وزن اولیه formula_98 است و ما تراکم اشیای انتخابی را تا زمانی که با محدودیت های ظرفیت مغایرت نداشته باشد، زیاد می کنیم: formula_99 را بیشینه کنید، به طوریکه formula_7 و formula_8، formula_71. تعداد دیگری مسئله های مشابه کوله پشتی نیز وجود دارند که البته نسبت به مسئله های ذکرشده کمتر متداول هستند، شامل: سه مسئلهٔ آخر در مرجع کار کلرر و همکارانش، مشکلات کوله پشتی، مورد بحث و بررسی قرار گرفته اند.
ونسا لی کارلتن (زاده ۱۶ اوت ۱۹۸۰) خواننده و آهنگساز آمریکایی است. نخستین تک آهنگ او به نام یک هزار مایل در سال ۲۰۰۱ در جایگاه پنجم ۱۰۰ آهنگ داغ بیلبورد قرار گرفت و موجب شهرت وی گردید. کارلتن تا سال ۲۰۱۱ چهار آلبوم استودیویی منتشر کرد. زندگی. زندگی شخصی. کارلتن در جریان رژه دگرباشان نشویل در سال ۲۰۱۰ اعلام کرد که دوجنس گراست و به این موضوع افتخار می کند.
در هندسه محاسباتی و نظریه گراف هندسی، بتا اسکلت یک گراف بدون جهت است که بر روی مجموعه ای از نقاط هندسه اقلیدسی تعریف می شود. دو نقطه p و q در صورتی توسط یک یال به یکدیگر متصل می شوند که همه زاویه های "prq" از آستانه تعیین شده توسط پارامتر عددی "β" کمتر باشد. تعریف مبتنی بر دایره. اگر "β" یک عدد حقیقی مثبت باشد، زاویه "θ" با استفاده از فرمول زیر بدست می آید: برای هر دو نقطه "p" و "q" در صفحه، "R""pq" را مجموعه ای از نقاط در نظر بگیرید به طوری که زاویه "prq" از "θ" بزرگتر باشد. در این صورت به ازای "β" ≥ 1 و "θ" ≤ π/2 مجموعه "R""pq" به صورت اجتماع دو دایره با اندازه قطر "βd"("p","q") در خواهد آمد و به ازای "β" ≤ 1 و "θ" ≥ π/2 مجموعه "R""pq" به صورت اشتراک دو دایره به قطر "d"("p","q")/"β" خواهد شد. در صورتی که "β" = 1 باشد هر دو فرمول بالا جواب "θ" = π/2 را خواهند داد و مجموعه "R""pq" به صورت یک دایره به قطر "pq" خواهد شد. اگر "S" یک مجموعه مجزا از نقاط در صفحه هندسه اقلیدسی باشد، بتا اسکلت آن یک گراف بدون جهت است که در آن دو نقطه "p" و "q" در صورتی با یال "pq" به یکدیگر متصل می شوند که "R""pq" حاوی هیچ یک از نقا
ط مجموعه "S" نباشد. در حقیقت بتا اسکلت یک گراف ناحیه خالی می باشد که با ناحیه های "R""pq" تعریف شده اند. هنگامی که مجموعه "S" شامل نقطه "r" باشد به طوری که زاویه "prq" بزرگتر از "θ" باشد، "pq" یال بتا اسکلت نخواهد بود؛ بتا اسکلت شامل آن جفت "pq" هایی می باشد که همچین نقطه "r" ای برای آن ها وجود نداشته باشد. تعریف مبتنی بر هلال. بعضی از نویسنده ها تعریف دیگری را بیان می کنند که در آن ناحیه های خالی "R""pq" به ازای "β" &gt; 1 اجتماع دو دایره نیستند بلکه عدسی می باشند (در این متن به آن ها هلال می گوییم )، یعنی اشتراک دو دایره متناجس به قطر "βd"("p,q") هستند به طوری که پاره خط "pq" بر روی شعاع هر دو دایره قرار می گیرد و همچنین دو نقطه "p" و "q" روی مرز تقاطع دایره ها قرار خواهند گرفت. همانند تعریف مبتنی بر دایره، بتا اسکلت مبتنی بر هلال نیز، در صورتی دارای یال "pq" می باشد که ناحیه "R""pq" از نقاط دیگر خالی باشد. با توجه به این تعریف، گراف همسایه مرتبط یک حالت خاص از بتا اسکلت با "β" = 2 می باشد. هر دو تعریف مبتنی بر دایره و مبتنی بر هلال به ازای "β" ≤ 1 یکسانند اما برای مقادیر بزرگ تر "β"، تعریف بتا اسکلت مبتنی
بر دایره زیر گرافی از بتا اسکلت مبتنی بر هلال می باشد. یک تفاوت مهم میان بتا اسکلت مبتنی بر دایره و هلال در این است که به ازای هر مجموعه نقاطی که روی یک خط قرار نداشته باشند، همیشه یک مقدار به اندازه کافی بزرگ برای "β" وجود دارد که بتا اسکلت مبتنی بر دایره آن یک گراف تهی باشد. در مقابل اگر یک جفت نقاط "p" و "q" دارای این ویژگی باشند که برای همه نقاط "r" دیگر، یکی از دو زاویه "pqr" و "qpr" منفرجه شود، در آن صورت بدون توجه به این که "β" چقدر بزرگ باشد بتا اسکلت مبتنی بر هلال حتماً حاوی یال "pq" خواهد بود. تاریخچه. بتا اسکلت اولین بار توسط به عنوان یک گونه مستقل از مقیاس از شکل های آلفای مطرح شد. نام “بتا اسکلت” به این علت ایجاد شده است که بتا اسکلت از بعضی جهات شکل یک مجموعه نقاط را شرح می دهد به همان طریقی که اسکلت توپولوژی شکل ناحیه های دوبعدی را بیان می کند. انواع بسیار دیگری از گراف های بتا اسکلت وجود دارند که با ناحیه های خالی دیگر تعریف می شوند. ویژگی ها. اگر β به صورت پیوسته از 0 تا ∞ تغییر کند، β-اسکلت های مبتنی بر دایره دنباله ای از گراف ها را، از گراف کامل تا گراف تهی، تشکیل می دهند. حالت خاصّ β=1 گرا
ف گابریل را نتیجه می دهد که شامل درخت پوشای کمینه اقلیدسی است. بنابراین، زمانی که β≤1، یک β-اسکلت شامل گراف گابریل و درخت پوشای کمینه هم هست. برای هر β ثابت، می توان از یک ساختار فراکتال که نمایانگر نسخه مسطح برف دانه کخ باشد برای مشخص کردن دنباله ای از گروه نقطه ها که β-اسکلت های آن ها مسیرهایی به طول دلخواه در یک مربع واحد است، استفاده کرد. بنابراین، برخلاف مسئله مرتبطِ مثلث بندی دیلانی، β-اسکلت ها پوشای هندسی نیستند. الگوریتم ها. یک الگوریتم بدیهی که برای هر سه تایی formula_2، formula_3 و formula_4 عضویت formula_4 را در محدوده formula_6 بررسی می کند، می تواند برای هر مجموعه formula_7تایی از نقاط، β-اسکلت را در زمان formula_8 بسازد. به ازای β≥1، یک β-اسکلت (با هر یک از تعریف ها) زیرگرافی از گراف گابریل است که آن هم زیرگرافی از مثلث بندی دیلانی است. اگر formula_9 یکی از یال های مثلث بندی دیلانی باشد که به β-اسکلت تعلق ندارد، آن گاه نقطه formula_4، یکی از دو نقطه ای که در مثلث بندی دیلانی با formula_3 و formula_2 تشکیل مثلث می دهند، زاویه بزرگ formula_13 را درست می کند. در نتیجه، برای این مقادیر β، یک β-اسکلت
مبتنی بر دایره با محاسبه مثلث بندی دیلانی و حذف کردن یال های اضافی با این آزمون برای یک مجموعه شامل formula_7 نقطه در زمان formula_15 ساخته می شود. به ازای β&lt;1 الگوریتم دیگری از ساختن β-اسکلت را در زمان formula_16 ممکن می سازد. کران بالای بهتری برای زمان اجرا در بدترین حالت ممکن نیست. زیرا برای هر مقدار ثابت β در محدوده ۰ تا ۱، در حالت کلی مجموعه هایی از نقاط وجود دارند که β-اسکلت آن ها یک گراف کامل است که تعداد یال هایش با توان دوم تعداد نقاط متناسب است. همچنین تمام طیف β (دنباله β-اسکلت های مبتنی بر دایره که از تغییر مقدار β به دست می آیند) در زمان مشابه (درجه دو) محاسبه می شود. کاربردها. از β-اسکلت مبتنی بر دایره می توان در آنالیز تصویر برای بازسازی شکل یک شیء دو بعدی با داشتن مجموعه ای از نقاط نمونه روی مرز آن شیء استفاده کرد.(شکل محاسباتی بازی وصل کردن نقاط، که در آن ترتیب نقطه ها در صورت مسئله نیست و باید توسط یک الگوریتم به دست آید.) اگرچه برای این کار باید مقدار مناسبی برای پارامتر β اتخاذ شود، ثابت می شود به ازای β=1.7، در صورتی که نسبت تراکم نمونه ها به انحنای موضعی سطح به اندازه کافی زیاد باشد،
β-اسکلت تمام مرز هر سطح صاف را بازسازی می کند و هیچ یال اضافی ای تولید نمی کند. البته در عمل، مقدار β=1.2 در یک سامانه اطلاعات جغرافیایی برای بازسازی نقشه خیابان ها از روی مجموعه ای از نقاط که روی خط میانی خیابان ها بودند مناسب تر بود. برای حالت های تعمیم یافته روش β-اسکلت برای بازسازی سطوح در سه بعد، را ببینید. از β-اسکلت های مبتنی بر دایره برای یافتن زیرگراف های مثلث بندی با وزن کمینه ی یک مجموعه از نقاط استفاده می شود: برای مقادیر به اندازه کافی بزرگ β، هر یال β-اسکلت به مثلث بندی با وزن کمینه تعلق دارد. اگر نقاط ورودی با این یال ها یک گراف همبند را تشکیل دهند، یال های باقی مانده مثلث بندی با وزن کمینه با برنامه نویسی پویا در زمان چندجمله ای به دست می آیند. البته مسئله مثلث بندی با وزن کمینه در حالت کلی ان پی-سخت است و یال های به دست آمده با این روش الزاماً یک گراف همبند درست نمی کنند. علاوه بر این، β-اسکلت ها در یادگیری ماشین برای حلّ مسائل شناسایی هندسی و در شبکه های بی سیم ادهاک به عنوان یک سازوکار برای کنترل پیچیدگی ارتباط، با انتخاب یک زیرمجموعه از جفت ایستگاه های بی سیم که توانایی ارتباط با یک دیگر
را دارند، کاربرد دارند.
&lt;ns&gt;0&lt;/ns&gt; &lt;revision&gt; &lt;parentid&gt;41942154&lt;/parentid&gt; &lt;timestamp&gt;2025-08-27T05:03:08Z&lt;/timestamp&gt; &lt;contributor&gt; &lt;username&gt;مهرآیین1374&lt;/username&gt; &lt;/contributor&gt; &lt;origin&gt;42493590&lt;/origin&gt; &lt;model&gt;wikitext&lt;/model&gt; &lt;format&gt;text/x-wiki&lt;/format&gt; الگوریتم های ایجاد هزارتو روش هایی خودکار برای تولید هزارتو (ماز) هستند. روش های مبتنی بر نظریه گراف ها. یک هزارتو می تواند توسط یک چیدمان از پیش تعیین شده از خانه ها با دیوارهایی در بین آن ها تولید شود. خانه ها به طور معمول شبکه های مستطیلی هستند اما چیدمان های دیگر هم ممکن است. این چیدمان های از پیش تعیین شده را می توان در قالب گراف همبند تصور کرد که در آن یال ها نشانگر مکان های ممکن برای دیوار و گره ها نشانگر خانه ها باشند. در این صورت هدف این الگوریتم را می توان ساختن یک زیر گراف در نظر گرفت. زیرگرافی که در آن یافتن یک مسیر بین دو راس مشخص مورد بررسی باشد. اگر زیرگراف همبند نباشد، آنگاه قسمت هایی در گراف وجود خواهد داشت که بی استفاده می مانند. چرا که آن ها نقشی در فضای جست
جو بازی نمی کنند. اگر گراف شامل حلقه باشد، آنگاه امکان وجود چندین مسیر بین دو راس مشخص وجود دارد. به همین علت، تولید هزارتو به طور معمول از طریق تولید درخت پوشای تصادفی انجام می شود. حلقه ها می توانند موجب سردرگمی بازیکنان کم تجربه شوند. حلقه ها را می توان با اضافه کردن یال های تصادفی به نتیجه در مسیر تولید گراف ایجاد کرد. جستجوی عمق-اول. این الگوریتم یک نسخه تصادفی از الگوریتم جستجوی عمق-اول است. این الگوریتم که غالباً توسط پشته پیاده سازی می شود یکی از ساده ترین راه ها برای تولید یک هزارتو توسط رایانه است. فضای هزارتو را یک شبکه بزرگ از خانه ها (مانند یک صفحه شطرنج) تصور کنید به طوری که هر خانه در آن با ۴ دیوار در اطراف آن وجود دارند. با آغاز از یک خانه تصادفی، برنامه یکی از همسایه های آن خانه را که تاکنون انتخاب نشده است به طور تصادفی انتخاب می کند. حال دیوار بین آن دو خانه برداشته می شود و خانه جدید به پشته اضافه می شود (این کار مشابه کشیدن یک خط روی زمین است). سپس برنامه با همین روند ادامه پیدا می کند، با رسیدن به خانه ای که هیچ همسایهٔ قابل عزیمتی ندارد (همه همسایه های آن دیده شده اند) برنامه به بن بست
می رسد. در این مرحله مسیر طی شده در جهت عکس طی می شود تا اولین رأس با حداقل یک همسایه رویت نشده یافت شود. سپس مسیر با رویت این خانه جدید ادامه پیدا می کند (این کار معادل ساخت یک نقطه اتصال در هزارتو است). کار تا جایی ادامه پیدا می کند که تمامی خانه ها یک بار رویت شوند. در این حالت برنامه تمام مسیر را به سمت خانه اولیه بازمی گردد. این رویکرد، مشاهده تمام خانه های فضای هزارتو را تضمین می کند. همان طور که پیشتر بیان شد الگوریتم بسیار ساده عمل کرده و به تبع آن هزارتوهای بسیار پیچیده ای را هم تولید نمی کند. برخی اصلاحات مانند اصلاحات زیر می تواند به پیچیده تر کردن هزارتوهای ساخته شده کمک کند. همان طور که در بالا اشاره شد این الگوریتم دربردارنده یک روند بازگشتی عمیق است که در برخی معماری های رایانه می تواند موجب سرریز از پشته شود. می توان با ذخیره کردن اطلاعات حاصل از بازگشت از هر خانه بر روی هزارتو الگوریتم را به یک حلقه تغییر داد. این کار در عین حال یک راه سریع برای نشان دادن جواب را نیز ارائه می دهد:با شروع از هر خانه و بازگشت مسیر به سمت خانه خروج می توان مسیر موردنظر را تولید کرد. هزارتوهایی که با روش جستجوی ع