お気づきの点や感想要望などなんでもＯＫ！
ただただ感服です。いろいろお答えいただきありがとうございます。 「同じ出力の素子は作らない」と 「次の素子を考えるときは前の素子より両方とも子が小さいことはない」 というものだけでは、深さ１１でだめになりました。 その後、0f+0f,33+33,55+55は必ず使うという大胆な仮定をおいて 素子数１２まで探索しましたが、解は見つかりませんでした。 直感的にはnot素子を使うのは不利なような気がしてたので… プログラム、参考にさせていただきます。
高橋さん、としひでさん、こんばんは。deepgreenです。 いやぁ、まいりました。高橋さんの結果をみてこれ以上やる気がなくなりました。 素晴らしい結果です。ソースの方を参考にさせていただきます。
としひでさん、deepgreenさん、こんばんは。 「３．最小段数(５段)の全加算器のうち素子数最小のものを示せ。」 の答えは反復深化を使って素子数１２個という結果を得ました。 deepgreenさんも参加してきたのでつい熱くなってしまいました。 そのおかげで意外に早く結果が出たことは、良きライバルの存在 は素晴らしいことを証明するものでもあります。(感謝！感謝！) さて、としひでさんから「素子数１１くらいで計算不能に陥った」という 報告があったので最初から反復深化を採用したのですが、としひでさん が枝刈りに使ったという「子の大小関係に関するもの(*)」と「同じ出力の 素子を作らない(*)」という枝刈り以外にあと３つの枝刈りを使いました。 １．下限値による枝刈り ２．同じ出力の素子を作らない(*) ３．子の大小関係ルールを守り重複探索を防止(*) ４．逆解きで最大限界段数のテーブルを作る ５．得策段数で次の要素を追加する ひとつひとつ説明すると長くなるし文章を考えるのが面倒なので私の プログラムを直接見て下さい、、、（なんて、不詳してすみません。） プログラムは下のＵＲＬに置きました。どうしても理解不能な点は 気軽に質問して下さい。 枝刈り法として見送ったアイデアは対称性を考慮することです。 ３つの外部入力から最終的に出力される２つの出力の算式には完全な対称性 があるのでそれを考慮すれば探索量を１／３とか１／６とかに縮小出来ると 思ったのですが、それを検討する前に答えが出てしまいました。 私の見つけた解は全部で９種類ですがその１例は下図です。対称性の検討 とかが不十分なので全解が９通りという訳ではないと思います。 [1] time = 154.450007 sec 0: 0f(0) 0: 33(0) 0: 55(0) 1: aa(1) <- 55(0), 55(0) 2: cc(1) <- 33(0), 33(0) 3: ee(1) <- 33(0), 55(0) 4: f0(1) <- 0f(0), 0f(0) 5: 1f(2) <- ee(1), f0(1) 6: 77(2) <- aa(1), cc(1) 7: 99(3) <- ee(1), 77(2) 8: e8(3) <- 1f(2), 77(2) 9: 17(4) <- ee(1), e8(3) 10: 9f(4) <- 77(2), e8(3) 11: f6(4) <- 0f(0), 99(3) 12: 69(5) <- 9f(4), f6(4) 実行環境は、K-6の266MHz 64MB VC++(実行速度で最適化)
私の方法はボトムアップ方式ですね トップダウン方式だと再帰的に関数を呼び出して解けるのですね ということに今気がつきました トップダウンで一度やってみます 最小素子問題では、同一視できる解がたくさん出てきたので、 なんとかそれらを省く方法がわかればよいのですが、そこがなかなか
すみませんでした。ｃ’の式は誤りです。 とりあえず、わたしのやった方法を記します。 deepgreen氏のように、８ビットで場合分けを同時に扱い、 配列a[0]=A,a[1]=B,a[2]=Cとおいて、 各素子の２つの子（の素子）を持つデータ構造でやってみました。 枝刈りは、子の大小関係に関するものと、同じ出力の素子を作らないことくらいです。 あとはｆｏｒ文をいっぱい重ねて（笑） よくよく見てみると、下の私の書き込みの２３素子というのは２０素子の誤りでした。 手元にプログラムや出力結果がないので、内容があやふやになってすみません。 最小素子数の問題が解けたとき、 ｘｏｒが２回出てきているきれいな形には驚きました。
としひで さん、はじめまして。 deepgreenです。 ちょっとやってみましたが、最小段数(5)での最小要素を求める問題は、やはり、 要素数が１１の途中で中断しました。うまい枝刈りがみつからないとこれ以上 すすめません。難問ですね。もう少し、ねばってみます。 とりあえず、３つの部分に分解して求めた結果、１６個（G1=12,G2=4)の解 が見つかりました。もちろん、最適解はこれ以下なので１２−１５あたりに なりそうな感じです。 ========（最小段数の解：要素数１６）================================= 全加算器の入出力パターン ・入力パターン Ａ ００００１１１１ ０ｘ０ｆ Ｂ ００１１００１１ ０ｘ３３ Ｃ ０１０１０１０１ ０ｘ５５ （下からの繰り上がり） ・出力パターン Ｇ１ ０１１０１００１ ０ｘ６９ Ｇ２ ０００１０１１１ ０ｘ１７ （繰り上げ） Ｎａｎｄ素子の表現 ６９（ｄ７，ｂｅ）： 入力（ｄ７，ｂｅ）／出力（６９）のＮａｎｄ回路 ** : 外部入力（Ａ，Ｂ，Ｃ） @ : subtree内で共通の要素がある # : 他のsubtreeに共通の要素がある ------------------------------------------------------ G1: 69 (d7,be) ........... 12 個 ------------------------------------------------ d7 (3c,ab) ........ 6 個 3c (f3,cf) f3 (fc,0f) fc (0f,33) **0f (0f,0f) **33 (33,33) **0f (0f,0f) cf (fc,33) @fc (0f,33) **0f (0f,0f) **33 (33,33) **33 (33,33) ab (fc,55) @fc (0f,33) **0f (0f,0f) **33 (33,33) **55 (55,55) ------------------------------------------------ be (53,cd) ........ 6 個 ----> 5 個 53 (fc,af) #fc (0f,33) **0f (0f,0f) **33 (33,33) af (fa,55) fa (0f,55) **0f (0f,0f) **55 (55,55) **55 (55,55) cd (fa,33) @fa (0f,55) **0f (0f,0f) **55 (55,55) **33 (33,33) ------------------------------------------------ G2: 17 (fc,ea) ........ 6 個 ---> 4 個 #fc (cf,33) #cf (f0,33) f0 (0f,0f) **0f (0f,0f) **0f (0f,0f) **33 (33,33) **33 (33,33) ea (3f,55) 3f (cf,f0) @cf (f0,33) @f0 (0f,0f) **0f (0f,0f) **0f (0f,0f) **33 (33,33) @f0 (0f,0f) **0f (0f,0f) **0f (0f,0f) **55 (55,55) ----------------------------------------------------
失礼しました。(例えば下のＵＲＬ)のＵＲＬを書くのを忘れました。http://www.cs.shinshu-u.ac.jp/Lecture/LogicCirc/chap9/chap9.html
としひで さん、こんばんは。 随分と悩まさせていただきました。問題を理解するのにひと苦労し、ようやく 理解したものの私には問２の最少素子数が９個という結果をどうしても出せま せんでした。 ｃ’＝（ｘ・ｙ・！ｃ）＋（ｘ・！ｙ・ｃ）＋（！ｘ・ｙ・ｃ） この算式は間違っていませんか。？ ｘ，ｙ，ｃが総て真の場合この算式は偽になりますが、全加算器をキーワード にWebを検索して調べたところ(例えば下のＵＲＬ)、ｃ’は真になるようです。 こう変更することでやっと問２の最少素子数９個を出せました。(疲れた！) さてやっと問３ですが、素子数１１くらいで計算不能に陥ってしまった とのこと。幅優先探索を使ってメモリ不足になったと理解してよろしい でしょうか。ようやく出発点に立ったので私は反復深化で検討してみます。 ちなみに、問２は反復深化を使って186秒(266MHz)で解が出ましたが、 さすがに問３はご指摘のとおり難解で1時間待っても解が出ません。 巧い枝刈りが有りそうな予感だけはあります。考えてみます。
論理回路の組み合わせ探索で困っています。問題は、 ２入力ｎａｎｄ素子のみを用いて １．最小段数の全加算器を示せ。 ２．最小素子数の全加算器を示せ。 ３．最小段数の全加算器のうち素子数最小のものを示せ。 全加算器とは、入力（ｘ，ｙ，ｃ）に対して出力（ｚ，ｃ’）が ｚ＝ｘ ｘｏｒ ｙ ｘｏｒ ｃ ｃ’＝（ｘ・ｙ・！ｃ）＋（ｘ・！ｙ・ｃ）＋（！ｘ・ｙ・ｃ） を満たすものです。・はａｎｄ、＋はｏｒ、！はｎｏｔを示します。 １．は最小素子数９で段数６ ２．は最小段数５ と求まったのですが、 ３．は探索空間が広すぎて、素子数１１くらいで計算不能に陥ってしまいました。 因みに２．で見つけたパターンは２３の素子で構成できました。 なにかよい枝刈り方法はないでしょうか。 初かきこみで質問になってしまってすみません。 （内容はすでに提出期限のすぎたレポートからの引用です）
アッタジュニア、みなさん、クリアしたのですか？私は、ステージ３までしか行けません！ むずかしー！ これからも、このコーナーに、メッセージいれていいですか？ クリアがんばります！！