Atravesar un gráfico no ponderado no dirigido con un giro: visitas mínimas a cada nodo

Question

Estoy intentando escribir un código que atraviese un gráfico no ponderado no ponderado. Esencialmente, al método se le pasará un nodo (que conoce a todos sus vecinos). Luego, el método debe construir un modelo del gráfico de la manera más eficiente * yendo de un nodo a otro y recopilando información que los nodos se vinculan entre sí. Al final, el método tendrá una lista completa de todos los nodos y todos los vértices que los conectan.

* El meollo del problema radica en la palabra de manera eficiente y lo que quiero decir con eso. Permítanme dirigir su atención a este pequeño gráfico:

Digamos que me pongo en el nodo G. bien puedo visitar C, B, C, D, H, J o E. quiero minimizar el cantidad de veces que visito un nodo y para visitar un nodo, debo pasar por todos los nodos en el camino hacia ese nodo.

Ejemplo: digamos que decido visitar el nodo C. El próximo nodo a visitar podría ser A, B, F, D, H, J o E. Sin embargo, para visitar cualquier nodo, excepto A, tendría pasar de nuevo por G que se considera ineficiente. Y para visitar A, tendría que visitar G y C nuevamente y luego pasar por C y luego G para volver al resto del gráfico. Entonces decido visitar a A. Esto significa que tengo que pasar por C nuevamente para llegar a G. Por lo tanto, desde el punto de vista lógico, tiene sentido visitar la rama C al final.

Sin embargo, el programa, cuando comienza en el nodo G, no sabe que la rama C conduce a un callejón sin salida. Mientras escribo esto, creo que podría ser imposible, pero lo pregunto de todos modos: ¿hay alguna manera de recorrer este gráfico de la manera más eficiente posible (como lo he definido previamente) usando solo la información dada (es decir, que el programa solo conoce acerca de los nodos de su visitados y de los bordes que emana de esos nodos? ¿O debo ir con el algoritmo una variación de Dijkstra con el fin de asegurar que visita cada nodo?

todo esto será escrito en Java si lo que importa.

Answer 1

¿quieres simplemente para atravesar el gráfico completo (independientemente de la ruta tomada), y hacer alguna operación en cada nodo, o ¿desea calcular la ruta más corta de un nodo a otro? (Puede que no entienda su objetivo.)

En el primer caso, mantenga un algoritmo transversal como Breadth First Search. Para el otro, es posible que desee considerar Dijkstra mediante el uso de bordes con el mismo valor (es decir = 1).

Puede ver el BFS como un caso especial de Dijkstra cuando solo está interesado en un nodo inicial y todos los bordes tienen el mismo peso. Con diferentes costos, puede usar la Búsqueda uniforme de costos.

Answer 2

haría no sólo una recursión simple con un cobro revertido-argumento?

public void traverse(Node n, Set<Node> visisted) { 

    visited.add(n); 

    for (Node neighbour : n.getNeighbours()) { 

    if (!visited.contains(neighbour)) { 
     traverse(neighbour, visited); 
    } 

    } 

} 

Answer 3

Un problema interesante ... pero todavía no está claro cuál es el problema/objetivo original de las respuestas hasta la fecha.

¿Es esto una nueva declaración válida del problema?:

• El nodo de inicio se especifica
• El costo de visitar cada nodo es "1"
• Objetivo: visitar cada nodo
• Objetivo: planificar una ruta que minimice el costo
• Restricción: la nodo final no especificado (puede ser cualquier nodo)
• El algoritmo tiene pleno conocimiento del gráfico antes de que se incurra en ningún costo (la búsqueda de todas las rutas posibles no tiene ningún costo)

Si ese es el correcto "leer" de su problema, y ​​luego considerar estas observaciones:

• Si el costo de "visitar un nodo" es "1", es decir lo mismo que "el costo para atravesar cualquier borde "es" 1 "... ya que hay una correspondencia uno a uno entre" visitar un nodo "y" atravesar un borde ". (No puede ingresar un nodo, excepto al atravesar su borde.)
• Si dos nodos no están conectados directamente, todavía están "transitivamente conectados", ya que puede simplemente atravesar los nodos intermedios. (Como alternativa: que aparentemente no ofrecen la restricción "es posible que no re-visitar un nodo".)

Por lo tanto: todos los nodos están "conectados" a través de algún "distancia", y que desea visitar todos nodos, mientras se minimiza la "distancia" recorrida.

¿Es correcto?

Si es así, afirmo que su problema es casi exactamente el clásico "Problema del vendedor ambulante". La única diferencia que veo es que a veces la declaración del TSP requiere que "start-node y end-node sean lo mismo". Pero, creo, permites que el nodo de inicio y el nodo de extremo sean diferentes.

Si eso suena bien, y en realidad solo intentas "resolver" el TSP de manera eficiente, ¡entonces únete a las multitudes que han intentado hacer lo mismo antes que a ti! Puede que no haya una mejor solución que simplemente "probar todas las combinaciones, calificar cada una y tomar el mínimo".

Answer 4

se trata de recorrer todos los nodos del gráfico y calcula el costo mínimo de desplazamiento espero les ayude T

package capgemni; 
/** 
* 
* @author amit 
*/ 
public class Graphtraversing { 
public static void main(String[] args) { 
    int res = 0; 
    String[] input1= {"A", "B", "C", "D"}; 
    int[] input2 = {4, 8, 6, 3, 3, 5}; 

    res = minimum_cost(input1, input2); 
    System.out.println(res); 

} 
static int minimum_cost(String[] input1,int[] input2) 
{ 
    int d = input1.length; 
    int costmatrix[][]=new int[input1.length][input1.length]; 
    int i=0,j=0,k=0; 


    for(i=0;i<input1.length;i++){ 
    for(j=i;j<input1.length;j++){ 
     costmatrix[i][j]=0; 
    } 
    } 

    for(i=0;i<input1.length;i++){ 
    for(j=i;j<input1.length;j++){ 
     if(i==j){ 
     costmatrix[i][j] = 0; 
     } 
else{ 
     costmatrix[i][j] = input2[k]; 
     k++; 
} 

    } 
    } 

for(i=0;i<input1.length;i++){ 
for(j=0;j<input1.length;j++){ 
    costmatrix[j][i] = costmatrix[i][j]; 
} 
} 

int cost = 0; 
int mcost = 0; 
int first = 1; 
for(i=0; i<input1.length; i++){ 

for(j=0; j<input1.length; j++){ 

    cost = cost + costmatrix[i][j]; 

} 
if(first == 1){ 
mcost = cost; 
first = 0; 
} 
else if(cost < mcost){ 
mcost = cost; 
} 
cost = 0; 
} 


    return mcost; 
} 
}