0
\$\begingroup\$

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.

\$\endgroup\$
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 Wolfe Jun 17 '15 at 2:51
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.