خوارزمية لإيجاد نقطتين أبعد من بعضها البعض

Question

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

• خوارزمية العمل داخل ثنائية الأبعاد في الفضاء
• من كل نقطة واحدة فقط يمكن أن تعبر إلى النقطة التالية في الاتجاهات الأربعة ؛ أعلى والأسفل واليسار واليمين
• نقاط يمكن أن تكون إما محجوبة أو nonblocked فقط nonblocked نقاط يمكن اجتيازه

بخصوص حساب المسافة فإنه لا ينبغي أن يكون "الطيور مسار" لعدم وجود كلمة أفضل.الطريق بين A و B يجب أن تكون أطول إذا كان هناك جدار (أو غيرها من حجب المنطقة) بينهما.

ايم متأكد من أين تبدأ التعليقات هي موضع ترحيب للغاية و الحلول المقترحة هي المفضلة في البرمجية الزائفة.

تحرير: صحيح.بعد النظر من خلال ع قانون أعطيته فرصة أخرى.بدلا من بيثون ، أنا هذه المرة كتب في C++.ولكن لا يزال حتى بعد القراءة على Dijkstras الخوارزمية, ، floodfill و حسام Alys الحل, لقد فشلت في أي بقعة الفرق.قانون بلدي لا يزال يعمل ، ولكن ليس بالسرعة التي يبدو أن يكون الحصول على لك لتشغيل.المصدر الكامل على باسط.فقط مثيرة للاهتمام خطوط (أعتقد) هو البديل الخاص ديكسترا نفسها على خطوط 78-118.

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

• في حسام Alys الخوارزمية هو الفرق الوحيد أنه مسح من الحدود بدلا من كل عقدة?
• في Dijkstras تتبع والكتابة مشى مسافة ، ولكن ليس في floodfill ولكن هذا عن ذلك ؟

Answer 1

على افتراض الخريطة مستطيلة ، يمكنك حلقة على جميع النقاط الحدودية والبدء في ملء الفيضانات إلى العثور على نقطة أبعد من نقطة البداية:

bestSolution = { start: (0,0), end: (0,0), distance: 0 };
for each point p on the border
    flood-fill all points in the map to find the most distant point
    if newDistance > bestSolution.distance
        bestSolution = { p, distantP, newDistance }
    end if
end loop

أعتقد أن هذا سيكون في O(n^2).إذا لم أكن مخطئا, انها (L+W) * 2 * (L*W) * 4, حيث L هو طول ، W هو عرض الخريطة ، (L+W) * 2 يمثل عدد من النقاط الحدودية على محيط ، (L*W) هو عدد من النقاط ، 4 هو افتراض أن الفيضانات ملء أن الوصول إلى نقطة كحد أقصى 4 مرات (من جميع الاتجاهات).منذ n يعادل عدد النقاط ، وهذا هو ما يعادل (L + W) * 8 * n, الذي ينبغي أن يكون أفضل من O(n²).(إذا كانت الخريطة مربع ، سيكون O(16n^1.5).)

تحديث: كما في التعليقات ، منذ الخريطة أكثر من متاهة (من واحد مع بسيطة العقبات كما كنت أفكر في البداية), هل يمكن جعل نفس المنطق أعلاه ، ولكن التحقق من جميع النقاط في الخريطة (بدلا من النقاط على الحدود فقط).هذا ينبغي أن يكون في أمر من O(4n²), الذي لا يزال أفضل من كل و-W و الخاص ديكسترا.

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

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

P. S.أي تعليقات أو تصويبات هي موضع ترحيب.

Answer 2

متابعة السؤال عن فلويد-Warshall أو خوارزمية بسيطة من حسام علي:

أنا خلقت اختبار البرنامج الذي يمكن استخدام كلتا الطريقتين.هذه هي الملفات:

• متاهة الخالق
• العثور على أطول مسافة

في جميع حالات الاختبار فلويد-Warshall كان كبير الحجم أبطأ, ربما هذا بسبب كمية محدودة جدا من حواف أن تساعد هذه الخوارزمية لتحقيق ذلك.

هذه هي الأيام في كل مرة كان مجال توائم و 3 من 10 حقول عقبة.

Size         Hosam Aly      Floyd-Warshall
(10x10)      0m0.002s       0m0.007s     
(20x20)      0m0.009s       0m0.307s
(40x40)      0m0.166s       0m22.052s
(80x80)      0m2.753s       -
(160x160)    0m48.028s      -

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

PS:أنا لم أكتب C أو C++ في وقت طويل ، أتمنى أنني لم ارتكب أخطاء كثيرة جدا.

Answer 3

حذف المشاركة الأصلية التوصية فلويد-Warshall الخوارزمية.:(

ع لم واقعية القياسي وتخمين ما, F-W أبطأ بكثير من حسام علي في "ملء الفيضانات" خوارزمية نموذجية خريطة الأحجام!حتى على الرغم من F-W هو بارد خوارزمية أسرع بكثير من الخاص ديكسترا كثيفة من الرسوم البيانية ، لا أستطيع أن أوصي به بعد الآن OP المشكلة التي ينطوي ضئيلة جدا البيانية (كل قمة لديه فقط 4 حواف).

للعلم:

• كفاءة تنفيذ الخاص ديكسترا الخوارزمية يأخذ O(Elog V) الوقت على الرسم البياني مع ه حواف V القمم.
• حسام علي في "ملء الفيضانات" هو اتساع البحث الأولى, التي O(V).هذا ويمكن اعتبار حالة خاصة من الخاص ديكسترا الخوارزمية التي لا vertex يمكن أن يكون لها مسافة التقديرات المنقحة.
• على فلويد-Warshall الخوارزمية يأخذ O(V^3) الوقت من السهل جدا أن قانون و لا يزال أسرع كثيفة من الرسوم البيانية (تلك الرسوم البيانية حيث القمم عادة ما تكون مرتبطة إلى العديد من القمم الأخرى).لكنه ليس الخيار الصحيح بالنسبة OP المهمة التي ينطوي ضئيلة جدا البيانية.

Answer 4

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

عن مستطيل المتاهة ، وهذا يعني أن اثنين من الفيضانات يملأ يجب أن تحصل جيدة زوج من نقطة البداية والنهاية.

Answer 5

رايموند زايدل يعطي طريقة بسيطة باستخدام مصفوفة الضرب لحساب جميع أزواج مصفوفة المسافة على مرجحة ، صليات الرسم البياني (وهو بالضبط ما تريد) في القسم الأول من الورقة على جميع أزواج-أقصر مسار المشكلة في مرجحة صليات الرسوم البيانية [pdf].

المدخلات هي مصفوفة الجوار و إخراج جميع أزواج أقصر مسار مصفوفة المسافة.تشغيل الوقت O(M(n)*log(n)) ن حيث م نقطة(n) هو وقت التشغيل الخاص بك مصفوفة الضرب الخوارزمية.

الورقة أيضا يعطي طريقة الحوسبة الفعلية مسارات (في نفسه) إذا كنت بحاجة إلى هذا أيضا.

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

هنا هو شبة الكود:

Let A be the nxn (0-1) adjacency matrix of an unweighted, undirected graph, G

All-Pairs-Distances(A)
    Z = A * A
    Let B be the nxn matrix s.t. b_ij = 1 iff i != j and (a_ij = 1 or z_ij > 0)
    if b_ij = 1 for all i != j return 2B - A //base case
    T = All-Pairs-Distances(B)
    X = T * A
    Let D be the nxn matrix s.t. d_ij = 2t_ij if x_ij >= t_ij * degree(j), otherwise d_ij = 2t_ij - 1
    return D

للحصول على زوج من النقاط مع أكبر مسافة نعود فقط argmax_ij(d_ij)

Answer 6

الانتهاء من الثعبان نموذج بالحجم الطبيعي من الخاص ديكسترا حل المشكلة.رمز حصلت قليلا طويلة لذا نشرت في مكان آخر: http://refactormycode.com/codes/717-dijkstra-to-find-two-points-furthest-away-from-each-other

في حجم تعيين, يستغرق حوالي 1.5 ثانية لتشغيل خوارزمية عقدة واحدة.تشغيله على كل عقدة يستغرق بضع دقائق.

لا يبدو أن العمل على الرغم من أنه يعرض دائما topleft و bottomright ركن أطول الدرب ؛ 58 البلاط.والتي بالطبع هو صحيح ، عندما لم يكن لديك العقبات.ولكن حتى إضافة بضع وضعت بشكل عشوائي منها, البرنامج لا يزال يجد أن أحد أطول.ربما لا يزال صحيحا إلى من دون الأشكال الأكثر تقدما.

ولكن ربما يمكن على الأقل تظهر طموحي.

Answer 7

حسنا, "حسام خوارزمية" هو اتساع البحث الأول مع الاختيار الأولي على العقد.الخاص ديكسترا خوارزمية لا ينبغي أن تطبق هنا ، لأن حواف الخاصة بك لم يكن لديك الأوزان.

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

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

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

لذا وسيلة جيدة للقيام بذلك هو استخدام اتساع البحث الأول من كل جهة ، ولكن إزالة نقطة البداية بعد البحث (كنت تعرف بالفعل كل الطرق المؤدية إلى ذلك).تعقيد واتساع أول O(n) حيث n = V |+|E|.ونحن نفعل ذلك مرة واحدة كل عقدة في الخامس حتى يصبح O(n^2).

Answer 8

الوصف يبدو لي وكأنه متاهة التوجيه المشكلة.تحقق من لي الخوارزمية.كتب عن المكان و الطريق المشاكل في VLSI التصميم قد تساعدك - زوجات في "خوارزميات VLSI التصميم المادي الآلي" هو جيد ، VLSI التصميم المادي الآلي عن طريق سيت و يوسف فائدة (و أرخص في جوجل الإصدار...)

Answer 9

إذا كانت الكائنات (نقطة) لا تتحرك في كثير من الأحيان يمكنك تنفيذ مثل هذا الحساب في أقصر بكثير من O(n^3) الوقت.

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

هذا الحل يعمل إذا كانت المسافة المقاييس المستمر.وهكذا إذا كان, فعلى سبيل المثال هناك العديد من الحواجز في الخريطة (كما في متاهات), هذه الطريقة قد تفشل.