We propose an approach to enhance the problem-solving process in case-based reasoning recommender systems, addressing the limitations of existing methods that rely solely on leveraging the system’s pre-acquired knowledge. The proposed approach involves exploring the space of possible solutions, with the primary objective not being to immediately find an optimal solution, but rather to discover new knowledge that can help improve the system’s performance in the future, leading to more informed and adaptive decision-making. To accelerate the knowledge discovery process, the exploration is built upon a heuristic designed to systematically focus on less dense yet promising regions of the solution space, rather than relying on a random search. Empirical evaluations were conducted in the context of energy consumption optimization in buildings. The results of these experiments demonstrate the potential of the proposed approach to improve system performance.