先月、組み合わせ爆発を数えるおねえさんが話題になりました。
http://d.hatena.ne.jp/nowokay/20120911#1347338066
結びになっている、「おねえさんに教えてあげたい・・・」をこっちにも教えてもらいたかったので、いろいろ調べてみました。
とりあえず、格子のグラフを作る必要があるっぽいので、まずはそのグラフの生成から。
こんな感じのグラフが作成されます。
ここで、左上を始点、右下を終点として、始点から近い順に頂点に番号を振って、幅優先で辺を生成してるところがあとで大切になります。
ネタバレしておくと、この、グラフでの経路の数え上げ問題は、クヌース先生の「The Art of Computer Programming Volume 4, Fascicle 1」の7.1.4二分決定図の章の演習問題225として載っています。
- 作者: Donald E. Knuth,和田英一
- 出版社/メーカー: アスキー・メディアワークス
- 発売日: 2011/05/20
- メディア: 大型本
- 購入: 2人 クリック: 17回
- この商品を含むブログ (14件) を見る
解答みてもよくわからんのですけど。simpathで検索すると、他の人の解説が出てくるので、それを参考にします。
目次
『フカシギの数え方』 おねえさんといっしょにみんなも25万年数えよう
おねえさんを組み合わせ爆発から救う:格子グラフを生成する
おねえさんを組み合わせ爆発から救う:2分決定木を作る
おねえさんを組み合わせ爆発から救う:無駄を省いてBDDを作る
おねえさんを組み合わせ爆発から救う:ZDDがおねえさんを救う
おねえさんを組み合わせ爆発から救う:完結編おねえさんは星になった
とりあえず、格子グラフ生成プログラムのソース
package simpath; import java.awt.BasicStroke; import java.awt.Color; import java.awt.Graphics; import java.awt.Graphics2D; import java.awt.image.BufferedImage; import java.io.IOException; import java.util.ArrayList; import java.util.Collections; import java.util.LinkedHashMap; import java.util.List; import java.util.Map; import javax.swing.ImageIcon; import javax.swing.JFrame; import javax.swing.JLabel; public class CreateLattice { /** * ノード */ public static class LatticeNode{ int x; int y; int num; public LatticeNode(int x, int y, int num) { this.x = x; this.y = y; this.num = num; } } /** * エッジ */ public static class LatticeEdge{ LatticeNode from; LatticeNode to; public LatticeEdge(LatticeNode from, LatticeNode to) { this.from = from; this.to = to; } @Override public String toString() { return String.format("%d:%d", from.num, to.num); } } public static void main(String[] args) throws IOException{ List<LatticeEdge> edges = new ArrayList<>(); Map<Integer, LatticeNode> nodeMap = new LinkedHashMap<>(); generateGraph(3, nodeMap, edges); //描画 BufferedImage img = new BufferedImage(300, 300, BufferedImage.TYPE_INT_RGB); Graphics g = img.getGraphics(); g.setColor(Color.WHITE); g.fillRect(0, 0, 300, 300); g.setColor(Color.BLACK); int gap = 80;int offset = 15; //エッジ描画 ((Graphics2D)g).setStroke(new BasicStroke(1, BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND, 1, new float[]{2, 4}, 0)); for(LatticeEdge re : edges){ g.drawLine(re.from.x * gap + offset, re.from.y * gap + offset, re.to.x * gap + offset, re.to. y * gap + offset); g.drawString(re.toString(), (re.from.x + re.to. x) * gap / 2 + offset, (re.from.y + re.to.y) * gap / 2 + offset); } //ノード描画 ((Graphics2D)g).setStroke(new BasicStroke(1)); for(LatticeNode nd : nodeMap.values()){ int x = nd.x * gap + offset - 10; int y = nd.y * gap + offset - 10; g.setColor(Color.WHITE); g.fillOval(x, y, 20, 20); g.setColor(Color.BLACK); g.drawOval(x, y, 20, 20); g.drawString(nd.num + "", x + 7, y + 14); } g.dispose(); //保存 //ImageIO.write(img, "png", new File("c:/Users/naoki/Desktop/lattice.png")); //表示 JFrame jf = new JFrame("lattice"); jf.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); JLabel l = new JLabel(new ImageIcon(img)); jf.add(l); jf.setSize(400, 350); jf.setVisible(true); } static void generateGraph(int size, Map<Integer, LatticeNode> nodeMap, List<LatticeEdge> edges) { LatticeNode root = new LatticeNode(0, 0, 1); nodeMap.put(0, root); List<LatticeNode> tempNodes = Collections.singletonList(root); int counter = root.num; while(!tempNodes.isEmpty()){ List<LatticeNode> nextNodes = new ArrayList<>(); int maxCount = counter; for(LatticeNode rn : tempNodes){ if(rn.x + 1 < size){ //横へ maxCount = getNode(size, rn, rn.x + 1, rn.y, nodeMap, nextNodes, edges, maxCount); } if(rn.y + 1 < size){ //下へ maxCount = getNode(size, rn, rn.x, rn.y + 1, nodeMap, nextNodes, edges, maxCount); } } counter = maxCount; tempNodes = nextNodes; } } static int getNode(int size, LatticeNode rn, int x, int y, Map<Integer, LatticeNode> nodeMap, List<LatticeNode> nextNodes, List<LatticeEdge> edges, int counter){ int idx = x + y * size; LatticeNode nn = nodeMap.get(idx); if(nn == null){ nn = new LatticeNode(x, y, counter + 1); nodeMap.put(idx, nn); nextNodes.add(nn); } edges.add(new LatticeEdge(rn, nn)); return nn.num; } }