V rámci procvičování na CodingGame jsem narazil na problém, do jehož řešení jsem dost zabředl. Jedná se o řešení hry Sliding Puzzle, tedy skládání kostiček do správného pořadí s využitím jednoho prázdného místa.
Vlastní bádání nad problémem bylo dost zábavné, proto bych se rád o něj podělil.
Budu vycházet z toho, že řeším hru o velikost 3×3 kostičky (ono v zadání je 4×3, ale na řešení to vliv nemá, je to jen jeden z parametrů).
Výchozí stav hry, tedy náhodně poskládané kostičky, můžu reprezentovat jako posloupnost čísel 0 až 8, kdy 0 představuje volné políčko. Posloupnost je poskládaná řazením řádků za sebou. Bylo by pochopitelně možné reprezentovat stav hry jako dvourozměrné pole, ale to by bylo asi komplikovanější na zápis i zpracování.
Konečný stav je ten, kdy jsou všechna čísla v posloupnosti seřazena vzestupně.
Tohle je příklad jednoho možného zadání:
[7, 5, 1, 3, 4, 2, 0, 8, 6] ==> [0, 1, 2, 3, 4, 5, 6, 7, 8]
Pokud bych mohl kostičky libovolně přehazovat, pak by bylo řešení triviální. Nicméně to v tomto případě nejde. Mohu jen posouvat kostičky do volného místa (nebo posouvat volné místo, jak se chcete na to dívat).
Z výchozího stavu se mohu posunout do jednoho z následujících stavů (volné místo mám v levém dolním rohu, takže jej můžu posunout doprava nebo nahoru):
[7, 5, 1, 3, 4, 2, 0, 8, 6] -> [[7, 5, 1, 3, 4, 2, 8, 0, 6], [7, 5, 1, 0, 4, 2, 3, 8, 6]]
A dále mohu vyzkoušet tyto stavy. Posunout se dále, a to vše opakovat, dokud nenajdu cílový stav.
Pokud budu postupně procházet všechny stavy hry postupným přesouváním kostiček, pak v podstatě procházím strom všech možných stavů a hledám cestu k tomu konečnému stavu.
Kdybych vycházel pouze z předchozí úvahy, pak by se nejednalo o strom: Byl by to graf s cykly, protože se můžu po několika tazích vrátit do stavu, ve kterém jsem již byl. Nicméně docela jednoduchým způsobem se dá zajistit, že se o strom jednat bude. Prostě nebudu pokračovat ve hledávání do stavu, který jsem již dříve navštívil.
Pro řešení se nabízí několik možností, které jsem postupně vyzkoušel:
U posledních dvou metod je možné ještě experimentovat s vyhodnocovacími pravidly a heuristikami.
Takže nakonec z toho vyšlo několik různých variant řešení.
A jdeme na to … nejdříve nějaké společné definice:
import heapq
W, H = 3, 3
MAX_COST = 50
final_state = list(range(W * H))
print(final_state)
[0, 1, 2, 3, 4, 5, 6, 7, 8]
heapq
ze standardní knihovny PythonVýsledkem vyhodnocovací funkce je počet tahů, kterými se dostanu z výchozího stavu do toho cílového.
def solve(initial_state, cost_function):
q = []
heapq.heappush(q, (cost_function(initial_state, 0), initial_state, 0))
visited_states = []
while q:
cost, state, moves = heapq.heappop(q)
if state == final_state:
return moves
else:
for st in next_states(state):
if st not in visited_states:
cost = cost_function(st, moves + 1)
if cost <= MAX_COST:
heapq.heappush(q, (cost, st, moves + 1))
visited_states.append(state)
return None
Pro běh hlavního algoritmu potřebuji pomocnou funkci, která mně vrátí všechny možné následující stavy pro zadaný stav:
def next_states(state):
i = state.index(0)
res = []
# UP
if i - W >= 0:
st = state[:]
st[i], st[i - W] = st[i - W], st[i]
res.append(st)
# DOWN
if i + W < W * H:
st = state[:]
st[i], st[i + W] = st[i + W], st[i]
res.append(st)
# LEFT
if i % W - 1 >= 0:
st = state[:]
st[i], st[i - 1] = st[i - 1], st[i]
res.append(st)
# RIGHT
if i % W + 1 < W:
st = state[:]
st[i], st[i + 1] = st[i + 1], st[i]
res.append(st)
return res
Výběr vyhodnocovací funkce rozhodne o variante použitého algoritmu, takže pro:
Tady to bude velice jednoduché, neboť stavy řešíme v pořadí, v jakém jsme na ně narazili při průchodu stromem v jednotlivých úrovních.
def cost_bfs(state, moves):
return moves
Pro vyhodnocení, jak „dobrý“ je zadaný stav, použiji počet rozdílných políček proti cílovému stavu. Při řešení bych tedy měl upřednostnit ty stavy, které jsou nejvíce podobné cílovému stavu.
def cost_tiles(state, moves):
return moves + len([(x, y) for x, y in zip(state, final_state) if x != y])
Do vyhodnocení ceny řešení zahrnu počet tahů, které jsem potřeboval k dosažení tohoto stavu, a heuristiku, kterou odhadnu počet tahů do cílového stavu.
Jako heuristiku použiji Manhattan vzdálenost všech kostiček proti cílovému stavu.
def cost_a_asterisk(state, moves):
dist = 0
for i1, val in enumerate(final_state):
i2 = state.index(val)
x1, y1 = i1 % W, i1 // H
x2, y2 = i2 % W, i2 // H
dist += abs(x1 - x2) + abs(y1 - y2)
return moves + dist
A teď bych již měl mít vše, co potřebuji pro testování jednotlivých variant řešení.
Připravil jsem si testovací vzorky, na kterých zkusím jednotlivé algoritmy a vyhodnocovací funkce. Dále budu měřit čas, jak dlouho mně trvá vyhledání výsledku.
Testovací vzorky jsem vytvářel náhodným přesouváním kostiček z výchozího stavu. Podle toho, kolik náhodných tahů provedu, dostanu více složité zadání.
V prvním testovacím vzorku jsem udělal 30 náhodných tahů. Vzhledem k tomu, že výsledky pro BFS jsou výrazně horší než pro zbylé dva algoritmy, udělal jsem ještě jednu sadu se 100 náhodnými tahy.
samples_30 = [
[3, 1, 4, 6, 2, 8, 0, 7, 5],
[4, 2, 7, 1, 0, 3, 6, 8, 5],
[2, 6, 0, 1, 3, 5, 7, 8, 4],
[4, 1, 0, 3, 6, 2, 7, 8, 5],
[3, 1, 4, 6, 2, 8, 0, 7, 5],
]
samples_100 = [
[3, 7, 1, 6, 2, 5, 0, 8, 4],
[3, 2, 7, 5, 8, 4, 6, 1, 0],
[3, 5, 0, 6, 7, 1, 2, 8, 4],
[1, 8, 7, 3, 0, 4, 5, 2, 6],
[0, 4, 8, 6, 5, 2, 3, 1, 7],
[0, 1, 7, 6, 3, 2, 8, 4, 5],
]
def timed(func):
def func_wrapper(*args, **kwargs):
import time
start_time = time.time_ns()
result = func(*args, **kwargs)
end_time = time.time_ns()
return result, (end_time - start_time) // 10**6
return func_wrapper
@timed
def timed_solve(st, f):
return solve(st, f)
print("*** 1. sample set (30 random moves)", "*"*24)
for sample in samples_30:
print(sample)
res = timed_solve(sample, cost_bfs)
print(f" BFS: ==> moves required: {res[0]:4d}, time consumed: {res[1] / 1000:.03f}")
res = timed_solve(sample, cost_tiles)
print(f" Dijkstra: ==> moves required: {res[0]:4d}, time consumed: {res[1] / 1000:.03f}")
res = timed_solve(sample, cost_a_asterisk)
print(f" A*: ==> moves required: {res[0]:4d}, time consumed: {res[1] / 1000:.03f}")
print()
print("*** 2. sample set (100 random moves)", "*"*24)
for sample in samples_100:
print(sample)
res = timed_solve(sample, cost_tiles)
print(f" Dijkstra: ==> moves required: {res[0]:4d}, time consumed: {res[1] / 1000:.03f}")
res = timed_solve(sample, cost_a_asterisk)
print(f" A*: ==> moves required: {res[0]:4d}, time consumed: {res[1] / 1000:.03f}")
*** 1. sample set (30 random moves) ************************ [3, 1, 4, 6, 2, 8, 0, 7, 5] BFS: ==> moves required: 14, time consumed: 1.021 Dijkstra: ==> moves required: 14, time consumed: 0.004 A*: ==> moves required: 14, time consumed: 0.002 [4, 2, 7, 1, 0, 3, 6, 8, 5] BFS: ==> moves required: 12, time consumed: 0.209 Dijkstra: ==> moves required: 12, time consumed: 0.001 A*: ==> moves required: 12, time consumed: 0.000 [2, 6, 0, 1, 3, 5, 7, 8, 4] BFS: ==> moves required: 16, time consumed: 7.465 Dijkstra: ==> moves required: 16, time consumed: 0.013 A*: ==> moves required: 16, time consumed: 0.001 [4, 1, 0, 3, 6, 2, 7, 8, 5] BFS: ==> moves required: 12, time consumed: 0.153 Dijkstra: ==> moves required: 12, time consumed: 0.001 A*: ==> moves required: 12, time consumed: 0.002 [3, 1, 4, 6, 2, 8, 0, 7, 5] BFS: ==> moves required: 14, time consumed: 1.182 Dijkstra: ==> moves required: 14, time consumed: 0.004 A*: ==> moves required: 14, time consumed: 0.002 *** 2. sample set (100 random moves) ************************ [3, 7, 1, 6, 2, 5, 0, 8, 4] Dijkstra: ==> moves required: 16, time consumed: 0.015 A*: ==> moves required: 16, time consumed: 0.003 [3, 2, 7, 5, 8, 4, 6, 1, 0] Dijkstra: ==> moves required: 22, time consumed: 4.363 A*: ==> moves required: 22, time consumed: 0.083 [3, 5, 0, 6, 7, 1, 2, 8, 4] Dijkstra: ==> moves required: 20, time consumed: 0.661 A*: ==> moves required: 20, time consumed: 0.121 [1, 8, 7, 3, 0, 4, 5, 2, 6] Dijkstra: ==> moves required: 22, time consumed: 5.387 A*: ==> moves required: 22, time consumed: 0.035 [0, 4, 8, 6, 5, 2, 3, 1, 7] Dijkstra: ==> moves required: 20, time consumed: 0.472 A*: ==> moves required: 20, time consumed: 0.046 [0, 1, 7, 6, 3, 2, 8, 4, 5] Dijkstra: ==> moves required: 18, time consumed: 0.075 A*: ==> moves required: 18, time consumed: 0.014
Jak se asi dalo očekávat, nejslibnější výsledky dává algoritmus A* s heuristikou počítanou jako Manhattan vzdálenost všech kostiček proti cílovému stavu.
Na Googlu je možné najít další varianty řešení s lepším odhadem potřebných tahů, jako je třeba „Linear conflicts heauristic“.
Jak jsem již psal v úvodu, tenhle problém jsem řešil v rámci cvičení na CodingGame.
To, co mne ještě dost zabavilo, bylo následující pravidlo pro danou hru:
Constraints:
Response time first turn ≤ 1000ms
Jinak řečeno, výsledek jsem potřeboval dostat do jedné sekundy. A to byl dost velký problém.
Některé úpravy, které jsem udělal pro zlepšení rychlosti řešení:
Manhattan distance
s korekcí na Linear Conflicts
No a dále uvádím výsledek svého snažení bez dalších zbytečných komentářů:
import sys
import heapq
W = 4
H = 3
MAX_COST = 50
initial_state = []
for i in range(3):
for j in input().split():
x = int(j)
initial_state.append(x)
class Tiles:
def __init__(self, seq):
self.data = tuple(seq)
self.value = int(''.join(("{0:02d}".format(i) for i in self.data)))
def __eq__(self, other):
return self.value == other.value
def __iter__(self):
return iter(self.data)
def __len__(self):
return len(self.data)
def __getitem__(self, key):
return self.data[key]
def __lt__(self, other):
return self.value < other.value
def __str__(self):
return f"Tiles:[val={self.value}, data={self.data}]"
def index(self, value):
return self.data.index(value)
def next_states(self):
def swap(data, a, b):
for i in range(len(data)):
if i == a:
yield data[b]
elif i == b:
yield data[a]
else:
yield data[i]
i, st = self.data.index(0), []
if i - W >= 0:
st.append(Tiles(swap(self.data, i, i - W)))
if i + W < len(self.data):
st.append(Tiles(swap(self.data, i, i + W)))
if i % W - 1 >= 0:
st.append(Tiles(swap(self.data, i, i - 1)))
if i % W + 1 < W:
st.append(Tiles(swap(self.data, i, i + 1)))
return st
start_state = Tiles(initial_state)
final_state = Tiles(range(W * H))
def get_manhattan_distance(a, b=final_state):
dist = 0
for i1, val in enumerate(a):
if val:
i2 = b.index(val)
x1, y1 = i1 % W, i1 // H
x2, y2 = i2 % W, i2 // H
dist += abs(x1 - x2) + abs(y1 - y2)
return dist
def get_linear_conflicts(a):
rows = (tuple((a[i + j] for j in range(0, W) if i <= a[i + j] < i + W)) for i in range(0, len(a), W))
conflicts = 0
for row in rows:
if not row:
continue
min_value = row[0]
for i in range(len(row)):
if row[i] < min_value:
conflicts, min_value = conflicts + 1, row[i]
return conflicts
def get_linear_distance(a, b=final_state):
return get_manhattan_distance(a, b) + get_linear_conflicts(a)
def solve_a_asterisk(st, f):
q = []
heapq.heappush(q, (f(st), st, []))
visited = set()
while q:
pri, state, prev = heapq.heappop(q)
prev.append(state)
visited.add(state.value)
if state == final_state:
return prev
else:
for t in state.next_states():
if t.value not in visited:
cost = len(prev) + f(t)
if cost <= MAX_COST:
heapq.heappush(q, (cost, t, prev[:]))
return []
res = solve_a_asterisk(start_state, get_manhattan_distance)
for m in res[1:]:
i = m.index(0)
print(i // W, i % W)
A to je vše.
Pokud budete chtít experimentovat, pak zde je zdroj článku.
A nezkoušel jsi napsat algoritmické řešení, místo brute force? To by mělo být podstatně rychlejší. Myšleno runtime, nikoliv na dobu vývoje :-)
Pokud se dobře pamatuju z dětsví, skládal jsem vždy prvních N - 2 řádků, pak M - 2 sloupců a na posledních 4 pole v rohu už by šlo mít předpočítanou koncovku pro všechny varianty.
Zkoušel, ale nepodařilo se mi vymyslet postup tak, abych se vešel do maximálního počtu tahů. Tím ale netvrdím, že to nejde.
Do maximálního počtu tahů 50 pro úlohu 3x4 se dá vejít v 99.9995% případů, ale z 1219 stavů to nejde. V nejhorším případě to z 18 stavů vyžaduje 53 tahů. Vycházel jsem z toho, že počet stavů je factorial(12)/2 takže takovou mapu nejkratší vzdálenosti od výchozího stavu stihne notebook snadno v Pythonu sestavit přes noc. (Taková mapa by se mohla hodit pro trénování parametrů rychlého heuristického algoritmu přibližného hodnocení vzdálenosti.)
Tohle jsem onehdy vyresil pro arduino i s grafickym spracovanim. Pricemz arduino nema ani 2 KB Ram.
https://github.com/Trsek/loyd15
https://www.youtube.com/watch?v=_v7p95zSl_I&feature=youtu.be
ja by som take dve drobnosti rad podotkol:
- to co volas Dijkstrovym algoritmom nie je v skutocnosti Dijkstrov algoritmus, ale iba A* s inou (horsou) heuristikou. Dijkstrov algoritmus je zovseobecnenim BFS pre pripady, ze vzdialenosti medzi stavmi mozu byt vacsie ako 1. A* je generalizacia Dijkstrovho algoritmu s pouzitim heuristiky.
- tvoje BFS je tak vyrazne pomale, lebo robis zakladnu chybu pri BFS: do visited_states vrchol pridavas az ked ho vyberies z fronty.., nie v momente ked ho pridavas do fronty, takze sa ti moze stat, ze vrchol mas vo fronte viackrat (ked donho existuje viacero ciest rovnakej dlzky, co v tomto grafe plati dost casto), navstivis ho teda viackrat, a z linearnej casovej zlozitosti (vrcholy maju max. stupen 4) mas zrazu exponencialnu...
Super clanok, aspon som sa tiez nieco naucil, napr. ze existuje heapq. Cele by sa mi to urcite nechcelo riesit, ale aspon som to trocha pooptimalizoval. Napr. len zamenou 2 riadkov som urobil asi o 40% vyssi vykon:
class Tiles: def __init__(self, seq): self.data = bytes(seq) self.value = self.data
Povodne mi ten kod ale nezbehol cez test case 8 (38), stale uletel timeoutom, tak som to este dalej optimalizoval a par zmenami sa mi to podarilo zbehnut. Aj ked je pravda, ze to nezbehne stale, treba parkrat kliknut na opakovany test8, ale asi na 20-30% to zbehne bez timeoutu.
Upravil som to, ze som vlastne cele Tiles zrusil, pouzil priamo bytes a z next_states som urobil funkciu. Dalej som este upravil swap, aby bol rychlejsi pre pouzitie bytes:
def swap(data, a, b): if a<b: return data[:a]+data[b:b+1]+data[a+1:b]+data[a:a+1]+data[b+1:] return data[:b]+data[a:a+1]+data[b+1:a]+data[b:b+1]+data[a+1:]
Ak ma niekto zaujem, zverejnim aj cely kod.
Povodny kod riesil 20 opakovani tych testov co su v clanku asi 1290ms, upraveny na bytes asi 818ms, vratane vsetok uprav asi 448ms, takze ten novy zbehne asi za 1/3 casu.
Samozrejme riesenie s bytes je obmedzene na puzzle velkosti x*y<256, ale ak by ste chceli vacsie, je vhodne este pouzit array.array, tam mozete s dobrym vykonom ist az do velmi velkych puzzle.
Hodnotící funkce pro dijkstru je špatně. Správná hodnotící funkce pro dijkstru je rovná ceně stavu - tedy minimálnímu počtu tahů od počátečního stavu. V tomto jednoduchém případě, kdy cena přechodu do dalšího stavu je rovná jedné, je dijkstra prakticky totožný s DFS.
To co uvádíte není dijkstra, dokonce to může dávat "horší" výsledek než dijkstra, protože hodnotí nízkým score stav: (0<-5<-6), tedy:
5 1 2
3 4 6
0 7 8
Ten ale rozhodně není blízko cílovému stavu.
V podstatě dijkstra je "vážený" DFS, kde "hloubka" není rovná počtu přechodů ale ceně stavu, tedy nejkratší cestě do daného stavu. To je zajímavé pokud různé tahy mají různou cenu (například kdyby horizontální přesun stál 1 a vertikální přesun stál 100 - potom by se snažil najít cestu s minimálním počtem vertikálních přesunů a teprve mezi řešeními se stejným počtem vertikálních přesunů by hledal to s nejmenším počtem horizontálních).
Jo, a self.data.index(x) má složitost N (což v případě 4x3 je 12, takže docela rychlé, ale v případě 50x50 už by to bylo znát).
Obecně denormalizace - uchování "zbytečných" předpočítaných hodnot ve stavu (jako třeba index(0)) - umožňuje často zrychlit alogritmus za cenu (většinou mírně) vyšších nároků na pamět.
pracuje na pozici IT architekta. Poslední roky se zaměřuje na integrační a komunikační projekty ve zdravotnictví. Mezi jeho koníčky patří také paragliding a jízda na horském kole.
Přečteno 24 511×
Přečteno 22 960×
Přečteno 18 574×
Přečteno 17 531×
Přečteno 16 786×