Questa domanda riguarda la progettazione di una funzione ricorsiva che modifica lo stato di un gruppo di elementi elaborandone uno alla volta, con l'obiettivo di raggiungere uno stato desiderato.
Lo stato iniziale degli elementi è uno che non soddisfa i requisiti. Cerchiamo di correggerlo elaborando determinati elementi che possiamo scegliere come target, ma una volta che un elemento è stato elaborato correttamente, anche quelli relativi ad esso devono essere elaborati per bilanciare l'azione precedente. Quindi, quelli relativi a questi devono essere elaborati anche a loro volta, e così via, cue la funzione ricorsiva.
def satisfy(e, visited_elements=set()):
# e is an element that is in such state that is preventing the whole from being satisfied
visited_elements.add(e)
# the element is processed in a way that aims to satisfy the state
if e.process():
# if e is processed, other specific elements need to be processed too
# these are not directly related to e, but to a group g related to e
# processing successfully all elements in any of these groups will do
for g in e.related_groups:
if all([satisfy(r, visited_elements) for r in g.related_elements(exclude=visited_elements)]):
return True
# if processing e fails, or the related elements could not be processed, the action needs to be undone
e.undo_process()
# so that it can be used again in a different combination
visited_elements.remove(e)
return False
La soluzione viene raggiunta se una particolare combinazione di elementi viene elaborata. Una particolare combinazione di elementi è ciò che chiamiamo uno stato (del tutto).
Il problema è che il numero totale di combinazioni è così grande che restiamo bloccati in una catena molto lunga. L'unico modo per garantire che venga fermato a un tempo ragionevole è la rimozione di visited_elements.remove(e) , ma in questo modo ridurremmo notevolmente lo spazio degli stati da visitare e ignoreremmo le possibili soluzioni.
Quindi, quando abbiamo una funzione ricorsiva che genera combinazioni o stati che potrebbero potenzialmente richiedere molto tempo, cosa possiamo fare per limitarlo?
Se la risposta sta arrivando con condizioni di arresto, cosa posso fare per aiutarmi a identificare quale sia una buona condizione di arresto per il mio problema quando non esiste un modo semplice per aiutare l'algoritmo a prendere una decisione migliore? (la decisione qui sarebbe quali elementi da elaborare per primi, e quali gruppi o gruppi correlati sembrano più promettenti rispetto agli altri)