Applicazione del problema della galleria d'arte al posizionamento ottimale del sensore

Question

Applicazione del problema della galleria d'arte al posizionamento ottimale del sensore

#1 da (3 voti)

3

Sto provando a progettare un algoritmo per posizionamento ottimale del sensore in una determinata area.

Dopo aver fatto qualche ricerca ho trovato il Problema della galleria d'arte . Tuttavia, questo problema presuppone che le guardie possano vedere fino al perimetro dalle loro posizioni, il che non è il caso dei sensori (i sensori hanno una portata). È possibile risolvere il problema di posizionamento ottimale del sensore mappandolo a un problema di galleria d'arte e provando qualche soluzione ricorsiva?

Sarei grato se qualcuno potesse far luce su questa domanda o guidarmi verso una risorsa appropriata.

recursion algorithms

posta shar 25.02.2014 - 14:28

fonte

1 risposta

Leggi altre domande sui tag recursion algorithms

Design orientato agli oggetti e corretta architettura Java per il mio programma classe di messaggistica e stato globale

score 3 · Accepted Answer

Come dici correttamente, il problema della galleria d'arte non è positivo perché non ha la nozione di distanza limitata. Sembra che quello che stai cercando di fare possa essere mappato al problema di copertura impostato . Puoi discretizzare la stanza in una serie di luoghi. Per ogni luogo in cui è possibile inserire un sensore, è possibile associarlo all'insieme di punti che il sensore può rilevare. La domanda è quindi: qual è il numero minimo di tali set necessari per coprire l'intera stanza?

Data questa mappatura, puoi usare uno dei molti algoritmi per la copertura del set, per esempio l'algoritmo greedy (scegli il set che copre il maggior numero di posti non ancora coperti, itera fino a quando tutto è coperto).