|
|
— |
pl:prolog:pllib:acyclic_path_2 [2019/06/27 15:50] (aktualna) |
| ====== Acyclic path 2 ====== |
| {{tag>graphs operators}} |
| ===== Description ===== |
| Path-finding in a graph, acyclic path with cost |
| |
| **Source**: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7. |
| ===== Download ===== |
| Program source code: {{prolog:pllib:acyclic_path_2.pl}} |
| ===== Listing ===== |
| <code prolog> |
| % Figure 9.21 Path-finding in a graph: Path is |
| % an acyclic path with cost Cost from A to Z in Graph. |
| |
| :- op( 900, fy, not). |
| |
| % path( A, Z, Graph, Path, Cost): |
| % Path is an acyclic path with cost Cost from A to Z in Graph |
| |
| path( A, Z, Graph, Path, Cost) :- |
| path1( A, [Z], 0, Graph, Path, Cost). |
| |
| path1( A, [A | Path1], Cost1, Graph, [A | Path1], Cost1). |
| |
| path1( A, [Y | Path1], Cost1, Graph, Path, Cost) :- |
| adjacent( X, Y, CostXY, Graph), |
| not member( X, Path1), |
| Cost2 is Cost1 + CostXY, |
| path1( A, [X, Y | Path1], Cost2, Graph, Path, Cost). |
| |
| % not Goal): negation as failure; |
| % Note: This is often available as a built-in predicate, |
| % often written as prefix operator "\+", e.g. \+ likes(mary,snakes) |
| |
| not Goal :- |
| Goal, !, fail |
| ; |
| true. |
| </code> |
| ===== Comments ===== |
| |