3 ms·
Instead of randomized hill-climbing (genetic programming's search algo) why not try a little A*?
by reader5000 14y ago
Instead of randomized hill-climbing (genetic programming's search algo) why not try a little A*?
- sunir 14y agoHow would you envision that working? What is the estimated distance function?
- DasIch 14y agoThe "distance" of a regular expression could be the specifity (think CSS) or the size of the language described by the regular expression (with some adjustments to account for repetition as a* being infinite is probably not what is intended.) The real problem is that the space of possible solutions is very large, so you will have to do that lazily, which would make an implementation in a lot of languages rather annoying. I'd also expect this algorithm to be biased towards regular expressions that are more specific than the user intended them to be, especially for example sets that are small or not very diverse.
- __alexs 14y agoIs a* more or less infinite than .*?
- krallja 14y agohttp://en.wikipedia.org/wiki/A*_search_algorithm http://en.wikipedia.org/wiki/A*_search_algorithm
- __alexs 14y agohttp://en.wikipedia.org/wiki/Aleph_number http://en.wikipedia.org/wiki/Aleph_number
- DasIch 14y agoI intended `a` to mean `a` repeated zero or more times, meaning that `a` defines a language of infinite size as there are an infinite number of strings that match that grammar.
- songgao 14y agoThe searching space is too large - there are too many combinations to search for. Genetic Programming makes it faster to get a good solution. The solution might not be the optimal one, but it's good enough :-)