Wyznaczenie najmniejszej odległości

[woj117]

Witam,

zmierzam się z następującym problemem. Wyobraźmy sobie siatkę 5 x 5:

 

|0|1|1|0|1|

|0|1|1|0|1|

|1|0|1|0|0|

|1|1|0|0|1|

|0|1|1|1|1|

 

gdzie 0 oznacza pole wolne a 1 pole zajęte. Teraz trzeba do takiej siatki wstawić dodatkowo np. 4 elementy, ale tak aby po wstawieniu 1-szego elementu, następne były umieszczane w jak najmniejszej odległości od tego pierwszego, czyli np:

 

|0|1|1|0|1|

|0|1|1|0|1|

|1|0|1|3|3|

|1|1|3|2|1|

|0|1|1|1|1| a nie np.

 

|0|1|1|3|1|

|3|1|1|0|1|

|1|0|1|0|0|

|1|1|3|2|1|

|0|1|1|1|1|

gdzie 2 oznacza 1-wszy nowo wstawiony element a 3 pozostałe. Czy może ktoś z forumowiczów może zaproponować rozwiązanie problemu, lub też dać jakieś wskazówki??

 

Pozdrawiam

WojciechW.

[DarkAndrew]

wybierasz 2 tak zeby nie byla przy krawedzi

a potem sprawdzasz do okola czy sa wolne pola

jezeli sa no to je zapelniasz

jezeli nie ma idziesz od poczatku

[Force]

Wg mnie za mało informacji podajesz. Co się ma na wejściu? dowolną planszę czy 5x5 albo czy położenie pierwszego pola trzeba samemu wybrać czy jest podany oraz czy to ile obiektów chce się dodać jest stałe czy dowolne.

Na pierwszy rzut oka uważam że tak powinieneś zrobić:

Załóżmy że plansza jest kwadratem, x - to jego szerokość

Dla każdego pola obliczasz taką wartość:

suma - wartość pola

int suma = 0;
for(int i=0;i<=x;++i)
 suma += (Ilość wolnX<YHźZJH
ZJN

I tak dla każdego pola, i wybierasz pole co ma największą wartość.

Oczywiście x nie musi być równe szerokości, to jest po prostu zasięg, moze chcesz aby było tylko 5.

8 w kodzie jest bo w w odległości równej 1 jest 8 pól wokół. Jak chcesz to wraz ze zwiększaniem odległości ta liczba rosła, bo pół w odległości równej 2 jest już 12, ogólnie wraz ze wzrostem i to rośnie, więc może zamiast 8 wpisać (i+1)*4, ale po próbuj.

Jeśli pole jest blisko krawędzi to ma mniejszą wartość niż jakby było od niej dalej.

Jak już masz te pole początkowe to jak masz dodać kolejny obiekt wybierasz jego najbliższego sąsiada z największą wartością, itd.

Algorytm można ulepszyć, np. mając znaną wartość sąsiadów próbować interpolować ją dla pół pośrednich, i np. w każdej linii na zmianę brać parzyste i nieparzyste pola, a pozostałe uśredniać, zależy jaką chcesz mieć dokładność wyników, bo myślę, że ten co podałem algorytm znajdzie te pole początkowe najbardziej idealne.

 

Edit: a przepraszam, teraz zauważyłem że ma być c++

int suma = 0;
for(int i=0;i<=x;++i)
 suma += (Ilość wolnX<YHźZJH
ZJN

[woj117]

Dzięki Force za zainteresowanie, ale z przykrością stwierdzam, że nie do końca rozumiem twoją podpowiedź.

Może faktycznie za mało informacji podałem...

Generalnie problem dotyczy magazynu chaotycznego składowania. A więc wyobraźmy sobie, że do magazynu przychodzą 4 palety z towarem. I teraz chodzi o to, że pierwsza paleta idzie na dowolne wolne miejsce, ale jeśli chodzi o następne to powinny być usytuowane możliwie blisko pierwszej. A więc reasumując: plansza jest w rzeczywistości większa niż 5x5, nie (musi być/jest) kwadratowa, no i ilość obiektów nie jest stała.

Tak więc (i to może było dodatkowo zmyłkowe) obiekty nie mają zróżnicowanej wartości (2,3) chciałem tylko schematycznie przedstawić sytuację. Obiekt albo zajmuje miejsce (1) albo miejsce jest puste (0).

 

Pozdrawiam

WojciechW.

[Force]

W tym co napisałem chodziło mi o to, że oblicza się wartości pól, i im większa wartość pola tym bardziej opłaca się na nim postawić obiekt. Wartość jest tym większa im więcej pół jest bliżej, dlatego wraz ze wzrostem odległości wykładnik we wzorze maleje. I jak już sie obliczy na początku te wartości dla pól, to pierwsze pole jakie wybierasz ma mieć największą wartość, a kolejne pola to wybierasz pole o największej wartości będące sąsiadem tego pierwszego. Trzeci obiekt kładziesz na polu o największej wartości będącym sąsiadem któregoś z istniejących,i i tak dalej.