Il problema con il campione di braccio robotico in "Algorithm Design Manual" di Skiena sembra non essere valido per me [chiuso]

Question

Il problema con il campione di braccio robotico in "Algorithm Design Manual" di Skiena sembra non essere valido per me [chiuso]

#1 da (2 voti)
#2 da (1 voti)
#3 da (0 voti)

3

Sto leggendo il Algorithm Design Manual di Skiena e c'è un problema a pagina 5, "Robot Tour Optimization", dove dice questo sul problema di esempio: "Supponiamo di ricevere un braccio robotizzato dotato di uno strumento, ad esempio un saldatore.Nelle schede di circuito di produzione, tutti i chip e gli altri componenti devono essere fissati sul substrato.Più specificamente, ogni chip ha una serie di punti di contatto che devono essere saldato alla lavagna Per programmare il braccio del robot per questo lavoro, dobbiamo prima costruire un ordinamento dei punti di contatto in modo che il robot visiti il primo punto di contatto, il secondo ecc ... "

"Dobbiamo prima costruire un ordinamento" - mi sembra strano.

Perché, beh, ogni chip ha un certo numero di pin e sono numerati e la loro posizione è documentata, guarda qui:

Voglio dire che il chip non ha un set di pin, ha una lista ordinata di pin, ok, ma non ha dimensioni molto specifiche e ordine specifico di pin su ciascun lato così la loro posizione precisa (e ordine) può essere facilmente calcolato.

Forse non correlato, ma probabilmente IRL la tavola si muove su una sorta di morsetto in X, dimensione Y e il ferro di saldatura va solo su e giù.

Il problema più semplice che posso dare come esempio di Robot Optimization tour è un corriere della pizza che guida un'auto e ha bisogno di visitare tutti i suoi clienti (supponiamo che il traffico sia vicino allo zero) e ritorna al ristorante con la poca benzina spesa il più possibile Quindi ha bisogno di uno strumento (navigatore di auto), che risolverà questo problema per lui. E quell'applicazione di navigazione deve trovare il percorso ottimale, quindi illustra il problema.

Ho ragione che l'illustrazione del problema originale con braccio del robot è sbagliata?

algorithms

posta Stuart Marks 22.08.2012 - 23:33

fonte

3 risposte

Leggi altre domande sui tag algorithms

Problemi di memoria durante la pianificazione della fuga dall'inferno DLL in Delphi [chiuso] Generazione di CMakeLists.txt [chiusa]

score 2 · Answer 1

Ci sono in genere più chip di varie dimensioni sulla scacchiera. In che ordine ti muovi tra i gettoni? Stai dando per scontato che il braccio finisca di saldare un chip prima di passare al successivo? Potrebbe richiedere meno movimento del braccio del robot per saldare i pin sui bordi adiacenti dei chip vicini prima di terminare i pin sul lato più lontano.

score 1 · Answer 2

È vero che i pin su un chip sono numerati. Ma quando si individua l'ordine migliore per saldare i pin, la numerazione esistente non è necessariamente ottimale. Quando i perni sono disposti su una linea attorno al bordo, la numerazione data è probabilmente ottimale. Ma quando hai un layout strano, come il layout in un processore x86, potrebbe non esserlo.

Ineffetti,ipinsutaleprocessorenonsononumerati,maacuisifariferimentoperrigaecolonna:

score 0 · Answer 3

Prima che il robot possa saldare i pin, deve prima sapere dove si trovano i pin, ed è probabilmente più efficiente visitare i pin in una sequenza specifica, piuttosto che visitarli casualmente. Quindi, l'ordine.

Ricorda che le macchine non sanno nulla tranne quello che dici loro, quindi se vuoi che visitino i punti in una sequenza specifica, devi dire loro qual è quella sequenza, in modo che possa eseguire i calcoli per muovere il braccio da un punto all'altro.

Si noti che il chip nella figura è un dispositivo a montaggio superficiale; è altamente probabile che sia saldato usando una fase di vapore o un sistema di convezione, che salda tutti i perni contemporaneamente senza richiedere un braccio robotico. Pertanto, probabilmente non è un ottimo esempio.