| 1 | ================================================================ |
|---|
| 2 | Logtalk - Open source object-oriented logic programming language |
|---|
| 3 | Release 2.35.0 |
|---|
| 4 | |
|---|
| 5 | Copyright (c) 1998-2009 Paulo Moura. All Rights Reserved. |
|---|
| 6 | Logtalk is free software. You can redistribute it and/or modify |
|---|
| 7 | it under the terms of the "Artistic License 2.0" as published by |
|---|
| 8 | The Perl Foundation. Consult the "LICENSE.txt" file for details. |
|---|
| 9 | ================================================================ |
|---|
| 10 | |
|---|
| 11 | |
|---|
| 12 | % start by loading the example and the required library files: |
|---|
| 13 | |
|---|
| 14 | | ?- logtalk_load(searching(loader)). |
|---|
| 15 | ... |
|---|
| 16 | |
|---|
| 17 | |
|---|
| 18 | % farmer, cabbage, goat and wolf problem |
|---|
| 19 | |
|---|
| 20 | | ?- farmer::initial_state(Initial), depth_first(10)::solve(farmer, Initial, Path), farmer::print_path(Path). |
|---|
| 21 | |
|---|
| 22 | cgwf.<__>..........____ |
|---|
| 23 | c_w_..........<__>.f_g_ |
|---|
| 24 | c_wf.<__>..........__g_ |
|---|
| 25 | __w_..........<__>.fcg_ |
|---|
| 26 | _gwf.<__>.........._c__ |
|---|
| 27 | _g__..........<__>.fc_w |
|---|
| 28 | _g_f.<__>.........._c_w |
|---|
| 29 | ____..........<__>.fcgw |
|---|
| 30 | |
|---|
| 31 | Path = [(north,north,north,north),(north,south,north,south),(north,south,north,north),(south,south,north,south),(south,north,north,north),(south,north,south,south),(south,north,south,north),(south,south,south,south)], |
|---|
| 32 | Initial = (north,north,north,north) ? |
|---|
| 33 | |
|---|
| 34 | yes |
|---|
| 35 | |
|---|
| 36 | |
|---|
| 37 | % missionaires and cannibals problem, solved using a hill-climbing strategy |
|---|
| 38 | |
|---|
| 39 | | ?- miss_cann::initial_state(Initial), hill_climbing(16)::solve(miss_cann, Initial, Path, Cost), miss_cann::print_path(Path). |
|---|
| 40 | |
|---|
| 41 | MMMCCC.<__>.......... |
|---|
| 42 | MMCC..........<__>.MC |
|---|
| 43 | MMMCC.<__>..........C |
|---|
| 44 | MMM..........<__>.CCC |
|---|
| 45 | MMMC.<__>..........CC |
|---|
| 46 | MC..........<__>.MMCC |
|---|
| 47 | MMCC.<__>..........MC |
|---|
| 48 | CC..........<__>.MMMC |
|---|
| 49 | CCC.<__>..........MMM |
|---|
| 50 | C..........<__>.MMMCC |
|---|
| 51 | CC.<__>..........MMMC |
|---|
| 52 | ..........<__>.MMMCCC |
|---|
| 53 | |
|---|
| 54 | Cost = 15, |
|---|
| 55 | Path = [((3,3),left,0,0),((2,2),right,1,1),((3,2),left,0,1),((3,0),right,0,3),((3,1),left,0,2),((1,1),right,2,2),((2,2),left,1,1),((0,2),right,3,1),((0,3),left,3,0),((0,1),right,3,2),((0,2),left,3,1),((0,0),right,3,3)], |
|---|
| 56 | Initial = ((3,3),left,0,0) |
|---|
| 57 | yes |
|---|
| 58 | |
|---|
| 59 | |
|---|
| 60 | % same problem as above with the addition of a monitor to measure hill-climbing performance |
|---|
| 61 | |
|---|
| 62 | | ?- performance::init, miss_cann::initial_state(Initial), hill_climbing(16)::solve(miss_cann, Initial, Path, Cost), miss_cann::print_path(Path), performance::report. |
|---|
| 63 | |
|---|
| 64 | MMMCCC.<__>.......... |
|---|
| 65 | MMCC..........<__>.MC |
|---|
| 66 | MMMCC.<__>..........C |
|---|
| 67 | MMM..........<__>.CCC |
|---|
| 68 | MMMC.<__>..........CC |
|---|
| 69 | MC..........<__>.MMCC |
|---|
| 70 | MMCC.<__>..........MC |
|---|
| 71 | CC..........<__>.MMMC |
|---|
| 72 | CCC.<__>..........MMM |
|---|
| 73 | C..........<__>.MMMCC |
|---|
| 74 | CC.<__>..........MMMC |
|---|
| 75 | ..........<__>.MMMCCC |
|---|
| 76 | solution length: 12 |
|---|
| 77 | number of state transitions: 26 |
|---|
| 78 | ratio solution length / state transitions: 0.461538 |
|---|
| 79 | minimum branching degree: 1 |
|---|
| 80 | average branching degree: 2.30769 |
|---|
| 81 | maximum branching degree: 3 |
|---|
| 82 | time: 0.02 |
|---|
| 83 | |
|---|
| 84 | Cost = 15, |
|---|
| 85 | Path = [((3,3),left,0,0),((2,2),right,1,1),((3,2),left,0,1),((3,0),right,0,3),((3,1),left,0,2),((1,1),right,2,2),((2,2),left,1,1),((0,2),right,3,1),((0,3),left,3,0),((0,1),right,3,2),((0,2),left,3,1),((0,0),right,3,3)], |
|---|
| 86 | Initial = ((3,3),left,0,0) ? |
|---|
| 87 | |
|---|
| 88 | yes |
|---|
| 89 | |
|---|
| 90 | |
|---|
| 91 | % bridge problem, solved using a hill climbing strategy |
|---|
| 92 | |
|---|
| 93 | | ?- performance::init, bridge::initial_state(Initial), hill_climbing(30)::solve(bridge, Initial, Path, Cost), bridge::print_path(Path), performance::report. |
|---|
| 94 | |
|---|
| 95 | _|____________|_ lamp 1 3 6 8 12 |
|---|
| 96 | 1 3 lamp _|____________|_ 6 8 12 |
|---|
| 97 | 3 _|____________|_ lamp 1 6 8 12 |
|---|
| 98 | 1 3 6 lamp _|____________|_ 8 12 |
|---|
| 99 | 3 6 _|____________|_ lamp 1 8 12 |
|---|
| 100 | 3 6 8 12 lamp _|____________|_ 1 |
|---|
| 101 | 6 8 12 _|____________|_ lamp 1 3 |
|---|
| 102 | 1 3 6 8 12 lamp _|____________|_ |
|---|
| 103 | solution length: 8 |
|---|
| 104 | state transitions: 367 |
|---|
| 105 | ratio solution length / state transitions: 0.0217984 |
|---|
| 106 | minimum branching degree: 1 |
|---|
| 107 | average branching degree: 7.32579 |
|---|
| 108 | maximum branching degree: 15 |
|---|
| 109 | time: 0.28 |
|---|
| 110 | |
|---|
| 111 | Initial = [], right, [1, 3, 6, 8, 12] |
|---|
| 112 | Path = [ ([], right, [1, 3, 6, 8, 12]), ([1, 3], left, [6, 8, 12]), ([3], right, [1, 6, 8, 12]), ([1, 3, 6], left, [8, 12]), ([3, 6], right, [1, 8|...]), ([3, 6|...], left, [1]), ([6|...], right, [...|...]), ([...|...], ..., ...)] |
|---|
| 113 | Cost = 29 |
|---|
| 114 | |
|---|
| 115 | yes |
|---|
| 116 | |
|---|
| 117 | |
|---|
| 118 | % water jugs problem solved using a breadth and a depth first strategy, with performance monitors |
|---|
| 119 | % it's interesting to compare the results |
|---|
| 120 | |
|---|
| 121 | | ?- performance::init, water_jug::initial_state(Initial), breadth_first(6)::solve(water_jug, Initial, Path), water_jug::print_path(Path), performance::report. |
|---|
| 122 | |
|---|
| 123 | 4-gallon jug: 0 |
|---|
| 124 | 3-gallon jug: 0 |
|---|
| 125 | |
|---|
| 126 | 4-gallon jug: 0 |
|---|
| 127 | 3-gallon jug: 3 |
|---|
| 128 | |
|---|
| 129 | 4-gallon jug: 3 |
|---|
| 130 | 3-gallon jug: 0 |
|---|
| 131 | |
|---|
| 132 | 4-gallon jug: 3 |
|---|
| 133 | 3-gallon jug: 3 |
|---|
| 134 | |
|---|
| 135 | 4-gallon jug: 4 |
|---|
| 136 | 3-gallon jug: 2 |
|---|
| 137 | |
|---|
| 138 | 4-gallon jug: 0 |
|---|
| 139 | 3-gallon jug: 2 |
|---|
| 140 | |
|---|
| 141 | solution length: 6 |
|---|
| 142 | number of state transitions: 109 |
|---|
| 143 | ratio solution length / state transitions: 0.0550459 |
|---|
| 144 | minimum branching degree: 2 |
|---|
| 145 | average branching degree: 3.63158 |
|---|
| 146 | maximum branching degree: 4 |
|---|
| 147 | time: 0.02 |
|---|
| 148 | |
|---|
| 149 | Path = [(0,0),(0,3),(3,0),(3,3),(4,2),(0,2)], |
|---|
| 150 | Initial = (0,0) ? |
|---|
| 151 | |
|---|
| 152 | yes |
|---|
| 153 | |
|---|
| 154 | |
|---|
| 155 | | ?- performance::init, water_jug::initial_state(Initial), depth_first(10)::solve(water_jug, Initial, Path), water_jug::print_path(Path), performance::report. |
|---|
| 156 | |
|---|
| 157 | 4-gallon jug: 0 |
|---|
| 158 | 3-gallon jug: 0 |
|---|
| 159 | |
|---|
| 160 | 4-gallon jug: 4 |
|---|
| 161 | 3-gallon jug: 0 |
|---|
| 162 | |
|---|
| 163 | 4-gallon jug: 4 |
|---|
| 164 | 3-gallon jug: 3 |
|---|
| 165 | |
|---|
| 166 | 4-gallon jug: 0 |
|---|
| 167 | 3-gallon jug: 3 |
|---|
| 168 | |
|---|
| 169 | 4-gallon jug: 3 |
|---|
| 170 | 3-gallon jug: 0 |
|---|
| 171 | |
|---|
| 172 | 4-gallon jug: 3 |
|---|
| 173 | 3-gallon jug: 3 |
|---|
| 174 | |
|---|
| 175 | 4-gallon jug: 4 |
|---|
| 176 | 3-gallon jug: 2 |
|---|
| 177 | |
|---|
| 178 | 4-gallon jug: 0 |
|---|
| 179 | 3-gallon jug: 2 |
|---|
| 180 | |
|---|
| 181 | solution length: 8 |
|---|
| 182 | number of state transitions: 12 |
|---|
| 183 | ratio solution length / state transitions: 0.666667 |
|---|
| 184 | minimum branching degree: 1 |
|---|
| 185 | average branching degree: 2 |
|---|
| 186 | maximum branching degree: 3 |
|---|
| 187 | time: 0.00 |
|---|
| 188 | |
|---|
| 189 | Path = [(0,0),(4,0),(4,3),(0,3),(3,0),(3,3),(4,2),(0,2)], |
|---|
| 190 | Initial = (0,0) ? |
|---|
| 191 | |
|---|
| 192 | yes |
|---|
| 193 | |
|---|
| 194 | |
|---|
| 195 | % salt puzzle using breadth first search |
|---|
| 196 | |
|---|
| 197 | | ?- performance::init, salt(100, 500, 200)::initial_state(Initial), breadth_first(6)::solve(salt(100, 500, 200), Initial, Path), salt(100, 500, 200)::print_path(Path), performance::report. |
|---|
| 198 | |
|---|
| 199 | (0, 0, 0) all_empty |
|---|
| 200 | (0, 500, 0) fill(m1) |
|---|
| 201 | (0, 300, 200) transfer(m1, m2) |
|---|
| 202 | (0, 300, 0) empty(m2) |
|---|
| 203 | (0, 100, 200) transfer(m1, m2) |
|---|
| 204 | (100, 0, 200) transfer(m1, acc) |
|---|
| 205 | solution length: 6 |
|---|
| 206 | state transitions (including previous solutions): 405 |
|---|
| 207 | ratio solution length / state transitions: 0.0148148 |
|---|
| 208 | minimum branching degree: 1 |
|---|
| 209 | average branching degree: 4.06863 |
|---|
| 210 | maximum branching degree: 6 |
|---|
| 211 | time: 0.03 |
|---|
| 212 | Initial = (0, 0, 0, all_empty), |
|---|
| 213 | Path = [ (0, 0, 0, all_empty), (0, 500, 0, fill(m1)), (0, 300, 200, transfer(m1, m2)), (0, 300, 0, empty(m2)), (0, 100, 200, transfer(m1, m2)), (100, 0, 200, transfer(..., ...))] . |
|---|
| 214 | |
|---|
| 215 | yes |
|---|
| 216 | |
|---|
| 217 | |
|---|
| 218 | | ?- performance::init, salt(200, 250, 550)::initial_state(Initial), breadth_first(7)::solve(salt(200, 250, 550), Initial, Path), salt(200, 250, 550)::print_path(Path), performance::report. |
|---|
| 219 | |
|---|
| 220 | (0, 0, 0) all_empty |
|---|
| 221 | (0, 250, 0) fill(m1) |
|---|
| 222 | (0, 0, 250) transfer(m1, m2) |
|---|
| 223 | (0, 250, 250) fill(m1) |
|---|
| 224 | (0, 0, 500) transfer(m1, m2) |
|---|
| 225 | (0, 250, 500) fill(m1) |
|---|
| 226 | (0, 200, 550) transfer(m1, m2) |
|---|
| 227 | (200, 0, 550) transfer(m1, acc) |
|---|
| 228 | solution length: 8 |
|---|
| 229 | state transitions (including previous solutions): 2475 |
|---|
| 230 | ratio solution length / state transitions: 0.00323232 |
|---|
| 231 | minimum branching degree: 1 |
|---|
| 232 | average branching degree: 4.21042 |
|---|
| 233 | maximum branching degree: 6 |
|---|
| 234 | time: 0.29 |
|---|
| 235 | Initial = (0, 0, 0, all_empty), |
|---|
| 236 | Path = [ (0, 0, 0, all_empty), (0, 250, 0, fill(m1)), (0, 0, 250, transfer(m1, m2)), (0, 250, 250, fill(m1)), (0, 0, 500, transfer(m1, m2)), (0, 250, 500, fill(...)), (0, 200, ..., ...), (200, ..., ...)] . |
|---|
| 237 | |
|---|
| 238 | yes |
|---|
| 239 | |
|---|
| 240 | |
|---|
| 241 | | ?- performance::init, salt(100, 250, 550)::initial_state(Initial), breadth_first(11)::solve(salt(100, 250, 550), Initial, Path), salt(100, 250, 550)::print_path(Path), performance::report. |
|---|
| 242 | |
|---|
| 243 | (0, 0, 0) all_empty |
|---|
| 244 | (0, 0, 550) fill(m2) |
|---|
| 245 | (0, 250, 300) transfer(m2, m1) |
|---|
| 246 | (0, 0, 300) empty(m1) |
|---|
| 247 | (0, 250, 50) transfer(m2, m1) |
|---|
| 248 | (50, 250, 0) transfer(m2, acc) |
|---|
| 249 | (50, 0, 0) empty(m1) |
|---|
| 250 | (50, 0, 550) fill(m2) |
|---|
| 251 | (50, 250, 300) transfer(m2, m1) |
|---|
| 252 | (50, 0, 300) empty(m1) |
|---|
| 253 | (50, 250, 50) transfer(m2, m1) |
|---|
| 254 | (100, 250, 0) transfer(m2, acc) |
|---|
| 255 | solution length: 12 |
|---|
| 256 | state transitions (including previous solutions): 189914 |
|---|
| 257 | ratio solution length / state transitions: 6.31865e-05 |
|---|
| 258 | minimum branching degree: 1 |
|---|
| 259 | average branching degree: 4.47592 |
|---|
| 260 | maximum branching degree: 6 |
|---|
| 261 | time: 94.44 |
|---|
| 262 | Initial = (0, 0, 0, all_empty), |
|---|
| 263 | Path = [ (0, 0, 0, all_empty), (0, 0, 550, fill(m2)), (0, 250, 300, transfer(m2, m1)), (0, 0, 300, empty(m1)), (0, 250, 50, transfer(m2, m1)), (50, 250, 0, transfer(..., ...)), (50, 0, ..., ...), (50, ..., ...), (..., ...)|...] . |
|---|
| 264 | |
|---|
| 265 | yes |
|---|
| 266 | |
|---|
| 267 | |
|---|
| 268 | % eight puzzle solved using a hill-climbing strategy |
|---|
| 269 | |
|---|
| 270 | | ?- performance::init, eight_puzzle::initial_state(five_steps, Initial), hill_climbing(25)::solve(eight_puzzle, Initial, Path, Cost), eight_puzzle::print_path(Path), performance::report. |
|---|
| 271 | |
|---|
| 272 | 283 |
|---|
| 273 | 164 |
|---|
| 274 | 7 5 |
|---|
| 275 | |
|---|
| 276 | 283 |
|---|
| 277 | 1 4 |
|---|
| 278 | 765 |
|---|
| 279 | |
|---|
| 280 | 2 3 |
|---|
| 281 | 184 |
|---|
| 282 | 765 |
|---|
| 283 | |
|---|
| 284 | 23 |
|---|
| 285 | 184 |
|---|
| 286 | 765 |
|---|
| 287 | |
|---|
| 288 | 123 |
|---|
| 289 | 84 |
|---|
| 290 | 765 |
|---|
| 291 | |
|---|
| 292 | 123 |
|---|
| 293 | 8 4 |
|---|
| 294 | 765 |
|---|
| 295 | solution length: 6 |
|---|
| 296 | number of state transitions: 15 |
|---|
| 297 | ratio solution length / state transitions: 0.4 |
|---|
| 298 | minimum branching degree: 2 |
|---|
| 299 | average branching degree: 3.13333 |
|---|
| 300 | maximum branching degree: 4 |
|---|
| 301 | time: 0.01 |
|---|
| 302 | |
|---|
| 303 | Cost = 5, |
|---|
| 304 | Path = [[2/1,1/2,1/3,3/3,3/2,3/1,2/2,1/1,2/3],[2/2,1/2,1/3,3/3,3/2,3/1,2/1,1/1,2/3],[2/3,1/2,1/3,3/3,3/2,3/1,2/1,1/1,2/2],[1/3,1/2,2/3,3/3,3/2,3/1,2/1,1/1,2/2],[1/2,1/3,2/3,3/3,3/2,3/1,2/1,1/1,2/2],[2/2,1/3,2/3,3/3,3/2,3/1,2/1,1/1,1/2]], |
|---|
| 305 | Initial = [2/1,1/2,1/3,3/3,3/2,3/1,2/2,1/1,2/3] ? |
|---|
| 306 | |
|---|
| 307 | yes |
|---|
| 308 | |
|---|
| 309 | |
|---|
| 310 | % eight puzzle solved using a best-first strategy |
|---|
| 311 | |
|---|
| 312 | | ?- performance::init, eight_puzzle::initial_state(five_steps, Initial), best_first(25)::solve(eight_puzzle, Initial, Path, Cost), eight_puzzle::print_path(Path), performance::report. |
|---|
| 313 | |
|---|
| 314 | 283 |
|---|
| 315 | 164 |
|---|
| 316 | 7 5 |
|---|
| 317 | |
|---|
| 318 | 283 |
|---|
| 319 | 1 4 |
|---|
| 320 | 765 |
|---|
| 321 | |
|---|
| 322 | 2 3 |
|---|
| 323 | 184 |
|---|
| 324 | 765 |
|---|
| 325 | |
|---|
| 326 | 23 |
|---|
| 327 | 184 |
|---|
| 328 | 765 |
|---|
| 329 | |
|---|
| 330 | 123 |
|---|
| 331 | 84 |
|---|
| 332 | 765 |
|---|
| 333 | |
|---|
| 334 | 123 |
|---|
| 335 | 8 4 |
|---|
| 336 | 765 |
|---|
| 337 | solution length: 6 |
|---|
| 338 | number of state transitions: 15 |
|---|
| 339 | ratio solution length / state transitions: 0.4 |
|---|
| 340 | minimum branching degree: 2 |
|---|
| 341 | average branching degree: 3.13333 |
|---|
| 342 | maximum branching degree: 4 |
|---|
| 343 | time: 0.02 |
|---|
| 344 | |
|---|
| 345 | Cost = 5, |
|---|
| 346 | Path = [[2/1,1/2,1/3,3/3,3/2,3/1,2/2,1/1,2/3],[2/2,1/2,1/3,3/3,3/2,3/1,2/1,1/1,2/3],[2/3,1/2,1/3,3/3,3/2,3/1,2/1,1/1,2/2],[1/3,1/2,2/3,3/3,3/2,3/1,2/1,1/1,2/2],[1/2,1/3,2/3,3/3,3/2,3/1,2/1,1/1,2/2],[2/2,1/3,2/3,3/3,3/2,3/1,2/1,1/1,1/2]], |
|---|
| 347 | Initial = [2/1,1/2,1/3,3/3,3/2,3/1,2/2,1/1,2/3] ? |
|---|
| 348 | |
|---|
| 349 | yes |
|---|
| 350 | |
|---|
| 351 | |
|---|
| 352 | % turn off performance monitor |
|---|
| 353 | |
|---|
| 354 | | ?- performance::stop. |
|---|
