Ci sono più percorsi hamiltoniani su un grafico?

Question

Ci sono più percorsi hamiltoniani su un grafico?

#1 da (3 voti)

4

Qualcuno può suggerire un algoritmo per questo problema.

Dato un grafo ciclico non ponderato non orientato, e un dato nodo iniziale e finale in quel grafico, vorrei determinare se c'è un esattamente un percorso valido dall'inizio alla fine che visita tutti i nodi (es. un percorso hamiltoniano, non un ciclo).

È NP-difficile, ma il mio N è relativamente piccolo (fino a 30 nodi o giù di lì) e la connettività di ciascun nodo è in genere molto piccola (non più di 4-5, spesso 2 o 3, in genere collegamenti locali [cioè corrispondono alle posizioni in 2d collegate ai vicini vicini]), quindi sono fiducioso che sia fattibile.

Gli algoritmi pubblicati sono in genere per cicli, per trovare una soluzione singola e per i punti di inizio e fine sconosciuti. Sono curioso di sapere se qualcuno può suggerire qualcosa di più appropriato, o se hai qualche intuizione su un approccio.

algorithms graph

posta Ian 06.05.2016 - 04:59

fonte

1 risposta

Leggi altre domande sui tag algorithms graph

Come implementare l'algoritmo di riempimento di piene su più macchine? Quanto deve andare lontano l'incapsulamento in JavaScript?

score 3 · Accepted Answer

Se il problema è abbastanza piccolo, un approccio totalmente ingenuo funziona bene. Vogliamo generare tutti i percorsi hamiltoniani bloccati che connettono due nodi a e b in un dato grafico . Per questo, generiamo solo tutti i percorsi validi provenienti da a e filtriamo quelli che non sono hamiltoniani o che non terminano in b .

Il seguente snippet di codice è un'implementazione di questa idea in OCaml. Sulla mia macchina può trovare tutto il percorso hamiltoniano riposto in un grafico completo di dimensione 9 (ci sono (9-2)! = 5040 tali percorsi, sono tutte le permutazioni di 7 nodi non appuntati), ma il programma non può gestire il caso della dimensione 10. Questo dovrebbe darti un'idea della complessità dell'operazione, ma come puoi vedere, non potrei essere meno ingenuo quando implemento questo.

module Graph =
struct
  type t = {
    node: int list;
    edge: (int * int list) list;
  }

  let nodes graph =
    List.sort_uniq Pervasives.compare graph.node

  let neighbours graph n =
    try List.assoc n graph.edge
    with Not_found -> []

  let pointed_hamiltonian_paths graph a =
    let is_visiting_all_nodes path =
      let sort = List.sort Pervasives.compare in
      sort path = sort graph.node
    in
    let hamiltonian_extensions path =
      match path with
      | [] -> []
      | node :: _ ->
          match List.filter
                  (fun x -> not(List.mem x path))
                  (neighbours graph node)
          with
          | [] -> [ path ]
          | newnodes -> List.map (fun x -> x :: path) newnodes
    in
    let rec loop paths =
      match List.concat (List.map hamiltonian_extensions paths) with
      | [] -> []
      | newpaths ->
          if newpaths = paths then paths else loop newpaths
    in
    List.filter is_visiting_all_nodes (loop [[a]])

  let pinned_hamiltonian_paths graph a b =
    List.filter (fun path -> (match path with hd ::_ -> hd = b | [] -> false))
      (pointed_hamiltonian_paths graph a)

  let example_1 = {
    node = [1; 2; 3; 4; 5];
    edge = [
      1, [ 4 ];
      2, [ 4; 5];
      3, [ 5 ];
      4, [ 1; 2; 5 ];
      5, [ 2; 3; 4 ];
    ];
  }

  let example_2 = {
    node = [ 6; 7; 8 ];
    edge = [
      6, [ 7; 8];
      7, [ 6; 8];
      8, [ 6; 7];
    ];
  }

  let example_3 = {
    node = example_1.node @ example_2.node;
    edge = example_1.edge @ example_2.edge;
  }

  let complete n =
    let rec loop ax i =
      if i < 1 then ax else loop (i :: ax) (pred i)
    in
    let seq = loop [] n in {
      node = seq;
      edge = List.map (fun x -> x, seq) seq;
    }
end

Ci sono tre esempi di grafici definiti, il primo è:

il secondo è un grafico completo senza loop (i bordi hanno lo stesso punto iniziale e finale) e il terzo è l'unione disgiunta dei due. Con queste definizioni possiamo sperimentare un po 'in alto:

# Graph.pinned_hamiltonian_paths Graph.example_1 1 3;;
- : int list list = [[3; 5; 2; 4; 1]]

# Graph.pinned_hamiltonian_paths Graph.example_2 6 8;;
- : int list list = [[8; 7; 6]]

# Graph.pinned_hamiltonian_paths Graph.example_3 1 3;;
- : int list list = [] (* The graph is not connected! :) *)

# Graph.pinned_hamiltonian_paths (Graph.complete 4) 1 4;;
- : int list list = [[4; 3; 2; 1]; [4; 2; 3; 1]]