algorithm - lyrics - ¿Cuál sería un buen algoritmo para una verificación de referencia circular en este caso?

algorithms book

Question

Dado que tienes la siguiente clase (mala C #, pero obtienes la deriva):

public abstract class AmICircular
{
  // assume Children is never null
  private List<AmICircular> Children {get;set;}

  // assume target is never null
  public void Add(AmICircular target)
  {
    target.PerformCircularReferenceCheck(this);
    Children.Add(target);
  }

  // throws when a circular reference is detected
  protected abstract void PerformCircularReferenceCheck(AmICircular target);
}

¿Cómo implementaría PerformCircularReferenceCheck? Y, no, esto no es tarea.

La implementación ingenua, imo, sería hacer una verificación de referencia sobre this y todos los niños, luego llamar a PerformCircularReferenceCheck en el target , pasando this . Pero me pregunto si hay formas mejores y comprobadas de hacerlo, como agregar un método para colapsar todo el árbol de referencias Children para this y target y luego examinar los resultados (¿hay menos presión en la pila?), O quizás evite el cheque por completo utilizando una colección diferente (¡tal vez autocomprobación!) que no sea List <T>?

¿Cómo harías esto?

editar: Como señaló Stefan, solo es necesario determinar si el objetivo puede alcanzarlo

Answer 1

En el caso de que nunca agregue objetos que se autorreferencien (a ser definidos más adelante), su estructura de datos describe un gráfico acíclico dirigido ( http://en.wikipedia.org/wiki/Directed_acyclic_graph ), donde cada instancia del IAmCircular class describe un nodo con un conjunto de nodos sucesores directos = Children.

Asumiendo la precondición de que hasta el momento no se ha creado un ciclo, la función que desea, PerformCircularReferenceCheck, solo necesita verificar si "this" es alcanzable desde "target". Si es así, debería devolver una excepción.

En cuanto a la teoría de la complejidad, este problema es la conectividad ST ( http://en.wikipedia.org/wiki/St-connectivity ) y está completa para la clase NL ( http://en.wikipedia.org/wiki/NL_(complexity) ) ), incluso cuando restringe la entrada a gráficos acíclicos (que es su caso).

En particular, el teorema de Savitch ( http://en.wikipedia.org/wiki/Savitch%27s_theorem ) ofrece una forma constructiva de crear un algoritmo de espacio O (log ^ 2 n) (que se ejecuta en el tiempo O (n ^ 2)) para it, donde n es la cantidad de nodos.

Además, al ser NL-completo, es poco probable que exista un algoritmo que se ejecute en el espacio O (log n) (es decir, use solo un número constante de punteros a nodos), ya que eso implicaría la improbable NL = L. EDITAR: en en particular, pequeñas variaciones del algo de liebre y tortuga sugeridas por alguien no funcionarían (porque usarían muy poco espacio).

Recomendaría implementar el algoritmo trivial O (n) time, O (n) space, que genera para "objetivo" su conjunto de sucesores (recursivamente) y verificar si "this" aparece en este conjunto.

Tenga cuidado, la construcción explícita del conjunto es importante. De lo contrario, si solo verifica recursivamente si "cualquier persona que suceda" puede alcanzar "esto", corre el riesgo de correr en tiempo exponencial.

Le recomendé el algoritmo de O (n) tiempo / O (n) espacio porque es asintóticamente el mejor que puede hacer en cuanto al tiempo, y ya está usando O (n) espacio para su estructura de datos.

Answer 2

La solución iterativa es definir un conjunto R (alcanzable) y CR (hijos de Alcanzable).

Empiezas con R = {this} y CR = {this.children} .

En cada paso, verifica si CR contiene this (o target , dependiendo de su objetivo exacto). De lo contrario, agregue CR a R y establezca CR para los hijos de CR, y elimine los elementos de R de CR.

Si CR se vacía, R es el conjunto completo de elementos alcanzables a partir de this .