300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | DeutschSelfill©
Floodfill oynamaq üçün bələdçi
Xəritəni rəngləmək üçün minimal sayda rənglərdən istifadə problemi izah edildiyi kimi uzun bir tarixə malikdir. Məsələn, bu Vikipediyada. 4 rəngin həmişə təyyarə xəritəsini rəngləməyin kifayət etdiyi teorem, insanın istehsal etdiyi "riyazi" sübut vasitəsilə deyil, yalnız kompüter vasitəsilə sübut edilə biləcək 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ə, N bö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, o zaman effektiv alqoritmlər məlumdur.
Effektiv üsul əldə etmək üçün daha bir imkan alqoritmin ALWAYS 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ə çətin olduğu ortaya çıxarsa, sonrakı tryaların sayını azaldır.
Q. Hansı rənglərin seçimi pulsuzdur?
- Çox ilk rəngləmədə istifadə edilən rəng mütləq pulsuzdur.
- Bir bölgəni rəng etmək üçün ikinci bir rəng istifadə edilən ilk dəfə bu rəng seçimi, əgər bu bölgə birinci rəng ilə bir bölgəyə toxunarsa, yəni ikinci bir rəng lazımdırsa pulsuzdur.
- Üçüncü bir rəng bir bölgəni rəng etmək üçün ilk dəfə istifadə edilir. Bu bölgə birinci rəng ilə bir bölgəyə, ikinci rəng ilə bir bölgəyə toxunarsa, yəni üçüncü bir rəng lazım gələrsə, bu rəng seçimi pulsuzdur.
Q. Növbəti hansı bölgə rənglənməlidir?
- Növbəti dəfə bir bölgəni rəngləməliyik ki, bunun üçün yalnız bir mümkün rəng qalıb ki, bu rəngdə səhv edə bilmə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 biri müəyyən bir xəritəni rənglənə bilən ən az sayda rəng tapmaq istəyirsə, onda ilk növbədə 2 rəngin kifayət edib-etmədiyini yoxlamaq lazımdır. Bunu səmərəli şəkildə etmək olar.
Əgər yalnız iki rəng A və B istifadə olunmalıdırsa və bölgələrdən birinin artıq rəngi varsa, onda kəsişmə nöqtəsi ətrafında getmək bütün digər bölgələrin rəngini düzəldir:
Bu qayda 3 və ya 4 rəngə ehtiyacı olan xəritələrin ilk rəngləmə cəhdi üçün də faydalıdır. Məsələn, əgər aşağıda yerləşən 1-ci bölgə artıq rəng A olubsa, onda 2 və 4-cü bölgələrin fərqli rəngə ehtiyacı var və bunun nə ola biləcəyini heç təsəvvür edə bilmirik, amma bilirik ki, rəngli A ilə 3-cü bölgənin rənglənməsi 2 və 4-cü bölgələrin rənglənməsinə əlavə şərt yaratmır, çünki onların artıq rəng qonşusu var A.
Şəkil 3 xəritənin yalnız kiçik bir hissəsini göstərir, lakin yuxarıda göstərilən heuristik can hər hansı bir xəritə üçün daha dəqiq düzəldiləcək. Əgər 3-cü bölgənin bütün qonşuları (Şəkil 3, region 2 və 4-də) ən azı bir qonşu A rəngində (Şəkil 3, bölgü 1), onda rəng A olan 3-cü bölgənin rənglənməsi səhv ola bilməz. Səbəb isə A ilə rənglənmə bölgəsi 3-ə qonşularına heç bir yeni məhdudiyyət yaratmır, çünki artıq rəng A olması qadağandır. Beləliklə, əgər növbəti rəngləmə prosesində səhvin düzəldiyi ortaya çıxırsa (rənglərin sayı kifayət etmədiyi üçün), o zaman bölgü 3-ə A-dan fərqli rəng verməyin mənası yoxdur, bəzi digər rənglənmələr yenidən sınaqdan keçirilməlidir. - Bəs əgər yuxarıda 3-cü bölgə də başqa bir bölgənin diaqonal qonşusudursa, deyin ki, region 9-dur. Bu bölgənin artıq rəngi fərqlidir, B rəngi kimi? A və ya B ilə 3 rənglənməlidir? Həmçinin burada 3-cü qonşuların hamısını yoxlamağa kömək edir ki, onların artıq rəng A olması qadağandır, yoxsa rəng B-yə sahib olmaq qadağandır. Əgər belə deyilsə, onda 3 rənglə gözləyə bilərik.
Yeniliklər üçün izləyin və ya abunə olun: