はじめに
学生時代，大学食堂で最適な栄養バランスを達成するメニューの組み合わせ（献立）を見つけ出そうとしたことはないだろうか．
私にはある．
特に，自分の好きな食べ物を含むような，それでいて栄養バランスのよい献立が推薦されると素晴らしい．そんなアルゴリズムを考えたことがあるので，今回取り上げる．
github.com
なお，上に挙げているリポジトリのソースコードはserver-clientなシステムからローカルで動作可能なものに書き換えたものであるため，クラスやメソッド名がそれを前提としたものになっていることに注意してほしい．
最適な栄養バランス
「最適な献立を見つける」ということで今回コンピュータにしてほしいのは，探索である．探索とはある条件を満たす最適なパラメータの組み合わせを見つけ出すことなので，最初に取り組むべきは何をパラメータにするのかということである．
パラメータとして一番に挙げられる五大栄養素を軸とした食事バランスについては，農水省の誰もが目にしたことがあるであろう以下の図がある．
www.maff.go.jp
五大栄養素は上から「主食，副菜，主菜，牛乳/乳製品，果物」とある．直感的にはこれらに含まれる栄養素を逐次パラメータに探索すれば良さそうに思えるが，大学食堂で各食品を取り寄せパラメータを決めていくのでは埒が明かない．
幸い我が大学食堂ではこの五大栄養素をベースとした3群点数法を採用しており，しかもそれは食品ごとに予め決められていた．
これは「体の中で血や肉になる食品」を「赤」，「体の調子をよくする食品」を「緑」，「力や体温になる食品」を「黄」とするものだ．
www.univcoop.or.jp
そこで，最適な献立を見つけるためのパラメータとしてこれらを主に使用する．具体的な食品の入力データのひとつを以下に取り上げる．
{ "name":"きつねそば", "cost":216, "foodColors" : { "red":0.7, "green":0, "yellow":4.1 }, "nutrients" : { "energy" : 389, "protein" : 14.4, "lipid" : 6.7, "carbohydrate" : 68.0, "salt" : 4.0, "calcium" : 123, "vegetables" : 10 }, "layout":"1110" },
costは値段．foodColorsが3群点数法のパラメータになる．nutrientsはその他食品の情報で，実は探索で用いないパラメータも混じる．layoutは後述するアルゴリズムに使用する．
これに対する具体的な献立の評価関数の計算式は次のようなもの．正直なところメソッド名は悪い．
class FoodScoreCalculator { private double redLimit, greenLimit, yellowLimit, saltLimit, vegetablesLimit, costLimit; ... double score(SelectedFoods _selectedFoods){ return Math.pow((redLimit-_selectedFoods.foodColors.red)/redLimit, 2)+ Math.pow((greenLimit-_selectedFoods.foodColors.green)/greenLimit, 2)+ Math.pow((yellowLimit-_selectedFoods.foodColors.yellow)/yellowLimit, 2)+ Math.pow((saltLimit-_selectedFoods.nutrients.salt)/saltLimit, 2)+ Math.pow((vegetablesLimit-_selectedFoods.nutrients.vegetables)/vegetablesLimit, 2)+ 2*Math.pow((costLimit-_selectedFoods.cost)/costLimit, 2); } }
探索における組み合わせの評価関数は以上のように理想的な値との簡単な最小二乗誤差で求める．3群点数法だけでなく塩分量や含まれる野菜の量，学生なのでお値段も考慮した探索を行うようにする．塩分量は実際日本人が多くとりすぎる傾向にある栄養素で，注意が必要らしい．
因みに，昼食時に成人男性/成人女性が取らなければならない3群点数法によるスコアは以下のようなものらしい．
class BestScoreModel { double red, green, yellow; BestScoreModel(String _gender){ switch (_gender){ case FoodConst.Man: this.red = 2.0; this.green = 1.0; this.yellow = 7.0; break; case FoodConst.Woman: this.red = 2.0; this.green = 1.0; this.yellow = 4.0; break; } } }
探索の方針
ここまでくると後は探索するだけである．しかしこのままの全探索では献立としてよろしくない，例えば主菜が無く副菜だけの献立や，逆に副菜がなくご飯だけの献立が最適解として出力される恐れがある．制約条件が必要である．
そこで，これを解決するために一汁三菜を導入する．具体的には「汁物，主菜，副菜，副菜」となるような組み合わせを探す．大学食堂のメニューの数は，精々10^2に満たない．そのため，この制約の下でも全探索で間に合うレベルである．ただし，きつねそばなどは汁物と主菜と副菜を兼ねるとして定義，探索する．
一汁三菜グラフ
これを達成するため一汁三菜グラフというものを考えた．これは一汁三菜をたどるようなグラフを生成し理想的なスコアと，たどるパスのスコアの差を最小化するよう全探索するものだ．一汁三菜のレイアウトを守るために，例えば味噌汁やごはんなど，汁物と主菜を含むようなパターンだと以下の図のようなグラフで探索を行う．
一方，きつねそばのように汁物と主菜が混在しているような麺類の場合は以下のように，汁物と主菜のレベルできつねそばなど麺類を割り当てる．
パスの生成の際には同じ副菜が2度選ばれないよう注意する．
今回制作したアプリケーションでは，ユーザが入力する例えば"きつねそば"などメニューを含むような献立をユーザの入力の都度全探索し，その結果として出力するようにする．きつねそばが選ばれた場合は，麺類のレベルでカレーうどんのノードが生成されず，かつ汁物/主菜のノードも生成されないということ．簡単に言うと，副菜の組み合わせのみの全探索になる．
実装
具体的な一汁三菜グラフの実装は以下のソースコードで確認できる．ここではその一部を取り上げる．
github.com
隣接行列の生成
メニュー間のエッジはグラフ問題お馴染みの隣接行列で定義する．以下が該当箇所．
// エッジコストの登録 categorizedFoodIndexes.entrySet().stream() .filter(entry->!entry.getValue().isEmpty()) .forEach(entry->{ int key_=entry.getKey(); List<Integer> indexes_=entry.getValue(); // start - 主食，丼 if(key_>=1000){ // スタートとつなぐ indexes_.forEach(idx-> registerEdgeCosts(idx, Arrays.asList(0), 0)); } // 主食 - 汁物 else if(key_>=100 && categorizedFoodIndexes.containsKey(1000)){ indexes_.forEach(idx-> registerEdgeCosts(idx, categorizedFoodIndexes.get(1000), 0)); } // 汁物 - 主菜 else if(key_>=10 && categorizedFoodIndexes.containsKey(100)){ indexes_.forEach(idx-> registerEdgeCosts(idx, categorizedFoodIndexes.get(100), 0)); } else{ // 丼 - 副菜 if(categorizedFoodIndexes.containsKey(1110)) indexes_.forEach(idx-> registerEdgeCosts(idx, categorizedFoodIndexes.get(1110), 0)); // 主菜 - 副菜 if(categorizedFoodIndexes.containsKey(10)) indexes_.forEach(idx-> registerEdgeCosts(idx, categorizedFoodIndexes.get(10), 0)); // 副菜が2つ選択されている場合には未対応 // 副菜 - 副菜 if(categorizedFoodIndexes.containsKey(1)) { // 副菜がユーザにより選択されていたとき if(selectedSubFoodLayoutCount==1 && selectedFoodLayouts_.contains(1)) { selectedFoodParams_.stream() .filter(foodParam -> foodParam.layout == 1) .forEach(foodParam -> { registerEdgeCosts(foodParam.index + offset, indexes_, offset); registerEdgeCosts(nodeSize - 1, Arrays.asList(foodParam.index + offset), 0); }); } else { indexes_.forEach(idx -> registerEdgeCosts(idx + offset, categorizedFoodIndexes.get(1), offset)); registerEdgeCosts(nodeSize - 1, indexes_.stream().map(idx -> idx + offset).collect(Collectors.toList()), 0); } } } });
エッジコストの登録ではメニューに定義づけられていたパラメータであるLayoutに応じて，それぞれノードのつながりが隣接行列として記録されていく．
Java8のStreamsを使用しているため少し見づらいかもしれないが，簡単に言うと以下のLayoutのidごとに，状態分けを行いノードの接続を定義づけている．実装ではLayout idはint型に変換されるため最上位が0であれば4桁未満の数となる．
| メニュー | Layout id |
| 主食 | 1000 |
| 汁物 | 0100 |
| 主菜 | 0010 |
| 副菜 | 0001 |
| 丼 | 1110 |
categorizedFoodIndexesはLayout idをkey，menuのindexをvalueとするようなdictionaryになっている．ループでLayout id（key）に対応するindexのArray（value）を見て，そのLayout idが接続するにふさわしい接続先とエッジをつなぐ．例えば，いま見ているdictionaryのentryが汁物（0100）だったとき，その接続先は主食（1000）となる．探索の都合上，主食のレベルはスタートノードとつなぐ．
探索
隣接行列ができればいよいよお待ちかね？の探索である．とはいっても単純な全探索である．
定石通り，キューにエンキューされた探索ノードに対して，接続ノードがあれば順次さらにエンキューしていく．ゴールノードに到達したとき，一汁三菜を守った1つの組み合わせが選ばれているはず．その組み合わせから，最もスコアの高い組み合わせを献立として出力する．
public void init(String _gender, List<String> _selectedFoodNames, double _cost){ foodColorScoreCalculator = new FoodScoreCalculator(new BestScoreModel(_gender), _cost); initAdjacencyMatrix(_selectedFoodNames); } public List<SelectedFoods> provideMenu(){ class SearchNode{ private int index; private List<SelectedFoods> selectedMenuList; private SearchNode(int _index, List<SelectedFoods> _selectedMenuList){ this.index=_index; this.selectedMenuList = _selectedMenuList; } } List<SelectedFoods>[] nodes_ = new ArrayList[nodeSize]; Arrays.fill(nodes_, new ArrayList<>(Arrays.asList(new SelectedFoods()))); int offset_=(int)foodList.stream().filter(food -> food.layout==1).count(); Queue<SearchNode>que=new ArrayDeque<>(); que.add(new SearchNode(0, new ArrayList<>(Arrays.asList(new SelectedFoods())))); while(!que.isEmpty()){ SearchNode searchNode_=que.poll(); List<SelectedFoods> searchNodeMenuList_ = searchNode_.selectedMenuList; int nodeIndex_ = searchNode_.index; for(int x=1;x<nodeSize;++x){ if(costs[nodeIndex_][x]==1.0){ List<SelectedFoods> updatedFoodMenuList_; if(x != nodeSize-1) { final Food selectedFood_ = x > foodList.size() && x != nodeSize-1 ? foodList.get(x-offset_-1) : foodList.get(x-1); updatedFoodMenuList_ = searchNodeMenuList_.stream() .map(foodMenu -> foodMenu.clone().updateAttributes(selectedFood_)) .collect(Collectors.toList()); nodes_[x] = updatedFoodMenuList_; } // ゴールノードに到達したとき else if(x==nodeSize-1){ updatedFoodMenuList_ = searchNodeMenuList_; nodes_[x].addAll(updatedFoodMenuList_); } else continue; que.add(new SearchNode(x, updatedFoodMenuList_)); } } } return nodes_[nodeSize-1].stream() .sorted(Comparator.comparingDouble(foodColorScoreCalculator::score)) .distinct() .collect(Collectors.toList()); }
動作のようす
少し早くて見切れてしまいそうになっている．
GWは過去に書いた献立推薦のやつのリファクタリングをしていました（生存報告） pic.twitter.com/GczzcsYBSe
— やまもと (@NB29979) 2021年5月5日
入力「きつねそば」に対するオススメの献立は，「きつねそば，大学芋，フルーツヨーグルト」だそうだ．
