Traversata in ampiezza con alcuni bordi preferiti

Una coda di priorità qui probabilmente ti servirebbe al meglio. Una coda di priorità non è altro che una coda che ordina in base a un criterio.

Algoritmo

Si inizia aggiungendo il nodo iniziale all'elenco associato al livello 0.

L'algoritmo è il seguente:

Pop a node.  
For each edge in node
    Add to priority queue with level of node + 1

Profondità prima

La chiave qui sta specificando i criteri per il tuo ordine. Profondità prima semplicemente ordini per livello (decrescente), in modo da far apparire prima il nodo "più profondo".

Prima larghezza semplice

Per semplicità, prima è il contrario. Ordina per livello crescente, quindi i nodi "più superficiali" vengono selezionati per primi.

Prima leggermente meno semplice

Quindi, come faresti allora a scegliere i nodi preferenziali con lo stesso livello prima? Semplicemente cambia i criteri in modo che il livello superi qualsiasi altro ordine che potresti avere. Questo garantisce che tu possa ottenere prima la ricerca. Il secondo ordine avrà un impatto, ma solo se il livello non ha voce in capitolo.

Supponendo che tu stia determinando il "punteggio" di un nodo, potrebbe essere qualcosa del tipo:

10000*level + getSecondaryPriority()

Ciò presuppone naturalmente che la tua seconda priorità non superi mai il 10000, ma in termini più formali, per qualsiasi due nodi, quello che viene prima deve essere considerato prima confrontando il suo livello. Se i livelli sono uguali, solo allora li confronti per la priorità secondaria. In Java potrebbe sembrare qualcosa di simile:

public int compare(Node node1, Node node2) {
    int levelDiff = node1.level - node2.level;
    return levelDiff != 0 ? levelDiff : node1.getSecondaryPriority() - node2.getSecondaryPriority();
}

Conclusione

Questa soluzione è anche un po 'più pulita anche per il fatto che l'algoritmo non differisce, solo l'ordine della coda di priorità. Le code prioritarie sono usate per aiutare gli scacchi IA a determinare quali considerazioni devono essere prima pesate (cioè se la regina è in pericolo, l'albero decisionale considera più pesantemente una decisione che coinvolge il movimento della regina e conseguentemente potenziali contromosse del giocatore rispetto ad altre azioni è senza dubbio un albero decisivo senza fine).

Spero che ti aiuti!

Un attraversamento in profondità e un attraversamento in ampiezza possono essere entrambi realizzati utilizzando una coda per l'archiviazione e il ciclo semplice. Accodare inizialmente il vertice iniziale. Quindi, rimuovendo i nodi dalla testa fino a quando l'elenco non è vuoto, per ogni nodo rimosso aggiungi tutti i suoi figli alla lista.

Per attraversamento in ampiezza, aggiungi i nodi secondari alla fine della coda.

Per l'attraversamento in profondità, aggiungi i nodi figlio all'inizio della coda (magari in ordine inverso).

Quindi, forse quello che potresti considerare è aggiungere nodi in modo condizionale all'inizio se il margine di raggiungimento è preferito rispetto alla fine se il margine di raggiungimento non è preferito.

Questo mescolerà depth-first e breadth-first, in base alla peferred'ness dei bordi.

(vedi qui per un confronto tra BFS e DFS)

Altre alternative potrebbero comportare l'utilizzo di una coda di priorità se è possibile assegnare, ad esempio, una preferenza numerica al nodo che entra nella coda, probabilmente in base alla profondità e ad altri fattori. Quindi puoi inserire i nodi da visitare in una posizione adeguata nella coda di priorità.