Timeline for Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 18, 2013 at 9:49 | comment | added | Roland Bacher | Parameters are $k$ and the numbers of vertices and edges of the initial graph. | |
| Feb 17, 2013 at 13:23 | comment | added | Günter Rote | A "given concrete Sokoban problem" can be always be solved in constant time. To meaningfully speak of polynomial time requires a problem with some inputs, some parameters, with an infinite family of instances. | |
| Feb 17, 2013 at 12:17 | comment | added | Alexander Chervov | Thank you for your answer ! Let me mention that what I describe in "Example of algorithm" is based on similar idea - create a "big-new-graph" and reduce the problem to existence of the path between two vertices in the "big-new-graph". What seems to be quite interesting to understand - how specific are these "Sokoban-graphs" ? Can we say in advance that it is better to use deepth-search instead of breadth-search algorithms ? | |
| Feb 17, 2013 at 8:01 | history | answered | Roland Bacher | CC BY-SA 3.0 |