300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | РусскийFloodfill©
Qaliblərin ümumi sayı: 209822
Floodfill Oynamaq üçün Bələdçi
Xəritəni rəngləmək üçün minimum sayda rəngdən istifadə problemi, məsələn, bu Vikipediya məqaləsində izah edildiyi kimi uzun tarixə malikdir. Müstəvi xəritəsini rəngləmək üçün hər zaman 4 rəngin kifayət etdiyi teoremi insan tərəfindən deyil, yalnız kompüter tərəfindən sübut oluna bilən ilk böyük riyazi teorem kimi məşhurlaşdı.
Xəritələri həmişə səmərəli şəkildə rəngləndirən heç bir alqoritm məlum deyil. "Səmərəli" dedikdə, Nbölgələrinin sayı çox böyükdürsə, lazımi rəngləmə cəhdlərinin sayı yalnız Nk kimi artır, burada k olmayan rəqəmdir. N-dən asılıdır. Başqa sözlə, "səmərəli" alqoritmlər üçün cəhdlərin sayı yalnız N polinomu kimi artır. Bunun əvəzinə, məlum rəngləmə alqoritmləri sözdə eksponensial mürəkkəbliyə malikdir, yəni cəhdlərin sayı 4N kimi N-dən asılıdır.
Əgər birinə 5 və ya 6 rəngdən istifadə etməyə icazə verilirdisə və ya xəritəyə yalnız 2 rəng lazımdırsa, onda effektiv alqoritmlər məlumdur.
Effektiv üsul əldə etmək üçün daha bir imkan alqoritmin HƏMİŞƏ effektiv olması tələbini atmaqdır. Ən azı bir çox hallarda işləyən belə bir heuristik (yəni təlimatlar dəsti) aşağıda müzakirə olunmalıdır:
Q. İlk növbədə hansı bölgə rənglənməlidir?
- Əvvəlcə mümkün qədər çox qonşuya malik olan bölgəni rəngləməyin faydası var, çünki əgər həmin bölgə A rəngi alsa, onda bütün qonşuları rəng A almamaq üçün məhdudiyyət əldə edəcəklər. Bu isə bu qonşu bölgələr üçün rəng seçimlərinin sayını azaldır və beləliklə, rəngləmənin çətin olduğu ortaya çıxarsa, sonrakı dövrlərin sayını azaldır.
Q.Hansı rənglərin seçimi pulsuzdur?
- İlk rəngləmədə istifadə olunan rəng mütləq pulsuzdur.
- Bir bölgəni rəngləmək üçün ikinci rəngdən ilk dəfə istifadə edildikdə, əgər bu bölgə birinci rəngin olduğu bölgəyə toxunursa, yəni ikinci rəng lazımdırsa, bu rəng seçimi pulsuz olur.
- Bir bölgəni rəngləmək üçün üçüncü rəngdən ilk dəfə istifadə edildikdə, əgər bu bölgə birinci rəngə malik olan bölgəyə və ikinci rəngə malik bölgəyə toxunarsa, yəni üçüncü rəng lazımdırsa, bu rəng seçimi pulsuzdur.
Q.Növbəti hansı bölgə rənglənməlidir?
- Yanında yalnız bir mümkün rəng qalan bölgəni rəngləməliyik ki, bu rəngləmədə səhv etməyək.
- Rəngləmə cəhdlərinin sayı mütləq 4N-dən azdır (bütün N regionlar üçün bütün 4 rəng sınanır). Beləliklə, bu rəngləmə cəhdlərinin sayı kritik olaraq bölgələrin sayından asılıdır N. Nəticə etibarı ilə, rəngləmə xəritənin ağ (rəngsiz) hissəsini ayrı-ayrılıqda ayrılmış ağ alt xəritələrə ayırarsa, bu, faydalıdır. Bu bölgələrdə yalnız N1 və N2 bölgə var (N = N1 + N2), indi ən çoxu 4 lazımdır N1 + 4N2 cəhdi 4N1 &dəfədən çox azdır; 4N2 = 4N cəhd.
- Əgər verilmiş xəritəni rəngləndirə biləcək ən az sayda rəng tapmaq istəyirsənsə, əvvəlcə 2 rəngin kifayət edib-etmədiyini yoxlamaq lazımdır. Bu, səmərəli şəkildə edilə bilər.
Əgər yalnız iki rəng A və B istifadə ediləcəksə və bölgələrdən birinin artıq rəngi varsa, kəsişmə nöqtəsi ətrafında hərəkət etmək bütün digər bölgələrin rəngini düzəldir:
Bu qayda həmçinin 3 və ya 4 rəngə ehtiyacı olan xəritələrin ilk rənglənməsi cəhdi üçün faydalıdır. Məsələn, aşağıda 1-ci bölgə artıq A rənginə malikdirsə, 2 və 4-cü bölgələrin fərqli rəngə ehtiyacı var və bunun nə ola biləcəyini bilmirik, lakin bilirik ki, 3-cü bölgəni A rəngi ilə rəngləmək 2-ci bölgənin rənglənməsi üçün əlavə şərtlər yaratmır , çünki onların artıq A rənginin qonşusu var.
Şəkil 3 xəritənin yalnız kiçik bir hissəsini göstərir, lakin yuxarıdakı evristik hər hansı bir xəritə üçün daha dəqiqləşdirilə bilər. Əgər 3-cü bölgənin bütün qonşularında (Şəkil 3-də, 2 və 4-də) A rənginin ən azı bir qonşusu varsa (Şəkil 3-də, region 1), onda 3-cü bölgənin A rəngi ilə rənglənməsi səhv ola bilməz. Səbəb odur ki, 3-cü bölgənin A ilə rənglənməsi qonşuları üçün heç bir yeni məhdudiyyət yaratmır, çünki onlarda A rənginə sahib olmaq qadağandır. Beləliklə, sonrakı rəngləmə prosesində səhvə yol verildiyi üzə çıxarsa (çünki rənglərin sayı kifayət deyil), onda 3-cü bölgəyə A-dan fərqli bir rəng vermənin mənası yoxdur, bəzi digər rəngləri yenidən sınamaq lazımdır. - Əgər yuxarıdakı 3-cü bölgə də başqa bir bölgə ilə diaqonal qonşudursa, məsələn, B rəngi kimi fərqli rəngə malik olan bölgə 9-cu bölgədir? 3 A və ya B ilə rənglənməlidir? Həmçinin burada 3-ün bütün qonşularının artıq A rənginin olması qadağan edilib-edilmədiyini və ya B rənginin qadağan edilib-edilmədiyini yoxlamağa kömək edir. Əgər belə deyilsə, 3-ün rəngini gözləyə bilərik.
Yeniliklər üçün izləyin və ya abunə olun: