お気づきの点や感想要望などなんでもOK!
ただただ感服です。いろいろお答えいただきありがとうございます。 「同じ出力の素子は作らない」と 「次の素子を考えるときは前の素子より両方とも子が小さいことはない」 というものだけでは、深さ11でだめになりました。 その後、0f+0f,33+33,55+55は必ず使うという大胆な仮定をおいて 素子数12まで探索しましたが、解は見つかりませんでした。 直感的にはnot素子を使うのは不利なような気がしてたので… プログラム、参考にさせていただきます。
高橋さん、としひでさん、こんばんは。deepgreenです。 いやぁ、まいりました。高橋さんの結果をみてこれ以上やる気がなくなりました。 素晴らしい結果です。ソースの方を参考にさせていただきます。
としひでさん、deepgreenさん、こんばんは。 「3.最小段数(5段)の全加算器のうち素子数最小のものを示せ。」 の答えは反復深化を使って素子数12個という結果を得ました。 deepgreenさんも参加してきたのでつい熱くなってしまいました。 そのおかげで意外に早く結果が出たことは、良きライバルの存在 は素晴らしいことを証明するものでもあります。(感謝!感謝!) さて、としひでさんから「素子数11くらいで計算不能に陥った」という 報告があったので最初から反復深化を採用したのですが、としひでさん が枝刈りに使ったという「子の大小関係に関するもの(*)」と「同じ出力の 素子を作らない(*)」という枝刈り以外にあと3つの枝刈りを使いました。 1.下限値による枝刈り 2.同じ出力の素子を作らない(*) 3.子の大小関係ルールを守り重複探索を防止(*) 4.逆解きで最大限界段数のテーブルを作る 5.得策段数で次の要素を追加する ひとつひとつ説明すると長くなるし文章を考えるのが面倒なので私の プログラムを直接見て下さい、、、(なんて、不詳してすみません。) プログラムは下のURLに置きました。どうしても理解不能な点は 気軽に質問して下さい。 枝刈り法として見送ったアイデアは対称性を考慮することです。 3つの外部入力から最終的に出力される2つの出力の算式には完全な対称性 があるのでそれを考慮すれば探索量を1/3とか1/6とかに縮小出来ると 思ったのですが、それを検討する前に答えが出てしまいました。 私の見つけた解は全部で9種類ですがその1例は下図です。対称性の検討 とかが不十分なので全解が9通りという訳ではないと思います。 [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++(実行速度で最適化)
私の方法はボトムアップ方式ですね トップダウン方式だと再帰的に関数を呼び出して解けるのですね ということに今気がつきました トップダウンで一度やってみます 最小素子問題では、同一視できる解がたくさん出てきたので、 なんとかそれらを省く方法がわかればよいのですが、そこがなかなか
すみませんでした。c’の式は誤りです。 とりあえず、わたしのやった方法を記します。 deepgreen氏のように、8ビットで場合分けを同時に扱い、 配列a[0]=A,a[1]=B,a[2]=Cとおいて、 各素子の2つの子(の素子)を持つデータ構造でやってみました。 枝刈りは、子の大小関係に関するものと、同じ出力の素子を作らないことくらいです。 あとはfor文をいっぱい重ねて(笑) よくよく見てみると、下の私の書き込みの23素子というのは20素子の誤りでした。 手元にプログラムや出力結果がないので、内容があやふやになってすみません。 最小素子数の問題が解けたとき、 xorが2回出てきているきれいな形には驚きました。
としひで さん、はじめまして。 deepgreenです。 ちょっとやってみましたが、最小段数(5)での最小要素を求める問題は、やはり、 要素数が11の途中で中断しました。うまい枝刈りがみつからないとこれ以上 すすめません。難問ですね。もう少し、ねばってみます。 とりあえず、3つの部分に分解して求めた結果、16個(G1=12,G2=4)の解 が見つかりました。もちろん、最適解はこれ以下なので12−15あたりに なりそうな感じです。 ========(最小段数の解:要素数16)================================= 全加算器の入出力パターン ・入力パターン A 00001111 0x0f B 00110011 0x33 C 01010101 0x55 (下からの繰り上がり) ・出力パターン G1 01101001 0x69 G2 00010111 0x17 (繰り上げ) Nand素子の表現 69(d7,be): 入力(d7,be)/出力(69)のNand回路 ** : 外部入力(A,B,C) @ : 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) ----------------------------------------------------
失礼しました。(例えば下のURL)のURLを書くのを忘れました。http://www.cs.shinshu-u.ac.jp/Lecture/LogicCirc/chap9/chap9.html
としひで さん、こんばんは。 随分と悩まさせていただきました。問題を理解するのにひと苦労し、ようやく 理解したものの私には問2の最少素子数が9個という結果をどうしても出せま せんでした。 c’=(x・y・!c)+(x・!y・c)+(!x・y・c) この算式は間違っていませんか。? x,y,cが総て真の場合この算式は偽になりますが、全加算器をキーワード にWebを検索して調べたところ(例えば下のURL)、c’は真になるようです。 こう変更することでやっと問2の最少素子数9個を出せました。(疲れた!) さてやっと問3ですが、素子数11くらいで計算不能に陥ってしまった とのこと。幅優先探索を使ってメモリ不足になったと理解してよろしい でしょうか。ようやく出発点に立ったので私は反復深化で検討してみます。 ちなみに、問2は反復深化を使って186秒(266MHz)で解が出ましたが、 さすがに問3はご指摘のとおり難解で1時間待っても解が出ません。 巧い枝刈りが有りそうな予感だけはあります。考えてみます。
論理回路の組み合わせ探索で困っています。問題は、 2入力nand素子のみを用いて 1.最小段数の全加算器を示せ。 2.最小素子数の全加算器を示せ。 3.最小段数の全加算器のうち素子数最小のものを示せ。 全加算器とは、入力(x,y,c)に対して出力(z,c’)が z=x xor y xor c c’=(x・y・!c)+(x・!y・c)+(!x・y・c) を満たすものです。・はand、+はor、!はnotを示します。 1.は最小素子数9で段数6 2.は最小段数5 と求まったのですが、 3.は探索空間が広すぎて、素子数11くらいで計算不能に陥ってしまいました。 因みに2.で見つけたパターンは23の素子で構成できました。 なにかよい枝刈り方法はないでしょうか。 初かきこみで質問になってしまってすみません。 (内容はすでに提出期限のすぎたレポートからの引用です)
アッタジュニア、みなさん、クリアしたのですか?私は、ステージ3までしか行けません! むずかしー! これからも、このコーナーに、メッセージいれていいですか? クリアがんばります!!