Solving the (n2 − 1)-Puzzle with 8/3 n3 Expected Moves
| Autor: | Ian Parberry |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: | |
| Zdroj: | Algorithms, Vol 8, Iss 3, Pp 459-465 (2015) |
| Druh dokumentu: | article |
| ISSN: | 1999-4893 |
| DOI: | 10.3390/a8030459 |
| Popis: | It is shown that the greedy algorithm for the \((n^2-1)\)-puzzle makes \(\tfrac{8}{3}n^3 +O(n^2)\) expected moves. This analysis is verified experimentally on 10,000 random instances each of the \((n^2-1)\)-puzzle for \(4 \leq n \leq 200\). |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|