Ho cercato di trovare un algoritmo ottimale per un problema ispirato alla "città tripla" del gioco. Il gioco va così:Algoritmo ottimale di tripla città
Si posizionano gli oggetti in una griglia e, ogni volta che si crea un set di tre, si condensano in un oggetto di livello superiore nella posizione dell'ultimo oggetto posizionato.
Inoltre, se si inserisce tre di questi oggetti b insieme di nuovo comprimono per formare un oggetto livello ancora più alto.
Nota: in questi diagrammi livello di un oggetto è espressa come i, b i, ec i e il pedice indica gli oggetti intorpiditi er nel set di tre.
Per semplificare le cose, sto solo considerando quando ogni oggetto che devi posizionare è del livello più basso.
Ora le mie domande sono:
1: Esiste un algoritmo per determinare la quantità minima di zona della griglia necessaria per rendere un oggetto di livello x, x data?
Ad esempio, per il livello a è necessario 1 x 1, per il livello b è necessario 1 x 3, per il livello c è necessario 1 x 5.
2: Date le dimensioni di una griglia, possiamo trovare il livello più alto e il numero di oggetti realizzabili?
Ad esempio, per un 2x2 è possibile ottenere 2 'Livello A e di livello 2' di b
3: Esiste un algoritmo per trovare l'ordine ottimale e la posizione degli oggetti per ottenere il più alto livello possibile, data una griglia fissa?
Ad esempio, per un 2x2 è possibile ottenere (1,1), (1,2), (2,2)
4: Data una posizione di un oggetto di livello x previsto, quale set di mosse ridurre al minimo la quantità di spazio necessario per realizzare questo oggetto?
5: Quali sono le complessità ottimali di questi algoritmi?
Aggiornamento:
Una cosa che penso è di primo piano nella ricerca di soluzioni è che il ottenere un articolo di livello x non può essere fatto in qualsiasi luogo arbitrario.
Ad esempio: [ _ _ _ _ c] è impossibile da ottenere in una griglia fissa 1 per 5 perché è necessario l'ultimo b in quinta posizione e quindi l'ultimo a in quinta posizione. Quindi per posizionare il primo b: [a _ _ _ _]->[a a _ _ _]->[_ _ b _ _] o [_ a _ _ _]->[_ a a _ _]->[_ _ _ b _]. In entrambi i casi non c'è abbastanza spazio per posizionare 3 'a per fare l'ultima b del c.
Un'altra cosa, non possiamo presumere che qualsiasi cosa possa essere srotolata su una griglia 1 dimensionale. Questo diventa chiaro con il mio prossimo punto.
qualcosa di interessante che ho trovato:
C'è una vicinanza minima per il confine che un oggetto di livello C può essere in una griglia tridimensionale 1. [_ _ a a a]->[_ _ _ b]->[_ a a a b]->[_ _ _ b b]->[a a a b b]->[_ _ c _ _]. Quindi un oggetto di livello c in una griglia (ottimale) da 1 a 5 può essere fatto solo nella 3a posizione.
Ne consegue che questo è il livello più alto che può essere eseguito in 1 da qualsiasi griglia numerica. Prendete un 1 per griglia infinito:
..._ a a a _ ... -> ... _ a a a b _ ... -> ... _ a a a b b _ ... -> ... _ c _ ...
ora cerchiamo di ottenere un altro c direttamente accanto ad essa:
..._ c a a a _ ... = ... _ c b _ ... or ... _ c _ b _ ... or ... _ c _ _ b _ ...
L'unica opzione è ..._ c b _ ... perché gli altri rendono impossibile per formare un altro b tra c eb. La nostra unica opzione impedisce il nostro unico modo di creare c direttamente accanto al nostro primo c perché blocca l'ultimo c di andare lì. Pertanto, in una dimensione, c è il livello più alto che possiamo fare. In altre parole, il problema deve essere considerato in 2 dimensioni.
Questa è una domanda e mezza. :) – biziclop
Hai risultati intermedi? –
Solo quelli che riuscivo a capire nella mia testa per i valori di bassa griglia. Sto ancora pensando al modo migliore per affrontarlo. – Raufio