Vengrijos algoritmas: minimalaus nulio nustatymo linijų skaičius?

Stengiuosi įgyvendinti Vengrijos algoritmą , bet aš įstrigo 5 žingsnyje . Iš esmės, atsižvelgiant į skaičių n X n matricą, kaip galiu rasti minimalų vertikalių + horizontalių linijų skaičių, pvz., Nulius matricoje?

Prieš tai, kai kažkas šį klausimą nurodo kaip dublikatą, minėtas sprendimas yra neteisingas, ir kažkas taip pat susidūrė su klaida tekste pateiktame tekste .

Aš nerandu kodo, bet koncepcija, kuria galiu piešti šias eilutes ...

Redaguoti: neskelbkite paprasto (bet neteisingo) godumo algoritmo: atsižvelgiant į šį įvestį:

 (0, 1, 0, 1, 1) (1, 1, 0, 1, 1) (1, 0, 0, 0, 1) (1, 1, 0, 1, 1) (1, 0, 0, 1, 0) 

Akivaizdu, kad 2 stulpelis (0 indeksuotas):

 (0, 1, x, 1, 1) (1, 1, x, 1, 1) (1, 0, x, 0, 1) (1, 1, x, 1, 1) (1, 0, x, 1, 0) 

Dabar galiu pasirinkti 2 arba 1 eilutę, kuri turi du „likusius“ nulius. Jei pasirenku col2, šiuo keliu gaunu neteisingą sprendimą:

 (0, x, x, 1, 1) (1, x, x, 1, 1) (1, x, x, 0, 1) (1, x, x, 1, 1) (1, x, x, 1, 0) 

Teisingas sprendimas naudoja 4 eilutes:

 (x, x, x, x, x) (1, 1, x, 1, 1) (x, x, x, x, x) (1, 1, x, 1, 1) (x, x, x, x, x) 
21
30 апр. nustatyti pathikrit 30 Bal. 2014-04-30 07:23 '14, 7:23 AM 2014-04-30 07:23
@ 5 atsakymai

Atnaujinti

Vengrijos algoritmą įgyvendinau tuos pačius veiksmus, kuriuos nurodėte nuoroda: vengrų algoritmas p>

Čia yra failai su komentarais: Github

3 žingsnio algoritmas (pagerintas godumas): (Šis kodas yra labai išsamus ir naudingas, kad suprastumėte brėžinio pasirinkimo sąvoką: horizontalus ir vertikalus. Tačiau pastebėkite, kad šis žingsnio kodas yra pagerintas mano kode „ Github“ )

  • Apskaičiuokite maksimalų vertikalių ir horizontalių nulių skaičių kiekvienai xy padėčiai įvesties matricoje ir išsaugokite rezultatą į atskirą masyvą, pavadintą m2 .
  • Apskaičiuojant, jei horizontalūs nuliai yra> vertikalūs nuliai, apskaičiuotas skaičius konvertuojamas į neigiamą. (tiesiog nustatykite, kurią kryptį pasirinkome vėlesniam naudojimui)
  • Slinkite per visus elementus m2 masyve. Jei vertė yra teigiama, m3 masyvą traukite vertikaliąja linija, jei vertė yra neigiama, traukite horizontalią liniją m3

Norėdami geriau suprasti algoritmą, atlikite toliau pateiktą pavyzdį:

Sukurti 3 masyvus:

  • m1: Pirmasis masyvas, kuriame yra įvesties reikšmės
  • m2: antrajame masyve yra maxZero (vertikalios, horizontalios) kiekvienoje padėtyje x, y
  • m3: trečiojoje matricoje yra paskutinės eilutės (0 indeksas nėra išplėstas, 1 indeksuotas)

Sukurti 2 funkcijas:

  • hvMax (m1, eilutė, stulpelis); grąžina maksimalų skaičių nulių horizontaliai arba vertikaliai. (Teigiamas skaičius reiškia vertikalią, neigiamas skaičius - horizontalus)
  • aiškūsNuotoliai (m2, m3, eilutė, kol.); negaliojantis, jis išvalys horizontalias kaimynes, jei eilutės stulpelių indekso reikšmė yra neigiama arba vertikalios kaimynės yra aiškios, jei jos yra teigiamos. Be to, jis nustatys m3 masyvo eilutę, pasukdamas nulinį bitą į 1.

kodą

 public class Hungarian { public static void main(String[] args) { // m1 input values int[][] m1 = { { 0, 1, 0, 1, 1 }, { 1, 1, 0, 1, 1 }, { 1, 0, 0, 0, 1 }, { 1, 1, 0, 1, 1 }, { 1, 0, 0, 1, 0 } }; // int[][] m1 = { {13,14,0,8}, // {40,0,12,40}, // {6,64,0,66}, // {0,1,90,0}}; // int[][] m1 = { {0,0,100}, // {50,100,0}, // {0,50,50}}; // m2 max(horizontal,vertical) values, with negative number for // horizontal, positive for vertical int[][] m2 = new int[m1.length][m1.length]; // m3 where the line are drawen int[][] m3 = new int[m1.length][m1.length]; // loop on zeroes from the input array, and sotre the max num of zeroes // in the m2 array for (int row = 0; row < m1.length; row++) { for (int col = 0; col < m1.length; col++) { if (m1[row][col] == 0) m2[row][col] = hvMax(m1, row, col); } } // print m1 array (Given input array) System.out.println("Given input array"); for (int row = 0; row < m1.length; row++) { for (int col = 0; col < m1.length; col++) { System.out.print(m1[row][col] + "\t"); } System.out.println(); } // print m2 array System.out .println("\nm2 array (max num of zeroes from horizontal vs vertical) (- for horizontal and + for vertical)"); for (int row = 0; row < m1.length; row++) { for (int col = 0; col < m1.length; col++) { System.out.print(m2[row][col] + "\t"); } System.out.println(); } // Loop on m2 elements, clear neighbours and draw the lines for (int row = 0; row < m1.length; row++) { for (int col = 0; col < m1.length; col++) { if (Math.abs(m2[row][col]) > 0) { clearNeighbours(m2, m3, row, col); } } } // prinit m3 array (Lines array) System.out.println("\nLines array"); for (int row = 0; row < m1.length; row++) { for (int col = 0; col < m1.length; col++) { System.out.print(m3[row][col] + "\t"); } System.out.println(); } } // max of vertical vs horizontal at index row col public static int hvMax(int[][] m1, int row, int col) { int vertical = 0; int horizontal = 0; // check horizontal for (int i = 0; i < m1.length; i++) { if (m1[row][i] == 0) horizontal++; } // check vertical for (int i = 0; i < m1.length; i++) { if (m1[i][col] == 0) vertical++; } // negative for horizontal, positive for vertical return vertical > horizontal ? vertical : horizontal * -1; } // clear the neighbors of the picked largest value, the sign will let the // app decide which direction to clear public static void clearNeighbours(int[][] m2, int[][] m3, int row, int col) { // if vertical if (m2[row][col] > 0) { for (int i = 0; i < m2.length; i++) { if (m2[i][col] > 0) m2[i][col] = 0; // clear neigbor m3[i][col] = 1; // draw line } } else { for (int i = 0; i < m2.length; i++) { if (m2[row][i] < 0) m2[row][i] = 0; // clear neigbor m3[row][i] = 1; // draw line } } m2[row][col] = 0; m3[row][col] = 1; } } 

Išeiti

 Given input array 0 1 0 1 1 1 1 0 1 1 1 0 0 0 1 1 1 0 1 1 1 0 0 1 0 m2 array (max num of zeroes from horizontal vs vertical) (- for horizontal and + for vertical) -2 0 5 0 0 0 0 5 0 0 0 -3 5 -3 0 0 0 5 0 0 0 -3 5 0 -3 Lines array 1 1 1 1 1 0 0 1 0 0 1 1 1 1 1 0 0 1 0 0 1 1 1 1 1 

PS: jūsų nurodytas pavyzdys niekada neįvyks, nes, matydami pirmąjį ciklą, atlikite skaičiavimus, imdami max (horizontalus, vertikalus) ir išsaugokite juos m2. Taigi, kol1 nebus pasirinktas, nes -3 reiškia horizontalią brėžinio liniją, o -3 buvo apskaičiuota atsižvelgiant į didžiausią tarp horizontalių ir vertikalių nulių. Taigi, pirmuoju iteracijos metu programos elementai patikrino, kaip traukti linijas, antroje iteracijoje programa traukia linijas.

11
02 мая '14 в 10:55 2014-05-02 10:55 atsakymas pateikiamas CMPS 02 gegužės 14 d. 10:55 2014-05-02 10:55

Kai kuriais atvejais gobšūs algoritmai gali neveikti.

Pirma, galite pertvarkyti savo problemą taip: atsižvelgiant į dvipartį grafiką, suraskite minimalų viršūnių padengimą. Šioje užduotyje yra 2n mazgai, n eilutėse ir n - stulpeliai. Tarp dviejų mazgų yra kraštas, jei atitinkamo stulpelio ir eilutės susikirtimo elementas yra nulis. Vertex viršelis yra mazgų (eilučių ir stulpelių) rinkinys, todėl kiekvienas kraštas nukrenta ant šio rinkinio mazgo (kiekvienas nulis yra padengtas eilute arba stulpelyje).

Tai gerai žinoma problema ir gali būti išspręsta O (n ^ 3) ieškant maksimalios atitikties. Skaityti daugiau apie „ wikipedia“

4
29 апр. Wanderer atsakymas, pateiktas balandžio 29 d. 2015-04-29 04:17 '15 ne 4:17 2015-04-29 04:17

Yra atvejų, kai „Amir“ kodas neveikia.

Apsvarstykite šiuos m1:

  0 0 1 0 1 1 1 0 1 

Geriausias sprendimas - per pirmuosius du stulpelius traukti vertikalias linijas.

„Amir“ kodas suteiks tokį m2:

 -2 -2 0 2 0 0 0 2 0 

Ir rezultatas - dvi vertikalios linijos: AS WELL AS - linija pirmoje eilutėje.

Man atrodo, kad problema yra išlaisvinti:

return vertical > horizontal ? vertical : horizontal * -1;

Dėl kodo rašymo, labai panašūs „m1“ negali:

  0 1 1 1 0 1 0 0 1 

Jei pirmoji linija pereina į apačią, nes valymo funkcija išvalys reikšmes nuo m2 iki šių ląstelių pasiekimo. Pirmuoju atveju pirmosios dvi vertės nukrenta, taigi horizontali linija eina per pirmąją liniją.

Aš tai padariau, ir tai aš turiu. Jei tai yra kaklaraištis, nenustatykite verčių arba nubrėžkite liniją per šias ląsteles. Tai susiję su pirmiau minėta matrica, tai darome šiame etape.

Akivaizdu, kad yra situacijų, kai liko 0, kurių neaptinkama. Toliau pateikiamas dar vienas matricos pavyzdys, kuris nepavyks Amir metodu (m1):

  0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1 

Geriausias sprendimas yra, pavyzdžiui, keturios eilutės. pirmuosius keturis stulpelius.

Amira metodas suteikia m2:

  3 -2 0 0 0 3 0 -2 0 0 3 0 0 -2 0 0 0 -2 -2 0 0 0 0 0 0 

Tai sudarys linijas pirmosiose keturiose eilutėse ir pirmame stulpelyje (neteisingas sprendimas, suteikiantis 5 eilutes). Vėlgi, probleminė problema yra problema. Tai išsprendžiame ne nustatydami nuorodų vertę, o ne pakartodami procedūros.

Jei ignoruojame ryšius, mes gauname m2:

  3 -2 0 0 0 3 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

Tai apima tik pirmąją ir pirmąją skiltį. Tada išeisime 0s, kurie bus padengti, kad nauji m1 būtų:

  1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 

Tada mes ir toliau kartojame procedūrą (ignoruojant nuorodas), kol pasieksime sprendimą. Pakartokite naujiems m2:

  0 0 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 

Tai du vertikalias linijas per antrą ir trečią stulpelius. Dabar visi 0 yra aprėpti, jiems reikia tik keturių eilučių (tai yra alternatyva suderinti pirmuosius keturis stulpelius). Minėtoje matricoje reikalingi tik 2 iteracijos, ir manau, kad daugeliu šių atvejų reikia tik dviejų iteracijų, jei nėra nuorodų rinkinių nuorodų rinkiniuose. Bandžiau sugalvoti vieną, bet sunku su ja susidoroti.

Deja, tai nėra pakankamai gera, nes bus atvejų, kurie išliks amžinai. Visų pirma, tais atvejais, kai yra „nesusijęs susietų ląstelių rinkinys“. Nežinote, kaip kitaip ją apibūdinti, išskyrus šiuos du pavyzdžius:

  0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 0 

arba

  0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 

Šiuose dviejuose pavyzdžiuose viršutiniame kairiajame 3 submatrice yra identiški mano pradiniam pavyzdžiui, po šio ir žemiau esančio pavyzdžio pridėjau 1 arba 2 eilutes / stulpelius. Vienintelis naujai pridėtas nulis, kur susikerta naujos eilutės ir stulpeliai. Aiškumo paaiškinimas.

Naudojant aprašytą iteracinį metodą, šios matricos bus sugautos begalinėje kilpoje. Nuliai visada bus susieti (skaičiuoti pagal eilių skaičių). Šiuo metu yra tikslinga tiesiog savavališkai pasirinkti kryptį, jei tai yra kaklaraištis, bent jau nuo to, ką galiu įsivaizduoti.

Vienintelė problema, su kuria susidūriau, buvo nustatyti ciklo stabdymo kriterijus. Negaliu manyti, kad pakanka 2 iteracijų (ar bet kokių n), bet taip pat negaliu suprasti, kaip nustatyti, ar ji turi tik begalines kilpas. Aš vis dar nesu įsitikinęs, kaip apskaičiuoti šiuos disjonuojamus rinkinius.

Čia pateikiamas iki šiol atliktas kodas (MATLAB scenarijuje):

 function [Lines, AllRows, AllCols] = FindMinLines(InMat) %The following code finds the minimum set of lines (rows and columns) %required to cover all of the true-valued cells in a matrix. If using for %the Hungarian problem where 'true-values' are equal to zero, make the %necessary changes. This code is not complete, since it will be caught in %an infinite loop in the case of disjoint-tied-sets %If passing in a matrix where 0s are the cells of interest, uncomment the %next line %InMat = InMat == 0; %Assume square matrix Count = length(InMat); Lines = zeros(Count); %while there are any 'true' values not covered by lines while any(any(~Lines  InMat)) %Calculate row-wise and col-wise totals of 'trues' not-already-covered HorzCount = repmat(sum(~Lines  InMat, 2), 1, Count).*(~Lines  InMat); VertCount = repmat(sum(~Lines  InMat, 1), Count, 1).*(~Lines  InMat); %Calculate for each cell the difference between row-wise and col-wise %counts. Ie row-oriented cells will have a negative number, col-oriented %cells will have a positive numbers, ties and 'non-trues' will be 0. %Non-zero values indicate lines to be drawn where orientation is determined %by sign. DiffCounts = VertCount - HorzCount; %find the row and col indices of the lines HorzIdx = any(DiffCounts < 0, 2); VertIdx = any(DiffCounts > 0, 1); %Set the horizontal and vertical indices of the Lines matrix to true Lines(HorzIdx, :) = true; Lines(:, VertIdx) = true; end %compute index numbers to be returned. AllRows = [find(HorzIdx); find(DisjTiedRows)]; AllCols = find(VertIdx); end 
3
03 янв. Atsakymą pateikė mhermher Jan 03 2015-01-03 02:50 '15 at 2:50 2015-01-03 02:50

5 žingsnis: Linijos braižymas matricoje yra apskaičiuotas įstrižai, kai matricos ilgis yra didžiausias.

Remiantis http://www.wikihow.com/Use-hungarian-Algorithm tik su 1-8 žingsniais.

Paleiskite kodo fragmentą ir peržiūrėkite rezultatus konsolėje

Konsolės išėjimas

 horizontal line (row): {"0":0,"2":2,"4":4} vertical line (column): {"2":2} Step 5: Matrix 0 1 0 1 1 1 1 0 1 1 1 0 0 0 1 1 1 0 1 1 1 0 0 1 0 Smallest number in uncovered matrix: 1 Step 6: Matrix xxxxx 1 1 x 1 1 xxxxx 1 1 x 1 1 xxxxx 

JSFiddle: http://jsfiddle.net/jjcosare/6Lpz5gt9/2/

3
29 апр. atsakymas, kurį pateikė jjcosare 29 Bal 2015-04-29 13:35 '15, 13:35, 2015-04-29 13:35
Atsakymas

@MPS nepavyksta keliose diagramose. Manau, kad įgyvendinau sprendimą, kuris išsprendžia problemą.

Vykdavau Vikipedijos straipsnį apie Vengrijos algoritmą , ir aš vykdiau įgyvendinimą, kuris, atrodo, veikia visą laiką. Iš „Wikipedia“ čia pateikiamas minimalių eilių skaičiavimo metodas:

Pirmiausia priskirkite kuo daugiau užduočių. Pažymėkite visas linijas be jokių paskyrimų. Pažymėkite visas (nepažymėtas) stulpelius, kuriuose yra nulio naujose pažymėtose eilutėse. Patikrinkite visas eilutes, kuriose yra naujų užduočių. Pakartokite visoms nepriskirtoms eilutėms.

Štai mano „Ruby“ įgyvendinimas:

 def draw_lines grid #copies the array marking_grid = grid.map { |a| a.dup } marked_rows = Array.new marked_cols = Array.new while there_is_zero(marking_grid) do marking_grid = grid.map { |a| a.dup } marked_cols.each do |col| cross_out(marking_grid,nil, col) end marked = assignment(grid, marking_grid) marked_rows = marked[0] marked_cols.concat(marked[1]).uniq! marking_grid = grid.map { |a| a.dup } marking_grid.length.times do |row| if !(marked_rows.include? row) then cross_out(marking_grid,row, nil) end end marked_cols.each do |col| cross_out(marking_grid,nil, col) end end lines = Array.new marked_cols.each do |index| lines.push(["column", index]) end grid.each_index do |index| if !(marked_rows.include? index) then lines.push(["row", index]) end end return lines end def there_is_zero grid grid.each_with_index do |row| row.each_with_index do |value| if value == 0 then return true end end end return false end def assignment grid, marking_grid marking_grid.each_index do |row_index| first_zero = marking_grid[row_index].index(0) #if there is no zero go to next row if first_zero.nil? then next else cross_out(marking_grid, row_index, first_zero) marking_grid[row_index][first_zero] = "*" end end return mark(grid, marking_grid) end def mark grid, marking_grid, marked_rows = Array.new, marked_cols = Array.new marking_grid.each_with_index do |row, row_index| selected_assignment = row.index("*") if selected_assignment.nil? then marked_rows.push(row_index) end end marked_rows.each do |index| grid[index].each_with_index do |cost, col_index| if cost == 0 then marked_cols.push(col_index) end end end marked_cols = marked_cols.uniq marked_cols.each do |col_index| marking_grid.each_with_index do |row, row_index| if row[col_index] == "*" then marked_rows.push(row_index) end end end return [marked_rows, marked_cols] end def cross_out(marking_grid, row, col) if col != nil then marking_grid.each_index do |i| marking_grid[i][col] = "X" end end if row != nil then marking_grid[row].map! {|i| "X"} end end grid = [ [0,0,1,0], [0,0,1,0], [0,1,1,1], [0,1,1,1], ] p draw_lines(grid) 
0
20 марта '17 в 15:34 2017-03-20 15:34 atsakymą pateikė KNejad kovo 20 d. 17:34 15:34 2017-03-20 15:34