العثور على "أكبر" كثيفة الفرعية مصفوفة كبيرة sparse matrix

Question

ونظرا كبير متفرق مصفوفة (أقول 10k+ قبل 1M+) أنا بحاجة إلى العثور على مجموعة فرعية ، وليس بالضرورة المستمر من الصفوف والأعمدة التي تشكل كثيفة مصفوفة (جميع العناصر غير الصفر).أريد هذا الفرعية مصفوفة أن تكون كبيرة بقدر الإمكان (لا أكبر مبلغ ، ولكن أكبر عدد من العناصر) في بعض جوانب نسبة القيود.

هل هناك أي معروف بالضبط أو aproxamate حلول لهذه المشكلة ؟

فحص سريع على جوجل يبدو أن تعطي الكثير من قريبة-لكن-لا-بالضبط النتائج. ما هي الشروط التي يجب أن تبحث عنه ؟

---

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

---

الفكر استنادا إلى تشاد Okere فكرة

1. ترتيب الصفوف من أكبر عد إلى أصغر عدد (ليس ضروري ولكن قد تساعد perf)
2. اختيار اثنين من الصفوف التي تحتوي على "كبير" التداخل
3. إضافة جميع الصفوف الأخرى التي لن تقلل من التداخل
4. سجل مجموعة
5. إضافة كل ما صف يقلل من التداخل الأقل
6. كرر في #3 حتى النتيجة يحصل الصغيرة
7. البدء من جديد في #2 مع انطلاق مختلفة زوج
8. تستمر حتى تقرر النتيجة جيدة بما يكفي

Answer 1

أفترض أنك تريد شيئا من هذا القبيل.لديك مصفوفة مثل

1100101
1110101
0100101

تريد الأعمدة 1,2,5,7 و الصفوف 1 و 2, صحيح ؟ أن submatrix أن 4x2 مع 8 عناصر.أو هل يمكن أن تذهب مع الأعمدة 1,5,7 مع صفوف 1,2,3 التي من شأنها أن تكون مصفوفة 3x3.

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

لذا أعلاه مصفوفة, إذا كنت وأضاف 1,1 و 2,2 سيكون لديك الصفوف 1 و 2 و الأعمدة 1,2 في جمع الخاصة بك.إذا حاولت إضافة 3,7 من شأنه أن يسبب مشكلة لأن 1,3 هو صفر.لذلك لا يمكنك إضافته.هل يمكن إضافة 2,5 و 2,7 على الرغم من.إيجاد 4x2 submatrix.

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

ثم تتوقف فقط عندما كنت لا يمكن العثور على أي أكثر من ذلك بعد حين.

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

Answer 2

هل هذا نيتفليكس المشكلة?

MATLAB أو متفرق مصفوفة المكتبات قد طرق التعامل معها.

هو القصد الخاص إلى الكتابة الخاصة بك ؟

ربما 1D نهج لكل صف من شأنها أن تساعدك.الخوارزمية قد تبدو مثل هذا:

1. حلقة أكثر من كل صف
2. تجد المؤشر الأول غير الصفر عنصر
3. تجد مؤشر غير الصفر صف عنصر مع أكبر span بين غير الصفر الأعمدة في كل صف و متجر على حد سواء.
4. فرز الصفوف من الأكبر إلى الأصغر span بين غير الصفر الأعمدة.

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

لا يمكنك تحديد ما إذا كان أو لم يكن كثيفة المصفوفة يجب أن يكون مربع.سأفترض لا.

أنا لا أعرف مدى كفاءة هذا أو ما Big-O قد يكون السلوك.ولكن هذا أسلوب القوة الغاشمة أن تبدأ مع.

Answer 3

تحرير.هذا ليس نفس المشكلة أدناه..بلدي سيئة...

ولكن على أساس آخر التعليق أدناه ، قد يكون equivilent التالية:

1. العثور على أبعد عموديا فصل الزوج من نقطة الصفر التي لا نقطة الصفر بينهما.
2. العثور على أبعد أفقيا فصل الزوج من نقطة الصفر التي لا الأصفار بينهما ؟

3. ثم الأفقي المنطقة تبحث عنه هو المستطيل الذي يناسب بين هذه اثنين من أزواج من النقاط ؟

   هذه المشكلة بالضبط يتم مناقشتها في جوهره من كتاب بعنوان "البرمجة اللؤلؤ" من قبل جون بنتلي ، ، ، على ما أذكر ، على الرغم من أن هناك حل في بعد واحد, ليس هناك إجابة سهلة عن 2-د أو أعلى الأبعاد المتغيرات ...

1=D المشكلة بشكل فعال ، والعثور على أكبر مبلغ من متجاورة فرعية من مجموعة من الأرقام:

من خلال تكرار العناصر تتبع ما مجموعه تشغيل محدد السابقة عنصر ، والحد الأقصى المجموع الفرعي رأيت حتى الآن (و بداية و نهاية elemnt أن generateds ذلك)...في كل عنصر ، إذا maxrunning المجموع أكبر من الحد الأقصى الكلي رأيت حتى الآن ، ماكس حتى الآن و endelemnt يتم إعادة تعيين...إذا كان ماكس تشغيل إجمالي يذهب تحت الصفر ، بداية عنصر إعادة تعيين إلى العنصر الحالي و تشغيل مجموعه إعادة تعيين إلى الصفر ...

2-D المشكلة جاءت من محاولة توليد البصرية خوارزمية معالجة الصور التي تحاول أن تجد داخل تيار brightnesss القيم تمثل بكسل في 2-صورة ملونة, العثور على "ألمع" مساحة مستطيلة الشكل في الصورة.أي تجد الواردة 2-D الفرعية مصفوفة مع أعلى مجموع قيم السطوع ، حيث "سطوع" كان يقاس الفرق بين بكسل brighness قيمة المتوسط العام سطوع الصورة بأكملها (الكثير من عناصر القيم السلبية)

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

Answer 4

أنا أعلم أنك لا تعمل على هذا بعد الآن, ولكن اعتقد شخص ما قد يكون نفس السؤال لي في المستقبل.

حتى بعد تحقيق هذا NP-hard المشكلة (عن طريق تخفيض ماكس-زمرة) قررت أن تأتي مع الكشف عن مجريات الأمور التي عملت بشكل جيد بالنسبة لي حتى الآن:

نظرا N x م ثنائي/منطقية مصفوفة, العثور على مجموعة كبيرة كثيفة submatrix:

الجزء الأول:توليد معقول المرشح submatrices

1. النظر في كل من N الصفوف أن تكون م-ثنائي الأبعاد مكافحة ناقلات ، v_i, حيث أنا=1 N
2. حساب مسافة مصفوفة N ناقلات باستخدام المبالغة المسافة
3. استخدام UPGMA (مرجحة زوج مجموعة الأسلوب مع المتوسط الحسابي) خوارزمية مجموعة ناقلات

في البداية, كل v_i ناقلات هو المفرد العنقودية.الخطوة 3 أعلاه (تجميع) يعطي الأمر أن ناقلات يجب أن تكون مجتمعة في submatrices.لذلك كل عقدة الداخلية في الهرمية تجميع شجرة مرشح submatrix.

الجزء الثاني:درجة ورتبة المرشح submatrices

1. لكل submatrix, حساب D, عدد من عناصر كثيفة فرعية من إتجاه submatrix من خلال القضاء على أي عمود مع واحد أو أكثر من الأصفار.
2. حدد submatrix يزيد D

كما كان بعض الاعتبارات المتعلقة دقيقة عدد الصفوف التي ينبغي الحفاظ عليها من الأولي مصفوفة كاملة ، وأود أن تجاهل أي مرشح submatrices التي لا تلبي هذه المعايير قبل اختيار submatrix مع ماكس D القيمة.