Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 11733 was 11732, checked in by gkronber, 9 years ago

#2283: refactoring and bug fixes

File size: 2.4 KB
RevLine 
[11690]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;
[11730]13    private readonly Queue<Sequence> bfsQueue = new Queue<Sequence>();
[11727]14    private readonly IProblem problem;
[11690]15
[11727]16    public ExhaustiveBreadthFirstSearch(IProblem problem, int maxLen) {
17      this.problem = problem;
[11708]18      this.maxLen = maxLen;
[11690]19    }
20
[11727]21    public void Run(int maxIterations) {
[11690]22      double bestQuality = double.MinValue;
[11730]23      bfsQueue.Enqueue(new Sequence(problem.Grammar.SentenceSymbol));
[11690]24      var sentences = GenerateLanguage(problem.Grammar);
25      var sentenceEnumerator = sentences.GetEnumerator();
26      for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
[11730]27        var sentence = sentenceEnumerator.Current.ToString();
[11732]28        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
[11690]29        RaiseSolutionEvaluated(sentence, quality);
30
31        if (quality > bestQuality) {
32          bestQuality = quality;
33          RaiseFoundNewBestSolution(sentence, quality);
34        }
35      }
36    }
37
38    // create sentences lazily
[11730]39    private IEnumerable<Sequence> GenerateLanguage(IGrammar grammar) {
[11690]40      while (bfsQueue.Any()) {
41        var phrase = bfsQueue.Dequeue();
42
[11730]43        char nt = phrase.FirstNonTerminal;
[11727]44        int ntIdx;
[11730]45
[11690]46        var alts = grammar.GetAlternatives(nt);
47        foreach (var alt in alts) {
[11730]48          var newPhrase = new Sequence(phrase);
49          newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
50          if (newPhrase.IsTerminal && newPhrase.Length <= maxLen) {
[11690]51            yield return newPhrase;
52          } else if (grammar.MinPhraseLength(newPhrase) <= maxLen) {
53            bfsQueue.Enqueue(newPhrase);
54          }
55        }
56      }
57    }
58
59
60    private void RaiseSolutionEvaluated(string sentence, double quality) {
61      var handler = SolutionEvaluated;
62      if (handler != null) handler(sentence, quality);
63    }
64    private void RaiseFoundNewBestSolution(string sentence, double quality) {
65      var handler = FoundNewBestSolution;
66      if (handler != null) handler(sentence, quality);
67    }
68  }
69}
Note: See TracBrowser for help on using the repository browser.