Oz Mozart - Program kostka - Programowanie w logice ograniczeń

0

Witam. Mam następujące zadanie do wykonania:
user image
user image
Mam taką kostkę, która składa się z 9 elementów o kształcie takim jak na zdjęciu.
Mam napisać program w logicznym języku programowania (Oz Mozart) bądź w Excelu jeżeli mam taka chęć, który ułoży tą kostkę. Program nie musi działać w pełni poprawnie. Najważniejsze są dla mnie ograniczenia, które potrzebne są do wykonania tego programu. Będę bardzo wdzięczny za jakiekolwiek ograniczenia, wskazówki bądź jakiekolwiek myśli.

Pozdrawiam

0

Zacznij od napisania jakie ograniczenia próbowałeś wykorzystać. Jak dla mnie to wystarczy reprezentować tą twoją kostkę jako odpowiednią macierz. Ograniczenia są dość oczywiste -> w każdym polu musi się znajdować tylko jeden element

0

W załączniku przesyłam co wymyśliliśmy. Ograniczenie jest na pewno takie, że są trzy warstwy tej kostki i na każdej musi być jedna mała kostka lub 2 obok siebie danego elementu. W sensie, że każdy element składa się z 3 małych kostek tak jak na 2 zdjęciu. Ciekawe czy zrozumiesz o co mi chodzi :P

0

Chciałem tylko pokazać to co mamy a ze nie jest napisane w języku programowania to nie mogę wstawić kodu. A co do zadania możesz coś doradzić?

4

W ILP możesz zrobić tak:
Dla każdego elementu k od 1 do 9 (mamy 9 elementów):
tworzysz 27 zmiennych binarnych P_{k,x,y,z} (bo cała kostka ma 27 elementów). x to numer wiersza, y to numer kolumny, z to numer warstwy (numerujesz w jakiej kolejności Ci wygodnie)
\sum_{x,y,z} P_{k,x,y,z} = 3 suma wszystkich zmiennych jest równa 3. To nam gwarantuje że nasz element będzie miał dokładnie 3 części.
\sum_{x,y,z} P_{k,x,y,z} \cdot (P_{k,x+1, y, z} + P_{k, x, y+1, z} + P_{k,x,y,z+1}) = 2 (tam gdzie indeksy mają sens) mnożymy przez siebie dwa sąsiednie elementy w każdym kierunku. Iloczyn będzie równy 1 tylko wtedy, gdy dwie części klocka są obok siebie, a ponieważ mamy 3 części klocka, to tym zagwarantujemy, że klocek nie zostanie "rozerwany".
\forall_{x} \forall_{y} \sum_{z} P_{k,x,y,z} \le 2 suma zmiennych każdej "pionowej" prostej jest równa co najwyżej 2. Dla wierszy i kolumn analogicznie. To nam gwarantuje, że nasz klocek nie będzie miał trzech elementów na jednej prostej (czyli go nie wyprostujemy).
\forall_{x} \forall_{y} \forall_{z} \sum_{k} P_{k,x,y,z} = 1 w każdym miejscu kostki jest część dokładnie jednego elementu.

Nie weryfikowałem, ale wydaje się sensowne.
Edycja:
Wprawne oko dostrzeże, że mnożenie zmiennych jest w ILP zabronione (bo wtedy nie byłby to program liniowy, tylko kwadratowy). Ale tutaj mnożymy zmienne binarne, co jest tożsame obliczaniu koniunkcji zmiennych, a to możemy zrobić tak:
Mając zmienne binarne a,b,c i chcąc, aby c = a \wedge b, dodajemy ograniczenie 0 \le a + b - 2c \le 1.

Edycja 2:
Zaimplementowałem ten program i daje dobre wyniki.

0

Wyszukałeś gdzieś informacje czy to twoja twórczość? Pytam ponieważ mógłbym poczytać coś więcej.

0

Moja. Nie wiem tylko, na ile Ci się to przyda, bo nie znam Mozarta i nie wiem, jak tam definiuje się ograniczenia.

0

Czekam na więcej myśli :)

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