مسافر متنقل، الربح الأمثل مع مرور الوقت

Question

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

مقدمة:

أحاول ترميز خوارزمية تجارة متعددة محسنة للربح/الوقت للعبة تتضمن مدن (عقد) متعددة داخل بلدان (مناطق) متعددة، حيث:

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

---

معلمات السؤال:

توجد بالفعل قاعدة بيانات في الذاكرة (python:sqlite) والتي تحتفظ بالصفقات بناءً على المدينة المصدر والمدينة الوجهة، والمدن ذات المسار الأقصر بين المصفوفة والمبلغ، والعامل المحدد مع نسبة العائد على إجمالي رأس المال (أو في حالة عدم وجود أي عامل محدد، عندها فقط الطريقة التي تعطي أعلى عائد على إجمالي رأس المال).

• أحاول العثور على الربح الأمثل لفترة معينة من الوقت (أي.30 دقيقة)
• إن عملية العبور إلى مدينة جديدة هي في الواقع عملية متزامنة
• عادةً ما يستغرق الأمر نفس مقدار الوقت المحدد للتنقل عبر خريطة المدينة (أي.2 دقيقة)
• يستغرق بدء التجارة الأولى أو أي تجارة جديدة نفس الوقت الذي يستغرقه عبور خريطة مدينة واحدة (أي.2 دقيقة)
• قد لا تحتوي نقطة البداية الخاصة بي على صفقة صالحة فعليًا (سأضطر إلى السفر إلى النقطة الأولى/الأقرب/الأفضل)

---

الحل الزائف حتى الآن

تحسين

أولاً، أدرك أنه نظرًا لأن لدي حدًا للوقت الذي تستغرقه، وأعرف المدة التي تستغرقها كل قفزة (بما في ذلك -1 لبدء التداول)، يمكنني قصر الرسم البياني على جميع الصفقات التي تقل قفزاتها عن أو تساويها. max_hops=int(max_time/route_time) -1.لقد قمت بقص عناصر قاعدة البيانات التجارية التي لا تقع ضمن هذا الحد الزمني، مما أدى إلى تقليم المدن التي لديها أقصر مسار أطوال أكبر من max_hops.

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

ثم آخذ الصفقات المتبقية التي ليست كذلك (current_city->starting_city) وإضافة طرق التجارة مع عائد 0٪ بين جميع الوجهات ومدن البداية حيث لا تتجاوز القفزات max_hops

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

بحث الرسم البيانيلقد تركت مع رسم بياني أصغر (كثيرًا) من الصفقات الممكنة خلال المهلة الزمنية (أي.30 دقيقة).

نظرًا لأن كافة العقد المتصلة متجاورة، تكون جميع الاتصالات مرجحة بشكل افتراضي بـ 1.أقوم بتقسيم نسبة العائد على عدد القفزات في التجارة ثم أخذ العكس وأضف + 1 (وهذا يعني وزن 1.01 لمسار العودة بنسبة 100٪).في حالة أن العائد هو 0٪، وأضيف ...2؟

وينبغي بعد ذلك العودة إلى الطريق الأكثر ربحية ...

---

السؤال:

خاصة،

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

2. كيف أعاقب على بدء طريق تجاري جديد؟

3. هل البحث في الرسم البياني مفيد في هذه الحالة؟

في ملحوظة جانبية،

3. ما هي أنواع التحسينات/التحسينات على الرسم البياني التي يجب عليّ (أو لا ينبغي عليّ) إجراؤها؟
4. هل طريقة الوزن الخاصة بي صحيحة؟لدي شعور بأنه سيعطيني أوزانًا غير متناسبة.هل يجب علي استخدام العائد الفعلي بدلاً من نسبة العائد؟
5. إذا كنت أقوم بالترميز باستخدام لغة بايثون، فهناك مكتبات مثل بيثون الرسم البياني مناسبة لاحتياجاتي؟أم أنه سيوفر لي الكثير من النفقات العامة (كما أفهم، يمكن أن تكون خوارزميات البحث في الرسم البياني مكثفة حسابيًا) لكتابة وظيفة متخصصة؟
6. هل أنا أفضل حالًا باستخدام بحث A*؟
7. هل يجب أن أقوم بحساب نقاط المسار الأقصر في قاعدة البيانات التجارية وتحقيق الحد الأقصى من التحسينات أم يجب أن أترك الأمر كله للبحث في الرسم البياني؟
8. هل يمكنك ملاحظة أي شيء يمكنني تحسينه؟

Answer 1

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

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

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

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

وهنا أ وصلة لمشكلة مماثلة في الميزانية الرأسمالية.

حظ سعيد !

Answer 2

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

بدلاً من ذلك، ماذا عن البحث البسيط الموسع أولاً؟

أنشئ قائمة بجميع المدن، وقم بوضع علامة عليها كغير مرغوب فيها

خذ مدينة البداية، وحدد وقت السفر على أنه صفر

for each city: 
  if not finished and travel time <> infinity then 
    attempt to visit all neighbors, only record the time if city is unvisited
  mark the city finished
repeat until all cities have been visited

يا ():تنفذ الحلقة الخارجية المدن * الحد الأقصى لأوقات القفزات.يتم تنفيذ الحلقة الداخلية مرة واحدة لكل مدينة.ليست هناك حاجة لتخصيصات الذاكرة.

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

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

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

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