البحث عن الحد الأدنى من المسار في شجرة مع العقد متعددة القيم

Question

ودروس الرياضيات بلادي هي وراء ذلك بكثير، وأنا أعاني حاليا من أجل إيجاد حل لائق لمشكلة أواجه: لدي شجرة، في أي العقد هي الإجراءات، وهي "مرجح" وفقا لمعايير متعددة: تكلفة العمل قال، في الوقت الذي ستستغرقه، والموارد اللازمة، واضطراب، الخ ...

واريد ان تجد في هذه الشجرة المسار الذي يقلل كل من التكلفة والوقت على سبيل المثال، أو اضطراب والتكلفة والوقت، الخ مشكلتي هي أن ليس لدي أي فكرة عن كيفية القيام بذلك، باستثناء قبل الخروج مع F العالمي دالة التكاليف (التكلفة والوقت والموارد، ...)، وتطبيق خوارزمية شجرة اجتياز العادية باستخدام نتيجة من F (...) وزني الوحيد. ولكن بعد ذلك، كيف يمكنني الخروج مع F؟ شيء من هذا القبيل "F (التكلفة والوقت والموارد) = تكلفة * + ب * وقت + ج * موارد" يشعر جدا "غير مهني" ...

وتحرير:

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

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

ولذا أعتقد سؤالي هو في الحقيقة، فإنه هناك منهجية لاختيار تلك الوظيفة؟

وشكرا لإجابات وتعليقاتكم، وانها بدأت في أن يكون قليلا أكثر وضوحا في رأسي الآن.

Answer 1

ودعونا نقول لدينا أربعة أزواج (س، ص) مثل (1، 4)، (5، 1)، (2، 3)، (3، 3). الآن كنت ترغب في تقليل "كلا x و y". ماذا تقصد بذلك؟ إذا كنت تقليل س أولا ثم ذ ينتهي بك الأمر مع (1، 4). إذا قمت بتصغير أولا ذ ثم س تجد (2، 3).

وإذا لم اخترت وظيفة التكلفة العالمية F (X، Y)، كما هو الحال في ملاحظتكم، لا أستطيع أن أرى أي معنى "كلا". (على أي حال، حالما يتم اختيار F، قد يكون لا يزال هناك العديد من الحد الأدنى نقطة). وبالمناسبة، في رأيي مزيج الخطي (مضاعفات إيجابية أ، ب، ج أن يكون مفهوما بأنه "الأوزان") ليست "غير مهني" على الإطلاق على الأقل إذا كان لديك أي فكرة عما يمكن أن تكون وظيفة أكثر تكلفة مناسبة.

وتحرير:

<اقتباس فقرة>   

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

والحذر. في الواقع هذه الاستراتيجية منطقية إلا إذا F غير الخطية. بالتأكيد التكلفة والوقت والموارد وما هي الوظائف المضافة، بمعنى أن الزمن (NODE1 -> NODE2 -> node3) = وقت (NODE1) + الوقت (NODE2) + الوقت (node3)، ولكن بشكل عام ليست هذه هي القضية لF، ما لم تكن خطية. (أي F (التكلفة (NODE1 -> NODE2)) = F (التكلفة (NODE1) + تكلفة (NODE2)) = F (التكلفة (NODE1)) + F (التكلفة (NODE2)))

إذا اخترت وظيفة التكلفة العالمية غير الخطية، الاستراتيجية الصحيحة هي لحساب، لكل عقدة، فإن التكلفة الإجمالية، والوقت الكلي، مجموع الموارد من الجذر إلى تلك العقدة، وحساب (ثم تصغير) F فقط للمحطة العقد.

Answer 2

والخروج مع F هو الشيء الأكثر أهمية. إذا وأستطيع أن أعطي لكم 6 التكلفة والوقت أو 5 5 الوقت و 6 التكلفة، والتي تفضل؟ تحتاج وظيفة الكلفة أن يأخذ ذلك في الاعتبار. لا يوجد خوارزمية أن يجري حل هذه المشكلة بالنسبة لك، لسوء الحظ. I نفى ان تكون لمدة أسبوع قبل أن جلس وكتب F لتطبيق الأمثل كنت أعمل على. أسوأ الحالات، وترك المعلمات للمستخدم للعب مع.

Answer 3

لماذا لن رسم بياني العادية خوارزمية البحث مثل وهناك عمل *؟

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

وو<م> قد تكون المسافة إلى أقرب ورقة، قبل احتساب لجميع أو بعض العقد، على الرغم من أن هذا يبدو بفظاعة باهظة الثمن. اعتمادا على هيكل شجرة الخاص بك، هل يمكن التوصل إلى أرخص تحت تقدير - لو كان متوازن تماما، على سبيل المثال، انها تافهة