Блог

Главная - Вопросы по программированию - Поиск всех узлов, связанных с вершиной в Prolog

Поиск всех узлов, связанных с вершиной в Prolog

#optimization #prolog #dijkstra #path-finding #logic-programming

#оптимизация #пролог #dijkstra #поиск пути #логическое программирование

Вопрос:

Мне любопытно узнать об алгоритмах поиска путей, поэтому я взглянул на Дейкстру. Я использую это видео в качестве руководства (и это то, на чем я основываю свой график). Вот график, с которым я работаю:

Изображение

Теперь я хочу иметь возможность находить все соединения данной вершины. Я думаю, что я должен использовать findall для этого, что я пытался использовать в all_connections цели ниже. Однако, с main моим выводом [b,b,b,b] . Почему это происходит? Это не имеет смысла. Если вы понимаете, что я делаю неправильно, пожалуйста, дайте мне знать.

 connection(s, c, 3).
connection(c, l, 2).
connection(l, i, 4).
connection(l, j, 4).
connection(i, j, 6).
connection(i, k, 4).
connection(j, k, 4).
connection(k, e, 5).
connection(e, g, 2).
connection(g, h, 2).
connection(h, f, 3).
connection(f, d, 5).
connection(d, a, 4).
connection(b, d, 4).
connection(b, a, 3).
connection(b, s, 2).
connection(b, h, 1).
connection(a, s, 7).

are_connected(A, B, Score) :-
    connection(A, B, Score);
    connection(B, A, Score).

all_connections(A, Z) :-
    findall(A, are_connected(A, _, _), Z).

main :-
    all_connections(b, X),
    write(X).

Комментарии:

1. Примечание: я только что решил свою проблему. Вот как я использовал findall : первый аргумент был результатом цели, которая будет решаться каждый раз, вторым был вызов функтора, а третьим был результат: findall(Connected, are_connected(Node, Connected, _), Connections).

2. Прошло некоторое время, я не видел fanfold paper (в последний раз в office for building security, с приложением NEC pinwriter)

Ответ №1:

Поздравляем с решением вашей проблемы. Если вы опубликуете решение в качестве ответа, мы можем проголосовать за него.

Это комментарий к чему-то другому: поскольку вы относительный новичок, сейчас самое подходящее время для изучения хороших соглашений о кодировании. В частности, это:

 are_connected(A, B, Score) :-
    connection(A, B, Score);
    connection(B, A, Score).

очень плохо. Дизъюнкция Prolog — очень мощный и часто сбивающий с толку инструмент. Когда вы используете его, использование должно действительно выделяться. В противном случае легко ошибочно принять ваш код за это:

 are_connected(A, B, Score) :-
    connection(A, B, Score),
    connection(B, A, Score).

То, как вы это написали, точку с запятой очень легко пропустить в конце строки. Эмпирическое правило: вы никогда не должны использовать ; в конце строки.

Альтернативы:

 are_connected(A, B, Score) :-
    connection(A, B, Score).
are_connected(A, B, Score) :-
    connection(B, A, Score).

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

 are_connected(A, B, Score) :-
    (   connection(A, B, Score)
    ;   connection(B, A, Score) ).

Или:

 are_connected(A, B, Score) :-
    (
        connection(A, B, Score)
    ;
        connection(B, A, Score)
    ).

Вы поняли идею. Каждый из этих вариантов дает понять, что то, что вы делаете, сильно отличается от использования conjunction .

Комментарии:

1. Как показано в Руководстве по кодированию для Prolog на странице 10 PDF.

2. Я все еще очень хочу, чтобы «Рекомендации по кодированию для Prolog» были где-нибудь на HTML-странице с возможностью комментирования, а не мумифицировались внутри PDF на arxiv.

3. @DavidTonhofer Есть arxiv-vanity.com для рендеринга документов arXiv в формате HTML, хотя в этом он захлебывается. И в любом случае не предлагает комментариев.

Ответ №2:

Вот как я решил свою проблему:

 are_connected(A, B, S) :-
    connection(A, B, S)
    ;
    connection(B, A, S).

Большое спасибо Изабель за то, что она дала мне совет по правильным соглашениям.

Метки: