تحسين مقيّد
تنظيم صفحاتك في مجموعات
يمكنك حفظ المحتوى وتصنيفه حسب إعداداتك المفضّلة.
تحسين القيد أو برمجة القيود (CP) هو الاسم الذي يتم منحه لتحديد الحلول الممكنة من مجموعة كبيرة جدًا من المرشحين، حيث يمكن وضع نمذجة للمشكلة من حيث القيود العشوائية.
تظهر مشكلات CP في العديد من التخصصات العلمية والهندسية. (كلمة "برمجة" هي تسمية خاطئة إلى حد ما، كما لو كانت كلمة "كمبيوتر" تعني في السابق
"شخص يقوم بإجراء عمليات حسابية". وتشير كلمة "البرمجة" هنا إلى ترتيب الخطة،
وليس البرمجة بلغة الكمبيوتر).
يعتمد CP إلى الجدوى (إيجاد حل ممكن) بدلاً من التحسين (إيجاد حل مثالي) ويركز على القيود والمتغيرات
بدلاً من الوظيفة الموضوعية. في الواقع، قد لا يكون لمشكلة CP سوى وظيفة موضوعية - قد يكون الهدف هو تضييق نطاق
مجموعة كبيرة جدًا من الحلول الممكنة لمجموعة فرعية أكثر قابلية للإدارة عن طريق إضافة
قيود إلى المشكلة.
ومن الأمثلة على المشاكل المناسبة لدليل CP هو جدولة الموظف.
تظهر المشكلة عندما تحتاج الشركات التي تعمل بشكل مستمر - مثل
المصانع - إلى إنشاء جداول أسبوعية لموظفيها. في ما يلي مثال مبسّط للغاية: تعمل شركة بثلاث نوبات عمل لمدة 8 ساعات في اليوم وتعين ثلاثة من موظفيها الأربعة نوبات عمل مختلفة يوميًا، مع منح رابع يوم إجازة. حتى في مثل هذه الحالة الصغيرة، يكون عدد الجداول الزمنية الممكنة كبيرًا: كل يوم، هناك 4! = 4 * 3 * 2 * 1 = 24 تعيينات محتملة للموظفين، وبالتالي فإن عدد الجداول الزمنية الأسبوعية المحتملة هو 247، أي ما يزيد عن 247.
عادة ما تكون هناك قيود أخرى تقلل من عدد الحلول
الممكنة - على سبيل المثال، أن كل موظف يعمل على الأقل
عدد من الأيام في الأسبوع على الأقل. تتبع طريقة CP الحلول التي تظل ممكنة عند إضافة قيود جديدة، مما يجعلها أداة قوية لحل مشكلات الجدولة الكبيرة في العالم الحقيقي.
تتمتع CP وقد تم تطبيق CP بنجاح في التخطيط والجدولة والعديد من المجالات الأخرى مع قيود غير متجانسة.
تقدّم Google بعض الطرق لحلّ مشاكل CP:
إذا كان من الممكن نمذجة مشكلتك باستخدام هدف خطي والقيود الخطية،
تكون هناك مشكلة في البرمجة الخطية وعليك التفكير في
MPSolver. (ومع ذلك، يتم عادةً حلّ مشاكل التوجيه باستخدام مكتبة توجيه المركبات لدينا حتى لو كان من الممكن تمثيلها في نموذج خطي).
أمثلة
يوضّح القسم التالي أداة حلّ CP-SAT، وهي أداة حلّ "أدوات OR" الأساسية لبرمجة القيود. (يشير SAT إلى
الرضا: تستخدم أداة الحلّ أساليب لحل مشاكل SAT إلى جانب طرق CP).
في ما يلي بعض الأمثلة على مشكلات الجدولة المناسبة لأداة حل CP-SAT:
هناك مشكلتان كلاسيكيتان بشأن CP وهما مشكلة N-queens وألغاز التشفير.
إنّ محتوى هذه الصفحة مرخّص بموجب ترخيص Creative Commons Attribution 4.0 ما لم يُنصّ على خلاف ذلك، ونماذج الرموز مرخّصة بموجب ترخيص Apache 2.0. للاطّلاع على التفاصيل، يُرجى مراجعة سياسات موقع Google Developers. إنّ Java هي علامة تجارية مسجَّلة لشركة Oracle و/أو شركائها التابعين.
تاريخ التعديل الأخير: 2024-08-09 (حسب التوقيت العالمي المتفَّق عليه)
[null,null,["تاريخ التعديل الأخير: 2024-08-09 (حسب التوقيت العالمي المتفَّق عليه)"],[[["\u003cp\u003eConstraint Programming (CP) helps find feasible solutions within a large set of possibilities by applying constraints to a problem.\u003c/p\u003e\n"],["\u003cp\u003eCP focuses on finding solutions that satisfy all constraints, rather than optimizing for a specific objective.\u003c/p\u003e\n"],["\u003cp\u003eEmployee scheduling, where numerous possible shift combinations exist, is an example of a problem effectively addressed using CP.\u003c/p\u003e\n"],["\u003cp\u003eGoogle provides tools like the CP-SAT solver and the original CP solver to tackle constraint programming problems.\u003c/p\u003e\n"],["\u003cp\u003eCP is widely used in various fields, with dedicated research and applications in planning and scheduling.\u003c/p\u003e\n"]]],["Constraint programming (CP) identifies feasible solutions from a vast set of candidates by modeling problems with constraints. CP focuses on feasibility, constraints, and variables rather than optimization. It's used in employee scheduling, where numerous constraints, such as shifts and days off, reduce the number of viable schedules. Tools like the CP-SAT solver and the original CP solver are available, and CP is applied to scheduling and planning problems, along with classic puzzles like N-queens and cryptarithmetic.\n"],null,["# Constraint Optimization\n\n**Constraint optimization** , or\n[**constraint programming**](https://en.wikipedia.org/wiki/Constraint_programming)\n(CP), is the name given to identifying feasible solutions out of a very large\nset of candidates, where the problem can be modeled in terms of arbitrary\nconstraints.\nCP problems arise in many scientific and engineering disciplines. (The word\n\"programming\" is a bit of a misnomer, similar to how \"computer\" once meant\n\"a person who computes\". Here, \"programming\" refers to the arrangement of a plan\n, rather than programming in a computer language.)\n\nCP is based on *feasibility* (finding a feasible solution) rather than\noptimization (finding an optimal solution) and focuses on the constraints and\nvariables rather than the objective function. In fact, a CP problem may not even\nhave an objective function --- the goal may be to narrow down a very\nlarge set of possible solutions to a more manageable subset by adding\nconstraints to the problem.\n\nAn example of a problem that is well-suited for CP is **employee scheduling** .\nThe problem arises when companies that operate continuously --- such as\nfactories --- need to create weekly schedules for their employees. Here's a\nvery simplified example: a company runs three 8-hour shifts per day and assigns\nthree of its four employees to different shifts each day, while giving the\nfourth the day off. Even in such a small case, the number of possible schedules\nis huge: each day, there are `4! = 4 * 3 * 2 * 1 = 24` possible employee\nassignments, so the number of possible weekly schedules is 24^7^, which\nis over 4.5 billion.\nUsually there will be other constraints that reduce the number of feasible\nsolutions --- for example, that each employee works at least a minimum\nnumber of days per week. The CP method keeps track of which solutions remain\nfeasible when you add new constraints, which makes it a powerful tool for\nsolving large, real-world scheduling problems.\n\nCP has a widespread and very active community around the world with dedicated\nscientific journals, conferences, and an arsenal of different solving techniques\n. CP has been successfully applied in planning, scheduling, and numerous other\ndomains with heterogeneous constraints.\n\nTools\n-----\n\nGoogle provides few ways to solve problems:\n\n- [CP-SAT solver](/optimization/cp/cp_solver): A **constraint programming** solver that uses SAT (satisfiability) methods.\n- [Original CP solver](/optimization/routing/original_cp_solver): A **constraint programming** solver used in the routing library.\n\nIf your problem can be modeled with a linear objective and linear constraints,\nthen you have a [linear programming](/optimization/lp) problem and should\nconsider [MPSolver](/optimization/lp/mpsolver). (However, routing problems are\ntypically best solved with our\n[vehicle routing library](/optimization/reference/constraint_solver/routing)\neven if they can be represented with a linear model.)\n\nExamples\n--------\n\nThe [next section](/optimization/cp/cp_solver) describes the CP-SAT solver, the\nprimary OR-Tools solver for constraint programming. (SAT stands for\n**satisfiability**: the solver uses techniques for solving SAT problems along\nwith CP methods.)\n\nHere are some examples of scheduling problems that are well-suited for the\nCP-SAT solver:\n\n- [Employee Scheduling](/optimization/scheduling/employee_scheduling)\n- [The Job shop problem](/optimization/scheduling/job_shop)\n\nTwo classic CP problems are the [N-queens problem](/optimization/cp/queens) and\n[cryptarithmetic puzzles](/optimization/puzzles/cryptarithmetic).\n\n*[CP]: Constraint Programming"]]
