Google SoCシリーズ:Rubyを使用した制約計画

Gecode/RはGoogle SoCから援助を受けたRubyプロジェクトで、Ruby言語の開発者が同様にオペレーティングにおける制約計画(Constraint Programming)方法を使用できるようにすることを目的としており、プロジェクトの発起人であるAndreas Launilaは制約計画についてこのように説明している.
制約計画は、開発者がプログラムに具体的な計算方法を教えるのではなく、どのような解決策が必要かを説明する宣言的な計画モデルです.コンストレイント計画を使用すると、開発者は問題のモデルを構築し、問題ハンドラにモデルセットをコミットしようとします.問題ハンドラは、問題ドメイン内のすべての実行可能な解を取得し、モデル内の制約条件を使用して、この部分の可能な解に本当にアクセスする必要がなく、これらの解の一部を除去します.
一般的な例は数独ゲーム(Soduko)であり、制約計画によって数独問題を解決する過程は、問題ハンドラに制約ルールを記入し(例えば、各行の数字が異なる必要がある)、すべての制約条件を同時に満たす解決策を探すことである.
Andreas氏は、現実世界で制約計画を使用して問題を解決する例があるかどうかを尋ねると、
制約計画はNP難解な組合せ問題を処理するための一般的な方法であり,この場合,一般には限られた選択しか存在しないが,特定の条件に基づいて探索する必要がある.現実世界の例には、タイミングの手配、サイクルの割り当て、人員の勤務時間の設定などの問題が含まれています.
Gecode/Rは、実際にはC++制約計画関数ライブラリGecodeに基づいて構築されたRuby言語パッケージであり、Ruby言語を使用してGecodeの機能を実現する理由について、Andreasは次のように説明しています.
私にとって、コンストレイント計画は私がよく使うツールボックスで非常に役立つツールです.制約計画を使用して適切な問題タイプを処理すると、多くの時間と作業を節約できます.高速符号化実装が可能であるため、より良いアルゴリズムが存在し、実行効率が最も考慮されていない場合(または、アルゴリズムの研究および実装に要する余分な時間よりも性能の違いは無視できる)、制約計画は、問題の迅速な解決に使用することができる.
興味深い話題は、Ruby言語を使用して制約計画を定義する方法についてです.
バインドだけでなく、フロントエンドを作成することを目的としています.私はDSL(Domain Specific Language、分野特定言語)だけでなくクラスライブラリと呼んでいますが、両者の境界はあまり厳密に定義されていません.プロジェクトが間もなく始まるため、正確な文法規則はまだ定義されていません.次の簡単なコードセグメントは、プロジェクトの概略的なガイドラインを示しますが、これは必ずしもプロジェクトが最終的に使用する文法規則ではありません.コードセグメントの例は、「send+more=money」という古典的な問題を解決します.
このようにして,比較法と算術法を線形拘束を表すために用い,配列を拡張することによって特殊拘束を表すことによって分岐選択に用いた.変数は、作成時に記録する必要があります.これにより、追跡が容易になります.記号「!=」はメソッドとして定義されていないため、不等式を使用する場合の構文は他の言語とは異なります.
次に、プログラムコードの作成例を示します.

#    send+more=money  。
class SendMoreMoneyProblem < Gecode::Space
  def initialize
    #     ， 0..9   8   .
    s,e,n,d,m,o,r,y = letters = IntVar.array(8, 0..9)
    #       .
    constrain equation_row(s, e, n, d) +
                  equation_row(m, o, r, e) ==
                  equation_row(m, o, n, e, y)
    constrain s.not_equal(0) #      "s != 0"             != .
    constrain m.not_equal(0)
    letters.all_distinct
    #                   .
    letters.branch_using(:variable => :min_size, :value => :min)
  end

private
  #             。          ，
  #                10         。
  #   ：x,y,z  100*x + 10*y + z .
  def equation_row(*variables)
    variables.inject(0){ |result, variable| variable + 10*result }
  end
end
#              
p SendMoreMoneyProblem.new.solutions(:first)

詳細については、ウィキペディアの「send+more=money」の見出しに関する記事を参照してください.
Ruby言語を使用してビジネスロジックまたはデータを定義する場合、内部DSLを使用して、より簡潔で読み取り可能なコードを記述することがよくあります.Andreasはコードの可能なスタイルについてこう説明しています.
もう1つのコードをDSLのように見える方法は、符号化においてクラス宣言をスキップすることである.この方法は単一のサンプルの問題を迅速に処理する際にはより優れているが,他のRubyコードと協働して制約計画を使用することを妨げる.
DSLメソッドを使用するコードの例を次に示します.

find_first_solution_to define_problem do |p|
  #     ， 0..9   8   。
  s,e,n,d,m,o,r,y = letters = p.create_int_vars(8, 0..9)
  #     。
  p.add 1000*s + 100*e + 10*n + d +
           1000*m + 100*o + 10*r + e ==
           10000*m + 1000*o + 100*n + 10*e + y
  p.add s.not_equal(0)
  p.add m.not_equal(0)
  p.add all_distinct(letters)
  #        。
  p.branch_on letters, :variable => :min_size, :value => :min
end

Gecode/Rはローカルクラスライブラリベースのバインディング実装であるため,潜在的なボトルネック問題がある.Andreasはプロジェクトの発展に影響を与える問題ではないと自信を持っています.
Gecodeでは一般的な制約の伝播機構が実現されているので,これらの制約の実際の伝播過程はここで完了した.ユーザーがカスタム伝播メカニズムを設定する場合、C言語とRuby言語を切り替える必要がありますが、パフォーマンスに問題があるかどうかはまだ分かりません.しかし、Gecodの設計は外部とうまくやり取りでき、Java言語とうまく連携できるので、Gecode/Rがローカルクラスライブラリでバインドを実現することがボトルネックになると言われたら驚くに違いありません.
Gecode/RはRubyForge上に構築されたオープンソースプロジェクトであり、興味のある開発者を引き付ける優れたサイトでもある.制約仕様に関連するAPIインタフェースと構文は、リンク内のWikiページで詳細に説明できます.AndreasはO'Reilly Rubyサイトに構築されたGecode/Rプロジェクト関連ブログも維持している.
Google SoC Series:Constraint programming with Ruby