algoritmo probabilista para encontrar camino hamiltoniano en un grafo dirigido

Question

A partir de este artículo de Wikipedia:

http://en.wikipedia.org/wiki/Hamiltonian_path_problem

Un algoritmo aleatorio para el hamiltoniano camino que es rápido en la mayoría de los gráficos es lo siguiente: Inicio de una al azar vértice, y continuar si hay un vecino no visitado. Si no hay vecinos más no visitados, y la ruta formada no es hamiltoniana, elija un vecino uniformemente al azar, y gire utilizando ese vecino como pivote. (es decir, añadir un borde para que vecino, y eliminar una de las bordes existentes de ese vecino tan que no se forme un bucle.) A continuación, siguen el algoritmo en el nuevo extremo de la trayectoria .

No entiendo muy bien cómo se supone que funciona este proceso pivotante. ¿Alguien puede explicar este algoritmo con más detalle? Quizás podamos eventualmente actualizar el artículo de Wiki con una descripción más clara.

Edit 1: Creo que ahora entiendo el algoritmo, pero parece que solo funciona para gráficos no dirigidos. ¿Alguien puede confirmar eso?

Aquí es por lo que creo que sólo funciona para grafos no dirigidos:

alt text http://www.michaelfogleman.com/static/images/graph.png

pretensión Los vértices están numerados así:

123 
456 
789 

Digamos que mi camino hasta ahora es: 9, 5, 4, 7, 8. Todos los vecinos de 8 han sido visitados. Digamos que elijo 5 para eliminar un borde de. Si elimino (9, 5), acabo creando un ciclo: 5, 4, 7, 8, 5, por lo que parece que tengo que eliminar (5, 4) y crear (8, 5). Si el gráfico no está dirigido, está bien y ahora mi camino es 9, 5, 8, 7, 4. Pero si imaginas que se dirigen esos bordes, no es necesariamente un camino válido, ya que (8, 5) es un borde pero (5, 8) podría no serlo.

Edición 2: supongo que para un grafo dirigido que podría crear la (8, 5) la conexión y luego dejar que el nuevo camino sea justo 4, 7, 8, 5, pero que parece contraproducente ya que tengo que cortar todo lo que anteriormente se llevó hasta el vértice 5.

Answer 1

Básicamente, una vez que su selección aleatoria de nodos ha construido un gráfico de tal manera que el último vértice A no tiene vértices vecinos no visitados, debe hacer que un vértice esté disponible para continuar.

Para hacer esto: seleccione un vértice vecino al azar, elimine uno de sus bordes existentes (en un camino hamiltoniano puede haber solo dos bordes desde cualquier vértice), luego dibuje un nuevo borde desde su vértice actual hasta ahora disponible al azar seleccionado. A continuación, rastrea desde el vértice seleccionado al azar hasta el final del gráfico (el primer vértice que tiene solo un borde que lo abandona) y continúa con el algoritmo.

En todo tipo de horrible pseudo-código:

Graph graph; 
    Vertex current; 
    Path path; 

    while(!IsHamiltonian(path)) 
    { 
    if(HasUnvisitedNeighbor(current, path)) 
    { 
     Vertex next = SelectRandomUnvisited(current, path); 
     DrawEdgeTo(next, current, path); 
     current= next; 
    } 
    else 
    { 
     Vertex next = SelectRandomNeighbor(current, path); 
     RemoveRandomEdgeFrom(next, path); 
     DrawEdgeTo(next, current, path); 
     path = FindEnd(next, current, path); //Finds the end of the path, starting from next, without passing through current 
    } 
    } 

Answer 2

¿Comprenden lo que es una ventaja? Si los vértices son v1, v2, ... vn, entonces un borde es un par (v1, v2) - imagine dibujar una línea entre v1 y v2, y eso es un borde.

Por lo tanto, básicamente se hace un algoritmo básico de alpinismo (seguir añadiendo bordes y visitar nodos no visitados) sujeto a la restricción de que no se visita un nodo más de una vez.

Y si encuentra que no puede continuar más (no puede alcanzar más nodos no visitados del vértice actual), entonces elige un vértice aleatorio que esté conectado (hay un borde entre ese vértice y uno de los vértices que ya ha visitado) y agrega un borde entre ese vértice y los nodos visitados que aún no están en la ruta.

Esto podría (y posiblemente, debe dejar eso a los matemáticos) crear un bucle. Puede eliminar el bucle eliminando otro borde de los bordes en la ruta.

Básicamente, este es un algoritmo de alpinismo, con un poco de perturbación aleatoria cuando te quedas atascado. Cuando te quedas atascado, básicamente agregas otro borde y eliminas uno del gráfico y tratas de continuar. Si estuvo completamente equivocado, aún puede llegar a una solución porque, en teoría, podría agregar todos los bordes correctos y eliminar todas sus elecciones incorrectas originales.

Answer 3

De hecho, es una explicación muy poco clara, y el algoritmo no parece provenir tampoco de ninguna de las referencias enumeradas.

La idea parece ser primero hacer una ruta aleatoria seleccionando el nodo inicial al azar y, a partir de eso, seleccionando vecinos aleatorios durante el tiempo que sea posible. Cuando no se pueden recoger más vecinos, el camino es hamiltoniano o no lo es. Si no es así, este último nodo en la ruta ya tiene un vecino en la ruta (ver abajo), por lo que pivotar significa hacer un borde desde el último nodo al vecino que ya está en la ruta y eliminar uno de los enlaces del vecino que ha sido elegido para el camino. Luego, hay un nuevo final en el camino, desde el cual se continúa el proceso.

Parece que este algoritmo supone, por ejemplo, que no hay nodos con un solo borde. Sin embargo, estos son fáciles de cubrir: si hay uno de ellos, solo comience desde allí, si hay dos, comience desde uno de ellos y trate de terminar en el otro, y si hay más de dos, no puede haberlos. un camino hamiltoniano.