Solving the \((n^2-1)\)-puzzle with \(\frac{8}{3}n^3\) expected moves (Q1736675): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Normalize DOI. |
||
| Property / DOI | |||
| Property / DOI: 10.3390/a8030459 / rank | |||
| Property / DOI | |||
| Property / DOI: 10.3390/A8030459 / rank | |||
Normal rank | |||
Latest revision as of 06:57, 11 December 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Solving the \((n^2-1)\)-puzzle with \(\frac{8}{3}n^3\) expected moves |
scientific article |
Statements
Solving the \((n^2-1)\)-puzzle with \(\frac{8}{3}n^3\) expected moves (English)
0 references
26 March 2019
0 references
Summary: It is shown that the greedy algorithm for the \((n^2-1)\)-puzzle makes \(\frac{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\).
0 references
15-puzzle
0 references
8-puzzle
0 references
analysis of algorithms
0 references
average-case analysis
0 references
greedy algorithm
0 references
\((n^2-1)\)-puzzle
0 references
