ابحث عن أفضل مجموعة من مجموعة معينة من المجموعات المتعددة

Question

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

Array
(
    [leg0] => Array
        (
            [UPS] => Array
                (
                    [days] => 1
                    [cost] => 5000
                )

            [FedEx] => Array
                (
                    [days] => 2
                    [cost] => 3000
                )

            [Conway] => Array
                (
                    [days] => 5
                    [cost] => 1000
                )

        )

    [leg1] => Array
        (
            [UPS] => Array
                (
                    [days] => 1
                    [cost] => 3000
                )

            [FedEx] => Array
                (
                    [days] => 2
                    [cost] => 3000
                )

            [Conway] => Array
                (
                    [days] => 3
                    [cost] => 1000
                )

        )

    [leg2] => Array
        (
            [UPS] => Array
                (
                    [days] => 1
                    [cost] => 4000
                )

            [FedEx] => Array
                (
                    [days] => 1
                    [cost] => 3000
                )

            [Conway] => Array
                (
                    [days] => 2
                    [cost] => 5000
                )

        )

)

كيف يمكنك العثور على أفضل مجموعة برمجياً؟

أفضل محاولتي حتى الآن (الخوارزمية الثالثة أو الرابعة) هي:

1. ابحث عن أطول شاحن لكل ساق
2. القضاء على أغلى واحد
3. ابحث عن أرخص شاحن لكل ساق
4. حساب التكلفة الإجمالية والأيام
5. إذا كانت الأيام مقبولة، أكمل، وإلا انتقل إلى 1

تم تصميمه بسرعة في PHP (لاحظ أن مصفوفة الاختبار أدناه تعمل بشكل جيد، ولكن إذا حاولت ذلك باستخدام مصفوفة الاختبار من الأعلى، فلن تجد المجموعة الصحيحة):

$shippers["leg1"] = array(
    "UPS"    => array("days" => 1, "cost" => 4000),
    "Conway" => array("days" => 3, "cost" => 3200),
    "FedEx"  => array("days" => 8, "cost" => 1000)
);

$shippers["leg2"] = array(
    "UPS"    => array("days" => 1, "cost" => 3500),
    "Conway" => array("days" => 2, "cost" => 2800),
    "FedEx"  => array("days" => 4, "cost" => 900)
);

$shippers["leg3"] = array(
    "UPS"    => array("days" => 1, "cost" => 3500),
    "Conway" => array("days" => 2, "cost" => 2800),
    "FedEx"  => array("days" => 4, "cost" => 900)
);    

$times = 0;
$totalDays = 9999999;

print "<h1>Shippers to Choose From:</h1><pre>";
print_r($shippers);
print "</pre><br />";

while($totalDays > $maxDays && $times < 500){
            $totalDays = 0;
            $times++;
            $worstShipper = null;
            $longestShippers = null;
            $cheapestShippers = null;

            foreach($shippers as $legName => $leg){
                //find longest shipment for each leg (in terms of days)
                unset($longestShippers[$legName]);
                $longestDays = null;        

                if(count($leg) > 1){
                    foreach($leg as $shipperName => $shipper){
                        if(empty($longestDays) || $shipper["days"] > $longestDays){
                            $longestShippers[$legName]["days"] = $shipper["days"];
                            $longestShippers[$legName]["cost"] = $shipper["cost"];
                            $longestShippers[$legName]["name"] = $shipperName;
                            $longestDays = $shipper["days"];
                        }
                    }           
                }
            }

            foreach($longestShippers as $leg => $shipper){
                $shipper["totalCost"] = $shipper["days"] * $shipper["cost"];

                //print $shipper["totalCost"] . " &lt;?&gt; " . $worstShipper["totalCost"] . ";";

                if(empty($worstShipper) || $shipper["totalCost"] > $worstShipper["totalCost"]){
                    $worstShipper = $shipper;
                    $worstShipperLeg = $leg;
                }
            }

            //print "worst shipper is: shippers[$worstShipperLeg][{$worstShipper['name']}]" . $shippers[$worstShipperLeg][$worstShipper["name"]]["days"];
            unset($shippers[$worstShipperLeg][$worstShipper["name"]]);

            print "<h1>Next:</h1><pre>";
            print_r($shippers);
            print "</pre><br />";

            foreach($shippers as $legName => $leg){
                //find cheapest shipment for each leg (in terms of cost)
                unset($cheapestShippers[$legName]);
                $lowestCost = null;

                foreach($leg as $shipperName => $shipper){
                    if(empty($lowestCost) || $shipper["cost"] < $lowestCost){
                        $cheapestShippers[$legName]["days"] = $shipper["days"];
                        $cheapestShippers[$legName]["cost"] = $shipper["cost"];
                        $cheapestShippers[$legName]["name"] = $shipperName;
                        $lowestCost = $shipper["cost"];
                    }
                }

                //recalculate days and see if we are under max days...
                $totalDays += $cheapestShippers[$legName]['days'];  
            }
            //print "<h2>totalDays: $totalDays</h2>";
        }

        print "<h1>Chosen Shippers:</h1><pre>";
        print_r($cheapestShippers);
        print "</pre>";

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

يحرر:للتوضيح، هذه ليست مهمة "واجب منزلي" (أنا لست في المدرسة).إنه جزء من مشروعي الحالي في العمل.

المتطلبات (كما هو الحال دائمًا) تتغير باستمرار.إذا تم إعطائي القيود الحالية في الوقت الذي بدأت فيه العمل على هذه المشكلة، فسأستخدم بعض أشكال خوارزمية A* (أو Dijkstra أو أقصر مسار أو بسيط أو شيء من هذا القبيل).لكن كل شيء كان يتحول ويتغير، وهذا أوصلني إلى ما أنا عليه الآن.

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

Answer 1

يمكن أن يغير بعض خوارزميات المسار الأقصر, ، مثل Dijkstra، لوزن كل مسار حسب التكلفة ولكن أيضًا تتبع الوقت والتوقف عن السير في مسار معين إذا تجاوز الوقت الحد الخاص بك.يجب أن تجد أرخص ما يجعلك تحت عتبة منزلك بهذه الطريقة

Answer 2

يبدو أن ما لديك يسمى "مشكلة البرمجة الخطية".يبدو أيضًا وكأنه مشكلة في الواجب المنزلي، وليس جريمة.

الحل الكلاسيكي لمشكلة LP يسمى "طريقة Simplex".ابحث في جوجل.

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

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

Answer 3

يبدو وكأنه وظيفة ل خوارزمية ديكسترا:

خوارزمية ديكسترا، التي ابتكرها عالم الكمبيوتر الهولندي إدسجر ديكسترا في عام 1959، 1 عبارة عن خوارزمية بحث في الرسم البياني تعمل على حل مشكلة أقصر مسار أحادي المصدر للرسم البياني بتكاليف مسار الحافة غير السالبة، مما يؤدي إلى إخراج شجرة أقصر مسار.تُستخدم هذه الخوارزمية غالبًا في التوجيه.

توجد أيضًا تفاصيل التنفيذ في مقالة ويكيبيديا.

Answer 4

إذا علمت أنه يتعين علي التعامل مع 5 مدن فقط، بترتيب محدد مسبقًا، وأن هناك 3 طرق فقط بين المدن المتجاورة، فسأجبرها على ذلك.لا فائدة من أن تكون أنيقًا.

من ناحية أخرى، إذا كان هذا واجبًا منزليًا وكان من المفترض أن أقوم بإنتاج خوارزمية يمكن أن تتوسع بالفعل، فمن المحتمل أن أتبع نهجًا مختلفًا.

Answer 5

كما قال بالتيمارك، هذه في الأساس مشكلة برمجة خطية.ولو لم تكن معاملات الشاحنين (1 للمضمن، 0 لغير المدرج) أعدادًا صحيحة (ثنائية) لكل طرف، لكان من الأسهل حل هذه المشكلة.أنت الآن بحاجة إلى العثور على بعض استدلالات البرمجة الخطية (ILP) لأن المشكلة صعبة NP.يرى ويكيبيديا على البرمجة الخطية الصحيحة للروابط؛في دورة البرمجة الخطية التي استخدمناها على الأقل فرع وملزمة.

في الواقع الآن بعد أن أفكر في الأمر، هذه الحالة الخاصة قابلة للحل بدون ILP الفعلي حيث أن عدد الأيام لا يهم طالما أنه <= 5.ابدأ الآن باختيار أرخص شركة طيران للاختيار الأول (كونواي 5:1000).بعد ذلك، تختار مرة أخرى الأرخص، وينتج عن ذلك 8 أيام و4000 وحدة عملة وهو مبلغ كبير للغاية، لذا قمنا بإلغاء ذلك.من خلال تجربة الآخرين أيضًا، نرى أن جميعهم ينتجون أيامًا > 5، لذلك نعود إلى الاختيار الأول ونجرب ثاني أرخص (FedEx 2:3000) ثم نرتفع في الثاني وفيديكس في الأخير.وهذا يعطينا إجمالي 4 أيام و9000 وحدة عملة.

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

نأمل أن يكون هذا التجوال ساعد قليلا :).

Answer 6

هذا ال مشكلة الحقيبة.الأوزان هي أيام العبور، ويجب أن يكون الربح 5000 دولار - تكلفة الساق.تخلص من جميع التكاليف السلبية وانطلق من هناك!

Answer 7

أعتقد أن خوارزمية Dijkstra مخصصة لإيجاد أقصر الطرق.

cmcculloh يبحث عن الحد الأدنى من التكلفة مع مراعاة القيد المتمثل في وصوله إلى هناك خلال 5 أيام.

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