qiao/PathFinding.js — pull request #25 by jpcanepa (2013-04-25 02:01:08+00:00)
Title: Added support for weighted A*

# Bounded relaxation for A*

## Motivation
I found this project to be so

1. unbelievably cool,
1. well-coded, and
1. right up my alley

that I couldn't resist the urge to contribute.

## What I did
I implemented the support for adding a weight *e* (e >= 1) to be applied to the heuristic, in order to allow the algorithm to consider paths that are suboptimal, but never by more than (1+e) times the actual optimal value, speeding up the search. If e=1 (default value) the behavior is the standard, optimal A* under that heuristic. For details, see [the entry on Wikipedia](http://en.wikipedia.org/wiki/A*_search_algorithm#Bounded_relaxation) about A*, under "bounded relaxation".

## Demo support
I tried to use the jquery-ui spinner widget, but since the visual part of the repo does not include the whole jqueri-ui thing, and given that the spinner was introduced in version 1.9, it was kind of a mess. I used a simple textbox instead and if the input cannot be converted to an int, then e=1 is used instead. I left it with the class "spinner" (to set its weight in style.css) to hint at that possible, future change.

## Tests
I didn't add any tests, though, because I wasn't sure how to phrase it correctly. Probably the correct thing is to test that with e > 1 the algorithm runs faster for specially crafted cases.