تمت ترجمة هذه الصفحة بواسطة Cloud Translation API‏.

محلل CP أصلي

يوضّح هذا القسم أداة حلّ برمجة القيود الأصلية، التي تم استبدالها بأداة حلّ CP-SAT الأفضل.

توضّح الأقسام التالية كيفية حلّ المثال الموضّح في قسم CP-SAT، هذه المرة باستخدام أداة حلّ CP الأصلية. وإذا كنت تصرّ على استخدام أداة حلّ CP الأصلية، يمكنك تصفّح مرجع واجهة برمجة التطبيقات. تجدر الإشارة إلى أنّ أداة حلّ CP الأصلية هي أساس مكتبة التوجيه، وقد تكون واجهة برمجة التطبيقات الخاصة بها ضرورية لتخصيص نموذج توجيه.

استيراد المكتبات

يؤدي الرمز التالي إلى استيراد المكتبة المطلوبة.

Python

from ortools.constraint_solver import pywrapcp

C++

#include <ostream>
#include <string>

#include "ortools/constraint_solver/constraint_solver.h"

Java

import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.DecisionBuilder;
import com.google.ortools.constraintsolver.IntVar;
import com.google.ortools.constraintsolver.Solver;
import java.util.logging.Logger;

C#

using System;
using Google.OrTools.ConstraintSolver;

تعريف أداة الحلّ

يعرِّف الرمز التالي أداة الحلّ.

Python

solver = pywrapcp.Solver("CPSimple")

C++

Solver solver("CpSimple");

Java

Solver solver = new Solver("CpSimple");

C#

Solver solver = new Solver("CpSimple");

إنشاء المتغيّرات

تنشئ التعليمة البرمجية التالية المتغيرات للمشكلة.

تنشئ أداة الحلّ ثلاثة متغيرات، هي x وy وz، ويمكن لكلٍ منها أن يأخذ القيم 0 أو 1 أو 2.

Python

num_vals = 3
x = solver.IntVar(0, num_vals - 1, "x")
y = solver.IntVar(0, num_vals - 1, "y")
z = solver.IntVar(0, num_vals - 1, "z")

C++

const int64_t num_vals = 3;
IntVar* const x = solver.MakeIntVar(0, num_vals - 1, "x");
IntVar* const y = solver.MakeIntVar(0, num_vals - 1, "y");
IntVar* const z = solver.MakeIntVar(0, num_vals - 1, "z");

Java

final long numVals = 3;
final IntVar x = solver.makeIntVar(0, numVals - 1, "x");
final IntVar y = solver.makeIntVar(0, numVals - 1, "y");
final IntVar z = solver.makeIntVar(0, numVals - 1, "z");

C#

const long numVals = 3;
IntVar x = solver.MakeIntVar(0, numVals - 1, "x");
IntVar y = solver.MakeIntVar(0, numVals - 1, "y");
IntVar z = solver.MakeIntVar(0, numVals - 1, "z");

قم بإنشاء القيد

تُنشئ التعليمة البرمجية التالية القيد x ≠ y.

Python

solver.Add(x != y)
print("Number of constraints: ", solver.Constraints())

C++

solver.AddConstraint(solver.MakeAllDifferent({x, y}));
LOG(INFO) << "Number of constraints: "
          << std::to_string(solver.constraints());

Java

solver.addConstraint(solver.makeAllDifferent(new IntVar[] {x, y}));
logger.info("Number of constraints: " + solver.constraints());

C#

solver.Add(solver.MakeAllDifferent(new IntVar[] { x, y }));
Console.WriteLine($"Number of constraints: {solver.Constraints()}");

الاتصال بأداة الحلّ

يستدعي الرمز التالي أداة الحلّ.

إنّ أداة إنشاء القرارات هي المدخل الرئيسي لأداة حلّ CP الأصلية. وهي تحتوي على ما يلي:

vars: مصفوفة تحتوي على المتغيّرات الخاصة بالمشكلة.
قاعدة لاختيار المتغير التالي لتعيين قيمة له.
قاعدة لاختيار القيمة التالية المطلوب تعيينها لهذا المتغيّر.

راجع أداة إنشاء القرار لمزيد من التفاصيل.

Python

decision_builder = solver.Phase(
    [x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE
)

C++

DecisionBuilder* const db = solver.MakePhase(
    {x, y, z}, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE);

Java

final DecisionBuilder db = solver.makePhase(
    new IntVar[] {x, y, z}, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

C#

DecisionBuilder db =
    solver.MakePhase(new IntVar[] { x, y, z }, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

طباعة الحلّ

في القسم التالي، يتم عرض الرمز الخاص بطابعة الحلول، التي تعرض كل حل حسب العثور عليه.

نظرًا لوجود أكثر من حل لمشكلتنا، يمكن تكرار الحلول من خلال التكرار الحلقي while solver.NextSolution(). (لاحظ أن هذه تعمل بشكل مختلف عن طابعة الحل الخاصة ببرنامج CP-SAT).

Python

count = 0
solver.NewSearch(decision_builder)
while solver.NextSolution():
    count += 1
    solution = f"Solution {count}:\n"
    for var in [x, y, z]:
        solution += f" {var.Name()} = {var.Value()}"
    print(solution)
solver.EndSearch()
print(f"Number of solutions found: {count}")

C++

int count = 0;
solver.NewSearch(db);
while (solver.NextSolution()) {
  ++count;
  LOG(INFO) << "Solution " << count << ":" << std::endl
            << " x=" << x->Value() << " y=" << y->Value()
            << " z=" << z->Value();
}
solver.EndSearch();
LOG(INFO) << "Number of solutions found: " << solver.solutions();

Java

int count = 0;
solver.newSearch(db);
while (solver.nextSolution()) {
  ++count;
  logger.info(
      String.format("Solution: %d\n x=%d y=%d z=%d", count, x.value(), y.value(), z.value()));
}
solver.endSearch();
logger.info("Number of solutions found: " + solver.solutions());

C#

int count = 0;
solver.NewSearch(db);
while (solver.NextSolution())
{
    ++count;
    Console.WriteLine($"Solution: {count}\n x={x.Value()} y={y.Value()} z={z.Value()}");
}
solver.EndSearch();
Console.WriteLine($"Number of solutions found: {solver.Solutions()}");

النتائج التي تعرضها أداة الحلّ

في ما يلي الحلول الثمانية عشر التي تم العثور عليها في أداة الحلّ:

Number of constraints:  1
Solution 1:
 x = 0 y = 1 z = 0
Solution 2:
 x = 0 y = 1 z = 1
Solution 3:
 x = 0 y = 1 z = 2
Solution 4:
 x = 0 y = 2 z = 0
Solution 5:
 x = 0 y = 2 z = 1
Solution 6:
 x = 0 y = 2 z = 2
Solution 7:
 x = 1 y = 0 z = 0
Solution 8:
 x = 1 y = 0 z = 1
Solution 9:
 x = 1 y = 0 z = 2
Solution 10:
 x = 1 y = 2 z = 0
Solution 11:
 x = 1 y = 2 z = 1
Solution 12:
 x = 1 y = 2 z = 2
Solution 13:
 x = 2 y = 0 z = 0
Solution 14:
 x = 2 y = 0 z = 1
Solution 15:
 x = 2 y = 0 z = 2
Solution 16:
 x = 2 y = 1 z = 0
Solution 17:
 x = 2 y = 1 z = 1
Solution 18:
 x = 2 y = 1 z = 2
Number of solutions found:  18
Advanced usage:
Problem solved in  2 ms
Memory usage:  13918208 bytes

إكمال البرنامج

في ما يلي البرامج الكاملة للمثال باستخدام أداة حل CP الأصلية.

Python

"""Simple Constraint optimization example."""

from ortools.constraint_solver import pywrapcp


def main():
    """Entry point of the program."""
    # Instantiate the solver.
    solver = pywrapcp.Solver("CPSimple")

    # Create the variables.
    num_vals = 3
    x = solver.IntVar(0, num_vals - 1, "x")
    y = solver.IntVar(0, num_vals - 1, "y")
    z = solver.IntVar(0, num_vals - 1, "z")

    # Constraint 0: x != y.
    solver.Add(x != y)
    print("Number of constraints: ", solver.Constraints())

    # Solve the problem.
    decision_builder = solver.Phase(
        [x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE
    )

    # Print solution on console.
    count = 0
    solver.NewSearch(decision_builder)
    while solver.NextSolution():
        count += 1
        solution = f"Solution {count}:\n"
        for var in [x, y, z]:
            solution += f" {var.Name()} = {var.Value()}"
        print(solution)
    solver.EndSearch()
    print(f"Number of solutions found: {count}")

    print("Advanced usage:")
    print(f"Problem solved in {solver.WallTime()}ms")
    print(f"Memory usage: {pywrapcp.Solver.MemoryUsage()}bytes")


if __name__ == "__main__":
    main()

C++

#include <ostream>
#include <string>

#include "ortools/constraint_solver/constraint_solver.h"

namespace operations_research {

void SimpleCpProgram() {
  // Instantiate the solver.
  Solver solver("CpSimple");

  // Create the variables.
  const int64_t num_vals = 3;
  IntVar* const x = solver.MakeIntVar(0, num_vals - 1, "x");
  IntVar* const y = solver.MakeIntVar(0, num_vals - 1, "y");
  IntVar* const z = solver.MakeIntVar(0, num_vals - 1, "z");

  // Constraint 0: x != y..
  solver.AddConstraint(solver.MakeAllDifferent({x, y}));
  LOG(INFO) << "Number of constraints: "
            << std::to_string(solver.constraints());

  // Solve the problem.
  DecisionBuilder* const db = solver.MakePhase(
      {x, y, z}, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE);

  // Print solution on console.
  int count = 0;
  solver.NewSearch(db);
  while (solver.NextSolution()) {
    ++count;
    LOG(INFO) << "Solution " << count << ":" << std::endl
              << " x=" << x->Value() << " y=" << y->Value()
              << " z=" << z->Value();
  }
  solver.EndSearch();
  LOG(INFO) << "Number of solutions found: " << solver.solutions();

  LOG(INFO) << "Advanced usage:" << std::endl
            << "Problem solved in " << std::to_string(solver.wall_time())
            << "ms" << std::endl
            << "Memory usage: " << std::to_string(Solver::MemoryUsage())
            << "bytes";
}

}  // namespace operations_research

int main(int /*argc*/, char* /*argv*/[]) {
  operations_research::SimpleCpProgram();
  return EXIT_SUCCESS;
}

Java

package com.google.ortools.constraintsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.DecisionBuilder;
import com.google.ortools.constraintsolver.IntVar;
import com.google.ortools.constraintsolver.Solver;
import java.util.logging.Logger;

/** Simple CP Program.*/
public class SimpleCpProgram {
  private SimpleCpProgram() {}

  private static final Logger logger = Logger.getLogger(SimpleCpProgram.class.getName());

  public static void main(String[] args) throws Exception {
    Loader.loadNativeLibraries();
    // Instantiate the solver.
    Solver solver = new Solver("CpSimple");

    // Create the variables.
    final long numVals = 3;
    final IntVar x = solver.makeIntVar(0, numVals - 1, "x");
    final IntVar y = solver.makeIntVar(0, numVals - 1, "y");
    final IntVar z = solver.makeIntVar(0, numVals - 1, "z");

    // Constraint 0: x != y..
    solver.addConstraint(solver.makeAllDifferent(new IntVar[] {x, y}));
    logger.info("Number of constraints: " + solver.constraints());

    // Solve the problem.
    final DecisionBuilder db = solver.makePhase(
        new IntVar[] {x, y, z}, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

    // Print solution on console.
    int count = 0;
    solver.newSearch(db);
    while (solver.nextSolution()) {
      ++count;
      logger.info(
          String.format("Solution: %d\n x=%d y=%d z=%d", count, x.value(), y.value(), z.value()));
    }
    solver.endSearch();
    logger.info("Number of solutions found: " + solver.solutions());

    logger.info(String.format("Advanced usage:\nProblem solved in %d ms\nMemory usage: %d bytes",
        solver.wallTime(), Solver.memoryUsage()));
  }
}

C#

using System;
using Google.OrTools.ConstraintSolver;

/// <summary>
///   This is a simple CP program.
/// </summary>
public class SimpleCpProgram
{
    public static void Main(String[] args)
    {
        // Instantiate the solver.
        Solver solver = new Solver("CpSimple");

        // Create the variables.
        const long numVals = 3;
        IntVar x = solver.MakeIntVar(0, numVals - 1, "x");
        IntVar y = solver.MakeIntVar(0, numVals - 1, "y");
        IntVar z = solver.MakeIntVar(0, numVals - 1, "z");

        // Constraint 0: x != y..
        solver.Add(solver.MakeAllDifferent(new IntVar[] { x, y }));
        Console.WriteLine($"Number of constraints: {solver.Constraints()}");

        // Solve the problem.
        DecisionBuilder db =
            solver.MakePhase(new IntVar[] { x, y, z }, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

        // Print solution on console.
        int count = 0;
        solver.NewSearch(db);
        while (solver.NextSolution())
        {
            ++count;
            Console.WriteLine($"Solution: {count}\n x={x.Value()} y={y.Value()} z={z.Value()}");
        }
        solver.EndSearch();
        Console.WriteLine($"Number of solutions found: {solver.Solutions()}");

        Console.WriteLine("Advanced usage:");
        Console.WriteLine($"Problem solved in {solver.WallTime()}ms");
        Console.WriteLine($"Memory usage: {Solver.MemoryUsage()}bytes");
    }
}

أداة إنشاء القرارات

إنّ المدخل الرئيسي لأداة حلّ CP الأصلية هو أداة إنشاء القرار، والتي تحتوي على متغيرات المشكلة وتحدّد الخيارات المتاحة للأداة.

يؤدي مثال الرمز البرمجي في القسم السابق إلى إنشاء أداة إنشاء قرارات باستخدام طريقة Phase (بالتوافق مع طريقة C++ MakePhase.

يشير مصطلح المرحلة إلى مرحلة البحث. في هذا المثال البسيط، هناك مرحلة واحدة فقط، ولكن بالنسبة للمشاكل الأكثر تعقيدًا، يمكن أن تشتمل أداة إنشاء القرار على أكثر من مرحلة واحدة، وبالتالي يمكن للأداة استخدام استراتيجيات بحث مختلفة من مرحلة إلى أخرى.

تتضمّن الطريقة Phase ثلاث معلَمات إدخال:

vars - مصفوفة تحتوي على المتغيّرات الخاصة بالمسألة، وهي [x, y, z] في هذه الحالة.
IntVarStrategy - قاعدة اختيار المتغيّر التالي غير المرتبط لتخصيص قيمة. في هذا المثال، يستخدم الرمز السمة CHOOSE_FIRST_UNBOUND التلقائية، ما يعني أنّه في كل خطوة، تختار أداة الحلّ أول متغيّر غير مرتبط بالترتيب الذي يحدث فيه مصفوفة المتغيّرات التي يتم تمريرها إلى طريقة Phase.
IntValueStrategy - قاعدة اختيار القيمة التالية التي سيتم تخصيصها لمتغير. يستخدم الرمز هنا القيمة التلقائية ASSIGN_MIN_VALUE، التي تحدد أصغر قيمة لم يسبق اختبارها على المتغيّر. هذا يعين القيم بترتيب متزايد. هناك خيار آخر هو ASSIGN_MAX_VALUE، وفي هذه الحالة ستعمل أداة الحلّ على تحديد القيم بترتيب تنازلي.