Summary: Probabilistic classifier chains have recently gained interest in multi-label classification, due to their ability to optimally estimate the joint probability of a set of labels. The main hindrance is the excessive computational cost of performing inference in the prediction stage. This pitfall has opened the door to propose efficient inference alternatives that avoid exploring all the possible solutions. The \(\epsilon \)-approximate algorithm, beam search and Monte Carlo sampling are appropriate techniques, but only \(\epsilon \)-approximate algorithm with \(\epsilon =0\) theoretically guarantees reaching an optimal solution in terms of subset 0/1 loss. This paper offers another alternative based on heuristic search that keeps such optimality. It consists of applying the \(\mathrm{A}^*\) algorithm providing an admissible heuristic able to explore fewer nodes than the \(\epsilon \)-approximate algorithm with \(\epsilon =0\). A preliminary study has already coped with this goal, but at the expense of the high computational time of evaluating the heuristic and only for linear models. In this paper, we propose a family of heuristics defined by a parameter that controls the trade-off between the number of nodes explored and the cost of computing the heuristic. Besides, a certain value of the parameter provides a method that is also suitable for the non-linear case. The experiments reported over several benchmark datasets show that the number of nodes explored remains quite steady for different values of the parameter, although the time considerably increases for high values. Hence, low values of the parameter give heuristics that theoretically guarantee exploring fewer nodes than the \(\epsilon \)-approximate algorithm with \(\epsilon =0\) and show competitive computational time. Finally, the results exhibit the good behavior of the \(\mathrm{A}^*\) algorithm using these heuristics in complex situations such as the presence of noise.