Найти путь между 2 точками из данных соединений

Question

Я хочу решить типичную проблему Пролога из здесь в Ocaml

Соединения представлены следующими данными:

arc(1,2).
arc(2,3).
arc(3,4).
arc(3,5).
arc(2,5).
arc(5,6).
arc(2,6).

Нужно найти заданный путьначальная и конечная точки (решение должно быть сохранено в P), например:

?- path(1,6,P).

Код пролога для этого выглядит следующим образом:

path(X,Y,[arc(X,Y)]) :- arc(X,Y).
path(X,Y,[arc(X,Z)|P]) :- arc(X,Z),path(Z,Y,P).

Вывод будет следующим:

P = [arc(1, 2), arc(2, 6)] .

Я вижу, что в Ocaml есть много возможностей для сопоставления с образцом.Как можно решить вышеуказанную проблему в Ocaml?

Редактировать: я не настаиваю на методе объединения.

Answer 1

OCaml не является языком логического программирования. Это обычный мультипарадигмальный, функциональный, императивный и объектно-ориентированный язык. Таким образом, нет встроенных конструкций для решения логических задач (кроме проверки типов) или чего-либо подобного.

Тем не менее, ваша проблема является типичной проблемой графов, поэтому вы можете использовать любую библиотеку графов, доступную в OCaml, чтобы решить ее, вот решение, реализованное с использованием Graphlib * кратчайшего пути алгоритм, который реализует классический алгоритм Дейкстры

open Core_kernel
open Graphlib.Std

module G = Graphlib.Make(Int)(Unit)

let graph = Graphlib.create (module G) () ~edges:[
          1,2,();
          2,3,();
          3,4,();
          3,5,();
          2,5,();
          5,6,();
          2,6,();
]

let () = 
  match Graphlib.shortest_path (module G) graph 1 6 with
  | None -> printf "No path\n"
  | Some p -> 
    Path.edges p |> Sequence.iter ~f:(fun e ->
      printf "Arc(%d, %d)\n" (G.Edge.src e) (G.Edge.dst e))

Вы можете установить graphlib используя opam

  opam install graphlib

затем, если вы поместите вашу программу в отдельную папку и имя, скажем, check_path.ml, вы можете собрать и запустить ее, используя ocamlbuild, например.

 $ ocamlbuild -package graphlib check_path.native --
 Arc(1, 2)
 Arc(2, 6)