# Różnice

Różnice między wybraną wersją a wersją aktualną.

 — pl:prolog:pllib:lee_routing [2019/06/27 15:50] (aktualna) Linia 1: Linia 1: + ====== Lee routing ====== + {{tag>​problem_solving}} + ===== Description ===== + Lee routing ​ + + **Source**: ​ The Art of Prolog + ===== Download ===== + Program source code: {{lee_routing.pl}} + ===== Listing ===== + + /* + lee_route(Source,​Destination,​Obstacles,​Path) :- + Path is a minimal length path from Source to + Destination which does not cross Obstacles. + */ + :-  op( 900, fy, not). + + ​lee_route(A,​B,​Obstacles,​Path) :- + waves(B,​[[A],​[]],​Obstacles,​Waves),​ + path(A,​B,​Waves,​Path). + + /* + waves(Destination,​Wavessofar,​Obstacles,​Waves) :- + Waves is a list of waves including Wavessofar + (except,​perhaps,​its last wave) that leads to Destination + without crossing Obstacles. + */ + + ​waves(B,​[Wave|Waves],​Obstacles,​Waves) :- member(B,​Wave),​ !. + ​waves(B,​[Wave,​LastWave|LastWaves],​Obstacles,​Waves) :- + ​next_wave(Wave,​LastWave,​Obstacles,​NextWave), ​ + waves(B,​[NextWave,​Wave,​LastWave|LastWaves],​Obstacles,​Waves). + + /* + next_waves(Wave,​LastWave,​Obstacles,​NextWave) :- + Nextwave is the set of admissible points from Wave, + that is excluding points from Lastwave, Wave, + and points under Obstacles. + */ + + ​next_wave(Wave,​LastWave,​Obstacles,​NextWave) :​-  ​ + ​findall(X,​admissible(X,​Wave,​LastWave,​Obstacles),​NextWave). + + ​admissible(X,​Wave,​LastWave,​Obstacles) :​-  ​ + ​adjacent(X,​Wave,​Obstacles), ​ + not member(X,​LastWave), ​ + not member(X,​Wave). + + ​adjacent(X,​Wave,​Obstacles) :- + member(X1,​Wave), ​ + neighbor(X1,​X), ​ + not obstructed(X,​Obstacles). + + ​neighbor(X1-Y,​X2-Y) :- next_to(X1,​X2). + ​neighbor(X-Y1,​X-Y2) :- next_to(Y1,​Y2). + + ​next_to(X,​X1) :- X1 is X+1. + ​next_to(X,​X1) :- X > 0, X1 is X-1. + + ​obstructed(Point,​Obstacles) :- + member(Obstacle,​Obstacles),​ obstructs(Point,​Obstacle). + + ​obstructs(X-Y,​obstacle(X-Y1,​X2-Y2)) :- Y1 =< Y, Y =< Y2. + ​obstructs(X-Y,​obstacle(X1-Y1,​X-Y2)) :- Y1 =< Y, Y =< Y2. + ​obstructs(X-Y,​obstacle(X1-Y,​X2-Y2)) :- X1 =< X, X =< X2. + ​obstructs(X-Y,​obstacle(X1-Y1,​X2-Y)) :- X1 =< X, X =< X2. + + /* + ​path(Source,​Destination,​Waves,​Path) :- + Path is a path from Source to destination going through Waves. + */ + + ​path(A,​A,​Waves,​[A]) :-  !. + ​path(A,​B,​[Wave|Waves],​[B|Path]) :- + ​member(B1,​Wave),​ neighbor(B,​B1),​ !, path(A,​B1,​Waves,​Path). + + % Testing and Data + + test_lee(Name,​Path) :- + ​data(Name,​A,​B,​Obstacles),​ lee_route(A,​B,​Obstacles,​Path). + + data(test1,​1-1,​3-3,​[]). + data(test2,​1-1,​5-5,​[obstacle(2-3,​4-5)]). + data(test,​1-1,​5-5,​[obstacle(2-3,​4-5),​obstacle(6-6,​8-8)]). + + % Program 16.6 Lee routing ​ + ​ + ===== Comments =====
pl/prolog/pllib/lee_routing.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)