cpdebugger
New member
אלגוריתם מאתגר
שלום רב מצ"ב קובץ JPG המכיל דוגמא מטריצה בולאנית (שיושבת כולה בזכרון) מהסוג שאני מקבל כקלט. (המימוש לא משנה – יש גישה לכל תא ופונקציות שימושיות שכתבתי). תא ריק ערכו – 0 ותא שיש בו X ערכו -1 . בלוק מוגדר כריבוע התחום בין שתי שורות ROW1, ROW2 ובין שני טורים COL1, COL2 במטריצה. בלוק בלתי תלוי מורכב מ – X ים כך שלכל X ששייך לבלוק ערכי row,col ROW1 <= row<= ROW2 COL2<= col <= COL1 בהתעלם כרגע משתי נקודות בעיתייות 13,28 ו 9,28, יש לי אלגוריתם פשוט המזהה את הבלוקים הבלתי תלויים במטריצה: האלגוריתם יזהה את: בלוק ראשון תחום ע"י 1,1-5,6 בלוק שני תחום ע"י 6,7-11,11 בלוק שלישי (המלא) תחום ע"י 12,12-19,17 בלוק רביעי תחום ע"י 20,18-40,37 האלגוריתם בפסאודו קוד.
שלום רב מצ"ב קובץ JPG המכיל דוגמא מטריצה בולאנית (שיושבת כולה בזכרון) מהסוג שאני מקבל כקלט. (המימוש לא משנה – יש גישה לכל תא ופונקציות שימושיות שכתבתי). תא ריק ערכו – 0 ותא שיש בו X ערכו -1 . בלוק מוגדר כריבוע התחום בין שתי שורות ROW1, ROW2 ובין שני טורים COL1, COL2 במטריצה. בלוק בלתי תלוי מורכב מ – X ים כך שלכל X ששייך לבלוק ערכי row,col ROW1 <= row<= ROW2 COL2<= col <= COL1 בהתעלם כרגע משתי נקודות בעיתייות 13,28 ו 9,28, יש לי אלגוריתם פשוט המזהה את הבלוקים הבלתי תלויים במטריצה: האלגוריתם יזהה את: בלוק ראשון תחום ע"י 1,1-5,6 בלוק שני תחום ע"י 6,7-11,11 בלוק שלישי (המלא) תחום ע"י 12,12-19,17 בלוק רביעי תחום ע"י 20,18-40,37 האלגוריתם בפסאודו קוד.
blocks = FindFirstlevelBlocks(m){ if (m==0){ // all elements of m are zeros blocks = struct(); // create an empty structure return; } row_ind = no. of the row that has the maximum sum; tmp_cols = all columns i such that m(row_ind, i) = 1; tmp_rows = (); cols = (); rows = (); while (length(tmp_rows) > length(rows) | length(tmp_cols) > length(cols)){ // while rows is not full yet, or cols is not full yet rows = tmp_rows; cols = tmp_cols; tmp_rows = all rows that contain 1 in any column i tmp_cols; tmp_cols = all columns that contain 1 in any row i tmp_rows; } blocks(1) = struct('rows', rows, 'cols', cols); // the first block is the one found above m(rows,cols) = 0; // equivalent to: mi,j = 0 for all i rows, j cols blocks(2, 3, 4, …) = FindFirstLevelBlocks(m); // find the rest of the blocks }
הבעיות מתחילות כאשר יש לי X ים כדוגמת 13,28 ו 9,28 הם הורסים לי את הבלוקים היפים והופכים (באלגוריתם שהצגתי) את המלבן התחום 6,7 40,37 לבלוק היררכי אחד כאשר למעשה הבלוקים 2,3,4 שמצאתי בלעדיהם נעלמו. אני מחפש דרך לזהות Xים בודדים כאלו כרעש במטריצה. כל רעיון, כיוון, LINK לדברים דומים שנעשו פעם, יתקבלו בברכה.