ضغط الرسم البياني الرياضي

Question

أريد رسم رسم بياني سيكون مثل هذا:النص البديل http://img25.imageshack.us/img25/9786/problemo.png.

يمكنك أن ترى 3 مسارات: A، B & C. كيف يمكنني تغيير موضع العناصر (1،2،3 ...، 9) لجعل الطريق لفترة قصيرة قدر الإمكان؟ أعني أن هذه الخطوط يجب أن تكون قصيرة قدر الإمكان.

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

على سبيل المثال، يجب أن يعمل البرنامج مثل هذا: في الإدخال، يجب أن تحصل على 3 مسارات

A = '1،5،7،7،4،4،2،6' B = '4،2،3،6،9،8،5' C = '7،9'

وفي الإخراج يجب أن تكون إحداثيات هذه العناصر.

Answer 1

كلما كان لدي مشكلة تحسين يصعب حلها، أفكر في الخوارزميات الوراثية. وبعد يتحمل حلاي أدناه أنك على دراية GA (ليس من الصعب جدا تنفيذه بنفسك)

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

00101 00100 11010 11110 11000     
  A     B     C     D     E

حيث يقوم كل جزء بترميز الموضع في الشبكة (في ثنائي) من العقد (بهذا الطلب). يعتمد طول كل جزء على حجم الشبكة (الطول = CEIL (LOG2 (N * N))).
الشبكة هي الصف صف حسب الصف، من اليسار إلى اليمين.

كمثال، للحصول على رسم بياني كامل مع 4 عقد (A، B، C، D) وشبكة 3x3، السلسلة:

0011 0001 0101 1000    =   3  1  5  8 
 A    B    C    D          A  B  C  D

يمثل التخطيط التالي:

. B .       00  01  02
A . C       03  04  05
. . D       06  07  08

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

مثالللتوضيح، النظر في التصميم السابق مع مسافة كتلة المدينة، بالنظر إلى المسارين التاليين: A D C B و C B D A

A -> D -> C -> B
  3  + 1  + 2    = 6        therefore
C -> B -> D -> A              fitness(0011 0001 0101 1000) = 6 + 8 = 14
  2  + 3  + 3    = 8

من الواضح أن الهدف هو العثور على التصميم الذي يقلل من وظيفة اللياقة البدنية.