For a psychology experiment - subject has to learn that the 2D grid is a checkerboard, and collect all the 1s (rewards). How do I test if subjects are actually doing it in the most optimal way -- making least effort for moving from one square to the next by taking smaller steps (or selecting closest reward neighbour). My guess is that if I could simulate a learning algorithm and approximate how long it takes to learn the reward distribution, and then explore it optimally (optimality is defined as a unit of time and exploring closest squares first), I could compare the behaviour.
1
-
\$\begingroup\$ It seems like you could also use a pathing algorithm like something based on A* to get an exact right answer so you wouldn't have to worry about your learning algorithm not finding the global minimum. \$\endgroup\$– Alan WolfeJun 17, 2015 at 2:51
Add a comment
|
1 Answer
\$\begingroup\$
\$\endgroup\$
If the grid size is large, this becomes unsolvable by a computer, as this is a NP problem.
See https://en.wikipedia.org/wiki/Travelling_salesman_problem
If your grid is small, you can get a computer to calculate all possibilities, and plan a optimal route. However, as your grid gets larger, your calculations get exponentially larger, to the point where it takes forever for a computer to determine the optimal path required.
To calculate all routes, a solution would be to utilize an A* pathfinding algorithm, to calculate the shortest path required to visit every single node.
You could calculate this by calculating every path possible, and taking the shortest one.
