Cost-Effective Algorithms for Average-Case Interactive Graph Search