UCS

Wilk, koza i kapusta – o UCS raz jeszcze

Ostatnio udało nam się znaleźć optymalne wyjście z labiryntu, uwzględniając różne czasy przejścia przez różne miejsca. Skomplikujmy zadanie. Niech robot przed wyjściem zbierze wszystkie monety. Jako bazę wykorzystajmy kod z poprzedniej części (przykładowe wyniki będą prezentowane dla wersji z czterema kierunkami ruchu zamiast ośmioma ale to nic nie zmienia. Rodzaje pól również zostają bez zmian (i również nie jest to istotne).

Reprezentacja stanu

Do tej pory stan świata był przedstawiony za pomocą pary współrzędnych (x,y). Teraz musimy dodać informację o monetach (sposób w jaki ich pozycje są ustalane nie będzie omawiany – nie jest to istotne z punktu widzenia rozważanego problemu). Najprostszym pomysłem wydaje się tablica wartości logicznych z informacją czy na danym polu znajduje się moneta. Zobaczmy ile będzie takich stanów. Labirynt ma rozmiar NM . Dla każdego pola są możliwe dwie wartości. Ilość możliwych kombinacji ustawień monet to 2^{MN} . W efekcie dostajemy coś koło 2^{MN} \ cdot MN . Dużo, nawet bardzo dużo. Spróbujmy inaczej – do informacji o pozycji robota dodajmy listę pól z monetami. Monet jest K. Możliwych list jest 2^K . Dostajemy 2^K \cdot MN. Jeśli monet jest znacząco mniej niż kafli labiryntu (K \ll MN) będzie to bardzo duża oszczędność. Osiągnęliśmy nie najgorszy efekt – 2^n rośnie wykładniczo (każde zmniejszenie n jest wartościowe) więc taka zmiana może być warta zachodu (innym miłym dodatkiem jest zmniejszenie użycia pamięci na reprezentację stanu wraz z rozwojem sytuacji kiedy monet jest coraz mniej).

Podsumowując, stan jest reprezentowany przez krotkę (x, y, coins_left) gdzie coins_left jest krotką z monetami pozostałymi na planszy.

Stan końcowy musi spełnić teraz dwa warunki. Stoimy na kaflu wyjściowym oraz nie pozostała żadna moneta do zebrania. (nic nie stoi ma przeszkodzie aby wystarczało tylko zebrać monety).

# sprawdź czy podany stan (x,y, c) jest stanem końcowym
def is_target_state(self, state):
	x, y, c = state
        return self.get_tile(state) == Tile.Target and len(c) == 0

Pozostało jeszcze zaimplementować get_after_decision oraz get_children. Niewielkie modyfikacje służą jedynie sprawdzeniu czy wskutek działania została zebrana moneta. Jedyna magia w kodzie polega na zamianie krotki na listę i odwrotnie.

# pobierz stan po podjęciu decyzji d w stanie state
def get_after_decision(self, state, d):
	x, y, c = state
	cc = list(c)
	dx, dy = Directions[d]
	if (x, y) in cc:
		cc.remove((x, y))
	return x + dx, y + dy, tuple(cc)
	
def get_children(self, state):
	x, y, c = state
	children = []
	# dla wszystkich potencjalnie możliwych ruchów
	for d in Directions:
		cc = list(c)
		dx, dy = Directions[d]
		# w zależności od typu kafla ustaw koszt przejścia
		t = self.get_tile((x + dx, y + dy, c))
		cost = 2 if t == Tile.Swamp else 1
		# jeżeli kafel zawierał monetę ustaw ją jako zebraną
		if (x + dx, y + dy) in cc:
			cc.remove((x + dx, y + dy))

		# jeżeli kafel nie jest ścianą dodaj do następników
		if t != Tile.Wall:
			children.append(((x + dx, y + dy, tuple(cc)), d, cost))
	# zapamiętaj fakt rozwinięcia (póki co nieistotne)
	self.expanded[y][x] = True
	if (x, y) in self.coins:
		self.coins.remove((x, y))

	return children

Zobaczmy jak to działa w praktyce.

dzxMWf

Zebranie monet

CRiKgn

Zebranie monet oraz wyjście

Voilà!

Wilk, koza i kapusta

Ariadna straciła pracę na rzecz komputera – Tezeuszowi do znalezienia Minotaura wystarczy UCS, ale we wstępie było o decyzjach w ogólności. Okazuje się, że jest to metoda na tyle uniwersalna aby poradzić sobie także z innymi problemami. Weźmy wszystkim znaną zagadkę z przewiezieniem przez rzekę wilka, kozy i kapusty. Brzmi ona następująco:

Pewien kupiec ma wilka, kozę i kapustę. Musi się on przeprawić przez rzekę i ma do dyspozycji jedną łódkę, do której może wejść w jednym momencie tylko on sam i jeden z przewożonych towarów. Wiadomo, że koza zje kapustę, a wilk kozę, gdy tylko któraś z tych par zostanie bez opieki. W jaki sposób kupiec ma pokonać rzekę nie tracąc przy tym żadnego z przewożonych towarów?

Kiedy człowiek zacznie się nad nią zastanawiać może pomyśleć następująco: „Ok, za pierwszym razem nie mogę zabrać ani wilka ani kapusty – musi to być koza. Kiedy wrócę mogę zabrać dowolnego z nich ale nie mogę zostawić ich razem…”
W poprzednim problemie nie było stanów które powodowały by porażkę które teraz się pojawiły. Jak możemy je obsłużyć? Na przynajmniej 3 sposoby.

1. Wykrywać stan porażki i informować o tym algorytm żeby go unikał.
2. Nie dopuszczać do pojawienia się takiego stanu w liście następników po rozwinięciu wierzchołka.
3. Przy próbie rozwinięcia stanu porażki zwrócić pustą listę następników – algorytm będzie musiał poszukać innej drogi gdyż ta jest ślepą uliczką.

Zdecydowałem się na 3 sposób gdyż jest on wg mnie najłatwiejszy w implementacji.

W jaki sposób należy pamiętać stan? Korzystam z z krotki 4 wartości logicznych mówiących czy dany osobnik jest po właściwej stronie rzeki. Dla wygody opakowałem to w klasę State.

class State:
    def __init__(self):
        self.human = False
        self.wolf = False
        self.goat = False
        self.cabbage = False

    def to_tuple(self):
        return self.human, self.wolf, self.goat, self.cabbage

    def from_tuple(self, t):
        self.human = t[0]
        self.wolf = t[1]
        self.goat = t[2]
        self.cabbage = t[3]

    def __str__(self):
        return 'Human: ' + str(self.human) + ' Wolf: ' + str(self.wolf) + ' Goat: ' + str(
            self.goat) + ' Cabbage: ' + str(self.cabbage)

Stan startowy oznacza że wszyscy są po złej stronie (4xFalse).

self.startState = State()

Stan końcowy wskazuje, że wszyscy są po właściwej stronie.

# sprawdź czy podany stan jest stanem końcowym
def is_target_state(self, state):
	s = State()
	s.from_tuple(state)
	return s.human and s.wolf and s.goat and s.cabbage

Sprawdzenie czy stan oznacza porażkę opera się prostym warunku.

def is_lose_state(self, s):
	return s.wolf == s.goat and s.wolf != s.human or s.goat == s.cabbage and s.goat != s.human

Rozwijając wierzchołek sprawdzamy czy stan nie oznacza porażki, jeżeli nie generujemy listę dozwolonych przejść.

def get_children(self, state):
	s = State()
	s.from_tuple(state)
	children = []

	if self.is_lose_state(s):
		return []

	#zawsze można przepłynąć pustą łódką
	no_transport = State()
	no_transport.human = not s.human
	no_transport.wolf = s.wolf
	no_transport.goat = s.goat
	no_transport.cabbage = s.cabbage

	children.append((no_transport.to_tuple(), "MOVE HUMAN", 1))

	if s.human == s.wolf:
		xd = State()
		xd.human = not s.human
		xd.wolf = not s.wolf
		xd.goat = s.goat
		xd.cabbage = s.cabbage
		children.append((xd.to_tuple(), "MOVE WOLF", 1))
	if s.human == s.goat:
		xd = State()
		xd.human = not s.human
		xd.goat = not s.goat
		xd.wolf = s.wolf
		xd.cabbage = s.cabbage
		children.append((xd.to_tuple(), "MOVE GOAT", 1))
	if s.human == s.cabbage:
		xd = State()
		xd.human = not s.human
		xd.cabbage = not s.cabbage
		xd.goat = s.goat
		xd.wolf = s.wolf
		children.append((xd.to_tuple(), "MOVE CABBAGE", 1))

	return children
	

I to wszystko. UCS nawet nie dotykaliśmy, wystarczyło zapewnić implementację kilku metod dla obiektu instance w sposób charakterystyczny dla problemu.

Panaceum?

Jeśli metoda jednolitego kosztu gwarantuje nam optymalne rozwiązanie to czy potrzebujemy czegoś więcej? Skoro to pytanie zostało postawione można się domyślić, że tak. O tym co możemy zrobić lepiej już niedługo.

Reklamy