كيفية العثور على أقرب متجه في {0,1,2}^12، مرارًا وتكرارًا

Question

أنا أبحث في مساحة من المتجهات بطول 12، مع الإدخالات 0، 1، 2.على سبيل المثال، أحد هذه المتجهات هو
001122001122.لدي حوالي ألف ناقل جيد، وحوالي ألف ناقل سيئ.لكل ناقل سيئ أحتاج إلى تحديد أقرب ناقل جيد.المسافة بين متجهين هي مجرد عدد الإحداثيات غير المتطابقة.المتجهات الجيدة ليست مرتبة بشكل جيد، وسبب كونها "جيدة" لا يبدو مفيدًا هنا.أولويتي الرئيسية هي أن تكون الخوارزمية سريعة.

إذا قمت بإجراء بحث شامل وبسيط، يجب أن أحسب حوالي 1000*1000 مسافة.هذا يبدو غليظ الرأس.

إذا قمت بتطبيق خوارزمية ديكسترا أولاً باستخدام المتجهات الجيدة، فيمكنني حساب أقرب متجه وأقل مسافة لكل متجه في الفضاء، بحيث يتطلب كل متجه سيئ بحثًا بسيطًا.لكن الفضاء يحتوي على 3^12 = 531,441 متجهًا، لذا فإن الحساب المسبق هو نصف مليون حساب مسافة.ليس الكثير من المدخرات.

هل يمكنك مساعدتي في التفكير بطريقة أفضل؟

يحرر:بما أن الناس سألوا بجدية ما الذي يجعلهم "صالحين":يمثل كل متجه وصفًا لصورة سداسية لستة مثلثات متساوية الأضلاع، وهي صورة ثنائية الأبعاد لترتيب ثلاثي الأبعاد للمكعبات (فكر في Q-bert المعمم).المثلثات متساوية الأضلاع هي أنصاف وجوه مكعبات (45-45-90) مائلة في المنظور.ستة من الإحداثيات تصف طبيعة المثلث (الأرضية المدركة، الجدار الأيسر، الجدار الأيمن)، وستة إحداثيات تصف طبيعة الحواف (الاستمرارية المدركة، نوعان من عدم الاستمرارية المدركة).المتجهات الجيدة الـ 1000 هي تلك التي تمثل الأشكال السداسية التي يمكن رؤيتها عند رؤية المكعبات من منظورها الصحيح.سبب البحث هو تطبيق التصحيحات المحلية على خريطة سداسية مليئة بالمثلثات...

Answer 1

هذا يشبه إلى حد كبير ما يتعين على المبيدات الإملائية القيام به. الخدعة عمومًا لإساءة الاستخدام يحاول.

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

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

لا توجد ضمانات صحيحة ، لأن كل من الخوارزمية والرمز خارج عن أعلى رأسي:

var goodTrie = new Trie(goodVectors)
var badTrie = new Trie(badVectors)
var result = new Map<Vector, Vector>()
var pq = new PriorityQueue(x => x.error)
pq.add(new {good: goodTrie, bad: badTrie, error: 0})
while pq.Count > 0
  var g,b,e = q.Dequeue()
  if b.Count == 0: 
      //all leafs of this path have been removed
      continue
  if b.IsLeaf:
      //we have found a mapping with minimum error for this bad item
      result[b.Item] = g.Item
      badTrie.remove(b) //prevent redundant results
  else:
      //We are zipping down the tries. Branch to all possibilities.
      q.EnqueueAll(from i in {0,1,2}
                   from j in {0,1,2}
                   select new {good: g[i], bad: b[j], error: e + i==j ? 0 : 1})

return result   

قد يكون التحسين النهائي هو إعادة طلب المتجهات ، لذا فإن المواقف ذات الاتفاق العالي بين المتجهات السيئة تأتي أولاً وتبادل المزيد من العمل.

Answer 2

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

رمز في الرياضيات:

bad = Table[RandomInteger[5, 12], {1000}];
good = Table[RandomInteger[2, 12], {1000}];
distance[a_, b_] := Total[Sign@Abs[a - b]];

bestMatch = #[[2]] & /@ 
   Position[
    Table[Ordering@
      Table[distance[good[[j]], bad[[i]]], {j, Length@good}], {i, 
      Length@bad}], 1] // Timing

كما قد تتوقع ، يتبع الوقت قانون O (n^2):

Answer 3

3^12 ليست مساحة بحث كبيرة جدًا. إذا كانت السرعة ضرورية وعمومية الخوارزمية ليست كذلك ، فيمكنك فقط تعيين كل متجه إلى int في النطاق 0..531440 واستخدامه كفهرس في جدول مسبق من "أقرب متجهات جيدة".

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

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

Answer 4

هندسي الحسابي خشن للغاية ، لكن يبدو أنك يجب أن تكون قادرًا على:

1. حساب مخطط Voronoi لمجموعة من المتجهات الجيدة.
2. حساب شجرة BSP لخلايا الرسم البياني.

سيعطيك مخطط Voronoi بدن محدب 12 عامًا لكل متجه جيد يحتوي على أن جميع النقاط الأقرب إلى هذا المتجه.

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

تحرير: لقد لاحظت للتو أنك تستخدم مسافات الهلام بدلاً من مسافات إقليدية. لست متأكدًا من كيفية تكييف هذا لتناسب هذا القيد. آسف.

Answer 5

بافتراض وجود تمثيل مكتظ للمتجهات، يمكن إكمال حساب مسافة واحدة (مقارنة متجه جيد ومتجه سيء ​​للحصول على المسافة) في حوالي 20 دورة ساعة أو أقل.ومن ثم يمكن إجراء مليون عملية حسابية للمسافة في 20 مليون دورة أو (بافتراض وحدة معالجة مركزية بسرعة 2 جيجا هرتز) في 0.01 ثانية.هل تساعد هذه الأرقام؟

ملاحظة: - 20 دورة هي مبالغة في التقدير.