ما هي الطريقة الأكثر فعالية من العثور على المسار من خلال عالم صغير البيانية ؟

Question

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

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

(وي:يمكن أن الشبكات العصبية أن تستخدم هنا؟)

شكرا

---

أنا أبحث في ACO.هل هناك أي شيء أفضل من ACO لهذا النوع من المشكلة ؟

---

الحق A* خوارزمية يجد الأقل تكلفة أو أسرع الطرق, دون تحميل موازنة.

دعونا نقول أن أسرع أو أقصر طريق هو الطريق الأكثر أهمية, ما هو أكثر أهمية هو اتباع المسار حيث مرجح العقد لها قيمة معينة.no1.

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

- إلا إذا im مخطئا ويساء فهمها A*

ثم ما يدق ACO?

---

يبدو حقا مثل عرض بين ACO و* ، كان هناك الكثير من الحديث الإيجابي عن* أنا سوف بالتأكيد نظرة أعمق في ذلك.

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

سوف البحوث* المزيد.ولكن أترككم مع السؤال الأخير!

سوف* أن يكون قادرا على نطاق واسع فضلا عن Antnet (ACO)?

Answer 1

ملاحظات عامة

الخاص ديكسترا خوارزمية وهو البديل الأمثل A* العثور على المسار مع "إن" الحد الأدنى من التكلفة من خلال الرسم البياني الخاص بك.الأشياء المهمة هي أ) تعريف الرسم البياني الخاص بك بشكل صحيح و ب) تحديد تكلفة مناسب وظيفة.

في مواجهة تغيير تكلفة وظيفة Dijksta يتطلب إعادة حساب الحل.

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

مستعمرة النمل الأمثل من ناحية أخرى يبدو أن تكون أكثر مرونة في التكيف مع تغير تكلفة وظيفة ، من خلال استمرار التكرار بعد/في حين أن تكلفة وظيفة التغييرات.

الكفاءة

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

Answer 2

مع* مسار التكلفة لا تحتاج إلى أن تكون ثابتة ، لذلك يمكن أن تبدأ مع الرسم البياني التالي:

A---1---B---1---C
|               |
\-------1-------/

أين نريد أن نذهب من A إلى C.في البداية, طريق إيجاد خوارزمية اختيار A-C المسار منذ أ-ب-ج 2 في حين أن-ج 1.ونحن يمكن أن تضيف إضافية الأجل إلى مسارات:

A---r---B---r---C
|               |
\-------r-------/

مع

r(NM) = k(NM) + users(NM) / 10

حيث

r(NM) is the cost for a connection between N and M,
k(NM) is the constant cost for a connection between N and M,
users(NM) is the number of objects using the connection

كما إضافة المستخدمين إلى النظام, الطريق A-C سوف تصبح أكثر تكلفة من A-B-C في العشرين من المستخدمين (1 + 20/10) = 3 ، A-B-C 2.كما المستخدمين يتم إزالتها من نظام ، A-C الطريق سوف تصبح الخيار الأفضل مرة أخرى.

القوة الحقيقية A* هو ارشادي كنت تستخدم حساب تكلفة كل اتصال.

Answer 3

الخوارزمية الأكثر استخداما لهذه المشكلة A* (نجمة), وهو المعمم الخاص ديكسترا الخوارزمية البحث مع إضافة الاستدلال - الغرض من الاستدلال هو توجيه البحث نحو البحث عن الهدف بحيث نموذجية البحث الانتهاء بشكل أسرع.

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

Answer 4

بالتأكيد*.أ* إما العثور على أفضل مسار ممكن أو أي مسار في كل حال لا وجود المسار.E. g.مسار هذا القارب قد تم حسابها باستخدام*

_{(المصدر: cokeandcode.com)}

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

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

الخوارزمية يمكن وصفه

1. اسمحوا ف تكون نقطة انطلاق
2. تعيين g, h, f قيم P
3. إضافة P لفتح قائمة (في هذه النقطة P هو إلا عقدة في القائمة).
4. اسمحوا ب يكون أفضل عقدة من فتح قائمة (أفضل == أدنى قيمة f)
   • إذا كان B هو الهدف عقدة -> إنهاء وجدت الطريق
   • إذا فتح القائمة فارغة -> الإقلاع عن التدخين ، لا وجود المسار
5. اسمحوا C تكون صالحة عقدة اتصال ب
   • تعيين ز ، ح ، و أن ج
   • تحقق مما إذا كان C هو على فتح أو إغلاق قائمة
     • إذا كان الجواب نعم, تحقق ما إذا كان مسار جديد هو الأكثر كفاءة (أقل من f-value)
       • إذا كان الأمر كذلك, تحديث المسار
     • آخر إضافة إلى فتح قائمة
   • كرر الخطوة 5 على كافة العقد متصلا ب
6. إضافة B إلى قائمة مغلقة (نحن استكشاف جميع الجيران)
7. كرر الخطوة 4.

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

Answer 5

لقد سمعت من NN تنفيذ للتعامل مع هذا النوع من المشكلة.حتى إذا كنت ترغب في استخدام NNs في نهاية المطاف سوف تجد طريقك ;-) ولكن يجب أن تكون أقل شأنا بالمقارنة مع "الخوارزميات الجينية".

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

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

Answer 6

أن المشترك الخاص ديكسترا لا تكون كافية ؟

http://improve.dk/generic-dijkstras-algorithm/

Answer 7

Dijkstras الخوارزمية ، مثال صغير بالنسبة لك

graph = {}

graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["finish"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["finish"] = 5
graph["finish"] = {}

infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["finish"] = infinity
print "The weight of each node is: ", costs

parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["finish"] = None

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

node = find_lowest_cost_node(costs)
print "Start: the lowest cost node is", node, "with weight",\
    graph["start"]["{}".format(node)]

while node is not None:
    cost = costs[node]
    print "Continue execution ..."
    print "The weight of node {} is".format(node), cost
    neighbors = graph[node]
    if neighbors != {}:
        print "The node {} has neighbors:".format(node), neighbors
    else:
        print "It is finish, we have the answer: {}".format(cost)
    for neighbor in neighbors.keys():
        new_cost = cost + neighbors[neighbor]
        if costs[neighbor] > new_cost:
            costs[neighbor] = new_cost
            parents[neighbor] = node
    processed.append(node)
    print "This nodes we researched:", processed
    node = find_lowest_cost_node(costs)
    if node is not None:
        print "Look at the neighbor:", node

# to draw graph
import networkx
G = networkx.Graph()
G.add_nodes_from(graph)
G.add_edge("start", "a", weight=6)
G.add_edge("b", "a", weight=3)
G.add_edge("start", "b", weight=2)
G.add_edge("a", "finish", weight=1)
G.add_edge("b", "finish", weight=5)

import matplotlib.pyplot as plt
networkx.draw(G, with_labels=True)
plt.show()

print "But the shortest path is:", networkx.shortest_path(G, "start", "finish")