Trova il numero minimo di passaggi per un obiettivo senza stimatore per quanto sono vicini all'obiettivo i passaggi intermedi

Question

Trova il numero minimo di passaggi per un obiettivo senza stimatore per quanto sono vicini all'obiettivo i passaggi intermedi

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

4

Ho cercato di trovare un buon modo per risolvere il seguente problema, ma non sono sicuro di come inquadrarlo. Penso che potrebbero esserci soluzioni relativamente conosciute con cui non ho familiarità, dal momento che non ho molta conoscenza degli algoritmi. Come potrei avvicinarmi a questo?

Esempio di problema:

C'è uno stato iniziale A conosciuto e uno stato terminale B conosciuto. Esiste una sequenza nota di (una grande quantità di) punti che portano da A a B . Mi piacerebbe trovare un numero minimo / piccolo di punti che descrivono il percorso da A a B . Posso testare qualsiasi sequenza di punti sia che raggiunga B usando quello, ma se non lo fa non ho una stima di quanto sia vicino a raggiungere B . Fondamentalmente sto cercando di trovare i punti che sono essenziali per arrivare a B , ma non saprò se sono sufficienti finché il percorso non è completo.

Quello che ho trovato finora:

Il problema appare un po 'simile alla semplificazione della polilinea, e una opzione sarebbe l'algoritmo Ramer Douglas Peucker . Non penso che funzionerà bene per il mio problema, perché non voglio necessariamente seguire i punti non essenziali sul percorso (che possono essere valori anomali o inutili).

La soluzione che mi è venuta in mente mi sembra un po 'avida e amp; ricerca binaria:

Seleziona il punto centrale C tra A e B e scarta tutti i punti tra A e C .
Verifica se questo percorso raggiunge B .
Se B non può essere raggiunto, c'è un punto essenziale tra A e C che abbiamo perso, quindi scegli il punto centrale D tra A e C e percorso di test con punti tra A e D scartati.
Se B può essere raggiunto, potremmo essere in grado di scartare il punto C e alcuni punti successivi, quindi scegli D tra C e B e scartare i punti fino a D .
Fai questo finché non identificato un punto D più lontano da A che porta ancora a B se tutti i punti tra A e D sono scartati.
Inizia questa ricerca, ora a partire da D invece di A finché non sono stati identificati tutti i punti essenziali

Altri pensieri:

Potrei essere in grado di fornire una stima di "similarità" per lo stato terminale B1 che è raggiunto da qualche punto C rispetto allo stato finale target B . Fornirebbe una più ampia varietà di algoritmi applicabili?

algorithms search

posta Z.F. 04.02.2016 - 16:28

fonte

2 risposte

Leggi altre domande sui tag algorithms search

Richiesta di filtro e risposte nello stack MEZZO RESTful Come si può dimostrare il contenuto del sito Web del sito client dopo che i siti sono stati aggiornati?

score 1 · Answer 1

Il tuo problema suona come può essere descritto in termini di trovare il percorso più breve tra due punti su un grafico; se sei in grado di riformularlo in questi termini, l'algoritmo di Dijkstra è probabilmente quello che stai cercando.

Dici che non hai modo di stimare la lunghezza del percorso, ma se riesci a fornire un limite inferiore su di esso che varia in qualche misura potresti essere in grado di ridurre la quantità di sforzo richiesta per eseguire la ricerca usando Ricerca A* .

score 0 · Answer 2

Inizialmente hai passaggi n che vanno da A a B . Ora costruisci un vettore p contenente n 0s o 1s in cui l'i-th 0 indica che il passo i-esimo è escluso e un 1 indica che il passo è stato eseguito.

Vuoi trovare un p con una norma minima (somma di elementi) a condizione che la funzione f ( p ) = 1.

f ( p ) è definito come 1 se il percorso che contiene i passi in cui p è 1 ti sta dando da A a B . La funzione f è data da te. O è solo 1 e 0 (il percorso non raggiunge B) o potresti avere anche una stima di similarità (quanto vicino il percorso raggiunge B) che corrisponde a f prendendo ad esempio tutti i valori possibili tra 0 e 1 dove vicino a 1 significa "quasi raggiunto B".

Ora non hai specificato ulteriori informazioni su f . Ha molti optima locali o è continuo (se è la misura di somiglianza)?

Se non si sa nulla di f , suppongo che l'unica scelta stia iniziando con p di norma minima e procedendo verso l'alto (quindi solo un passo, quindi tutte le combinazioni di solo due passaggi, ...) fino a quando non si preme la prima volta una soluzione e si interrompe. Questo potrebbe finire in tempo di esecuzione NP.

Se f è continuo, questo tipo di promemoria mi ricorda moltiplicatori di Langrange che potrebbero essere utilizzati per ridurre al minimo la norma di p mantenendo il percorso descritto da p una soluzione.