عادل توزيع المنتجات الخوارزمية
-
29-09-2019 - |
سؤال
هنا مشكلتي:
- دليل شركات توزيع والمنتجات.
- جميع المنتجات يجب أن توزع في أيام k
- توزيع منتجات شركة Ci يجب أن تكون متتالية - وهذا يعني أنه يمكن أن تكون موزعة على أيام 2,3,4,5 ولكن ليس 2,3,6,7
- عدد من توزيع المنتجات من قبل شركة Ci على ي اليوم يجب أن تكون أقل من (أو مساوية) في اليوم j-1 (إذا كانت هناك أي في يوم j-1)
- الفرق بين توزيع المنتجات بين أيام أنا و ي لا ينبغي أن يكون أكبر من 1
على سبيل المثال:
لدينا 3 أيام لتوزيع المنتجات.منتجات الشركة:a,a,a,a,a.منتجات الشركة ب:ب ، ب ، ب.المنتجات من شركة C:ج ، c
توزيع عادل: [aab,aabc ، abc]
صالح توزيع: [aabc,aabc,ab] لأنه في يوم 1 هناك 4 المنتجات في يوم 3 2 منتجات (الفرق > 1)
صالح توزيع: [abc ، aabc,aab] لأنه في يوم 1 هناك منتج واحد ، و في يوم 2 هناك 2 المنتجات ، وبالتالي توزيع المنتج لا غير يتناقص
تحرير إذا كان هناك حالة أن يجعل التوزيع العادل المستحيل يرجى تقديم وصف مختصر ، سوف يقبل الجواب
المحلول
غاريث ريس التعليق على djna الجواب هو صحيح ... التالية بالدليل غير قابلة للحل:
- 3 أيام, 7 عناصر من الشركة و 5 عناصر من الشركة ب
أنا اختبرت هذا مع التالية أغبى-من الممكن القوة الغاشمة بيرل البرنامج (الذي يأخذ حسنا إطار في الثانية ، على الرغم من كونها فعالة جدا):
my ($na, $nb) = (7, 5);
for (my $a1 = 0; $a1 <= $na; ++$a1) {
for (my $a2 = 0; $a2 <= $na - $a1; ++$a2) {
my $a3 = $na - $a1 - $a2;
for (my $b1 = 0; $b1 <= $nb; ++$b1) {
for (my $b2 = 0; $b2 <= $nb - $b1; ++$b2) {
my $b3 = $nb - $b1 - $b2;
if ($a1 >= $a2 && $a2 >= $a3 || $a1 == 0 && $a2 >= $a3 || $a1 == 0 && $a2 == 0) {
if ($b1 >= $b2 && $b2 >= $b3 || $b1 == 0 && $b2 >= $b3 || $b1 == 0 && $b2 == 0) {
if (max($a1 + $b1, $a2 + $b2, $a3 + $b3) - min($a1 + $b1, $a2 + $b2, $a3 + $b3) <= 1) {
print "Success! ($a1,$a2,$a3), ($b1,$b2,$b3)\n";
}
}
}
}
}
}
}
يرجى إلقاء نظرة والتحقق من انني لم ارتكب أي أخطاء غبية.(لقد حذفت max()
و min()
الإيجاز فقط تفعل ما كنت تتوقع.)
نصائح أخرى
منذ ظننت أن المشكلة كانت ممتعة ، لم نموذجا إيجاد حلول باستخدام MiniZinc.مع Gecode الخلفية الأولى يظهر المثال إلى 20 الحلول في حوالي 1.6 ms.
include "globals.mzn";
%%% Data
% Number of companies
int: n = 3;
% Number of products per company
array[1..n] of int: np = [5, 3, 2];
% Number of days
int: k = 3;
%%% Computed values
% Total number of products
int: totalnp = sum(np);
% Offsets into products array to get single companys products
% (shifted cumulative sum).
array[1..n] of int: offset = [sum([np[j] | j in 1..i-1])
| i in 1..n];
%%% Predicates
predicate fair(array[int] of var int: x) =
let { var int: low,
var int: high
} in
minimum(low, x) /\
maximum(high, x) /\
high-low <= 1;
predicate decreasing_except_0(array[int] of var int: x) =
forall(i in 1..length(x)-1) (
(x[i] == 0) \/
(x[i] >= x[i+1])
);
predicate consecutive(array[int] of var int: x) =
forall(i in 1..length(x)-1) (
(x[i] == x[i+1]) \/
(x[i] == x[i+1]-1)
);
%%% Variables
% Day of production for all products from all companies
array[1..totalnp] of var 1..k: products
:: is_output;
% total number of products per day
array[1..k] of var 1..totalnp: productsperday
:: is_output;
%%% Constraints
constraint global_cardinality(products, productsperday);
constraint fair(productsperday);
constraint
forall(i in 1..n) (
let {
% Products produced by company i
array[1..np[i]] of var int: pi
= [products[j] |
j in 1+offset[i]..1+offset[i]+np[i]-1],
% Products per day by company i
array[1..k] of var 0..np[i]: ppdi
} in
consecutive(pi) /\
global_cardinality(pi, ppdi) /\
decreasing_except_0(ppdi)
);
%%% Find a solution, default search strategy
solve satisfy;
المسندات decreasing_except_0
و consecutive
كلاهما ساذجة جدا و كبيرة التفسخ.لحل أكبر الحالات ربما ينبغي استبدالها أكثر ذكاء المتغيرات (على سبيل المثال باستخدام العادية القيد).
وقد تبين أن النقاط 4 و 5 تتنافى:
- 4:في أي يوم ي ، أي الشركة ، ج(ي,و) == 0 أو ج(ي,و) >= ج(ي+1)
- 5:أي أيام i و j ،
|C(i) - C(j)| <= 1
وبالتالي تحتاج الاسترخاء إما القيد.بصراحة, في حين يمكنني الحصول على شعور لماذا 4
وضعت في المكان (لتجنب تأخير توزيع من شركة واحدة إلى أجل غير مسمى) أعتقد أنه يمكن أن يعبر عنها خلاف ذلك إلى النظر في أول و آخر يوم من توزيع بأنها الخاصة (منذ اليوم الأول ، عادة ما يستغرق ما تبقى من الشركة السابقة و في اليوم الأخير توزيع ما تبقى).
النقطة 3 لا قوة التواصل.
رياضيا:
أي الشركة التي لديها منتجات توجد يومين انا و ي مثل هذا:
- ج(أنا) > 0 and C(ي,و) > 0
- في أي يوم x بحيث x < أنا أو x > j, C(x) = 0
- أي في اليوم العاشر من هذا القبيل أن كنت < x < ي ، C(x) = C(x)
باعتراف الجميع, المشكلة ثم يصبح تافهة حل :)
أنا لا أعتقد أنه يمكنك دائما الوفاء الاحتياجات الخاصة بك.
النظر في 4 أيام, 6 عناصر من المورد و 6 عناصر من المورد B.