Red Hat Summit Red Hat Summitサポートコンソール開発者トライアルの開始お問い合わせ

第10章 Red Hat ビルドの OptaPlanner で提供される例

Red Hat Decision Manager には、Red Hat ビルドの OptaPlanner のサンプルが複数同梱されています。たとえばコードなどを確認して、ニーズに合ったものに変更できます。

注記

Red Hat は、Red Hat Decision Manager ディストリビューションに含まれるコードサンプルのサポートはしていません。

OptaPlanner サンプルには、教育関連のコンテストで出題された問題を解決するものもあります。以下の表の Contest 列には、このようなコンテストが掲載されています。また、コンテストの目的として、現実的 か、非現実的 かの識別をしています。現実的なコンテスト とは、以下の基準を満たす、独立した公式コンテストを指します。

  • 明確に定義された実際のユースケースであること
  • 実際に制約があること
  • 実際のデータセットが複数あること
  • 特定のハードウェアで特定の時間内に結果を再現できること
  • 教育機関および/または企業の運用研究コミュニティーが真剣に参加していること

現実的なコンテストでは、競合のソフトウェアや教育研究と OptaPlanner を客観的に比較できます。

Expand
表10.1 サンプルの概要
例ドメインサイズコンテストディレクトリー名

N クィーン

エンティティークラス 1 つ

(変数 1 つ)

エンティティー ⇐ 256

値 ⇐ 256

探索空間 ⇐ 10^616

無意味 (不正が可能)

nqueens

クラウドバランシング

エンティティークラス 1 つ

(変数 1 つ)

エンティティー ⇐ 2400

値 ⇐ 800

探索空間 ⇐ 10^6967

いいえ (弊社が定義)

cloudbalancing

巡回セールスマン

エンティティークラス 1 つ

(連鎖変数 1 つ)

エンティティー ⇐ 980

値 ⇐ 980

探索空間 ⇐ 10^2504

現実的でない TSP Web

tsp

テニスクラブのスケジュール

エンティティークラス 1 つ

(変数 1 つ)

エンティティー ⇐ 72

値 ⇐ 7

探索空間 ⇐ 10^60

いいえ (弊社が定義)

tennis

会議のスケジュール

エンティティークラス 1 つ

(変数 2 つ)

エンティティー ⇐ 10

値 ⇐ 320 および ⇐ 5

探索空間 ⇐ 10^320

いいえ (弊社が定義)

meetingscheduling

コースの時間割

エンティティークラス 1 つ

(変数 2 つ)

エンティティー ⇐ 434

値 ⇐ 25 および ⇐ 20

探索空間 ⇐ 10^1171

現実的 ITC 2007 track 3

curriculumCourse

マシンの再割当て

エンティティークラス 1 つ

(変数 1 つ)

エンティティー ⇐ 50000

値 ⇐ 5000

探索空間 ⇐ 10^184948

ほぼ現実的 ROADEF 2012

machineReassignment

配送経路

エンティティークラス 1 つ

(連鎖変数 1 つ)

シャドウエンティティークラス 1 つ

(自動シャドウ変数 1 つ)

エンティティー ⇐ 2740

値 ⇐ 2795

探索空間 ⇐ 10^8380

現実的でない VRP Web

vehiclerouting

時間枠がある中での 配送経路

配送経路すべて

(シャドウ変数 1 つ)

エンティティー ⇐ 2740

値 ⇐ 2795

探索空間 ⇐ 10^8380

現実的でない VRP Web

vehiclerouting

プロジェクトジョブのスケジュール

エンティティークラス 1 つ

(変数 2 つ)

(シャドウ変数 1 つ)

エンティティー ⇐ 640

値 ⇐ ? および ⇐ ?

探索空間 ⇐ ?

ほぼ現実的 MISTA 2013

projectjobscheduling

タスクの割り当て

エンティティークラス 1 つ

(連鎖変数 1 つ)

(シャドウ変数 1 つ)

シャドウエンティティークラス 1 つ

(自動シャドウ変数 1 つ)

エンティティー ⇐ 500

値 ⇐ 520

探索空間 ⇐ 10^1168

いいえ (弊社が定義)

taskassigning

試験の時間割

エンティティークラス 2 つ (同じ階層)

(変数 2 つ)

エンティティー ⇐ 1096

値 ⇐ 80 および ⇐ 49

探索空間 ⇐ 10^3374

現実的 ITC 2007 track 1

examination

看護師の勤務表

エンティティークラス 1 つ

(変数 1 つ)

エンティティー ⇐ 752

値 ⇐ 50

探索空間 ⇐ 10^1277

現実的 INRC 2010

nurserostering

巡回トーナメント

エンティティークラス 1 つ

(変数 1 つ)

エンティティー ⇐ 1560

値 ⇐ 78

探索空間 ⇐ 10^2301

現実的でない TTP

travelingtournament

コストを抑えるスケジュール

エンティティークラス 1 つ

(変数 2 つ)

エンティティー ⇐ 500

値 ⇐ 100 および ⇐ 288

探索空間 ⇐ 10^20078

ほぼ現実的 ICON Energy

cheaptimescheduling

投資

エンティティークラス 1 つ

(変数 1 つ)

エンティティー ⇐ 11

値 = 1000

探索空間 ⇐ 10^4

いいえ (弊社が定義)

investment

会議スケジュール

エンティティークラス 1 つ

(変数 2 つ)

エンティティー ⇐ 216

値 ⇐ 18 および ⇐ 20

探索空間 ⇐ 10^552

いいえ (弊社が定義)

conferencescheduling

ロックツアー

エンティティークラス 1 つ

(連鎖変数 1 つ)

(シャドウ変数 4 つ)

シャドウエンティティークラス 1 つ

(自動シャドウ変数 1 つ)

エンティティー ⇐ 47

値 ⇐ 48

探索空間 ⇐ 10^59

いいえ (弊社が定義)

rocktour

航空機乗組員のスケジューリング

エンティティークラス 1 つ

(変数 1 つ)

シャドウエンティティークラス 1 つ

(自動シャドウ変数 1 つ)

エンティティー ⇐ 4375

値 ⇐ 750

探索空間 ⇐ 10^12578

いいえ (弊社が定義)

flightcrewscheduling

10.1. N クィーン
リンクのコピー

n サイズのチェスボードで、他のクィーンに取られない場所に n 個のクィーンを置きます。最も一般的な n クィーンパズルは、n = 8 の 8 個のクィーンパズルです。

nQueensScreenshot

制約:

  • n 列および n 行のチェスボードを使用します。
  • チェスボードに n 個のクィーンを置きます。
  • クィーンが他のクィーンに取られないように配置します。クィーンは、同じ水平線上、垂直線上、対角線上にある他のクィーンを取ることができます。

本書では、4 つのクイーンパズルを主な例として多用しています。

以下が提案された解です。

図10.1 クィーン 4 個のパズルの誤った解

partiallySolvedNQueens04Explained

上記の解は、A1 と B0 (および B0 と D0) のクィーンがお互いに駒を取れるので間違っています。B0 のクィーンをどかせば他のクィーンに取られないようにするという制約は順守できますが、n 個のクィーンを置くという制約に違反します。

以下は正しい解です。

図10.2 クィーン 4 個のパズルの正しい解

solvedNQueens04

すべての制約が満たされているので、これが正解です。

n クィーンパズルでは、正解が複数存在する場合が多々あります。指定した n に対して考えられるすべての解を見つけるのではなく、指定の n に対する正しい解を 1 つ導き出すことに焦点をあてます。

問題の規模

4queens   has   4 queens with a search space of    256.
8queens   has   8 queens with a search space of   10^7.
16queens  has  16 queens with a search space of  10^19.
32queens  has  32 queens with a search space of  10^48.
64queens  has  64 queens with a search space of 10^115.
256queens has 256 queens with a search space of 10^616.

n クィーンは、初心者用のサンプルとして実装されているため、最適化はされていません。それにもかかわらず、クィーンが 64 個になっても簡単に処理できます。何点か変更を加えると、クィーンが 5000 個以上になっても簡単に対応できることが立証されています。

10.1.1. N クィーンのドメインモデル
リンクのコピー

この例では、4 つのクィーンの問題を解決するドメインモデルを使用します。

  • ドメインモデルの作成

    適切なドメインモデルを使用すると、プランニングの問題をより簡単に理解し、解決することができます。

    以下は、n クィーンの例のドメインモデルです。 

    public class Column {

    private int index;

    // ... getters and setters
}
     
    public class Row {

    private int index;

    // ... getters and setters
}
     
    public class Queen {

    private Column column;
    private Row row;

    public int getAscendingDiagonalIndex() {...}
    public int getDescendingDiagonalIndex() {...}

    // ... getters and setters
}

  • 探索空間の計算

    Queen インスタンスには Column (例: 0 は列 A、1 は列 B​) および Row (例: 0 は行 0、1 は行 1​) が含まれます。

    列と行をもとに、昇順の対角線、および降順の対角線を計算することができます。

    列と行のインデックスは、チェスボードの左上隅から数えています。 

    public class NQueens {

    private int n;
    private List<Column> columnList;
    private List<Row> rowList;

    private List<Queen> queenList;

    private SimpleScore score;

    // ... getters and setters
}

  • 解の求め方

    1 つの NQueens インスタンスには Queen インスタンスの一覧が含まれています。これが Solution 実装として提供され、Solver が解決して読み出します。

たとえば、4 クイーンのサンプルでは、NQueens の getN() メソッドが常に 4 を返します。

図10.3 クィーン 4 個の解

partiallySolvedNQueens04Explained
Expand
表10.2 ドメインモデルの解の詳細
 columnIndexrowIndexascendingDiagonalIndex (columnIndex + rowIndex)descendingDiagonalIndex (columnIndex - rowIndex)

A1

0

1

1 (**)

-1

B0

1

0 (*)

1 (**)

1

C2

2

2

4

0

D0

3

0 (*)

3

3

(*) や (**) のように、クィーン 2 つが同じ行、列、対角線を共有する場合は、2 つの駒が互いを取ることができます。

Red Hat logoGithubredditYoutubeTwitter

詳細情報

試用、購入および販売

コミュニティー

会社概要

Red Hat は、企業がコアとなるデータセンターからネットワークエッジに至るまで、各種プラットフォームや環境全体で作業を簡素化できるように、強化されたソリューションを提供しています。

多様性を受け入れるオープンソースの強化

Red Hat では、コード、ドキュメント、Web プロパティーにおける配慮に欠ける用語の置き換えに取り組んでいます。このような変更は、段階的に実施される予定です。詳細情報: Red Hat ブログ.

Red Hat ドキュメントについて

Red Hat をお使いのお客様が、信頼できるコンテンツが含まれている製品やサービスを活用することで、イノベーションを行い、目標を達成できるようにします。 最新の更新を見る.

Legal Notice

Theme

© 2026 Red Hatトップに戻る