I wrote a library for finding paths on arbitrary graphs, and I would like to share it with you .
An example of use on a huge graph:
To play around with the demo, you can here
The library uses a little-known version of the A * search, which is called NBA * . This is a bidirectional search, with relaxed requirements for the heuristic function, and a very aggressive termination criterion. Despite its little-known algorithm, the algorithm has an excellent speed of convergence to the optimal solution.
The description of the various variants of A * has already been found on the hub several times. I really liked this is , so I will not repeat this article. Under the cut I will explain in more detail why the library works quickly and how the demo was done.
An amusing find was shared today by the user fj333 with Reddit . Analyzing Qualcomm Technologies' proprietary code for Android, which appeared one year ago, he found that an unknown programmer decided to use the sorting with a bubble in production-code in order to find ... maximum in the array.
You can view the original file by under the link to Github or under the cut, and any owner of the device with Qualcomm Snapdragon 200 MSM8610 running Android can estimate it in operation.
As anyone who is familiar with sorting algorithms knows, sorting by a bubble is an educational algorithm, and in industrial code it is usually not used due to its inefficiency ; The matter is that in the worst and average cases it has the complexity O (n2) , besides its capacitive complexity in this case - O (n) . Whom it was not convinced - to use the sorting by a bubble does not recommend even Barack Obama .
And this is all not taking into account the fact that to search for the maximum would be enough and a simple search.
Basilio Noris PhD from the Federal Polytechnic School of Lausanne created a remarkable program that is perfect for the demo of some tasks that solve the machine learning algorithms (classification, clustering, and regression using the various methods). In one program are captured the libraries, algorithms and code patches that could be found. Unlike Matlab, here GUI runs fast in the interactive mode, thus it comes out very well.
MLDemos 0.3.2 for Windows (minimum requirements: XP SP3)
MLDemos 0.3.2 for Mac (minimum requirements: Snow Leopard)
MLDemos 0.1.3 for Linux 32bit (deb) (build for: Ubuntu 10.04)