ホームページへ戻る  書き込みリストへ戻る
「コンピュータ&パズル」訪問者の自由メッセージコーナー

お気づきの点や感想要望などなんでもOK!


池e:論理回路の組み合わせ探索 投稿者:としひで  投稿日:02月16日(金)07時30分49秒

ただただ感服です。いろいろお答えいただきありがとうございます。
「同じ出力の素子は作らない」と
「次の素子を考えるときは前の素子より両方とも子が小さいことはない」
というものだけでは、深さ11でだめになりました。
その後、0f+0f,33+33,55+55は必ず使うという大胆な仮定をおいて
素子数12まで探索しましたが、解は見つかりませんでした。
直感的にはnot素子を使うのは不利なような気がしてたので…
プログラム、参考にさせていただきます。


re:論理回路の組み合わせ探索  投稿者:deepgreen  投稿日:02月15日(木)23時16分16秒

高橋さん、としひでさん、こんばんは。deepgreenです。

いやぁ、まいりました。高橋さんの結果をみてこれ以上やる気がなくなりました。
素晴らしい結果です。ソースの方を参考にさせていただきます。


re:論理回路の組み合わせ探索 投稿者:高橋謙一郎  投稿日:02月15日(木)21時01分14秒

としひでさん、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++(実行速度で最適化)

../temp/nand0215.c


つづき 投稿者:としひで  投稿日:02月14日(水)14時48分58秒

私の方法はボトムアップ方式ですね
トップダウン方式だと再帰的に関数を呼び出して解けるのですね
ということに今気がつきました
トップダウンで一度やってみます

最小素子問題では、同一視できる解がたくさん出てきたので、
なんとかそれらを省く方法がわかればよいのですが、そこがなかなか


論理回路 投稿者:としひで  投稿日:02月14日(水)11時35分48秒

すみませんでした。c’の式は誤りです。
とりあえず、わたしのやった方法を記します。
deepgreen氏のように、8ビットで場合分けを同時に扱い、
配列a[0]=A,a[1]=B,a[2]=Cとおいて、
各素子の2つの子(の素子)を持つデータ構造でやってみました。
枝刈りは、子の大小関係に関するものと、同じ出力の素子を作らないことくらいです。
あとはfor文をいっぱい重ねて(笑)
よくよく見てみると、下の私の書き込みの23素子というのは20素子の誤りでした。
手元にプログラムや出力結果がないので、内容があやふやになってすみません。

最小素子数の問題が解けたとき、
xorが2回出てきているきれいな形には驚きました。


re:論理回路の組み合わせ探索  投稿者:deepgreen  投稿日:02月13日(火)22時45分04秒

としひで さん、はじめまして。 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)
----------------------------------------------------


re:論理回路の組み合わせ探索 投稿者:高橋謙一郎  投稿日:02月13日(火)22時00分53秒

失礼しました。(例えば下のURL)のURLを書くのを忘れました。

http://www.cs.shinshu-u.ac.jp/Lecture/LogicCirc/chap9/chap9.html


re:論理回路の組み合わせ探索 投稿者:高橋謙一郎  投稿日:02月13日(火)21時55分53秒

としひで さん、こんばんは。

随分と悩まさせていただきました。問題を理解するのにひと苦労し、ようやく
理解したものの私には問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時間待っても解が出ません。
巧い枝刈りが有りそうな予感だけはあります。考えてみます。


はじめまして 投稿者:としひで  投稿日:02月09日(金)16時31分14秒

論理回路の組み合わせ探索で困っています。問題は、
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の素子で構成できました。
なにかよい枝刈り方法はないでしょうか。
初かきこみで質問になってしまってすみません。
(内容はすでに提出期限のすぎたレポートからの引用です)


おっはー! 投稿者:千葉 (小4)  投稿日:02月07日(水)14時49分50秒

 アッタジュニア、みなさん、クリアしたのですか?私は、ステージ3までしか行けません!
 むずかしー!
 これからも、このコーナーに、メッセージいれていいですか?
クリアがんばります!!


 ホームページへ戻る  書き込みリストへ戻る