Searching algorithms in AI

[nbro]

I had already implemented BFS and DFS, even though currently they were removed temporarily from this project, since the graph data structure was also removed (because I'd to fix a few things with it), but I would like to add also other algorithms like:

• Uniform-cost search (also called cheapest-first search)

  • This is a variant of the famous Dijkstra's algorithm, where instead of starting with a queue full of nodes, it starts only with one item, and inserts new items as they are discovered. This can avoid some "decrease-key" operations.

  • Dijkstra's algorithm finds the shortest path between a source node and all nodes in a graph, whereas UCS only finds the shortest path between a source and a destination node.

• Depth-limited search

  • http://www.cs.colostate.edu/~anderson/cs440/index.html/doku.php?id=notes:week2b

• Bidirectional search

• Iterative-deepening (depth-first) search

• Best-first search

  These algorithms are usually used in path finding in combinatorial search. There's also a particular version of best-first search, i.e. a greedy version, where paths that are predicted to be closer are chosen first.

• Beam search

• A* (not a greedy version of a best-first search)

  • A (A* without admissible heuristics)

• IDA* (or iterative-deepening A*)

• Alpha-Beta pruning

Local search

• Hill climbing

• 2-opt, 2.5-opt, 3-opt, Lin–Kernighan, etc.

Interesting articles

• Iterative deepening vs depth-first search

Possibly useful resources

• Chapter 3.5 of Russell and Norvig.
• Slides of prof. Gambardella

[nbro]

Many of these algorithms need a graph to run on. Currently, I do not have a good implementation of the graph data structure.

Questions

• Should I wait to implement these algorithms until I have a robust and flexible graph data structure? In any case, I don't want them to be tightly coupled with the implementation of the graph data structure, but I would like they to be quite flexible and applicable in the most important cases and implementations, if possible.

• Should I use an external library to run these implementations on?

• Should I implement these algorithms by simply representing graphs using Python dictionaries?

• How could I implement these algorithms so that they are as much flexible as possible? Contracts must be defined anyway..!!

[nbro]

The issue above does not make sense to be opened.

This issue tracker should be used to report

• issues regarding existing code, or
• possible improvements of existing code

This issue tracker should not be used to report:

• possible future features which have nothing to do with the existing code, or
• report issues of code that is no more part of this project