Pomysł na algorytm (upychanie kwadratów w siatce)

0

Witam, mam problem z pomysłem na algorytm.

Opis sytuacji:
Zadaniem jest upchnięcie jak największej ilości kwadratów na siatkę (kwadrat zajmuje 4 pola z tej siatki, a pola są mniejszymi kwadratami (1/4 dużego kwadratu)), sama siatka jest nieregularna, co uniemożliwia proste ułożenie kwadratów. Celem jest ułożenie największej możliwej ilości kwadratów. Nie mam pojęcia jak to ugryźć, żeby stworzyć algorytm, który będzie podawał użytkownikowi prawidłową odpowiedź jaka jest ta maksymalna ilość kwadratów dla dowolnej nieregularnej siatki jaką podaje użytkownik.

Jeśli coś jest niejasne, to narysuje przykład:

Siatka regularna 3x2:

[][][]
[][][]

Maksymalna ilość kwadratów dla podanej siatki 3x2 wynosi 1:

[x][x][]
[x][x][]

Wszystko ładnie i pięknie, ale jak sobie z tym poradzić kiedy siatka wygląda np. tak?

[][][][][][]
[][][] [][]
[][] [][]
[][][]
[][][][]
[][][][][][]
[][][][][][][]
[][][][][][][][]
[][]

Ktoś ma jakiś pomysł? (Nie na rozwiązanie ostatniego przykładu, tylko na algorytm, który będzie obliczał prawidłową maksymalną ilość kwadratów dla dowolnej siatki podanej przez użytkownika?

0

ja bym zaczął od zredukowania (albo i nie) problemu do znajdowania zbioru niezależnego w grafie: jeżeli w jakimś miejscu można wstawić kwadrat, to to miejsce jest reprezentowane przez wierzchołek, następnie łączymy krawędziami te wierzchołki, których kwadraty na siebie nachodzą, znajdujemy składowe spójności i dla każdej staramy się znaleźć największy zbiór niezależny

0

To by się sprawdziło w takim przypadku:

Prosty przykład siatki:

1	2	3
4	5	6
7	8	
9

Maksymalna ilość kwadratów dla podanej siatki wynosi 1:

X	X	3
X	X	6
7	8	
9

(X - zaznaczony duży kwadrat)

Wszystko ładnie i pięknie, ale czy się sprawdzi, kiedy siatka wygląda np. tak?

									1									
							2	3	4	5								
						6	7	8	9	10	11							
					12	13	14	15	16	17	18	19						
					20	21	22	23	24	25	26	27	28					
					29	30	31	32	33	34	35	36	37	38				
				39	40	41	42	43	44	45	46	47	48	49	50			
		51	52	53	54	55	56	57	58	59	60	61	62	63	64	65		
66	67	68	69	70	71	72	73	74	75	76	77	78	79	80	81	82	83	
84	85	86	87	88	89	90	91	92	93	94	95	96	97	98	99	100	101	102
103	104	105	106	107	108	109	110	111	112	113	114	115	116	117	118	119	120	121
	122	123	124	125	126	127	128	129	130	131	132	133	134	135	136	137	138	
		139	140	141	142	143	144	145	146	147	148	149	150	151	152	153		
			154	155	156	157	158	159	160	161	162	163	164	165	166			
				167	168	169	170	171	172	173	174	175	176	177				
					178	179	180	181	182	183	184	185	186					
						187	188	189	190	191	192	193						
							194	195	196	197	198							
								199	200	201								
									202

Bo jeżeli ustawie kwadraty od lewej do prawej:


									1									
							X	X	X	X								
						6	X	X	X	X	11							
					X	X	X	X	X	X	X	X						
					X	X	X	X	X	X	X	X	28					
					X	X	X	X	X	X	X	X	X	X				
				39	X	X	X	X	X	X	X	X	X	X	50			
		X	X	X	X	X	X	X	X	X	X	X	X	X	X	65		
66	67	X	X	X	X	X	X	X	X	X	X	X	X	X	X	82	83	
X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	102
X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	121
	122	X	X	X	X	X	X	X	X	X	X	X	X	X	X	137	138	
		X	X	X	X	X	X	X	X	X	X	X	X	X	X	153		
			154	X	X	X	X	X	X	X	X	X	X	165	166			
				X	X	X	X	X	X	X	X	X	X	177				
					178	X	X	X	X	X	X	185	186					
						X	X	X	X	X	X	193						
							194	X	X	197	198							
								X	X	201								
									202

to otrzymam wartość 43 (dużych kwadratów), ale wówczas stracę przestrzeń 82, 83 i 137, 138, ja zauważę, że mogę kwadrat zamiast na polach 100, 101, 119, 120 ustawić dwa na pozycjach 82, 83, 100, 101 i 119, 120, 137, 138:


									1									
							X	X	X	X								
						6	X	X	X	X	11							
					X	X	X	X	X	X	X	X						
					X	X	X	X	X	X	X	X	28					
					X	X	X	X	X	X	X	X	X	X				
				39	X	X	X	X	X	X	X	X	X	X	50			
		X	X	X	X	X	X	X	X	X	X	X	X	X	X	65		
66	67	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	
X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	102
X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	121
	122	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	X	
		X	X	X	X	X	X	X	X	X	X	X	X	X	X	153		
			154	X	X	X	X	X	X	X	X	X	X	165	166			
				X	X	X	X	X	X	X	X	X	X	177				
					178	X	X	X	X	X	X	185	186					
						X	X	X	X	X	X	193						
							194	X	X	197	198							
								X	X	201								
									202

Tylko jak zrobić skuteczny algorytm, żeby podał 44 a nie 43 pola w tym przypadku i był skuteczny dla dowolnej siatki, nawet takiej z pustymi polami w środku?

0

to co podałem to tylko sposób uchwycenia problemu i zadziała dla każdej siatki, ale nie mówi jak znaleźć największy zbiór niezależny :D

jeśli chodzi o konkretny podany przez Ciebie przypadek jak to poprawić, to znajdowałbym niewykorzystane pary pól (para=2 obok siebie pionowo lub poziomo) i jeżeli są dwie pary na przeciwko siebie to je dodać

po grafowemu to by wyglądało chyba jakoś tak:

  • zbiór pokolorowanych wierzchołków oznaczamy X
  • wyznaczyć zbiór A nipokolorowanych wierzchołków, które mają dokładnie jednego pokolorowanego sąsiada
  • wyznaczyć zbiór B nipokolorowanych wierzchołków, które mają dokładnie dwóch pokolorowanych sąsiadów
  • jeżeli istnieje ścieżka postaci ax(bx)*a to zmieniamy jej kolorowanie powiększając tym samym liczbę pokolorowanych wierzchołków o 1
    to jest opis bardziej matematyczny niż algorytmiczny, sam wybierz, którą wersję będzie Ci łatwiej zaimplementować

PS: jak robisz asciiarty, to najpierw sprawdź na podglądzie czy się coś niepoprzesuwa i popraw :p

0

Najlepiej poszukaj w internecie: problem optymalnego rozkroju.

1 użytkowników online, w tym zalogowanych: 0, gości: 1