Пролог: Трассировка маршрутов между городами падает в бесконечный цикл

Question

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

код ниже:

road (city1, city2, distance).

road(campinas,valinhos,16.9). 
road(campinas,paulinia,30.1). 
road(campinas,hortolandia,27.6). 
road(campinas,holambra,41.1). 
road(valinhos,vinhedo,7.8). 
road(paulinia,cosmopolis,18.5). 
road(hortolandia,sumare,9.1). 
road(holambra,santo_antonio_de_posse,16.7). 
road(vinhedo,louveira,11.2). 
road(sumare,americana,12.3). 
road(sumare,santa_barbara_doeste,29.8). 
road(louveira,jundiai,12.9). 
road(americana,limeira,27.6). 
road(limeira,cordeiropolis,14.9). 
road(santa_barbara_doeste,piracicaba,28.0). 
road(cordeiropolis,araras,21.4). 

conects(A,B,D):-road(A,B,D). 
conects(A,B,D):-road(B,A,D). 

distance(A,B,0):- A == B!. 
distance(A,B,D):- conects(A, B, D). 
distance(A,B,D):- distance(B1,B,D2), conects(A,B1,D1), not(conects(A,B,_)), D is D1 + D2. 

Что я делаю неправильно?

Answer 1

Если вы проследите свой код, вы увидите, что он переходит в бесконечный цикл, так как даже если он не может объединить первые два distance/3 положения, он всегда может объединить distance(A,B,D):- distance(B1,B,D2) так B1 является несвязанным.

Измените код следующим образом:

road(campinas,valinhos,16.9). 
road(campinas,paulinia,30.1). 
road(campinas,hortolandia,27.6). 
road(campinas,holambra,41.1). 
road(valinhos,vinhedo,7.8). 
road(paulinia,cosmopolis,18.5). 
road(hortolandia,sumare,9.1). 
road(holambra,santo_antonio_de_posse,16.7). 
road(vinhedo,louveira,11.2). 
road(sumare,americana,12.3). 
road(sumare,santa_barbara_doeste,29.8). 
road(louveira,jundiai,12.9). 
road(americana,limeira,27.6). 
road(limeira,cordeiropolis,14.9). 
road(santa_barbara_doeste,piracicaba,28.0). 
road(cordeiropolis,araras,21.4). 

conects(A,B,D):-road(A,B,D). 
conects(A,B,D):-road(B,A,D). 

distance(A,A,0). 
distance(A,B,D):- conects(A, B, D). 
distance(A,B,D):- not(conects(A,B,_)), conects(A1, A, D1), A1 \= A, conects(B1, B, D2), B1 \= B, distance(A1, B1, D3), D is D1 + D2 + D3. 

Тестовый прогон:

[debug] ?- distance(campinas, test, D). 
false. 

[debug] ?- distance(campinas, louveira, D). 
D = 35.9 

На самом деле можно найти бесконечное число расстояний, перемещая много раз между теми же городами:

[debug] ?- distance(campinas, louveira, D). 
D = 35.9 ; 
D = 95.49999999999999 ; 
D = 155.09999999999997 ; 
D = 214.7 ; 
D = 274.3 ; 
D = 333.90000000000003 ; 
D = 393.50000000000006 ; 
D = 453.1000000000001 ; 
D = 512.7 ; 
D = 572.3 ; 
D = 631.8999999999999 ; 
D = 691.4999999999998 ; 
D = 751.0999999999997 ; 
D = 810.6999999999996 ; 
D = 870.2999999999995 

Если вы не хотите, чтобы вы могли, например, дд ! следующим образом:

distance(A,B,D):- not(conects(A,B,_)), conects(A1, A, D1), A1 \= A, conects(B1, B, D2), B1 \= B, distance(A1, B1, D3), !, D is D1 + D2 + D3. 

тест-пробег:

[debug] ?- distance(campinas, louveira, D). 
D = 35.9. 

[debug] ?- 

Надеется, что это помогает ... trace/0 является вашим другом.