Merhaba arkadaşlar, bugün javada harita renklendirme problemini kodladık.Sabahın 5 i olması nedeniyle açıklamayı sonra yapacam..Yazdığım kodu uzun uzun açıklamayı düşünüyorum..Güzel bir beyin jimnastiği oldu benim için de..Problemimiz kısaca şu:
Elimizde bir harita var,bu haritayı komşu şehirler aynı renkte olmayacak şekilde en az renkle nasıl boyarız?
Dört renk teoremi olarak da biliniyor bu problem.Onun da tanımı vikipedi ye göre şöyle:
Teorem: Sonlu sayıda bölgeden oluşan bir harita, birbirine sonsuz sayıda nokta boyunca komşu olan iki bölgenin renkleri birbirinden farklı olmak üzere, boyanacaksa bu işlem için dört rengin yeterli olacağı bir strateji vardır.
Bu teoremin doğrudan uygulamalarından birisi harita boyanmasıdır; eğer her ülkenin tek bölgeden oluştuğu varsayılırsa bir siyasi haritanın tüm ülkeleri, komşu ülkeler aynı renge boyanmadan dört renge boyanabilir. Ancak bu uygulamadaki varsayım, dünya haritası için uygun olmayıp Amerika Birleşik Devletleri ve Azerbaycan gibi birden fazla bölgeden oluşan ülkeler bulunmaktadır.
Bu konjektür (ispatsız, fakat doğruluğu tahmin edilen sanı) 1852’de Augustus De Morgan‘ın bir öğrencisi olan Francis Guthrie tarafından ileri sürüldü.
Kaynak:Vikipedi
Proplem çözümü için şehirleri komşuluk ilişkilerine göre graf a çevirdik ve programa bu ilişkileri dizi şeklinde girdik..Bu kod aşağıdaki gibi bir papatyanın boyanması için gerekli girdileri içeriyor..Herhangi bir harita için de yapabilirsiniz..
Bunların komşuluk değerlerini bir diziye aktardık.Çift taraflı graf şeklinde olduğu için komşu olan iki şehirden sadece birini eklememiz yeterli.Ayrac olarak nokta(.) kullandım,farklı bir şey de seçilebilir.
arrKomsuluk.add(“1.2”);
arrKomsuluk.add(“1.3”);
arrKomsuluk.add(“1.4”);
arrKomsuluk.add(“1.5”);
arrKomsuluk.add(“1.6”);
arrKomsuluk.add(“1.7”);
arrKomsuluk.add(“1.8”);
arrKomsuluk.add(“1.9”);
arrKomsuluk.add(“2.3”);
arrKomsuluk.add(“4.3”);
arrKomsuluk.add(“4.5”);
arrKomsuluk.add(“6.5”);
arrKomsuluk.add(“6.7”);
arrKomsuluk.add(“8.7”);
arrKomsuluk.add(“8.9”);
arrKomsuluk.add(“2.9”);
Proplemi Çözerken Kullandığım Algoritma:
1.Boyanacak şehirler dizisinin ilk şehrini getir(varsa) ve renkler dizisinden de bir renk al.
2.Şehre bu rengi ata ve boyanacak şehirler listesinden çıkar.
3.Bu şehirin komşularını, komşular listesine ekle.
4.Boyanacak şehirler dizisinde dolaş.
4.Eğer dolaşılan şehir, komşu değilse o şehri de boya.
5.Komşu şehirlere ,bu boyanan şehrin komşularını da ekle.
6.Eklenen şehri boyanacak şehir listesinden çıkar.
6.Seçilen renk artık hiçbir şehri boyuyamıyorsa bir sonraki şehre ve bir sonraki renge geç.
Yani bir renk alıp,bununla tüm komşu olmayan şehirleri boyuyoruz.Bu renk ile boyanabilecek şehir kalmayınca da bir sonraki renge geçiyoruz..Tüm harita boyanana kadar da bu işlemleri devam ediyoruz.
Çözüm kısmında “1.1” şeklinde verilen outputlar, 1.şehri 1.renk i ile boyayacağımız anlamına geliyor.Biraz daha anlaşılır gözükmesi için bu sayılara sembolik olarak şehirler ve renkler atadım.. Adana-Turuncu gibi..
Kodlarımız da şöyle;
[java]
package haritaboya;
import java.util.ArrayList;
import java.util.Objects;
public class HaritaBoya {
static ArrayList<Integer> arrRenkler = new ArrayList<Integer>();
static ArrayList<Integer> arrSehirler = new ArrayList<Integer>();
static ArrayList<String> arrKomsuluk = new ArrayList<String>();
static ArrayList<String> arrEslesme = new ArrayList<String>();
static ArrayList<String> arrRenkAdleri = new ArrayList<String>();
static ArrayList<String> arrSehirAdlari = new ArrayList<String>();
public static void main(String[] args) {
sehirAdiDoldur();
renkAdiDoldur();
int renkSinir = 5;
for (int i = 1; i <= renkSinir; i++) {
arrRenkler.add(i);
}
int sehirSinir = 9;
for (int i = 1; i <= sehirSinir; i++) {
arrSehirler.add(i);
}
arrKomsuluk.add("1.2");
arrKomsuluk.add("1.3");
arrKomsuluk.add("1.4");
arrKomsuluk.add("1.5");
arrKomsuluk.add("1.6");
arrKomsuluk.add("1.7");
arrKomsuluk.add("1.8");
arrKomsuluk.add("1.9");
arrKomsuluk.add("2.3");
arrKomsuluk.add("4.3");
arrKomsuluk.add("4.5");
arrKomsuluk.add("6.5");
arrKomsuluk.add("6.7");
arrKomsuluk.add("8.7");
arrKomsuluk.add("8.9");
arrKomsuluk.add("2.9");
System.out.println("");
for (int i = 1; i <= arrSehirler.size(); i++) {
ArrayList<Integer> arrKomsular = komsulariGetir(i);
diziGoster(arrKomsular, i + " nin Komsuları : ");
}
while (arrSehirler.size() > 0) {
int sehir = arrSehirler.get(0);
ArrayList<Integer> arrKomsular = komsulariGetir(sehir);
int renk = arrRenkler.get(0);
arrEslesme.add(sehir + "." + renk);
System.out.println("Eslesme = Sehir: " + sehir + ", Renk : " + renk);
arrSehirler.remove(0);
int sehirBoyut = arrSehirler.size();
for (int i = 0; i < sehirBoyut; i++) {
boolean komsuMu = false;
for (int j = 0; j < arrKomsular.size(); j++) {
System.out.println("Karsilastirilan : " + arrSehirler.get(i) + "," + arrKomsular.get(j));
if (Objects.equals(arrSehirler.get(i), arrKomsular.get(j))) {
komsuMu = true;
System.out.println("Komsusu var,Atlaniyor..");
break;
}
}
if (!komsuMu) {
System.out.println("İc Eslesme = Sehir: " + arrSehirler.get(i) + ", Renk : " + renk);
arrEslesme.add(arrSehirler.get(i) + "." + renk);
ArrayList<Integer> arrKomsularTmp = komsulariGetir(arrSehirler.get(i));
arrSehirler.remove(i);
sehirBoyut--;
i--;
for (Integer integer : arrKomsularTmp) {
arrKomsular.add(integer);
}
}
}
arrRenkler.remove(0);
System.out.println("---------------");
}
diziGoster(arrEslesme, "Cozum : ");
System.out.println("Sembolik Cozum :");
for (int i = 0; i < arrEslesme.size(); i++) {
int noktaIndex = arrEslesme.get(i).indexOf(".");
int sehirIndex = Integer.parseInt(arrEslesme.get(i).substring(0, noktaIndex));
int renkIndex = Integer.parseInt(arrEslesme.get(i).substring(noktaIndex+1, arrEslesme.get(i).length()));
// System.out.println("SehirIndex: " + --sehirIndex + ",renkIndex: " + --renkIndex);
System.out.println(arrSehirAdlari.get(--sehirIndex) + " - " + arrRenkAdleri.get(--renkIndex));
}
}
public static void diziGoster(ArrayList<?> arrTmp, String strDiziBasligi) {
System.out.print(strDiziBasligi);
for (Object object : arrTmp) {
System.out.print(object + " ");
}
System.out.println("");
}
public static ArrayList<Integer> komsulariGetir(int sehir) {
ArrayList<Integer> arrKomsularTmp = new ArrayList<Integer>();
for (String komsu : arrKomsuluk) {
int noktaIndex = komsu.indexOf(".");
int sehir1 = Integer.parseInt(komsu.substring(0, noktaIndex));
int sehir2 = Integer.parseInt(komsu.substring(noktaIndex + 1, komsu.length()));
if (sehir1 == sehir) {
arrKomsularTmp.add(sehir2);
} else if (sehir2 == sehir) {
arrKomsularTmp.add(sehir1);
}
}
return arrKomsularTmp;
}
public static void sehirAdiDoldur() {
arrSehirAdlari.add("Adana");
arrSehirAdlari.add("Tunceli");
arrSehirAdlari.add("Mardin");
arrSehirAdlari.add("İstanbul");
arrSehirAdlari.add("Mersin");
arrSehirAdlari.add("Konya");
arrSehirAdlari.add("Izmir");
arrSehirAdlari.add("Isparta");
arrSehirAdlari.add("Kocaeli");
arrSehirAdlari.add("Antalya");
}
public static void renkAdiDoldur() {
arrRenkAdleri.add("Mavi");
arrRenkAdleri.add("Kırmızı");
arrRenkAdleri.add("Sarı");
arrRenkAdleri.add("Yesil");
arrRenkAdleri.add("Beyaz");
arrRenkAdleri.add("Mor");
arrRenkAdleri.add("Kahverengi");
arrRenkAdleri.add("Gri");
}
}
[/java]
Çıktı:
run:
1 nin Komsuları : 2 3 4 5 6 7 8 9
2 nin Komsuları : 1 3 9
3 nin Komsuları : 1 2 4
4 nin Komsuları : 1 3 5
5 nin Komsuları : 1 4 6
6 nin Komsuları : 1 5 7
7 nin Komsuları : 1 6 8
8 nin Komsuları : 1 7 9
9 nin Komsuları : 1 8 2
Eslesme = Sehir: 1, Renk : 1
Karsilastirilan : 2,2
Komsusu var,Atlaniyor..
Karsilastirilan : 3,2
Karsilastirilan : 3,3
Komsusu var,Atlaniyor..
Karsilastirilan : 4,2
Karsilastirilan : 4,3
Karsilastirilan : 4,4
Komsusu var,Atlaniyor..
Karsilastirilan : 5,2
Karsilastirilan : 5,3
Karsilastirilan : 5,4
Karsilastirilan : 5,5
Komsusu var,Atlaniyor..
Karsilastirilan : 6,2
Karsilastirilan : 6,3
Karsilastirilan : 6,4
Karsilastirilan : 6,5
Karsilastirilan : 6,6
Komsusu var,Atlaniyor..
Karsilastirilan : 7,2
Karsilastirilan : 7,3
Karsilastirilan : 7,4
Karsilastirilan : 7,5
Karsilastirilan : 7,6
Karsilastirilan : 7,7
Komsusu var,Atlaniyor..
Karsilastirilan : 8,2
Karsilastirilan : 8,3
Karsilastirilan : 8,4
Karsilastirilan : 8,5
Karsilastirilan : 8,6
Karsilastirilan : 8,7
Karsilastirilan : 8,8
Komsusu var,Atlaniyor..
Karsilastirilan : 9,2
Karsilastirilan : 9,3
Karsilastirilan : 9,4
Karsilastirilan : 9,5
Karsilastirilan : 9,6
Karsilastirilan : 9,7
Karsilastirilan : 9,8
Karsilastirilan : 9,9
Komsusu var,Atlaniyor..
---------------
Eslesme = Sehir: 2, Renk : 2
Karsilastirilan : 3,1
Karsilastirilan : 3,3
Komsusu var,Atlaniyor..
Karsilastirilan : 4,1
Karsilastirilan : 4,3
Karsilastirilan : 4,9
İc Eslesme = Sehir: 4, Renk : 2
Karsilastirilan : 5,1
Karsilastirilan : 5,3
Karsilastirilan : 5,9
Karsilastirilan : 5,1
Karsilastirilan : 5,3
Karsilastirilan : 5,5
Komsusu var,Atlaniyor..
Karsilastirilan : 6,1
Karsilastirilan : 6,3
Karsilastirilan : 6,9
Karsilastirilan : 6,1
Karsilastirilan : 6,3
Karsilastirilan : 6,5
İc Eslesme = Sehir: 6, Renk : 2
Karsilastirilan : 7,1
Karsilastirilan : 7,3
Karsilastirilan : 7,9
Karsilastirilan : 7,1
Karsilastirilan : 7,3
Karsilastirilan : 7,5
Karsilastirilan : 7,1
Karsilastirilan : 7,5
Karsilastirilan : 7,7
Komsusu var,Atlaniyor..
Karsilastirilan : 8,1
Karsilastirilan : 8,3
Karsilastirilan : 8,9
Karsilastirilan : 8,1
Karsilastirilan : 8,3
Karsilastirilan : 8,5
Karsilastirilan : 8,1
Karsilastirilan : 8,5
Karsilastirilan : 8,7
İc Eslesme = Sehir: 8, Renk : 2
Karsilastirilan : 9,1
Karsilastirilan : 9,3
Karsilastirilan : 9,9
Komsusu var,Atlaniyor..
---------------
Eslesme = Sehir: 3, Renk : 3
Karsilastirilan : 5,1
Karsilastirilan : 5,2
Karsilastirilan : 5,4
İc Eslesme = Sehir: 5, Renk : 3
Karsilastirilan : 7,1
Karsilastirilan : 7,2
Karsilastirilan : 7,4
Karsilastirilan : 7,1
Karsilastirilan : 7,4
Karsilastirilan : 7,6
İc Eslesme = Sehir: 7, Renk : 3
Karsilastirilan : 9,1
Karsilastirilan : 9,2
Karsilastirilan : 9,4
Karsilastirilan : 9,1
Karsilastirilan : 9,4
Karsilastirilan : 9,6
Karsilastirilan : 9,1
Karsilastirilan : 9,6
Karsilastirilan : 9,8
İc Eslesme = Sehir: 9, Renk : 3
---------------
Cozum : 1.1 2.2 4.2 6.2 8.2 3.3 5.3 7.3 9.3
Sembolik Cozum :
Adana - Mavi
Tunceli - Kırmızı
İstanbul - Kırmızı
Konya - Kırmızı
Isparta - Kırmızı
Mardin - Sarı
Mersin - Sarı
Izmir - Sarı
Kocaeli - Sarı
BUILD SUCCESSFUL (total time: 0 seconds)
Bu da papatyamızın boyanmış hali(Photoshop da ben boyadım,programın öyle bir özelliği yok şimdilik).Şimdilik kolay gelsin arkadaşlar..
