La complexité de la recherche de tous les chemins simples en utilisant la profondeur de la première recherche?

Merci à tous de répondre avec des idées et des solutions de rechange. Des moyens plus efficaces de résolution de problèmes sont toujours les bienvenus, ainsi que les rappels à remettre en question mes hypothèses. Cela dit, j'aimerais que vous ignorer un instant à ce problème, je vais essayer de résoudre avec l'algorithme, et viens m'aider à analyser le big-Oh complexité de mon algorithme, comme je l'ai écrit -- tous les chemins dans un graphe en utilisant la profondeur limitée de recherche comme décrit ici, et mis en œuvre ici. Merci!

Edit: C'est les devoirs, mais j'ai déjà présenté cette mission et je voudrais juste savoir si ma réponse correcte. Je suis un peu confuse sur Big-O complexité lors de la récursivité est impliqué.

Question d'origine ci-dessous:

J'essaie de trouver de la complexité de tous les chemins de la recherche, telle que donnée par cette algorithme.
Étant donnés deux sommets, je suis la recherche de tous les chemins simples entre eux à l'aide d'une profondeur d'abord de recherche.

Je sais que le temps de la complexité de DFS est en O(V+E) et son espace complexité est O(V), et mon intuition est que la complexité de tous les chemins de la recherche sera plus que cela, mais je suis incapable de déterminer ce qu'il sera.

SI des questions ici et ici.

Mise à jour (en réponse à un commentaire ci-dessous):

Je suis en train de résoudre le les six degrés de Kevin Bacon problème. En général, il faut trouver le plus bas degré de séparation entre une paire d'acteurs, mais je dois trouver TOUS les degrés de séparation (pour l'instant, à moins de 6, mais cela peut changer).

Mon application est en fait similaire à ce qui est décrit [ici][1], si cela peut vous aider dans l'analyse (qui est en fait un DFS, même si elle prétend être une BFS!). [1]: stackoverflow.com/questions/58306/...
Il y a peut-être de façon exponentielle beaucoup de chemins (considérer par exemple un graphe complet), donc juste à la sortie de prendre le temps exponentiel. Pourquoi voulez-vous trouver tous les chemins?
Partie d'un de plus grands devoirs. J'ai besoin de trouver tous les chemins, et j'ai utilisé cet algorithme. Maintenant, je vais avoir de la difficulté à exprimer sa complexité (en termes de Big-Oh). Aussi, si il ya un moyen plus efficace pour résoudre cela, alors je voudrais savoir.
Si vous souhaitez simplement trouver "TOUS les degrés de séparation", seuls les n sorties possibles, et c'est un problème bien plus simple que de trouver tous les chemins. Êtes-vous sûr que vous voulez trouver tous les chemins?
que diriez-je reformuler à "recherche de toutes les façons possibles, les deux acteurs sont liés au sein de # degrés" (où # dans le pire des cas = nombre d'acteurs). N'est-ce pas un tous-chemins, alors?

OriginalL'auteur hexium | 2009-12-02

  1. 5

    Le pire des cas est (je pense) le graphe complet sur n sommets. Ce graphique a n! chemins simples, et pour chacun d'eux votre algorithme ne au moins n^2 étapes de calcul, pour chaque sommet adjacent à la dernière dans le chemin d'accès, une analyse linéaire sur le site précédemment visité les nœuds. (C'est sans compter tous les stades intermédiaires de la recherche.) Si la complexité est au moins O(n^2 * n!), même pire.

    Ce qui est le plus grand problème que vous essayez de résoudre?

    Si je sais que le graphe est peu dense, il va alors devenir O b! * n^2)?
    (où b est le facteur de branchement)
    Je suis en train d'essayer de résoudre les six degrés de Kevin Bacon problème (en.wikipedia.org/wiki/Six_Degrees_of_Kevin_Bacon). En général, il faut trouver le plus bas degré de séparation entre une paire d'acteurs, mais je dois trouver TOUS les degrés de séparation (enfin, de moins de 6 (mais cela peut changer.))
    la factorielle aspect ne doit pas faire oublier le multiplicateur dans le n^2 facteur de
    disons que vous trouvez le chemin le plus court de tous les chemins en utilisant la profondeur de la première recherche. Quelle serait la complexité de l'être? En gros, j'ai utilisé de la profondeur d'abord chercher à calculer tous les chemins, puis est passé par tous ces chemins de trouver le plus court.

    OriginalL'auteur David

  2. 1

    Les 6 degrés, c'est agréable car il vous donne une limitation. Je me rends compte de la 6 peut changer, mais je pense que l'approche adoptée ici s'applique toujours. N'importe où je dis "6", en remplaçant simplement en "le nombre de degrés".

    Si vous le vouliez, vous pourriez utiliser la Largeur de Recherche (BFS). Si je comprends bien, vous êtes donné un point de départ (un acteur/actrice) et vous avez besoin de trouver tous les chemins d'accès à un point de terminaison (Kevin Bacon) qui sont inférieures ou égales à 6 bords de route. Vous pouvez casser cela en sous-problèmes en disant tout d'abord trouver toutes les connexions 1 bord à l'écart, puis tous les 2 bords des chemins, loin, ... , et enfin de trouver tous les chemins six bords de route. C'est exactement la façon dont un BFS fonctionnerait...d'abord examiner tous les nœuds d'un bord à l'écart, puis deux, etc.

    Alternativement, vous pouvez également utiliser une version modifiée de la Profondeur de Recherche d'Abord (DFS) en faisant un normal DFS et de suivre chaque chemin aussi loin que vous pouvez, mais garder un compteur et de l'empêcher d'aller plus que 6 bords profond de tout chemin d'accès particulier.

    Je pense que votre solution sera probablement beaucoup mieux que la normale O(V + E) tout simplement parce que vous êtes susceptible de ne pas visiter tous les Sommets de voyage ou le long de tous les Bords (en supposant que notre graphe est la relation entre un grand nombre d'acteurs), mais plutôt que vous êtes limité à un sous-graphe de l'ensemble du graphique. Vous commencez votre algorithme de recherche d'agir comme vous vous allez visiter tous les sommets/arêtes, mais peu importe si vous utilisez BFS ou DFS, vous serez en s'arrêtant à 6 arêtes de votre départ vertex plutôt que de regarder à travers l'ensemble du graphique.

    Considérer que quelque chose comme DFS peut être représenté comme O(V+E), mais il peut également être représenté comme O(b^d) où b est le facteur de branchement et d est la représentation graphique de la profondeur (voir Wikipedia_DFS pour plus d'info ). Donc, étant donné la façon dont de nombreux acteurs il y a, ce sera b? Compte tenu des contraintes que vous savez sur le problème (6 degrés et ce n'est pas), ce sera d?

    Je pense que j'ai probablement dit assez. J'espère que ça permet de lancer pour vous. Je devrais ajouter l'avertissement que je ne connais pas la réponse, c'est juste la façon dont le problème qui me frappe 😉

    Merci pour votre réponse, Brent Nash. En fait, j'ai déjà résolu le problème et mis en œuvre la solution, c'est juste l'analyse de la complexité, je ne peut pas envelopper la tête autour de. Je suis en effet à l'aide d'une profondeur limitée de la recherche (mais pour tous chemins < 6). Depuis le " 6 " peut changer, pour l'analyse de la complexité (que je comprends) j'ai besoin de prendre le pire des cas ici, et il dégénérera en plein DFS. J'ai essayé d'abstraire les détails dans la question puisque c'est seulement la complexité de l'analyse j'ai besoin d'aide.
    Je suis venu avec O((MAXDEPTH*b)^MAXDEPTH) de la complexité du temps et O(MAXDEPTH*b^MAXDEPTH) de la complexité du temps (basé sur le pseudocode -- analyse de la boucle de récursivité, etc.) mais je ne suis pas sûr que c'est correct
    Désolé de ne pas vous donner plus...j'ai juste hésitez pas à trop donner de l'aide supplémentaire sur les devoirs des problèmes. Bonne chance!

    OriginalL'auteur Brent Writes Code

  3. 1

    Pour répondre à ma propre question avec mon analyse, s'il vous plaît commentaire/corriger!

    The algorithm is simplified and analyzed as follows: 
(Note: here MAXDEPTH is the maximum degrees of separation to search for, default 6)
1. For the current vertex, get neighbors (amortized O(1))
2. For every neighbor, do the following [O(b), where b is the branching factor, or the avg. number of neighbors of a vertex]
2.1.    Check if already visited [O(MAXDEPTH), since it’s a linked list of max size MAXDEPTH)
2.2.    Append path to paths list [amortized O(1)]
3. End for 
4. Do the following MAXDEPTH times [O(MAXDEPTH)]
4.1.    For every neighbor do the following [O(b)]
4.1.1.      Check if already visited [O(MAXDEPTH)]
4.1.2.      Add to visited list [O(1)]
4.1.3.      Recursively call search again [becomes O(MAXDEPTH*b)]
4.1.4.      Delete from visited list [O(1)]
4.2 End for /* Neighbor */
5. End loop /* MAXDEPTH */

Thus, the complexity becomes O((MAXDEPTH*b)^MAXDEPTH).

    OriginalL'auteur hexium

  4. 0

    Je pensais à l'aide de O (n^2)*profondeur) algorhitm

    1. Pour chaque acteur de trouver l'ensemble des acteurs qu'il travaillait avec. (O(n^2) l'espace et le temps comlexity mais les deux en fonction du nombre réel de connexions et pour la plupart des acteurs ne pas dépasser les 500 ou 5x nombre de vos amis sur facebook) Cela apporte 500*n de temps&espace complexité.

    2. Assembler ensemble des trois va sur tout le monde à la même profondeur et l'ajout de toutes ces connexions. O(n^2*profondeur)

    Si vous utilisez doublement chaînée de l'arbre pour le stockage des connexions vous pouvez trouver toutes les connexions en profondeur*n complexité

    OriginalL'auteur Luka Rahne