Domanda

Sto leggendo la prova NP-Hardness di Super Mario Bros. nel documento "Classic Nintendo Games sono (computazionalmente) duri" di Greg Aloupis, Erik D. DeMaine, Alan Guo e Giovanni Viglietta.

Posso ottenere l'idea di base del framework di prova presentata nella Sezione 2.1. Penso di capire anche il gadget start, il gadget di finitura, il gadget variabile, il gadget clausole e il gadget crossover utilizzati individualmente in questa prova. Vedi la figura seguente.

Tuttavia, non sono riuscito a farlo Collega questi gadget al framework di prova per costruire un'istanza/scenario completo di Super Mario Bros. In particolare,

  1. Nel gadget variabile, Mario sceglie il percorso di cadere. Quindi Mario va a qualche clausola gadget dove colpisce il blocco degli articoli da sotto per rilasciare una stella. Non capisco come i gadget variabili siano collegati ai gadget della clausola in modo che gli orientamenti (cadere vs. "dal basso") si adattano insieme?
  2. Nel gadget della clausola, la barra del fuoco è sul lato destro. Tuttavia, nel framework di prove, il percorso di controllo va da destra a sinistra. Come può Mario scegliere la stella come desiderato in questo caso?
  3. Dove dovrebbero essere collegati i gadget crossover nel framework di prova? I cerchi sono tra i percorsi dalle variabili al crossover delle clausole?

mario-hardness

Nessuna soluzione corretta

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top