Chodź, pomaluj mój świat – kolorowanie mapy (grafu)

Ostatnim razem opracowaliśmy reprezentację niezbyt ogólną. Zanim zaczniemy ulepszać algorytm poprawmy implementację. Zamiast używać zmiennych i ograniczeń zamodelujemy całość w postaci grafu.

geo-map-australia-and-new-zealand-contour

Weźmy następujący problem. (Przykład pochodzi z książki Artificial Intelligence: A Modern Approach).
Mamy mapę Australii podzieloną na okręgi administracyjne. Należy ją pokolorować, oczywiście tak aby żadne dwa sąsiadujące nie używały tego samego koloru. Zgodnie z ostatnio używanymi oznaczeniami mamy 7 zmiennych:
\text{WA}, \text{NT}, \text{ST}, \text{Q}, \text{NSW}, \text{V}, \text{T} \in \{ \text{R}, \text{G}, \text{B} \}
gdzie R, G i B są kolorami. Ograniczenia prezentują się następująco:
\text{WA} \neq \text{ST} \newline  \text{NT} \neq \text{ST} \newline  \text{NSW} \neq \text{ST} \newline  \text{V} \neq \text{ST} \newline  \text{NT} \neq \text{Q} \newline  \text{NSA} \neq \text{V}\newline  \text{NSA} \neq \text{Q} \newline  \text{WE} \neq \text{NT}

Całość problemu można przedstawić jako graf. Zmienne będą wierzchołkami, ograniczenia – krawędziami między węzłami oznaczającymi związane zmienne.aus

Skutkiem ubocznym takiej reprezentacji jest natychmiastowe zauważenie, że Tasmania (T) nie ma narzuconych żadnych ograniczeń. Jeśli taki graf nie jest spójny (czyli da się go „rozdzielić” na kilka części) oznacza to, że poszczególne „kawałki” (składowe spójne) są osobnymi podproblemami, niezależnymi od siebie. Bardzo pożądana sytuacja.

Zaraz, wszystko super kiedy w ramach jednego ograniczenia występują dwie zmienne. A co jeśli jest ich więcej? Wtedy wprowadzamy inny typ wierzchołków do oznaczenia więzów. Dla przykładu z poprzedniego posta (kwadraty magiczne, wersja 3×3 aby było mniej bazgrołów):

magicsquaregraph3x3

Kolory nie wskazują na nic szczególnego, służą jedynie podniesieniu czytelności. Kwadraty są węzłami symbolizującymi ograniczenia miedzy zmiennymi.

Uaktualnijmy implementację.

Na początek ponumerujmy wierzchołki od zera do 6 (włącznie) w kolejności: WA, NT, ST, Q, NSW, V, T.

Wprowadzamy dziedzinę zmiennych jako obiekty klasy Color

class Color:
    def __init__(self):
        pass

    Red, Green, Blue = range(3)

Zmienne przyjmują teraz wartości z dziedziny {Red, Green, Blue} przez co zmienia się konstruktor klasy Variable.

class Variable(object):
    def __init__(self, fixed_value=None):
        self.domain =  [Color.Red, Color.Green, Color.Blue] if fixed_value is None else [fixed_value]
        self._value = fixed_value
	#...

W klasie Color będącej odpowiednikiem poprzedniej MagicSquare definiujemy graf. Robię to poprzez listę krawędzi, gdyż tak będzie mi później bardzo wygodnie.

class Color(object):
    def __init__(self):
        self.constraints = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5)]
	#...

Modyfikuję początkowe przypisanie tak aby składało się z samych wartości None

def get_initial_assignment(self):
        return Assingment(self.get_variables_from_values([None] * 7))

Dodaję drobną metodę sprawdzającą czy dla pojedynczej krawędzi są spełnione warunki. Jeśli zmienne są sobie równe to nastąpiło naruszenie, jeżeli nie wszystko jest OK. Oczywiście sytuacja gdzie obie są równe None jest jak najbardziej dozwolona.

def edge_invalid(self, a, b):
	if not a.is_assigned or not b.is_assigned:
		return False

	return a.value == b.value

Na koniec uaktualniam is_violating_constraints

def is_violating_constraints(self, assignment):
	# alias co by mniej pisać 😉
	v = assignment.variables

	for a, b in self.constraints:
		if self.edge_invalid(v[a],v[b]):
			return True

        return False

Wynik wykonania:

geo-map-australia-and-new-zealand-contour

Mamy teraz bazę, gotową do dalszego szlifowania, o czym już wkrótce.

Całość kodu

Obrazek tytułowy pochodzi ze slajdów do kursu CS 188: Artificial Intelligence prowadzonego przez UC Berkeley.

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s