Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveBreadthFirstSearch.cs @ 11690

Last change on this file since 11690 was 11690, checked in by gkronber, 8 years ago

#2283: added exhaustive BFS and DFS

File size: 2.3 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5using HeuristicLab.Problems.GrammaticalOptimization;
6
7namespace HeuristicLab.Algorithms.GrammaticalOptimization {
8  public class ExhaustiveBreadthFirstSearch {
9    public event Action<string, double> FoundNewBestSolution;
10    public event Action<string, double> SolutionEvaluated;
11
12    private readonly int maxLen;
13    private readonly Queue<string> bfsQueue = new Queue<string>();
14
15    public ExhaustiveBreadthFirstSearch(int maxLen) {
16      this.maxLen = maxLen;     
17    }
18
19    public void Run(IProblem problem, int maxIterations) {
20      double bestQuality = double.MinValue;
21      bfsQueue.Enqueue(problem.Grammar.SentenceSymbol.ToString());
22      var sentences = GenerateLanguage(problem.Grammar);
23      var sentenceEnumerator = sentences.GetEnumerator();
24      for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
25        var sentence = sentenceEnumerator.Current;
26        var quality = problem.Evaluate(sentence);
27        RaiseSolutionEvaluated(sentence, quality);
28
29        if (quality > bestQuality) {
30          bestQuality = quality;
31          RaiseFoundNewBestSolution(sentence, quality);
32        }
33      }
34    }
35
36    // create sentences lazily
37    private IEnumerable<string> GenerateLanguage(IGrammar grammar) {
38      while (bfsQueue.Any()) {
39        var phrase = bfsQueue.Dequeue();
40
41        var nt = phrase.First(grammar.IsNonTerminal);
42        var ntIdx = phrase.IndexOf(nt); // TODO perf
43        var alts = grammar.GetAlternatives(nt);
44        foreach (var alt in alts) {
45          var newPhrase = phrase.Remove(ntIdx, 1).Insert(ntIdx, alt);
46          if (newPhrase.All(grammar.IsTerminal)) {
47            yield return newPhrase;
48          } else if (grammar.MinPhraseLength(newPhrase) <= maxLen) {
49            bfsQueue.Enqueue(newPhrase);
50          }
51        }
52      }
53    }
54
55
56    private void RaiseSolutionEvaluated(string sentence, double quality) {
57      var handler = SolutionEvaluated;
58      if (handler != null) handler(sentence, quality);
59    }
60    private void RaiseFoundNewBestSolution(string sentence, double quality) {
61      var handler = FoundNewBestSolution;
62      if (handler != null) handler(sentence, quality);
63    }
64  }
65}
Note: See TracBrowser for help on using the repository browser.