Uzupełnianie dwuwymiarowej tablicy posiadając różne warunki na kolumny i wiersze

0

Witam.
Spotkałem się z ciekawym problemem algorytmicznym z którym próbowałem się zmierzyć i niestety nie mam pomysłu jak rozwiązać taki problem. Może ktoś z Was spotkał się z podobnym problemem i ma pomysł z czego mógłbym skorzystać. Ogólnie chcę uzupełnić tablicę danymi posiadając różne warunki dla kolumn i dla wierszy.

Posiadam kilka rodzajów figur w kilku różnych kolorach tak jak w załączniku nr. 1, oraz pustą tablicę dwuwymiarową o rozmiarach 30 wierszy na 15 kolumn którą należy uzupełnić figurami określonego koloru. Daje nam to łącznie 16 różnych kombinacji, a całkowita ilość obiektów to 450 (dokładnie tyle ile komórek w tablicy).

Kolory ustawiamy w obrębie kolumny. Raz ustawiony kolor może (ale nie musi) zostać zmieniony dopiero po 3 komórkach. Jeżeli ustawimy kolor zielony w pierwszej kolumnie i pierwszym wierszu, to w drugim i trzecim wierszu tej samej kolumny też musi zostać ustawiony kolor zielony. Dopiero w czwartej komórce możemy zdecydować czy kontynuujemy poprzedni kolor, czy zmieniamy na inny. W przypadku gdy dojdziemy do ostatniego wiersza kolumny, przechodzimy do pierwszego wiersza kolejnej kolumny nie przerywając działania algorytmu (czyli jeżeli w ostatniej komórce pierwszej kolumny ustawiliśmy kolor niebieski, to w pierwszych dwóch komórkach kolumny drugiej kolor niebieski musi być kontynuowany) - załącznik 2.

Figury ustawiamy w taki sposób, że sprawdzamy co było w poprzedniej kolumnie i możemy dokonać zmian max 10 kształtów na jedną kolumnę. Czyli w obrębie dwóch sąsiadujących kolumn możliwa jest zmiana z „20 kółek i 10 kwadratów” na „10 kółek, 10 kwadratów i 10 trójkątów”. Nie możliwa jest zmiana z „30 kółek” na „10 kółek i 20 kwadratów”.

Ogólnie próbowałem to rozwiązać na różne sposoby - moje pierwsze podejście zakładało że ustawię sobie odpowiednie figury w całej tablicy a dopiero po ustawieniu figur będę się zastanawiał jakie kolory będą wybierane dla już znanych mi figur. To rozwiązanie nie zawsze da mi prawidłowe rozwiązanie.

Zastanawiałem się nad sortowaniem dwuwymiarowym, ale w tym przypadku jest mowa o jednym rodzaju zmiennej (liczba), a w moim przypadku mamy dwie (kolor i kształt): https://stackoverflow.com/questions/4279524/how-to-sort-a-m-x-n-matrix-which-has-all-its-m-rows-sorted-and-n-columns-sorted

Zastanawiałem się również czy dla każdego pola nie wyliczać jakiś współczynników na podstawie których mógłbym wybrać która figura i kolor pasowałyby do konkretnej komórki, ale nie wiem jakie mogłyby być to współczynniki.

0

Constraint Programming powinien to rozwiązać.
Edycja 2: poniższe rozwiązanie jest na 98% błędne, bo nie ma warunku na zgodność koloru i figury (potraktowałem je niezależnie). Jak kiedyś będę miał czas, to je dodam, niemniej samo podejście ILP spokojnie da radę z tym zadaniem.

Edycja: odpaliłem w ILP, rozwiązało się w 10 minut. Jeżeli jesteś zainteresowany rozwiązaniem (i przy okazji sprawdzeniem poprawności, bo tutaj zbyt leniwy byłem), to jest ono poniżej.

Legenda:
Para liter oznacza komórkę. Pierwsza litera to kształt (O - okrąg (koło w Twojej nomenklaturze), K - kwadrat, T - trójkąt, P - prostokąt), druga litera oznacza kolor (Z - zielony, N - niebieski, C - czerwony, P - pomarańczowy (żółty w Twojej nomenklaturze)).

KN      OZ      OP      KP      KZ      PP      TN      TC      OP      ON      TP      KP      TN      OZ      OP
TN      OP      OP      KP      OC      PP      KZ      KC      PP      KN      KP      TP      PN      KN      TZ
KN      OP      OC      TP      OC      TP      OZ      KC      TN      TN      KP      KP      PN      TN      KZ
PN      OP      OC      PP      OC      PP      TZ      TC      TN      TZ      KC      OP      TP      TN      KZ
PN      OZ      OC      KP      OZ      KZ      PN      KP      KN      TZ      OC      KP      KP      OP      OZ
KN      KZ      PC      PZ      OZ      KZ      TN      KP      PN      OZ      PC      KP      OP      KP      OZ
OP      OZ      OC      PZ      TZ      KZ      TN      TP      KZ      OP      PP      OP      KP      OP      TP
OP      OP      PC      OZ      KZ      KZ      KN      KP      TZ      KP      TP      TC      OC      TP      TP
OP      OP      PC      TZ      KZ      TZ      KN      KN      KZ      TP      TP      TC      TC      KP      PP
KC      PP      OZ      KP      KZ      OZ      OP      PN      TZ      PP      KZ      TC      OC      KP      TP
OC      OC      OZ      PP      TP      OZ      KP      ON      OC      TP      TZ      TN      TP      PZ      PN
OC      OC      OZ      KP      PP      TN      OP      ON      TC      KP      OZ      ON      KP      KZ      KN
OZ      OC      OC      PP      TP      ON      OZ      OP      KC      OP      KN      ON      KP      KZ      KN
OZ      OC      KC      PP      KN      ON      OZ      KP      TP      TP      ON      PC      KP      KP      TP
KZ      TN      KC      OZ      TN      PN      TZ      TP      KP      KZ      PN      KC      KP      OP      PP
OZ      ON      KZ      OZ      TN      PP      PC      OP      KP      KZ      KN      KC      OC      KP      TP
TZ      PN      KZ      OZ      KP      OP      KC      OZ      PP      OZ      TZ      KC      OC      KZ      PZ
OZ      TN      OZ      TZ      KP      OP      OC      PZ      TC      OZ      OZ      TC      PC      PZ      KZ
OZ      KP      KC      KZ      KP      TZ      KC      PZ      TC      PZ      KZ      PN      ON      TZ      KZ
OZ      TP      TC      KZ      PP      KZ      PP      TP      TC      PZ      TZ      KN      PN      TC      KZ
PZ      OP      PC      OZ      KC      TZ      TP      KP      OC      KN      TZ      TN      KN      TC      OZ
PZ      KP      KC      OZ      OC      KC      PP      PP      TZ      TN      TZ      PZ      KZ      KC      OC
OZ      PP      KC      KZ      KC      OC      PN      TZ      PZ      TN      OZ      PZ      KZ      PC      KC
OZ      PN      ON      KZ      KP      OC      TN      TZ      KZ      TN      KZ      PZ      TZ      PN      OC
PN      PN      TN      TZ      OP      TC      ON      TZ      OC      TC      TZ      KC      TZ      ON      TP
KN      ON      KN      KC      OP      PC      KN      OC      KC      PC      TC      OC      KN      KN      KP
ON      PP      PC      PC      PC      KC      TP      TC      OC      PC      OC      OC      PN      KN      KP
OZ      KP      TC      KC      TC      KN      OP      PC      PP      KC      PC      KC      TN      PP      KC
OZ      OP      OC      OZ      PC      KN      KP      TC      TP      TP      PP      KN      KZ      OP      KC
TZ      KP      KC      OZ      PC      PN      KP      TP      OP      KP      TP      KN      KZ      TP      PC

A jeżeli interesuje Cię kod (chociaż bardziej zostawiam go jako kopię zapasową), to jest poniżej - C# z użyciem biblioteki CplexMilpSolver (autopromocja: jestem jej autorem):

public static void Start() {
	var solver = new CplexMilpSolver(10);

	int width = 15;
	int height = 30;

	var figures = new [] {
		new [] { 50, 20, 40, 15 },
		new [] { 30, 20, 30, 60 },
		new [] { 30, 25, 30, 20 },
		new [] { 15, 20, 5, 40 }
	};

	var colorVariables = Enumerable.Range(0, width).Select(x => Enumerable.Range(0, height).Select(y => solver.Create(string.Format("color_{0}_{1}", x, y), Domain.PositiveOrZeroInteger)).ToArray()).ToArray();
	var shapeVariables = Enumerable.Range(0, width).Select(x => Enumerable.Range(0, height).Select(y => solver.Create(string.Format("color_{0}_{1}", x, y), Domain.PositiveOrZeroInteger)).ToArray()).ToArray();

	for(int x = 0;x<width;++x) {
		for(int y = 0;y<height;++y) {
			colorVariables[x][y].Set(ConstraintType.GreaterOrEqual, solver.FromConstant(1)).Set(ConstraintType.LessOrEqual, solver.FromConstant(4));
			shapeVariables[x][y].Set(ConstraintType.GreaterOrEqual, solver.FromConstant(1)).Set(ConstraintType.LessOrEqual, solver.FromConstant(4));
		}
	}

	var colorMap = new Dictionary<int, string> {
		{
			1, "Z" },
		{
			2, "N" },
		{
			3, "C" },
		{
			4, "P" }
	};

	var shapeMap = new Dictionary<int, string> {
		{
			1, "O" },
		{
			2, "K" },
		{
			3, "T" },
		{
			4, "P" }
	};

	var shapesSums = Enumerable.Range(1, 4).Select(shape => Enumerable.Range(0, width).Select(x => {
		return Enumerable.Range(0, height).Select(y => shapeVariables[x][y].Operation(OperationType.IsEqual, solver.FromConstant(shape)))
			.Aggregate(solver.FromConstant(0), (previous, next) => previous.Operation(OperationType.Addition, next));
	}).ToArray()).ToArray();

	var colorSums = Enumerable.Range(1, 4).Select(color => {
		return Enumerable.Range(0, width)
			.SelectMany(x => Enumerable.Range(0, height)
				.Select(y => colorVariables[x][y].Operation(OperationType.IsEqual, solver.FromConstant(color)))
			).Aggregate(solver.FromConstant(0), (previous, next) => previous.Operation(OperationType.Addition, next));
	}).ToArray();

	for(int i = 0;i<4;++i) {
		colorSums[i].Set(ConstraintType.Equal, solver.FromConstant(Enumerable.Range(0, 4).Select(y => figures[y][i]).Sum()));
	}

	colorVariables[0][0].Set(ConstraintType.Equal, colorVariables[0][1]);
	colorVariables[0][1].Set(ConstraintType.Equal, colorVariables[0][2]);

	for(int x = 0;x<width;++x) {
		for(int y = 0;y<height;++y) {
			if(x == width-1 && y > height -4) {
				break;
			}

			List<IVariable> variables = new List<IVariable>();
			int copyY = y;
			int copyX = x;
			while(variables.Count < 4) {
				variables.Add(colorVariables[copyX][copyY]);
				copyY ++;
				if(copyY >= height) {
					copyY = 0;
					copyX ++;
				}
			}

			var isFirstThreeEqual = variables[0].Operation(OperationType.IsEqual, variables[1])
				.Operation(OperationType.Conjunction, variables[0].Operation(OperationType.IsEqual, variables[2]));

			var isLastThreeEqual = variables[1].Operation(OperationType.IsEqual, variables[2])
				.Operation(OperationType.Conjunction, variables[1].Operation(OperationType.IsEqual, variables[3]));

			var areParis = variables[0].Operation(OperationType.IsEqual, variables[1])
				.Operation(OperationType.Conjunction, variables[2].Operation(OperationType.IsEqual, variables[3]));

			isFirstThreeEqual
				.Operation(OperationType.Disjunction, isLastThreeEqual)
				.Operation(OperationType.Disjunction, areParis)
				.Set(ConstraintType.Equal, solver.FromConstant(1));
			
		}
	}

	for(int x = 1;x<width;++x) {
		var difference = Enumerable.Range(1, 4)
		.Select(shape => shapesSums[shape-1][x].Operation(OperationType.Subtraction, shapesSums[shape-1][x-1]).Operation(OperationType.AbsoluteValue))
		.Aggregate(solver.FromConstant(0), (previous, next) => previous.Operation(OperationType.Addition, next))
		.Set(ConstraintType.LessOrEqual, solver.FromConstant(10));
	}

	for(int i = 0;i<4;++i) {
		shapesSums[i].Aggregate(solver.FromConstant(0), (previous, next) => previous.Operation(OperationType.Addition, next))
		.Set(ConstraintType.Equal, solver.FromConstant(figures[i].Sum()));
	}

	solver.AddGoal("Goal", solver.FromConstant(0));
	solver.Solve();

	for(int y = 0;y<height;++y) {
		for(int x = 0;x<width;++x) {
			int shape = (int)solver.GetValue(shapeVariables[x][y]);
			int color = (int)solver.GetValue(colorVariables[x][y]);
			Console.Write(string.Format("{0}{1}\t", shapeMap[shape], colorMap[color]));
		}

		Console.WriteLine();
	}


	for(int i = 0;i<4;++i) {
		for(int x = 0;x<width;++x) {
			Console.Write(solver.GetValue(shapesSums[i][x]));
			Console.Write("\t");
		}
		Console.WriteLine();
	}


	for(int i = 0;i<4;++i) {
		Console.Write(solver.GetValue(colorSums[i]));
		Console.Write("\t");
	}
}
0

Dorzuciłem warunek na spójność koloru i kształtu, teraz powinno być dobrze, aczkolwiek nie zweryfikowałem ręcznie. Rozwiązanie:

PP      OC      ON      KZ      OZ      KN      PC      OC      TC      OC      KP      OZ      KN      PP      TP

PP      TZ      PN      OZ      KZ      PN      OC      TC      OC      KC      KP      PZ      PN      PP      OZ

PP      OZ      TC      OZ      OZ      KZ      KC      OC      TC      KC      PN      OZ      TN      PP      OZ

TZ      KZ      OC      OP      PZ      KZ      PC      PC      PP      KC      PN      TZ      PN      OZ      PZ

KZ      PP      KC      OP      PC      PZ      TC      TN      OP      KZ      KN      TZ      ON      OZ      TZ

KZ      KP      OC      PP      PC      KC      PP      TN      PP      OZ      KP      OZ      TZ      OZ      OZ

TC      OP      KC      OP      KC      KC      OP      PN      KC      KZ      OP      TZ      OZ      OZ      OZ

KC      PN      ON      TP      OP      OC      OP      PN      TC      PP      PP      KZ      OZ      PP      TZ

KC      ON      ON      PP      OP      OC      TC      PC      TC      PP      KP      OC      PN      TP      TN

ON      PN      PN      PN      KP      TZ      KC      TC      PN      PP      TZ      OC      TN      KP      PN

PN      PZ      TN      TN      KZ      TZ      TC      PC      PN      PN      TZ      TC      KN      PN      TN

ON      TZ      PN      PN      TZ      PZ      PN      KZ      PN      KN      TZ      PC      TN      ON      OZ

TN      PZ      PC      KZ      OZ      TZ      PN      KZ      TZ      ON      PN      TN      OP      KN      OZ

PN      TC      KC      OZ      ON      OZ      KN      OZ      TZ      OZ      KN      ON      PP      TN      OZ

OZ      TC      TC      OZ      ON      OZ      PP      PP      TZ      OZ      TN      ON      PP      ON      TZ

OZ      OC      PN      PN      PN      KP      PP      TP      TZ      TZ      KN      ON      KP      TN      PP

TZ      TZ      PN      KN      PN      PP      KP      KP      ON      TZ      ON      PN      PZ      ON      PP

KC      OZ      PN      PN      TC      OP      OZ      PC      ON      PC      PN      KC      TZ      PN      OP

PC      OZ      KZ      OZ      TC      TN      PZ      OC      KN      PC      OZ      KC      TZ      PN      KP

OC      PN      OZ      OZ      OC      PN      OZ      TC      KC      OC      KZ      TC      PN      TN      PP

KC      TN      PZ      OZ      ON      PN      KC      TC      TC      OC      OZ      ON      PN      KN      PP

TC      PN      KC      KZ      PN      ON      OC      PN      OC      TC      TZ      TN      ON      TN      OZ

PP      PP      OC      OZ      ON      TN      OC      KN      PN      TC      TN      PN      ON      TN      TZ

PP      PP      TC      TZ      PN      PP      PZ      KN      PN      PN      TN      KN      PP      ON      TZ

TP      PP      KC      PZ      TN      KP      KZ      PN      PN      PN      ON      PN      PP      TN      KP

PC      KN      TC      PZ      TZ      PP      TZ      TZ      PC      KN      KN      TC      KP      ON      OP

KC      TN      PN      KP      PZ      KP      PN      TZ      OC      TZ      OC      OC      OZ      PP      PP

KC      PN      TN      KP      OZ      PC      KN      OZ      TC      TZ      PC      PC      OZ      KP      TZ

PC      TN      ON      PP      KN      OC      PN      PC      OC      TZ      TC      PN      TZ      PP      OZ

TC      PN      KZ      KZ      TN      OC      TN      OC      KC      KP      OC      ON      PZ      OP      OZ

I poprawiony kod:

public static void Start() {
	var solver = new CplexMilpSolver(10);

	int width = 15;
	int height = 30;

	Console.WriteLine("Colors of shapes");
	var figures = new [] {
		new [] { 50, 20, 40, 15 },
        new [] { 30, 20, 30, 60 },
        new [] { 30, 25, 30, 20 },
        new [] { 15, 20, 5, 40 }
	};

	var colorVariables = Enumerable.Range(0, width).Select(x => Enumerable.Range(0, height).Select(y => solver.Create(string.Format("color_{0}_{1}", x, y), Domain.PositiveOrZeroInteger)).ToArray()).ToArray();
	var shapeVariables = Enumerable.Range(0, width).Select(x => Enumerable.Range(0, height).Select(y => solver.Create(string.Format("color_{0}_{1}", x, y), Domain.PositiveOrZeroInteger)).ToArray()).ToArray();

	for(int x = 0;x<width;++x) {
		for(int y = 0;y<height;++y) {
			colorVariables[x][y].Set(ConstraintType.GreaterOrEqual, solver.FromConstant(1)).Set(ConstraintType.LessOrEqual, solver.FromConstant(4));
			shapeVariables[x][y].Set(ConstraintType.GreaterOrEqual, solver.FromConstant(1)).Set(ConstraintType.LessOrEqual, solver.FromConstant(4));
		}
	}

	var colorMap = new Dictionary<int, string> {
		{
			1, "Z" },
		{
			2, "N" },
		{
			3, "C" },
		{
			4, "P" }
	};

	var shapeMap = new Dictionary<int, string> {
		{
			1, "O" },
		{
			2, "K" },
		{
			3, "T" },
		{
			4, "P" }
	};

	colorVariables[0][0].Set(ConstraintType.Equal, colorVariables[0][1]);
	colorVariables[0][1].Set(ConstraintType.Equal, colorVariables[0][2]);

	for(int x = 0;x<width;++x) {
		for(int y = 0;y<height;++y) {
			if(x == width-1 && y > height -4) {
				break;
			}

			List<IVariable> variables = new List<IVariable>();
			int copyY = y;
			int copyX = x;
			while(variables.Count < 4) {
				variables.Add(colorVariables[copyX][copyY]);
				copyY ++;
				if(copyY >= height) {
					copyY = 0;
					copyX ++;
				}
			}

			var isFirstThreeEqual = variables[0].Operation(OperationType.IsEqual, variables[1])
                .Operation(OperationType.Conjunction, variables[0].Operation(OperationType.IsEqual, variables[2]));

			var isLastThreeEqual = variables[1].Operation(OperationType.IsEqual, variables[2])
                .Operation(OperationType.Conjunction, variables[1].Operation(OperationType.IsEqual, variables[3]));

			var areParis = variables[0].Operation(OperationType.IsEqual, variables[1])
                .Operation(OperationType.Conjunction, variables[2].Operation(OperationType.IsEqual, variables[3]));

			isFirstThreeEqual
                .Operation(OperationType.Disjunction, isLastThreeEqual)
                .Operation(OperationType.Disjunction, areParis)
                .Set(ConstraintType.Equal, solver.FromConstant(1));
		}
	}

	var shapesSums = Enumerable.Range(1, 4).Select(shape => Enumerable.Range(0, width).Select(x => {
		return Enumerable.Range(0, height).Select(y => shapeVariables[x][y].Operation(OperationType.IsEqual, solver.FromConstant(shape)))
            .Aggregate(solver.FromConstant(0), (previous, next) => previous.Operation(OperationType.Addition, next));
	}).ToArray()).ToArray();

	for(int x = 1;x<width;++x) {
		var difference = Enumerable.Range(1, 4)
        .Select(shape => shapesSums[shape-1][x].Operation(OperationType.Subtraction, shapesSums[shape-1][x-1]).Operation(OperationType.AbsoluteValue))
        .Aggregate(solver.FromConstant(0), (previous, next) => previous.Operation(OperationType.Addition, next))
        .Set(ConstraintType.LessOrEqual, solver.FromConstant(10));
	}

	for(int color = 1;color<= 4;++color) {
		for(int shape = 1;shape<= 4;++shape) {
			Enumerable.Range(0, width).SelectMany(x => Enumerable.Range(0, height).Select(y =>
				colorVariables[x][y].Operation(OperationType.IsEqual, solver.FromConstant(color)).Operation(OperationType.Conjunction, shapeVariables[x][y].Operation(OperationType.IsEqual, solver.FromConstant(shape)))
			)).Aggregate(solver.FromConstant(0), (previous, next) => previous.Operation(OperationType.Addition, next)).Set(ConstraintType.Equal, solver.FromConstant(figures[color-1][shape-1]));
		}
	}

	solver.AddGoal("Goal", solver.FromConstant(0));
	solver.SaveModelToFile("problem.mps");
    solver.Solve();

    for(int y = 0;y<height;++y) {
        for(int x = 0;x<width;++x) {
            int shape = (int)solver.GetValue(shapeVariables[x][y]);
            int color = (int)solver.GetValue(colorVariables[x][y]);
            Console.Write(string.Format("{0}{1}\t", shapeMap[shape], colorMap[color]));
        }

        Console.WriteLine();
    }
}

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