Serve un algoritmo semi-efficiente per la sequenza crescente tridimensionale

Question

Serve un algoritmo semi-efficiente per la sequenza crescente tridimensionale

#1 da (3 voti)

1

Ho una serie di sfide puzzle per un prototipo di kit puzzle, simile ai prodotti commerciali offerti da Thinkfun e Popular Playthings. Ho una lista di candidati di 300 rompicapo e vorrei selezionarne 40. Per ogni sfida, ho un valore numerico che rappresenta la difficoltà della sfida, un altro valore che rappresenta la difficoltà della sfida dopo un suggerimento e un terzo valore che rappresenta la difficoltà della sfida dopo che è stato dato un secondo suggerimento.

Quando presento i puzzle ordinati per difficoltà, idealmente i puzzle dovrebbero avere ancora la stessa difficoltà relativa dopo che è stato fornito un suggerimento. Ad esempio, un puzzle difficile con un suggerimento non dovrebbe essere più facile di un puzzle facile con un suggerimento. Se riesco a selezionare 40 puzzle con quella proprietà, allora ho il vantaggio di poter dire "per i bambini più piccoli, dare due suggerimenti per ogni puzzle" e non dover riordinare i numeri del puzzle.

Non ho davvero bisogno di tutti i sottoinsiemi di 40 che corrispondono ai miei criteri, solo uno buono. Se avessi una lista di tutti i sottoinsiemi, comunque, sarei in grado di sceglierne uno usando più desiderata. Ad esempio, troverei uno che i migliori cluster in quattro gruppi di 10, e quindi etichettare le sfide "facile", "medio", "difficile" e "esperto".

Mi piacerebbe trovare tutti i sottoinsiemi di 40 punti in modo che, indipendentemente da quale dimensione ordino il sottoinsieme, l'ordine è lo stesso.

In altre parole, trova un sottoinsieme {P0, P1, P2, ... P39} in modo che ogni volta che A < B, X [PA] < X [PB], Y [PA] < Y [PB] e Z [PA] < Z [PB].

Ho provato uno stupido algoritmo greedy ricorsivo ed è troppo lento.

algorithms efficiency

posta onigame 12.06.2015 - 01:57

fonte

1 risposta

Leggi altre domande sui tag algorithms efficiency

Aggiornamento parziale della tabella del database Come far funzionare 100k linee di codice orfano [duplicato]

score 3 · Answer 1

Alla fine ho ottenuto la risposta che volevo da un approccio di programmazione dinamica più intelligente.

L'intuizione è stata rendersi conto che sebbene la natura del mio problema non permettesse un ordinamento totale di tutti gli elementi, ha permesso un ordinamento parziale di tutti gli elementi. La sfida, quindi, era calcolare i rivestimenti in quell'ordine parziale. Per fare ciò, ho usato il seguente algoritmo.

for each Point in (all points sorted increasingly by dimension X)
   let Coverings[Point] = empty set
   let Lowerset[Point] = empty set
   let Candidates = {all previous points}
   for each PrevPoint in (all previous points sorted decreasingly by dimension X) 
      if (PrevPoint in Candidates and PrevPoint < Point)
         add PrevPoint to Coverings[Point]
       let Lowerset[Point] = union(Lowerset[Point], Lowerset[PrevPoint], PrevPoint)
         let Candidates = intersection(Candidates, inverse(Lowerset[PrevPoint]))
     endif
    end for
end for

Avere le righe sui Candidati non è strettamente necessario, ma rende il codice un po 'più efficiente non dovendo controllare continuamente gli stessi nodi.

Una volta ottenuto il set di tutti i rivestimenti, sono stato quindi in grado di inviarlo a punti Graphviz per generare un diagramma di Hasse per il mio set.

E guardando il mio diagramma di Hasse , sono stato subito in grado di dire che il diametro di il mio grafico era 40, che è appena appena sufficiente per fare ciò che voglio fare.

P.S. Ho aggiunto un po 'di più del mio codice per tenere traccia della "profondità" in cui il nodo appare sul diagramma di Hasse. Con ciò sono stato in grado di generare un diagramma più semplice che ha rimosso tutti i rivestimenti che superano una generazione.