• Showing Page History #52471

← 先頭のページに戻る

デカルト言語による選択と決断

1. デカルト言語の選択と決断とは

ここで説明したい選択と決断とは、 デカルト言語のプログラミング機能に、選択と決断のための機能を付けることです。

まず、われわれ人間が物事を選択するときのことを、考えてみてください。

いろいろな選択肢を思い浮かべると思います。 あれやこれや、可能性のある幾通りものパターンについて、それぞれの損得を考えます。 簡単に短時間で、「えいやっ」と決めることもあれば、熟慮を重ねて考え抜いて決めることもあるでしょう。

今日の昼は何をどこで食べるか?夕飯は何にするか?

買い物に言ってくるか?外食にするか?

その前に銀行から預金を引き出してくるか?手持ちのお金で足りるか?

いろいろな選択肢を思い浮かべ、それぞれを組み合わせて、もっとも良いと思う決断をするでしょう。

デカルト言語にもこのような選択と決断のような動作を行わせる初歩的な機能の最初の一歩として、まず、順列と組み合わせの機能を付けることにします。

2. 順列と組み合わせ

順列(permutation)とは、n個の異なるものから、r個を取り出して並べることを 「n個から、r個とった順列」といい、その並べ方を nPr で表します。

たとえば、(a b c)の3つの中から2つ選ぶ順列は以下です。


(a b)
(a c)
(b a)
(b c)
(c a)
(c b)

6通りあります。

順列は並べ方の順も重要です。並べ方の順が異なるものは、異なる順列として扱います。

並べ方がいくつあるかは、以下のように計算できます。


    nPr = n!/(n-r)!

先に示した3つから2つ選ぶ順列は、次のように計算されます。


      3!/(3-2)! = 6

組み合わせ(combination)とは、n個の異なるものから、r個を取り出すことを 「n個から、r個とった組み合わせ」といい、その並べ方を nCr で表します。 順列との違いは、取り出す要素の順番は考えないことです。 単純にn個のものから、r個を取り出すだけです。

たとえば、(a b c)の3つの中から2つ選ぶ組み合わせは以下です。


(a b)
(a c)
(b c)

3通りあります。

組み合わせがいくつあるかは、以下のように計算できます。


    nCr=n!/(n-r)!/r!

先に示した3つから2つ選ぶ順列は、次のように計算されます。


      3!/(3-2)!/2! = 3

このような順列と組み合わせですが、コンピュータで扱うには厄介です。

まず、プログラムで作ってみると以外に難しいです。 ちょっと考えると簡単なように思えなくもありませんが、実際に組んでみると 大変だとわかると思います。頭の体操として考えてみてください。

そこで、プログラムするときにわざわざ毎回作らなくてもよいように、デカルト言語では、ライブラリモジュールとして組み込みました。

組み込んだ順列、組み合わせの述語には、2種類あります。

1種類目は、すべての順列や組み合わせをもれなく生成するものです。

2種類目は、広くサンプリング的に、順列や組み合わせを生成するものです。

3. デカルト言語ですべての順列や組み合わせの生成

3.1 デカルト言語ですべての順列の生成

すべての順列の組み合わせを生成する述語として、pemutationAll述語を使います。

それは、次に示すような形式です。

generatorモジュールに属するため、インクルード?<include generator>してから使用します。


::generator <permutationAll [RESULT_VAR] (VAR LIST [LEN]) PRED ... >

	LISTの要素からLEN数を選んだ順列をVAR変数に設定し、
	引数のPRED述語を呼び出します。
	すべての順列が順に実行されます。
	RESULT_VARには、PREDの第一引数を集めたものが結果として
	返されます。


たとえば、(a b c)の3つの要素のあるリストから2つ選び出す順列をプリントアウトするプログラムを作ってみましょう。


? <include generator>;

? ::generator <permutationAll (#i (a b c) 2)
                <print #i>>;

#i変数に、選ばれた順列の結果が設定されます。それをprint述語で表示します。 結果は次のようになります。


(a b)
(a c)
(b a)
(b c)
(c a)
(c b)
result --
        ::generator <permutationAll (Undef6 (a b c) 2) <print Undef6>>
-- true

前項で示した順列の組み合わせと同じですね。

3.2 デカルト言語ですべての組み合わせの生成

すべての組み合わせを生成する述語として、combinationAll述語を使います。

それは、次に示すような形式です。

generatorモジュールに属するため、インクルード?<include generator>してから使用します。


::generator <combinationAll [RESULT_VAR] (VAR LIST [LEN]) PRED ... >

	LISTの要素からLEN数を選んだ組み合わせをVAR変数に設定し、
	引数のPRED述語を呼び出します。
	すべての組み合わせが順に実行されます。
	RESULT_VARには、PREDの第一引数を集めたものが結果として
	返されます。


たとえば、(a b c)の3つの要素のあるリストから2つ選び出す組み合わせをプリントアウトするプログラムを作ってみましょう。


?<include generator>;

? ::generator <combinationAll (#i (a b c) 2) 
                          <print #i>>;

#i変数に、選ばれた組み合わせの結果が設定されます。それをprint述語で表示します。 結果は次のようになります。


(a b)
(a c)
(b c)
result --
        ::generator <combinationAll (Undef6 (a b c) 2) <print Undef6>>
-- true

3.3 アナグラム(プログラム例)

組み合わせのための述語、permutationAll述語を使って、アナグラムのプログラムを作ってみましょう。

ここでのアナグラムは、入力した単語の文字を並べ替える組み合わせをすべて出力する単純なものです。


? <include generator>;

<anagram #s>
        ::sys <char #slist #s>
        <print '----------------'>
        ::generator <permutationAll #r (#x #slist)
                ::sys <concat #str #x>
                <print #str>
        >
        ;

? ::sys <getline #l> <anagram #l>;

anagramuのプログラムについて説明しましょう。

まず、char述語はsysモジュールの組み込み述語です。引数#sを1文字ずつに分解して、 #slistにリスト形式にして返します。

たとえば、"おいしい"と入力すると、char述語が(お い し い)というリストを作成します。

concat述語は、やはりsysモジュールの組み込み述語です。 上記プログラムでは、permutationAll述語により、リストも文字の順番を入れ替えられた順列が、 引数#xに入力され#strに連結された文字列を返します。

たとえば、リスト(い い し お)を、concat述語が文字列"いいしお"と連結します。

最後の行にあるgetline述語もsysモジュールの組み込み述語で、キーボードから1行文字列を入力すると、その結果を#l引数に設定します。

アナグラムのプログラムをanagram1と保存して実行した結果を以下に示します。

このプログラムを起動したら、入力待ちになるので、何か文字列を入力してみてください。

以下では、起動後に"おいしい"と入力しています。


$ descartes  anagram1
おいしい
----------------
おいしい
おいいし
おしいい
おしいい
おいいし
おいしい
いおしい
いおいし
いしおい
いしいお
いいおし
いいしお
しおいい
しおいい
しいおい
しいいお
しいおい
しいいお
いおいし
いおしい
いいおし
いいしお
いしおい
いしいお
result --
        ::sys <getline おいしい>
        <anagram おいしい>
-- true

なお、もしも、このプログラムの実行で日本語表示が文字化けする場合には、文字コードが誤っている可能性があります。

descarteの引数に-uか-sかあるいは-eを付けて試してみてください。

どれかの引数で正しく実行されるようになるはずです。


$ descartes -u anagram1
または
$ descartes -s anagram1
または
$ descartes -e anagram1

4. デカルト言語で広くサンプリング的に、順列や組み合わせを生成

4.1 順列と組み合わせの問題点

順列や組み合わせのためのpermutationAllやcombinationAll述語は、 漏れなくすべての可能性をチェックするにはとても便利な機能です。

すべての可能性をチェックし、それらの評価の結果もっとも良い結果として選ばれるのは、 まさに最良の結果です。

しかし、順列も組み合わせも、どちらにも要素数が増えたときに大きな問題が発生します。

それは、要素数が増えると順列、組み合わせの数がとんでもなく大きく大量になってしまうということです。

たとえば、100個の要素から30個選んで並べる順列は、

100P30 = 7.7911e+57

57桁の数になってしまいます。

100個の要素から30個選ぶ組み合わせは、

100C30 = 2.9372e+25

25桁の数になってしまいます。

これだけ大量の数を処理するためには、最新のスーパーコンピュータを使ったとしても とても長い計算時間が必要になってしまい、現実的な時間の範囲では終わりません。

このような大量の順列、組み合わせがある場合に最良でなくても、より良い解を効率よく探すことができないでしょうか?

そのための述語として、デカルト言語では、permutation, combination述語を用意してあります。

名前は、permutationAll, combinationAllとは似ていて最後にAllが付いていないだけですが、使い方がまったく異なるものです。

次項から、詳細を説明します。

4.2 permutation述語

permutation述語は、指定された要素の順列をランダムにひとつだけ返します。

指定された要素のリストから、指定された数を取り出して並べ替えた順列を返します。


::generator permutation <VAR LIST [LEN]>

	LISTの要素からLEN数を選んだ順列をVAR変数に設定します。
	設定される順列は、ランダムに選ばれます。

順列の総数は、要素の数が多くなると、すべての順列を調べるにはあまりに多くなりすぎて手に負えなくなります。

要素の数が2桁くらいでも、もう処理しきれなくなるでしょう。 ましてや、1000要素や100万要素とかでは、どうしようもなくなります。

permutation述語では、ランダムにひとつだけの順列を返しますから、必要な数だけ、これを繰り返して実行することができます。

この述語の用途は、すべての順列の中からサンプリング的に広い範囲で順列を取り出し処理することです。

ランダムに順列を取り出しますので、繰り返し実行することにより広い範囲の順列を取り出すことができるのです。

それは、限られた処理回数で、十分と思われる順列を組み合わせて実行することができることを期待しています。

もちろん、順列のすべての範囲を調べた結果得られる最良の結果は得られないかもしれません。 しかし、調べた範囲の中でより良い結果を得ることができるようになるでしょう。

ちょっと、人間が行動するときに、いろいろな選択肢の組み合わせがある場合について考えてみましょう。

できればすべての組み合わせについて十分に吟味を重ねて検討して、結果を出せば最も良い結果が得られるとしても 往々にして限られた時間の中で決断を迫られることが多いでしょう。

そのような場合には、頭の中でざっと思い浮かぶ選択肢について検討して、決断することになるでしょう。

ぐずぐず考えても、目の前ですぐに決断しなければならないのに、最善の結論が1年後に出ても手遅れです。

そのような場合でも、よりよい結果が得られる方法として、この述語を実装しました。

順列の対象の性質がわかっていれば、いろいろと考案されている探索法を使い、もっと効率よく解が得られます。 しかし、どのような順列の対象であっても、このpermutation述語を使えば、ほどほどに良い結果が得られるのではないかと考えます。

4.3 combination述語

combination述語は、指定された要素の組み合わせをランダムにひとつだけ返します。

指定された要素のリストから、指定された数を取り出した組み合わせを返します。


::generator <combination VAR LIST [LEN]>

	LISTの要素からLEN数を選んだ組み合わせをVAR変数に設定します。
	設定される組み合わせは、ランダムに選ばれます。


組み合わせも、順列と同じです。 要素の数が大きくなると、まともに全部の組み合わせを試すことはできなくなります。

そこで、この述語により、広い範囲を限られた処理回数で、十分と思われる組み合わせで実行することができることを期待しています。

4.4 巡回セールスマン問題(プログラム例)

巡回セールスマン問題とは、以下のような問題です。


いろいろな地点にバラバラに存在しているお得意先を、1人のセールスマンが順に訪れます。

このセールスマンが移動するお得意様の地点の順序の中で、移動する距離の総和が最小の場合を求めるのが、巡回セールスマン問題です。

ちょっと考えると簡単なようですが、訪れる順序は結局全部の順列の中で最小のものを求めなけばなりません。 そのため、地点の数が増えるとあっというまに、調べなければならない順列が増えてしまい、結果が出るまで膨大な時間がかかってしまうのです。

4.4.1 全ルートのチェック

まずは、巡回セールスマン問題で全ルートをもれなくチェックするプログラムを以下に示しましょう。

巡回する地点は、いきなり沢山にはしないで、とりあえず7つとします。


? <include generator>;

<makedata #r #n>
        <for #r (#i #n)
                <nop (#x #y)>
                <letf #rad =<letf _ 2* ::sys <PI _>/#n*#i>>
                <letf #x = ::sys <cos _ #rad>>
                <letf #y = ::sys <sin _ #rad>>
        >
        ;

<len 0.0 ((_ _))>;

<len #l ((#x1 #y1) (#x2 #y2) : #r)>
        <letf #ll = (#x2 - #x1)*(#x2 - #x1) + (#y2 - #y1)*(#y2 - #y1)>
        <letf #l2 = ::sys <sqrt _ #ll>>
        <len #l3 ((#x2 #y2) : #r)>
        <letf #l = #l2+#l3>
        ;


<TraveringSalesman #r>
        <setVar maxlen 1000000>
        ::generator <permutationAll (#i #r)
                <maxlen #max>
                <len #l #i>
                [
                 <comparef #l < #max>
                        <print>
                        <printf "Length : " <%_"g" #l> <\_n>>
                        <print "   " #i>
                        <setVar maxlen #l>
                ]
        >
        ;

? <makedata #r1 7> ::generator <permutation #r #r1> <TraveringSalesman #r>;

最初のincludeは、permutation述語を使うために、generatorモジュールをインクルードしています。

次に定義されているmakedata述語では、巡回するための地点を作成しています。

ばらばらにランダムに地点を設定しても良いのですが、ここでは、円の周囲に巡回するための地点を設定してみましょう。

makedeta述語の引数の#rには、巡回するための地点の(x,y)座標のリストが生成されて返されます。

地点のリストは次に示すような形態です。


   ((1 0) (0.62349 0.781831) (-0.222521 0.974928) (-0.900969 0.433884) 
            (-0.900969 -0.433884) (-0.222521 -0.974928) (0.62349 -0.781831))

makedeta述語の引数の第2引数である#n引数には、生成する地点の数を指定します。

このmakedata述語の処理の中でfor述語により、円周上を等分します。 forの中で使われているnop述語は、ひとつの地点のx、y座標を返すために使っています。

次にlen述語は、第2引数に地点のリストを設定し、第1引数に地点間の距離を返します。

len述語は2つの定義で構成されています。それぞれ、地点リストの違いによるパターンマッチで選択されます。

最初の<len 0.0 ((_ _))>;は、地点のリストの最後のみを現します。最後のポイントなので距離は0なので、第1引数には0.0を返します。 このパターンは、再帰的にlen述語を実行したときの最後の処理を定義しています。

2つめのlen述語の定義は、地点間の距離を最初の2地点で計算し、のこりの地点間の距離は、再帰的に自分を呼び出すことによって行っています。

TraveringSalesman述語は、順に地点間の順列を生成して、地点間の距離を計算し、そのときの距離の短い順列を表示します。

以下に実行結果を示します。


$ descartes salesman1.pl

Length : 7.68048
    ((-0.222521 -0.974928) (-0.222521 0.974928) (0.62349 0.781831) (-0.900969 0.
433884) (-0.900969 -0.433884) (0.62349 -0.781831) (1 0))

Length : 7.37078
    ((-0.222521 -0.974928) (-0.222521 0.974928) (0.62349 0.781831) (1 0) (0.6234
9 -0.781831) (-0.900969 0.433884) (-0.900969 -0.433884))

Length : 6.98459
    ((-0.222521 -0.974928) (-0.222521 0.974928) (0.62349 0.781831) (1 0) (0.6234
9 -0.781831) (-0.900969 -0.433884) (-0.900969 0.433884))

   ... 長くなるので、途中を省略 ...


Length : 5.2066
    ((-0.222521 0.974928) (-0.900969 0.433884) (-0.900969 -0.433884) (-0.222521
-0.974928) (0.62349 -0.781831) (1 0) (0.62349 0.781831))

これが最も短い距離とその順列
Length : 5.2066      
    ((0.62349 -0.781831) (-0.222521 -0.974928) (-0.900969 -0.433884) (-0.900969
0.433884) (-0.222521 0.974928) (0.62349 0.781831) (1 0))

result --
        <makedata ((1 0) (0.62349 0.781831) (-0.222521 0.974928) (-0.900969 0.43
3884) (-0.900969 -0.433884) (-0.222521 -0.974928) (0.62349 -0.781831)) 7>
        ::generator <permutation ((-0.222521 -0.974928) (-0.222521 0.974928) (0.
62349 0.781831) (-0.900969 0.433884) (-0.900969 -0.433884) (0.62349 -0.781831) (
1 0)) ((1 0) (0.62349 0.781831) (-0.222521 0.974928) (-0.900969 0.433884) (-0.90
0969 -0.433884) (-0.222521 -0.974928) (0.62349 -0.781831))>
        <TraveringSalesman ((-0.222521 -0.974928) (-0.222521 0.974928) (0.62349
0.781831) (-0.900969 0.433884) (-0.900969 -0.433884) (0.62349 -0.781831) (1 0))>

-- true

4.4.2 広くサンプリング的にチェック

つづく