Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.ArtificialAnt/3.3/ArtificialAntExpressionGrammar.cs @ 3238

Last change on this file since 3238 was 3238, checked in by gkronber, 13 years ago

Implemented a solution visualizer for the artificial ant problem. #952 (Artificial Ant Problem for 3.3)

File size: 5.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22
23using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
24using System.Collections.Generic;
25using System;
26using System.Linq;
27using HeuristicLab.Core;
28namespace HeuristicLab.Problems.ArtificialAnt {
29  public class ArtificialAntExpressionGrammar : Item, ISymbolicExpressionGrammar {
30
31    private class EmptySymbol : Symbol { }
32
33    public ArtificialAntExpressionGrammar()
34      : base() {
35    }
36    #region ISymbolicExpressionGrammar Members
37
38    private EmptySymbol startSymbol = new EmptySymbol();
39    public Symbol StartSymbol {
40      get { return startSymbol; }
41    }
42
43    private static List<Symbol> allSymbols = new List<Symbol>() {
44      new IfFoodAhead(),
45      new Prog2(),
46      new Prog3(),
47      new Move(),
48      new Left(),
49      new Right()
50    };
51    private Dictionary<Type, Dictionary<int, IEnumerable<Symbol>>> allowedSymbols = new Dictionary<Type, Dictionary<int, IEnumerable<Symbol>>>() {
52      {
53        typeof(EmptySymbol),
54        new Dictionary<int, IEnumerable<Symbol>>()
55        {
56          { 0, allSymbols},
57        }
58      },      {
59        typeof(IfFoodAhead),
60        new Dictionary<int, IEnumerable<Symbol>>()
61        {
62          { 0, allSymbols},
63          { 1, allSymbols}
64        }
65      },
66      {
67        typeof(Prog2),
68        new Dictionary<int, IEnumerable<Symbol>>()
69        {
70          { 0, allSymbols},
71          { 1, allSymbols}
72        }
73      },
74      {
75        typeof(Prog3),
76        new Dictionary<int, IEnumerable<Symbol>>()
77        {
78          { 0, allSymbols},
79          { 1, allSymbols},
80          { 2, allSymbols}
81        }
82      },
83    };
84    public IEnumerable<Symbol> AllowedSymbols(Symbol parent, int argumentIndex) {
85      return allowedSymbols[parent.GetType()][argumentIndex];
86    }
87
88    private Dictionary<Type, int> minLength = new Dictionary<Type, int>() {
89      {typeof(EmptySymbol), 1},
90      {typeof(IfFoodAhead), 3},
91      {typeof(Prog2), 3},
92      {typeof(Prog3), 4},
93      {typeof(Move), 1},
94      {typeof(Left), 1},
95      {typeof(Right), 1}
96    };
97    public int MinimalExpressionLength(Symbol start) {
98      return minLength[start.GetType()];
99    }
100
101    private Dictionary<Type, int> maxLength = new Dictionary<Type, int>() {
102      {typeof(EmptySymbol), int.MaxValue},
103      {typeof(IfFoodAhead), int.MaxValue},
104      {typeof(Prog2), int.MaxValue},
105      {typeof(Prog3), int.MaxValue},
106      {typeof(Move), 1},
107      {typeof(Left), 1},
108      {typeof(Right), 1}
109    };
110    public int MaximalExpressionLength(Symbol start) {
111      return maxLength[start.GetType()];
112    }
113
114    private Dictionary<Type, int> minDepth = new Dictionary<Type, int>() {
115      {typeof(EmptySymbol), 1},
116      {typeof(IfFoodAhead), 1},
117      {typeof(Prog2), 1},
118      {typeof(Prog3), 1},
119      {typeof(Move), 0},
120      {typeof(Left), 0},
121      {typeof(Right), 0}
122    };
123    public int MinimalExpressionDepth(Symbol start) {
124      return minDepth[start.GetType()];
125    }
126
127
128    private Dictionary<Type, int> subTrees = new Dictionary<Type, int>() {
129      {typeof(EmptySymbol), 1},
130      {typeof(IfFoodAhead), 2},
131      {typeof(Prog2), 2},
132      {typeof(Prog3), 3},
133      {typeof(Move), 0},
134      {typeof(Left), 0},
135      {typeof(Right), 0}
136    };
137    public int MinSubTrees(Symbol start) {
138      return subTrees[start.GetType()];
139    }
140    public int MaxSubTrees(Symbol start) {
141      return subTrees[start.GetType()];
142    }
143
144    #endregion
145
146    #region ISymbolicExpressionGrammar Members
147
148
149    public bool IsValidExpression(SymbolicExpressionTree expression) {
150      if (expression.Root.Symbol != StartSymbol) return false;
151      return IsValidExpression(expression.Root);
152    }
153
154    #endregion
155
156    private bool IsValidExpression(SymbolicExpressionTreeNode root) {
157      if (root.SubTrees.Count < MinSubTrees(root.Symbol)) return false;
158      if (root.SubTrees.Count > MaxSubTrees(root.Symbol)) return false;
159      for (int i = 0; i < root.SubTrees.Count; i++) {
160        if (!AllowedSymbols(root.Symbol, i).Contains(root.SubTrees[i].Symbol)) return false;
161        if (!IsValidExpression(root.SubTrees[i])) return false;
162      }
163      return true;
164    }
165  }
166}
Note: See TracBrowser for help on using the repository browser.