A* algorithm

table of contents

• description
  • external dependencies
  • questions & answers
• HOWTO run the algorithm
  • docker
  • Sbt
• sample files
• packaging docker image
• build
• tests

description

This repository contains A* algorithm implementation in Scala which is my resolution for the given recruitment task. A* algorithm implementation follows this pseudocode.

The program is written in pure functional style (except of console io effect control in main function...). Program is referentially transparent and this was satisfied because of:

• immutability - no vars or setters
• pure functions - for the given input they return always the same result
• recursion | @tailrecursion - thanks to that algorithms/functions are strict, safe and self explaining

remark!

Diagonal moves within the maze (next to horizontal|vertical ones) are acceptable since such constraint wasn't pointed out within the task definition. However, additional docker image kczulko/intel-a-star:0.2 was released which satisfies such constraint of vertical|horizontal moves only. Though it was not tested, it seems to work really well.

external dependencies

Project contains two external dependencies and one plugin used for docker packaging.

External dependencies:

1. Scalaz - An extension to the core Scala library for functional programming. Across this project were used following structures from Scalaz library:
   • State monad - more information can be found here
   • ListT monad transformer - more information about MT can be found here
   • sequenceS | sequenceU - in general it allows to change the type structure of F[G[A]] into G[F[A]]
   • Disjunction (-\/ or \/-)
2. scalatest - testing library for Scala

questions and answers

1. How to build and run your code.

   Answers are here and here

2. The heuristic that you used.

   Euclidean distance was used as heuristic function. Within the code it is implemented at Cell::distanceTo function.

3. What you used for tie-breakers when you had two nodes in your priority queue with the same priority.

   Priority queue wasn't used in this algorithm. TraversableOnce[+A]::minBy function on Set structure was used instead.

4. What are the advantages of having a more sophisticated heuristic? Are there any disadvantages?

   Question is what does it mean more sophisticated heuristic? When heuristic is consistent then always the shortest one path will be found. In the opposite case (when the heuristic function is not monotonic) algorithm gets a little bit more complicated (we need to take under consideration nodes from closed set as well and update their metrics).

5. How do you know that a heuristic is admissable? How do you know that a heuristic is monotonic?

   Heuristic is admissable when it never overestimates the actual minimal cost of reaching the goal. Heuristic is monotonic when following equation is satisfied (heuristic satisfies consistency rule):

   h(x) <= d(x,y) + h(y)

   , where:

   • h(x) - heuristic value for point x
   • h(y) - heuristic value for point y
   • d(x,y) - real distance between x and y

   Since Euclidean distance was used as heuristic, this equation in fact satisfies triangle inequality between x, y and goal.

6. Does the way you break ties matter?

   In case of this heuristic it doesn't.

howto run the algorithm

docker

There are prepared two versions of the docker image:

1. 0.1 - supports moves for both diagonal and vertical|horizontal directions
2. 0.2 - supports moves only for vertical|horizontal direction (it has not been tested)

In order to run algorithm against provided samples, please execute:

$ docker run kczulko/intel-a-star:0.1 9.txt

Sample files from the task definition tarball were packaged to docker container so it is possible to choose one of them as the last argument (as it was done in the example).

Execution example:

$ docker run kczulko/intel-a-star:0.1 4.txt

Input maze:

_ s _ _ _
x x x x _
_ x x x _
_ _ g _ _

==========

Maze with path from 's' to 'g' (indicated by '*' character):

_ s * * _
x x x x *
_ x x x *
_ _ g * _

==========

Path found (rows and cols are indexed from 0):

List(Cell(0,1,s), Cell(0,2,_), Cell(0,3,_), Cell(1,4,_), Cell(2,4,_), Cell(3,3,_), Cell(3,2,g))

==========

Expanded locations amount: 9

sbt

1. Install sbt
2. Go to project's root directory.
3. Execute sbt 'run ./src/universal/10.txt' to run sample no. 10

sample files

Sample files used to execute an algorithm are located under src/universal directory.

build

$ sbt clean compile

docker packaging

1. Run sbt docker:publishLocal
2. Tag recently created image, e.g. docker tag intel-a-star:0.1 <username>/intel-a-star:0.1
3. Publish tagged image to docker hub, e.g.

$ docker login <username>
$ docker push <username>/intel-a-star:0.1

tests

$ sbt test