Floodfill^©

A Guide for Playing Floodfill

مشکل استفاده از کمترین تعداد رنگ برای رنگ کردن نقشه، بر اساس توضیحات ارائه شده، تاریخ طولانی دارد، به عنوان مثال، در یک مقاله ی ویکی پدیا. این قضیه که 4 رنگ همیشه کافی است که یک نقشه ی ساده را رنگ کرد به عنوان اولین قضیه ی ریاضی بزرگ معروف شد که فقط می توانست توسط رایانه ثابت شود و نه توسط اثبات ریاضی تولید شده توسط انسان.

هیچ الگوریتم شناخته شده ای برای بهینه رنگ کردن نقشه وجود ندارد. منظور از "بهینه" این است که اگر تعداد نواحی N عدد بزرگی است، آنگاه تعداد تلاش های لازم برای رنگ کردن مثل N^k رشد می کندکه در آن k عددی است که به N بستگی ندارد. به بیان دیگر، برای الگوریتم های "بهینه"، تعداد تلاش ها مثل یک چند جمله ای از N رشد می کند. در عوض، الگوریتم های رنگ آمیزی شناخته شده یک پیچیدگی توانی دارند، یعنی تعداد تلاش ها به N با رابطه ی ۴^N بستگی دارد.

گر استفاده از 5 یا 6 رنگ مجاز باشد، یا نقشه فقط دو رنگ نیاز داشته باشد، الگوریتم های بهینه شناخته شده اند.

فرصتی دیگر برای رسیدن به روش بهینه این است که، اینکه الگوریتم همیشه بهینه است، کنار گذاشته شود. همچین ابتکاری (یعنی مجموعه ی دستورالعمل ها) که حداقل در بیشتر موارد قابل به کار گیری است باید ذیل مطرح شود:

سوال اول. کدام ناحیه باید اول رنگ شود؟

سوال دوم. چه انتخابی از رنگها آزاد است؟

سوال سوم. کدام ناحیه در مرحله بعدی باید رنگ شود؟