Traverser un graphe non-orienté non-pondéré avec une torsion: visites minimales sur chaque noeud

Question

J'essaye d'écrire du code qui traversera un graphe non-orienté non-pondéré. Essentiellement, la méthode passera un nœud (qui connaît tous ses voisins). La méthode doit alors construire un modèle du graphe aussi efficacement * en allant de nœud en nœud et en collectant des informations que les nœuds lient les uns aux autres. À la fin, la méthode aura une liste complète de tous les nœuds et de tous les sommets qui les relient.

* Le nœud du problème réside dans le mot efficacement et ce que je veux dire par là. Permettez-moi de diriger votre attention sur ce petit graphique:

Disons que je commence au niveau du noeud G. Je peux soit visiter C, B, F, D, H, J ou E. Je veux minimiser la Nombre de fois que je visite un nœud et que je dois visiter un nœud, je dois traverser tous les nœuds sur le chemin de ce nœud. Exemple: disons que je décide de visiter le nœud C. Le prochain nœud à visiter pourrait être A, B, F, D, H, J ou E. Cependant, pour visiter n'importe quel nœud sauf A, j'aurais passer à nouveau par G qui est considéré comme inefficace. Et pour visiter A, je devrais à nouveau visiter G et C, puis passer par C puis G pour revenir au reste du graphique. Donc je décide de visiter A. Cela signifie que je dois à nouveau passer par C pour atteindre G. Donc, d'un point de vue logique, il est logique de visiter la branche C en dernier. Cependant, le programme, lorsqu'il démarre au nœud G, ne sait pas que la branche C conduit à une impasse. Au moment où j'écris ceci, je pense que c'est impossible, mais je le demande quand même: est-il possible de parcourir ce graphique le plus efficacement possible (comme je l'ai précédemment défini) en utilisant uniquement les informations fournies? les nœuds ses visités et les bords émanant de ces nœuds? Ou devrais-je aller juste avec l'algorithme de variation Dijkstra afin d'assurer que je visite chaque nœud?

tout cela sera écrit en Java si cette matière.

Answer 1

Voulez-vous simplement parcourir le graphe entier (quel que soit le chemin emprunté), et effectuer une opération sur chaque nœud, ou voulez-vous calculer le chemin le plus court d'un nœud à un autre nœud? (Je ne comprends peut-être pas votre objectif.)

Dans le premier cas, respectez un algorithme de traversée tel que Breadth First Search. Pour l'autre, vous pouvez envisager Dijkstra en utilisant des arêtes de même pondération (c'est-à-dire = 1).

Vous pouvez voir le BFS comme un cas particulier de Dijkstra lorsque vous êtes intéressé par un seul nœud de départ et que tous les bords ont le même poids. Avec des coûts différents, vous pouvez utiliser la recherche de coût uniforme.

Answer 2

Ne serait-ce pas une simple récursion avec un argument de collecte?

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 problème intéressant ... mais toujours pas clair quel est le problème/objectif original à partir des réponses à ce jour.

Est-ce une réaffirmation valide du problème?:

• Le noeud de départ est spécifié
• Le coût pour visiter chaque nœud est « 1 »
• Objectif: visiter chaque nœud
• Objectif: planifier un itinéraire qui minimise les coûts
• Contrainte: la le noeud final n'est pas spécifié (il peut s'agir de n'importe quel noeud)
• L'algorithme a une connaissance complète du graphique avant que des coûts ne soient encourus (la recherche de tous les chemins possibles n'engendre aucun coût)

Si c'est une bonne « lecture » de votre problème, tenir compte de ces observations:

• Si le coût de « visiter un noeud » est « 1 », qui est la même chose que « le coût pour traverser tout bord "est" 1 "... puisqu'il y a une correspondance biunivoque entre" visiter un noeud "et" traverser un bord ". (Vous ne pouvez pas entrer un nœud sauf en traversant son in-edge.)
• Si deux nœuds ne sont pas directement connectés, ils sont toujours "connectés de manière transitoire ", car vous pouvez simplement traverser les nœuds intermédiaires. (Alternative: vous semblez ne pas avoir la contrainte « vous ne pouvez pas Revisitez un noeud ».)

Ainsi: tous les noeuds sont « connectés » via une « distance », et que vous voulez visiter tous nœuds, tout en minimisant la «distance» parcourue.

Est-ce correct?

Si tel est le cas, je soutiens que votre problème est presque exactement le classique "Problème de vendeur itinérant". La seule différence que je vois est que parfois l'instruction du TSP exige que "start-node et end-node soient les mêmes". Mais je pense que vous autorisez le nœud de départ et le nœud de fin à être différents. Si cela vous semble juste - et vous essayez simplement de "résoudre" le TSP d'une manière efficace - alors rejoignez les multitudes devant vous qui ont essayé de faire la même chose! Il n'y a peut-être pas de meilleure solution que de simplement «essayer toutes les combinaisons, marquer chacune et prendre le minimum».

Answer 4

est de parcourir tous les nœuds du graphe et calcule le coût minimum de déplacement espère que cela vous aidera U

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; 
} 
}