Timeline for Average time to solve maze through backtracking
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 4, 2014 at 23:25 | comment | added | xiamx | Try to think how many times you will backtrack in average | |
| Nov 4, 2014 at 21:01 | comment | added | Gabriel Ratener | True, but as n increases, the probability of never having to backtrack becomes very small. | |
| Nov 4, 2014 at 20:04 | comment | added | xiamx | @GabrielRatener "The average height of the tree seems irrelevant in this case, since the algorithm must backtrack through multiple branches until it finds a series of branches that lead to a solution." The algorithm could have found the solution in the first branch it visits without ever having to backtrack. You need to look at average case, not worst case | |
| Nov 4, 2014 at 18:20 | comment | added | Gabriel Ratener | Would the ratio of the number of cells needing to be visited to the total number of cells in the maze change as the maze scales? | |
| Nov 4, 2014 at 18:18 | comment | added | Gabriel Ratener | The average height of the tree seems irrelevant in this case, since the algorithm must backtrack through multiple branches until it finds a series of branches that lead to a solution. | |
| Nov 4, 2014 at 14:22 | history | answered | xiamx | CC BY-SA 3.0 |