(57)【要約】【目的】ＴＳＰに代表される複雑な組合せ問題を解くのに必要とされる順列を公正に多数生成することを目的とする。ロジスティック写像、同相変換量子化及びその逆変換、モード演算の繰り返しをルックアップテーブル化する。【構成】順列の初期値を擬似乱数により与え、ルックアップテーブルとモード演算により公平に多数の順列を直接に高速に生成する。取得された一連の順列は擬似乱数の初期値に固有である。完全な再現性が保証されている。【選択図】　　　　図１
2004145835.tif 000002
【特許請求の範囲】
【請求項１】
初期値を順列Ｙｔ，ｉｔ’（ｔ＝０，ｔ’＝０，ｉ＝０，１，２，・・・，２ｎ，ｎは量子化分解能）の組で与えること、第１の調整項α＝０．２５または０．７５を加えて同相変換逆変換して内部状態ｘｔ，ｉｔ’を求めること、ロジスティック写像によりｘｔ，ｉｔ’＋１を求めること、
2004145835.tif 000005
フィードバック値を求めること、モード演算の第２の調整項βがβ＝ｍ（０≦ｍ≦２ｎ−１）ｉｆ｛（ｔ’＋１）ｍｏｄ　ｎ｝＝０またはβ＝０　ｉｆ　ｏｔｈｅｒｓという条件を満たすことにより順列を取得することを特長とする順列取得方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
ディジタルコンピュータが困難としている課題にＴＳＰ（ｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎ　ｐｒｏｂｌｅｍ，巡回セールスマン問題）がある。いわゆる複雑な組合せ問題といわれるものである。線形計画法を含む複雑な組合せ問題を効率よく解いていくためには、順列が高速、しかも公平に生成される必要がある。
【０００２】
１本の順列の生成時間と距離計算の時間がほぼ同じになるとき、ディジタルコンピュータはＴＳＰを最も効率よく解いていく。従来、順列の生成に長い時間がかかり、距離計算は高速にできた。本案は順列の高速生成を可能にする方法に関する。
【０００３】
ディジタルコンピュータの並列分散処理が複雑な組合せ問題に対して有効となるのは、順列の生成が極めて軽い負担で分散して可能となったときである。並列計算における仕事の分配が原理的に解決されている場合である。
【０００４】
【従来の技術】
ディジタルコンピュータで複雑な組合せ問題を取り扱うときには、順列と組合せを公平で大量に、しかも高速に生成できることが必要である。通常、算術乱数から順列も組合せも取得される。算術乱数は長い周期であることがわかっている。周期から順列や組合せを公平に取得することは難しい。
【０００５】
この欠点を克服したのは、ロジスティック写像が生成する擬似乱数Ｙｔ，１である。ロジスティック写像を同相変換量子化することによって得られるタイムシリーズは、周期にはいるまでは、すぐれた確率分布をもつ擬似乱数を生成する。その擬似乱数Ｙｔ，１（量子化分解能ｎ＝１）から組合せを取得することは容易である。一方、順列の取得は、重なりのない整数列を取得しなければならないから、重なったデータを捨てることをしなければならず、取得の効率が悪い。
【０００６】
【発明が解決しようとする課題】
ディジタルコンピュータは計算機械ではあるが、論理処理に比べると、数値計算処理には精度が限られ、しかも計算には時間がかかる。計算しないでいい手法の発見が求められる。本案は計算問題として説明されるが、繰り返しの計算をテーブル化することにより、順列の高速生成を実現する。
【０００７】
ロジスティック写像の計算には、初期値を決めて計算する。同相変換量子化を介して写像を計算するとき、調整項α＝０．２５または０．７５を加えておくと、多周期が取り出されることは知られている。初期値を無理数の内部状態ｘ０で与えるかわりに、同相変換量子化した量子（整数）Ｙｔ，ｉｔ’で与えてもよい。
【０００８】
１組の順列は、例えば０〜１５の順列は（３，８，６，１５，０，１１，５，７，１４，１２，１０，２，１，４，９，１３）のように重なりのない整数列であらわされる。２進数であらわせば、重なりのない４ビットコードで０〜１５の順列はあらわされる。Ｙｔ，ｉｔ’のｉは０〜１５の順番をあらわす。すなわち、初期値をＹ０，００＝３、Ｙ０，１０＝８、Ｙ０，２０＝６、・・・、Ｙ０，１５０＝１３と与えることを意味する。
【０００９】
０〜１５の順列の例は、量子化分解能ｎ＝４が対応している。Ｙｔ，ｉｔ’にさらに量子化分解能ｎをＹｔ，ｉｔ’，ｎと付しておかねばならぬが、符号があまりにも複雑となるので省略される。ｔは離散時間ｔ＝０，１，２，・・・であり、ｔ’は周期内の離散時間ｔ’＝０，１，２，・・・である。
【００１０】
【課題を解決するための手段】
初期値Ｙｔ，ｉｔ’を１回処理するプロセスを図１のブロック図で示す。ブロック▲１▼は初期値Ｙｔ，ｉｔ’である。はじめに与えられる初期値はＹ０，ｉ０、ｎ＝４のとき、Ｙ０．００、Ｙ０，１０、・・・、Ｙ０，１５０である。
【００１１】
ブロック図▲２▼は同相変換逆変換である。そのとき、Ｙｔ，ｉｔ’と第１の調整項α＝０．２５または０．７５を付加する。ｘｔ，ｉｔ’は無理数の内部状態である。
【００１２】
ブロック▲３▼はロジスティック写像の計算で、ワンステップあとの内部状態ｘｔ，ｉｔ’＋１が求まる。ブロック▲４▼はその同相変換量子化である。ブロック▲２▼Ｙｔ，ｉｔ’へフィード
2004145835.tif 000003
ロック▲６▼の条件文を満足する整数ｍである。整数ｍは０≦ｍ≦２ｎ−１である。ｍの値によって内部周期の長さが決められる。たとえば、ｎ＝４のとき、ｍ＝１５としたとき最大の内部周期の長さが得られ、その長さは２６４である。
【００１３】
図１の繰り返し計算は順列ｉ、ｎ＝４のときｉ＝０〜１５のすべてについて計算され、一連の順列Ｙｔ，ｉｔ’＋１が求まる。２６４本の順列が取り出されたあとは、ｔをｔ＋１にかえ、あらためて擬似乱数を用い、新たな初期値Ｙｔ＋１，ｉｔ’を与える。
【００１４】
【作用】
ブロック▲２▼、▲３▼、▲４▼の計算は、入力Ｙｔ，ｉｔ’が順列であり、重なりのない整数である。量子化分解能ｎが決まれば、その数は決定される。繰り返しの計算はテーブル化しておくことができる。ｎ＝４の場合の入出力の関係（Ｙｔ，４−Ｙｔ＋１，４）を表１に示す。
【００１５】
【表１】
2004145835.tif 000004
【００１６】
表１は、数値計算、ブロック▲２▼▲３▼▲４▼を実行することなく、ルックアップテーブルで逐次、次の状態が決定できることを意味している。ｍｏｄ演算▲５▼▲６▼は条件文に従った論理演算と等価であるから、順列の生成を数値計算なしで実行できる。
【００１７】
【実施例】
１６都市のＴＳＰは挑戦すべき技術の課題である。量子化分解能ｎ＝４はこの課題に相当する。ｎ＝４でｍ＝１５のとき内部周期の最大値は２６４である。擬似乱数Ｙｔ，１で１組の初期値の順列Ｙ０，ｉ０を与えると、２６４本の０〜１５の順列が得られる。離散時間ｔを１つずつ増加するたびに、新たな初期値Ｙｔ，ｉｔ’を擬似乱数Ｙｔ，１で生成する。ｔ＝２２１（＝約１００万）まで繰り返すと、生成される順列の本数は２６，４００万本（２．６４×１０８）となる。１６都市のＴＳＰの最短距離を求めるには、まだ十分ではない。１６！＝２．０９×１０１３通りもあるからである。
【００１８】
１６都市の右回りの最短距離と、同じ地図上の左回りの最短距離が等しくなったときに、１６都市のＴＳＰが解けたとすると、すべての順列２．０９×１０１３通りを十分越すだけの順列生成が必要になる。
【００１９】
擬似乱数Ｙｔ，１は、５２ビットの１つの初期値から生成され、ｔ＝２２１まで順列生成を行うと、２．６４×１０８本の０〜１５の順列が生成できる。擬似乱数Ｙｔ，１の初期値は２５２＝１０１６通りを与えることができる。この初期値を１０５通り、１０６ヶのｃｐｕにそれぞれ独立に与えるとすると、合計して１０１３通りの順列を並列に生成できる。距離計算はｃｐｕにとって軽い計算であるから、右回りの最短距離と左回りの最短距離が出力されるまで、順列の生成を繰り返すことができるようになる。
【００２０】
表１は０〜１５の順列を、フラクタルのルールに従って混合する仕方を示している。一方、２つのモード演算▲５▼▲６▼は内部的に周期に達したら、ジャンプをして状態をシフトするルールを与えている。
【００２１】
【発明の効果】
ディジタルコンピュータが苦手とする数値演算の繰り返しをテーブル化することにより、データの検索（ルックアップテーブル）とモード演算で大量の順列生成を高速に可能にし、複雑な組合せ問題を今日のディジタルコンピュータで解くことができるようにした。
【００２２】
擬似乱数Ｙｔ，１で初期値の順列を与える手法は１例であるが、浮動小数点６４ビット倍精度、有効数字５２ビットで計算した擬似乱数Ｙｔ，１は２０００万点は周期に入らないことが保証されている。異なる擬似乱数Ｙｔ，１の初期値から取得した順列は、その初期値に固有であり、生成の再現性は保証されている。
【図面の簡単な説明】
【図１】直接順列取得のフローチャートである。
【図１】
2004145835.tif 000006