פותר הבעיות המקורי

בקטע הזה מתואר פותר התכנות האילוצים המקורי, שהוחלף בפותר הבעיות CP-SAT.

הערה: מומלץ מאוד להשתמש בפותר הבעיות של CP-SAT ולא בפותר הבעיות המקורי של CP-SAT.

בקטעים הבאים מוסבר איך לפתור את הדוגמה שמתוארת בקטע CP-SAT, והפעם באמצעות ה-CP המקורי לפתרון בעיות. אם אתם מתעקשים להשתמש בפותר הבעיות המקורי של ה-CP, תוכלו לעיין בחומר העזר בנושא API. שימו לב שהפותר המקורי של CP הוא הבסיס של ספריית הניתוב, ויכול להיות שה-API שלו יהיה נחוץ להתאמה אישית של מודל הניתוב.

ייבוא הספריות

הקוד הבא מייבא את הספרייה הנדרשת.

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()}");

קריאה לפותר

הקוד הבא מפעיל את הפותר.

הכלי ליצירת החלטות הוא הקלט העיקרי לפותר הבעיות המקורי. הוא כולל את הפרטים הבאים:

• 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()}");

התוצאות שהוחזרו על ידי הפותר

אלה 18 הפתרונות שפותר הבעיות מצא:

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, במקרה כזה הפותר יקצה ערכים בסדר יורד.