Algoritmo del percorso di massimizzazione del peso (vertici pesati)

Question

Algoritmo del percorso di massimizzazione del peso (vertici pesati)

#1 da (2 voti)

1

Sto cercando una descrizione (nome dell'algoritmo, codice, pseudocodice, ecc.) che possa aiutarmi a inquadrare questo problema e trovare la ricorsione appropriata e la soluzione più efficiente.

problema :
Dato un grafico con nodi ponderati e un nodo di partenza, voglio generare un elenco di nodi ordinati per peso che giacciono su un percorso che inizia dal nodo di partenza e procede saltando al nodo adiacente di valore più elevato successivo, quindi al prossimo ecc. fino a quando non può più continuare (es. nessun nodo adiacente, nessun nodo adiacente non visitato, o tutti i nodi sono stati già visitati una volta).

Sto assumendo correttamente che si tratti di una variazione del problema del commesso viaggiatore? Qualsiasi suggerimento o suggerimento sarebbe molto apprezzato. Gli algoritmi non sono la mia area di competenza ...

Aggiornamento dai commenti : questa non è una domanda per i compiti a casa. ... Ci sono in realtà anni di ricerca empirica alla base del semplice essere in grado di inquadrare comportamenti apparentemente casuali di mammiferi come un problema algoritmico. ... Senza affrontare queste dinamiche di gruppo in modo algoritmico non sarò in grado di espandere i test oltre il mio campione iniziale e sfortunatamente, l'analisi di regressione non farà proprio il trucco.

algorithms graph

posta phaedrus 18.01.2014 - 15:44

fonte

1 risposta

Leggi altre domande sui tag algorithms graph

Concessione in licenza di un progetto di ricerca collaborativa Quando scrivere la documentazione del progetto software sul codice [duplicato]

score 2 · Answer 1

Se ho capito bene allora no, questa non è una variazione sul TSP. È un algoritmo avido piuttosto semplice.

Ecco alcuni psuedocode:

List visited = {}

Main(Node startNode)
  FindPath(startNode)
  sort(visited)

FindPath(Node node)
  visited.addNode(node)
  neighbours = node.getAdjactentNodes()
  neighbours.subtract(visited)
  if(neighbours.isEmpty())
    // all adjacted nodes are visited
    return
  else
    sort(neighbours)
    FindPath(neighbours.First())
  end if

Quindi - cosa sta succedendo qui?

Stiamo creando un elenco per contenere tutti i nodi che abbiamo visitato nel nostro viaggio.

In FindPath: Visitiamo quindi il nodo, lo aggiungiamo all'elenco dei nodi visitati e chiediamo una lista di vicini. Se non ci sono nodi adiacenti, allora siamo finiti (non ci sono più nodi da visitare). Se ci sono nodi associati, li ordiniamo in base al peso e passiamo il più grande a FindPath.

Quando la funzione FindPath finisce (alla fine ci ritroviamo su un nodo da cui non possiamo saltare da nessuna parte) ci ritroviamo con tutti i nodi che abbiamo visitato nell'elenco visitato e quindi abbiamo solo bisogno di ordinarlo a peso.

Spero che ti aiuti.