Prolog - Помогите установить правило

У меня есть база данных, полная таких фактов, как:

overground(newcrossgate,brockley,2).
overground(brockley,honoroakpark,3).
overground(honoroakpark,foresthill,3).
overground(foresthill,sydenham,2).
overground(sydenham,pengewest,3).
overground(pengewest,anerley,2).
overground(anerley,norwoodjunction,3).
overground(norwoodjunction,westcroydon,8).
overground(sydenham,crystalpalace,5).
overground(highburyandislington,canonbury,2).
overground(canonbury,dalstonjunction,3).
overground(dalstonjunction,haggerston,1).
overground(haggerston,hoxton,2).
overground(hoxton,shoreditchhighstreet,3).

Например: newcrossgate to brockley занимает 2 минуты.

Затем я создал правило, чтобы, если я введу запрос istime (newcrossgate, honoroakpark, Z). то пролог должен дать мне время, необходимое для поездок между этими двумя станциями. (Правило, которое я сделал, предназначено для расчета расстояния между любыми двумя станциями вообще, а не только соседними).

istime(X,Y,Z):- istime(X,Y,0,Z); istime(Y,X,0,Z).
istime(X,Y,T,Z):- overground(X,Y,Z), T1 is T + Z.
istime(X,Y,Z):- overground(X,A,T), istime(A,Y,T1), Z is T + T1.
istime(X,Y,Z):- overground(X,B,T), istime(B,X,T1), Z is T + T1.

он, кажется, отлично работает для newcrossgate для первых парных станций, например newcrossgate to foresthill или sydenham. Однако, после тестирования newcrossgate на westcroydon, который занимает 26 минут, я попробовал newcrossgate для crystalpalace, и пролог сказал, что это займет 15 минут... несмотря на то, что это следующая станция после westcroydon. Очевидно, что что-то неправильно здесь, однако оно работает на большинстве станций, время от времени придумывая случайные ошибки во времени, время от времени, может кто-нибудь сказать мне, что случилось? : S

3 ответа

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

Я вижу только то, что ваш "публичный" предикат istime/3 пытается сделать слишком много. Все, что он должен сделать, это istime/4 аккумулятор и вызвать рабочий предикат istime/4. Поскольку вы ищете маршрут/время в обоих направлениях, общественный предикат должен быть просто

istime( X , Y , Z ) :- istime( X , Y , 0 , Z ) .
istime( X , Y , Z ) :- istime( Y , X , 0 , Z ) .

istime/3 существу является первым предложением вашего предиката istime/3

istime(X,Y,Z):- istime(X,Y,0,Z); istime(Y,X,0,Z).

Остальные предложения istime/3, рекурсивные:

istime(X,Y,Z):- overground(X,A,T), istime(A,Y,T1), Z is T + T1.
istime(X,Y,Z):- overground(X,B,T), istime(B,X,T1), Z is T + T1.

должен должным образом быть частью istime/4 и иметь накопитель. Это где ваша проблема.

Сделайте еще один снимок и отредактируйте свой вопрос, чтобы показать следующую итерацию. Если вы все еще не можете понять это, я покажу вам несколько способов сделать это.

Некоторые подсказки

  1. Ваш "рабочий" предикат, скорее всего, будет похож на предыдущий "найти маршрут между двумя станциями", но у него будет дополнительный аргумент - накопитель на прошедшее время.

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

    • А и В находятся непосредственно рядом.
    • A и B соединены, по меньшей мере, с одним промежуточным упором.

Существует и другой подход, который может быть описан как использование lookahead, и в этом случае специальные случаи

  • A и B одинаковы, и в этом случае вы прибыли.
  • A и B не связаны и связаны нулевыми или более промежуточными остановками.

FWIW. Вы не должны ожидать, что маршрут будет первым найденным решением с самым коротким прошедшим временем или минимальным количеством прыжков. Backtracking будет производить все маршруты, но порядок их обнаружения должен соответствовать порядку, в котором данные хранятся в базе данных. Минимальный поиск стоимости графика - это еще один чайник рыбы.


Чтобы заставить его работать, вам нужно сделать обратное обоим поездкам, указанным в последнем пункте. Храните предикат как есть, istime (X, Y, Z) и просто создайте другое предложение, содержащее обратные поездки. Таким образом, он работает со всеми станциями. (Пробовал и тестировал)


Вы пытались пройти через ответы ; ? 26 минут - это не самое короткое время между newcrossgate и westcroydon...

Редактировать: мое плохое! По-видимому, более короткие результаты были вызваны ошибкой в вашем коде (см. Мой комментарий о четвертом предложении). Однако ваш код верен, 15 минут - это самый короткий маршрут между newcrossgate и crystalpalace. Только потому, что есть маршрут, идущий от newcrossgate до westcroydon, затем crystalpalace, это не значит, что это самый короткий маршрут, или маршрут, который ваша программа даст в первую очередь.

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

istime(X,Y,_,Z):- overground(X,A,T), istime(A,Y,T1), Z is T + T1.

Причина проста: ваше первое предложение свопит X с Y, что хорошо, поскольку с этим вы говорите, что маршруты симметричны. Тем не менее, 3-й пункт не выгоден от этого, потому что он никогда не вызывал замененный. Игнорируя третий аргумент (который вы все равно не используете), и, таким образом, разрешая вызов 1-го предложения, третий может исправить вашу проблему, так как теперь будут использоваться некоторые допустимые маршруты, которые ранее не использовались.

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

licensed under cc by-sa 3.0 with attribution.