поиск пути с помощью пролога

Я хочу узнать, есть ли путь из одной точки в другую или нет.

Например, 2 -> 4 -> 7 1 -> 3 -> 2 -> 9 5 -> 1 -> 6 -> 8

это путь. Я хочу написать предикатный путь (Начало, Конец), а дуги представлены набором фактов дуги (От, До).

Например, когда указан путь (1, 7), он должен возвращать истину. когда указан путь (6, 1), это должно возвращать false. потому что дуги направлены.


path path-finding prolog
person Burak Keceli    schedule 20.04.2012    source источник

Ответы (2)


arrow_upward
1
arrow_downward

  1. Если между X и Y есть дуга, тогда Path = arc (X, Y). То есть, если arc (X, Y), то path (X, Y)). Или в Прологе это:

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

  2. В противном случае, если есть дуга между X и каким-либо другим узлом Z, и есть путь от Z до Y, то существует и путь от X до Y. То есть, если дуга (X, Z) и путь (Z, Y), то путь (X, Y). В Прологе это:

    path (X, Y, [arc (X, Z) | P]): - arc (X, Z), путь (Z, Y, P).

Взято с этого сайта.

Вы также можете связать это в один предикат, который просто берет список дуг и рекурсивно ищет путь.

person keyser    schedule 20.04.2012
comment
Это кажется правдой, но мой путь будет принимать только 2 параметра. Этот путь принимает 3 параметра. - person Burak Keceli; 20.04.2012
comment
Просто продлите его с помощью path (From, To): - path (From, To, Path) - person Alexander Serebrenik; 20.04.2012
comment
Да, здесь можно ввести список дуг. Если вы хотите пропустить этот параметр, просто определите дуги в документе и расширьте их, как сказал Александр. - person keyser; 20.04.2012

arrow_upward
0
arrow_downward

Попробуйте ответить, разбив задачу на элементарные задачи.

path(From, To) :-
  arc(From, Intermediate),
  path(Intermediate, To).

Но видите ли вы, где должен остановиться путь? А если есть циклы, что происходит?

Что упускают, так это банальный случай, утверждающий, что path(X, X) это всегда правда. Добавьте к правилу выше:

path(To, To).

Может быть, будет понятнее, если мы напишем одно правило, используя If Then Else

path(From, To) :-
  (   From \= To
  ->  arc(From, Intermediate),
      path(Intermediate, To)
  ;   true
  ).
person CapelliC    schedule 20.04.2012