search

cmaclell / concept_formation

Python implementations of TRESTLE, COBWEB/3, and COBWEB
MIT License
61 stars 18 forks source link

Make structure mapping faster #16

Closed cmaclell closed 8 years ago

cmaclell commented 8 years ago

The code in concept_formation.structure_mapper.compute_rewards should probably be optimized so that the calculation is faster.

Also, look at the use of the rewards.. maybe we can do some kind of dynamic programming to cache previous parts of the search.

cmaclell commented 8 years ago

Currently, we used a form of graph search where we progressively build up the structure mapping in a greedy way. I'm currently exploring an alternative that enumerates a full mapping and then progressively improves it by flipping matches using hill climbing or simulated annealing.

Results with n-queens and similar problems suggests that this later, local-search based, approach is superior often yielding search time that is invariant of problem size (i.e., constant).

eharpste commented 8 years ago

This issue is addressed by the most recent pull request #22 so I am going to close it