इस पेज का अनुवाद Cloud Translation API से किया गया है.

ओरिजनल सीपी सॉल्वर

इस सेक्शन में, ओरिजनल कंस्ट्रेंट प्रोग्रामिंग सॉल्वर के बारे में बताया गया है. इसे बेहतर CP-SAT सॉल्वर से बदल दिया गया है.

नीचे दिए सेक्शन में, सीपी-एसएटी सेक्शन में बताए गए उदाहरण को हल करने का तरीका बताया गया है. इस बार, ओरिजनल सीपी सॉल्वर का इस्तेमाल करें. अगर आपको ओरिजनल सीपी सॉल्वर का इस्तेमाल करना है, तो एपीआई का रेफ़रंस ब्राउज़ किया जा सकता है. ध्यान दें कि ओरिजनल सीपी सॉल्वर, रूटिंग लाइब्रेरी का आधार है. साथ ही, रूटिंग मॉडल को पसंद के मुताबिक बनाने के लिए, इसका एपीआई ज़रूरी हो सकता है.

लाइब्रेरी इंपोर्ट करें

नीचे दिया गया कोड, ज़रूरी लाइब्रेरी को इंपोर्ट करता है.

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

प्रोग्राम पूरा करें

यहां ओरिजनल सीपी सॉल्वर का इस्तेमाल करने वाले उदाहरण के लिए सभी प्रोग्राम दिए गए हैं.

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

डिसिज़न बिल्डर

फ़ैसले बनाने वाला, ओरिजनल सीपी सॉल्वर के लिए मुख्य इनपुट होता है. इसमें सवाल से जुड़े वैरिएबल होते हैं और सॉल्वर के लिए विकल्प सेट किए जाते हैं.

पिछले सेक्शन में दिया गया कोड उदाहरण, Phase तरीके (C++ वाले तरीके के मुताबिक) MakePhase का इस्तेमाल करके डिसिज़न बिल्डर बनाता है.

चरण शब्द का मतलब खोज के उस चरण से है. इस आसान उदाहरण में, सिर्फ़ एक चरण है, लेकिन ज़्यादा मुश्किल समस्याओं के लिए, डिसिज़न बिल्डर में एक से ज़्यादा चरण हो सकते हैं. इससे सॉल्वर एक चरण से अगले चरण में, खोज की अलग-अलग रणनीतियों का इस्तेमाल कर सकता है.

Phase तरीके में तीन इनपुट पैरामीटर होते हैं:

vars — एक कलेक्शन जिसमें सवाल के लिए वैरिएबल होते हैं, जो इस मामले में [x, y, z] है.
IntVarStrategy — वैल्यू असाइन करने के लिए, अगले अनबाउंड वैरिएबल को चुनने का नियम. यहां कोड, डिफ़ॉल्ट CHOOSE_FIRST_UNBOUND का इस्तेमाल करता है. इसका मतलब है कि हर चरण में, सॉल्वर Phase तरीके को पास किए गए वैरिएबल कलेक्शन में मौजूद पहले अनबाउंड वैरिएबल को उसी क्रम में चुनता है.
IntValueStrategy — किसी वैरिएबल को असाइन करने के लिए, अगली वैल्यू चुनने का नियम. यहां कोड डिफ़ॉल्ट ASSIGN_MIN_VALUE का इस्तेमाल करता है, जो सबसे छोटी वैल्यू को चुनता है, जिसे पहले वैरिएबल के लिए नहीं आज़माया गया है. यह बढ़ते क्रम में वैल्यू असाइन करता है. दूसरा विकल्प ASSIGN_MAX_VALUE है. इस मामले में, सॉल्वर घटते क्रम में वैल्यू असाइन करेगा.