Backtracking du FPTAS

[laowantong]

Je me suis rendu compte qu’il y avait dans quelques instances une incohérence entre le c_max calculé et celui que je retrouvais par backtracking. Il s’avère que mon backtracking était faux. Et après m’être arraché quelques cheveux (des blancs, quitte à faire), j’en suis arrivé à la quasi-certitude que là encore, il n’y avait pas suffisamment d’informations dans le quadruplet pour faire la remontée.

Alors bien sûr, il y a la possibilité de stocker une information de plus pour pouvoir remonter. Mais ce serait contourner un problème qui me paraît en soi relativement intéressant. Est-ce qu'on pourrait : soit prouver l’impossibilité, soit trouver une méthode pour remonter sans erreur ?

À creuser !

[laowantong]

NB: actuellement, le backtracking proposé donne un résultat faux sur certaines instances, comme on peut s'en convaincre en décommentant l'avant-dernière ligne de cette fonction :

tree_structure/solver_fptas.py

Lines 42 to 72 in 9c4e1e8

	def retrieve_solution(self):
	"""Backtrack the logged states to tell which tiles are assigned to which bins."""
	assert self.log_result, "could not retrieve the solution when logging is disabled."
	self.best_states = [min(self.log_result[-1], key=lambda state: max(state[0], state[1]))]
	new = len(self.log_result) - 1
	for states in reversed(self.log_result[:-1]):
	best_state = self.best_states[-1]
	for state in states:
	if (
	best_state[0] > state[0]
	and best_state[1] == state[1]
	and best_state[3] == state[3]
	) or (
	best_state[1] > state[1]
	and best_state[0] == state[0]
	and best_state[2] == state[2]
	):
	self.best_states.append(state)
	break
	else:
	raise ValueError(f"cannot match {self.best_states[-1]} in {states}.")
	new -= 1
	tiles1 = set(state[2] for state in self.best_states if state[2] != NO_LAST_TILE)
	tiles2 = set(state[3] for state in self.best_states if state[3] != NO_LAST_TILE)
	w1 = sum(symbol.weight for symbol in merge_tiles(self.tiles[i] for i in tiles1))
	w2 = sum(symbol.weight for symbol in merge_tiles(self.tiles[i] for i in tiles2))
	c_max = max(w1, w2)
	assert not tiles1.intersection(tiles2), "the two bins have some tiles in common."
	assert len(tiles1.union(tiles2)) == self.tile_count, "some tiles were not assigned."
	# assert self.c_max == c_max, f"c_max: {self.c_max} (calculated) ≠ {c_max} (retrieved)."
	return (sorted(tiles1), sorted(tiles2))

[laowantong]

@SarahMinich Après discussion avec @imedk , on pense que c'est un bon petit problème pour toi : que le résultat soit positif (tu prouves que la remontée est possible avec seulement les informations nécessaires à la descente) ou négatif (tu construis un contre-exemple), c'est quelque chose que tu peux faire apparaître dans ton rapport de thèse.

[SarahMinich]

Je me penche sur la question !

[laowantong]

Quand tu auras les réponses, j'écrirai si nécessaire le stockage des informations permettant la remontée en m'arrangeant pour ne pas pénaliser le solveur si on ne veut pas les calculer.