Un graphique de taille par exemple. A-> B-> C-> D-> E est le graphique, Maintenant, e est à distance <= 2 de C, mais pas d'un, il ne faut donc pas être compté.
J'ai pensé à courir d'abord la première recherche de chaque nœud du sous-ensemble et en prenant intersection des réponses respectives. J'ai parcouru de nombreux postes sur ce que, mais ils sont tous directs de KD-arbres que je ne comprends pas, alors y a-t-il d'autre manière? n est donné et un sous-ensemble de taille m de ses nœuds est donné. Trouvez tous les nœuds qui sont à une distance <= k de tous les nœuds du sous-ensemble.
sous-ensemble = {A, c}, k = 2.
Peut-il être encore optimisé?
3 Réponses :
Je peux penser à deux optimisations non asymptotiques (je crois):
Bien sûr que cela n'aide pas si k est grand (près de N), je n'ai aucune idée dans ce cas. Je suis cependant positif que les arbres K / D ne sont pas applicables aux graphiques généraux :)
@Nuclearman HM, mais vous ne pouvez pas retirer les nœuds du sous-graphique, votre BFS n'est donc pas vraiment taillé, ou je manque quelque chose?
@Nuclearman sûr, mais si vous supprimez ces nœuds, vous ne pouvez plus faire de BFS d'un autre nœud, car il pourrait être à l'intérieur du rayon D autour du point de départ de votre première recherche
@Nuclearman, je ne comprends pas comment cela fonctionnerait si vous n'êtes plus connecté au graphique, car vous étiez à l'intérieur du rayon du premier point de départ. Désolé peut-être que je suis mal compris votre algorithme
Un point équitable, ce que j'avais à l'esprit nécessiterait le prétraitement de travailler correctement maintenant que j'y pense, et le prétraitement permet de plus de possibilités que cela.
@Nuclearman, je serais très intéressé par une bonne approche de ce problème comme vous pouvez l'imaginer, alors assurez-vous d'écrire une réponse si vous proposez quelque chose :)
Très bien, posté une réponse qui est peut-être un peu plus sensible à la sortie. On ne peut pas sembler résoudre le cas où K est grand ou vraiment le cas où la taille de la solution finale est O (n). Semble que la seule optimisation est dans le cas où il existe de nombreuses requêtes.
Les optimisations de Nicklas B peuvent être appliquées aux deux optimisations suivantes.
Optimisation n ° 1: Modifier BFS pour effectuer l'intersection car elle fonctionne plutôt que des nouveautés.
Le BFS et l'intersection semblent être la voie à suivre. Cependant, les travaux rédudants sont effectués par le BFS. Spécialement, il élargit les nœuds qu'il n'a pas besoin de se développer (après le premier BFS). Cela peut être résolu en fusionnant l'aspect intersection dans le BFS.
La solution semble conserver deux ensembles de nœuds, appelez-les "tovisiter" et "visité", plutôt que des nœuds d'étiquettes visités ou non.
Les nouvelles règles du BFS sont suivies:
Cela fonctionne mieux si l'ensemble de Govisit est faible en moyenne, ce qui tend à être le cas de M et K sont beaucoup moins importants que n.
Optimisation n ° 2: Pré-calculez les distances s'il y a suffisamment de requêtes afin que les requêtes ne font que faire des intersections. Bien que cela soit incompatible avec la première optimisation. S'il existe un nombre suffisant de requêtes sur des sous-ensembles et des valeurs de K différents, il est préférable de trouver les distances entre chaque paire de nœuds à l'avance à un coût de O (VE).
De cette façon, vous n'avez besoin que d'intersections, qui est O (v * m * q), où q est le nombre de requêtes, m est la taille moyenne du sous-ensemble sur les requêtes et V est le nombre de nœuds . Si cela devrait être le cas que O (m * q)> O (e), cette approche devrait être moins de travail. Notant les deux nœuds les plus distants sont utiles car tout K égal ou supérieur retournera toujours l'ensemble de tous les sommets, ce qui entraîne juste O (v) pour le coût de la requête dans ce cas.
Les données de distance doivent ensuite être stockées sous quatre formes.
le premier est "kcount [a] [k] = nombre de nœuds avec la distance k ou moins de A". Cela fournit une alternative à la suggestion de Niklas B. de "Démarrer avec les deux nœuds du sous-ensemble dont la distance est la plus grande pour obtenir le plus petit graphique de restes possibles" dans le cas où O (m)> O (SQRT (V)) depuis Trouver le plus petit est O (M ^ 2) et il est peut-être préférable d'éviter d'essayer de trouver le meilleur choix pour la paire de départ et choisissez simplement un bon choix. Vous pouvez commencer avec les deux nœuds du sous-ensemble avec la plus petite valeur pour la K donnée dans cette structure de données. Vous pouvez également trier les nœuds du sous-ensemble par cette métrique et faire les intersections dans cet ordre.
Le second est "KMAX [A] = max k pour A", qui peut être fait à l'aide d'un hashmap / dictionnaire. Si la K> = Cette valeur, celle-ci peut être ignorée à moins que kcount [a] [kmax [a]] <(nombre de sommets), ce qui signifie que tous les nœuds ne sont pas accessibles à partir d'une.
la troisième est "kfrom [a] [k] = ensemble de nœuds k Distance de A", car k est valide de 0 à la distance maximale, un hashmap / dictionnaire vers une matrice / liste pourrait être utilisé. ici plutôt qu'un hashmap / dictionnaire imbriqué. Cela permet à l'espace et à l'efficacité du temps *** Création de l'ensemble de nœuds avec la distance <= K de A.
Le quatrième est "dist [a] [b] = distance entre A à B", cela peut être effectué à l'aide d'un hashmap / dictionnaire imbriqué. Cela permet de manipuler les vérifications d'intersection assez rapidement.
* Si l'espace n'est pas un problème, cette structure peut alors stocker tous les nœuds k ou moins de distance d'un, mais qui nécessite un espace O (v ^ 3) et donc le temps. Le principal avantage est cependant qu'il permettant également de stocker une liste distincte de nœuds supérieure à K Distance. Cela permet à l'algorithme d'utiliser le plus petit des ensembles, dist> k ou dist <= k. Utilisation d'une intersection dans le cas de dist <= k et de soustraction définie dans le cas de dist <= k ou d'intersection, puis définissez la soustraction si l'ensemble principal a la taille minimisée.
c'est exactement pensé et voulait un autre algorithme
Élargi la réponse pour fournir des optimisations possibles dans le cas de nombreuses requêtes (oméga (v), idéalement oméga (v ^ 2)).
s ) et connectez-le à tous les nœuds m données.
- Ensuite, trouvez tous les nœuds qui sont à une distance inférieure ou égale à K + 1 à partir de
S et soustrayez m de celui-ci. t (n) = O (v + e)
C'est la même chose qu'un BFS multi-sources, et ne fonctionnera évidemment pas dans ce cas. Lisez la question. Tous Les nœuds doivent être au maximum une distance de distance k à l'écart et, dans de nombreux cas, votre technique prendra compte des nœuds ne satisfaisant pas cette condition.
Désolé j'ai mal compris votre problème alors supprimé le commentaire déroutant.
@MOHITJAIN: Vous aviez raison, le concept d'arbre k-d peut être appliqué ici
Vous voudrez peut-être poser cette question sur cs.stackexchange.com .
@ Adrianfrühwirth: peut-il être migré ou devrais-je me repousser là-bas?
Les modérateurs peuvent la migrer. Vous pouvez le signaler pour leur attention si vous souhaitez (bien que cela puisse la supprimer et le republier sur le site applicable, c'est mieux si vous êtes sûr que c'est le bon geste). Bien qu'ils ne puissent pas migrer cela, comme cela se trouve sur le sujet ici (ainsi que sur CS). Il suffit de publier la même question sur les deux sites, car ce n'est pas permis.
@Dukeling: OK, alors j'attendrai 1 jour, si je ne reçois pas de réponses, je supprimerai d'ici et posterai sur l'informatique
Est-ce un graphique dirigé?
Est-ce une interrogation à une fois ou allez-vous le faire avec le même graphique pour différentes valeurs de K?
Combien de bords y a-t-il? Et est le graphique d'un type spécifique. Votre exemple de graphique de ligne est beaucoup plus facile à résoudre que d'autres types de graphiques.
Y a-t-il de nombreuses questions? IE: recherchez différents types de valeurs M, ou différentes valeurs K ou lorsque M ou K change, mais où le graphique reste le même. Il y a quelques optimisations possibles dans ce cas.
Le graphique reste le même, et oui il y a beaucoup de requêtes
Un exemple de quel type de requêtes et une estimation quant au nombre d'entre eux pourrait être utile. Bien que l'optimisation principale, si K varie, auquel cas vous pouvez exécuter une recherche complète BFS une fois pour chaque nœud et stocker le résultat partitionné par k. Si vous connaissez toutes les questions à l'avance, il existe d'autres optimisations. Sinon, il semble qu'il ne semble pas que des optimisations importantes puissent être apportées.
Non, les requêtes ne sont pas connues à l'avance, k est variable et est donc l'ensemble.
Élargi ma réponse pour cette situation.