A tree search library for combinatorial optimization problems

Question

I noticed that somewhat of the “hard” combinatorial problems that I am facing can be applied to some type of tree search, such as alpha-beta pruning, or ray search, or a similar algorithm. However, programming them is like re-encoding the same things, and it's also pretty easy to make mistakes. It seems to me that there should be a library that implements these algorithms, and all I need to write is

• solution coding i.e. how to get a more specific solution from an incomplete solution. This will give a tree / graph structure.
• Given a partial decision, how to get the maximum / minimum cost and, possibly, evaluate the cost.
• Original solution / partial solution.
• Perhaps some solution to verify.

Sorry, I did not give any specific code, but I think I explained the problem. If I can write code for the functions described above, shouldn't I easily run multiple tree / graph search algorithms? Is there a user-friendly library / framework that easily supports this? I would like it to be in Python or C / C ++, but it would be interesting to hear any suggestions.

Edit: To be more precise, I'm talking about tree search information algorithms.

Answer 1

Fuego is an open source search engine (unlike the alpha beta tree) that can target full-featured games with two players (originally created for the target Go). This may be even more general than that.

http://fuego.sourceforge.net/

Edit: I just found out that it also has an alpha beta search engine. Here is a recent article: http://webdocs.cs.ualberta.ca/~mmueller/ps/fuego-TCIAIG.pdf

Answer 2

Boost has a Boost Graph Libary (BGL) . The Boost Graph library user guide has an example of a Knight route problem using implicit graphs.

Answer 3

Expressing a problem without specifying specific steps is a kind of declarative programming .

You are talking about "partial solutions." Does this mean that the problems you are considering have overlapping subtasks? If so, then it sounds as if you are asking for a way to general dynamic programming . All that really means is creating a function using successive steps, solving simpler versions of the problem, and then repeating. There are some good examples in this Mathematica article.

Have you considered Prolog ? This is not a framework, but the search algorithm, if you like, is built into the language. As a basis, you can write very general programming restrictions using something like Prolog. Python has a python constraint library , which is pretty nice - I used it in the past.

Answer 4

Quickgraph

For anyone who wants to go .Net, check out the open source QuickGraph library for all your graph / tree based processing. He neatly separates all concepts related to graphical representation, -algorithms, -mutations, and -representation. It has many extension points, so it should support most of the problems associated with graphics.

[EDIT] The set of algorithms supplied with QuickGraph does not include alpha-beta cropping or ray search at the moment, although there are 11 other methods in the search algorithm section that provide sufficient recommendations for implementing your favorite bypass algorithm, and over time I would suggest that it would support alpha beta and ray.

ad. 1 However, it satisfies your first criterion, because you can insert a delegate function in it that returns a few more specific solutions (for example, neighboring nodes) based on an incomplete solution (i.e. the Current node). This is handled by DelegateImplicitGraph (and variations) and is assumed to be memory efficient, as it prevents the simultaneous use of the entire search space in memory. ad. 2 In addition, custom delegates such as max / min / expected cost hueristics can accept algorithms (see AStarShortestPathAlgorithm ). This satisfies your second criteria.

In short, QuickGraph helps structure your problem, provides drop-in algorithms for various types of problems, and allows you to improve it by delivering new algorithms.

Answer 5

I found the Peter Norvig Python code for an informed and uninformed search on the Internet. It supports A-star search and can be used to program common problems from what I see. I wonder if it is enough enough or can be expanded to search for a ray, branch and border, etc.