Witam.
Mam napisać program, który tak rozstawi na planszy żołnierzy, żeby nie mogli ze sobą walczyć, tzn. żeby w każdym wierszu i w każdej kolumnie nie znajdował się więcej niż jeden (żeby się nie powtarzali). Trzeba to zrobić tak żeby liczba żołnierzy na planszy była jak najmniejsza.
Mam mały mętlik w głowie wiec proszę was o pomoc. Może ma ktoś jakieś sugestie co do tego algorytmu?
Z góry dzięki za pomoc i pozdrawiam.
- Rejestracja:około 12 lat
- Ostatnio:około 10 lat
- Postów:161
0
- Rejestracja:około 21 lat
- Ostatnio:prawie 3 lata
- Lokalizacja:Space: the final frontier
- Postów:26433
1
Ale chodzi o hetmanów czy o wieże? Bo hetman potrafi atakować też na skos ;] Jeśli chodzi o same wieże to sposób podałem ci już w ostatnim temacie, tzn wystarczy ustawić sobie ich "po skosie"
1 0 0 0 0 ... 0
0 1 0 0 0 ... 0
0 0 1 0 0 ... 0
0 0 0 1 0 ... 0
0 0 0 0 1 ... 0
...
0 0 0 0 0 ... 1
Ale jeśli chodzi o hetmanów to jest t bardziej skomplikowane.
http://www.algorytm.org/inne/problem-8-hetmanow.html
- Rejestracja:około 18 lat
- Ostatnio:około miesiąc
2
Poza sprostowaniem tej "najmniejszej ilości" napisz też, co to jest "żołnierz", bo takiej figury nie kojarzę.
msm
Chodzi o 8 hetmanów na 99%, dość klasyczne ćwiczenie na rekurencję z nawrotami.
msm
Widać moje umiejętności szacowania są kiepskie, jednak nie 8 hetmanów :(.
- Rejestracja:prawie 16 lat
- Ostatnio:4 miesiące
2
Zakładam że chodzi o problem 8 hetmanów (bo to chyba jedyne sensowne dopasowanie do Twojego opisu + to dość klasyczne zadanie).
Niezbyt mi się podoba opis i kod na algorytm.org linkowane przez shaloma (http://www.algorytm.org/inne/problem-8-hetmanow.html) + nigdy tego w sumie nie implementowałem, więc spróbuję samemu omówić.
No więc najpierw oczywista kwestia - nie może być dwóch hetmanów w jednym wierszu (bo by się nawzajem atakowali). Korzystając z tego, można reprezentować rozwiązanie za pomocą tablicy n-elementowej (n = wielkość szachownicy, w klasycznym przypadku 8), gdzie pierwsze pole oznacza kolumnę pierwszego hetmana, drugie pole kolumnę drugiego itp. Przykładowo, tablica [2, 0, 3, 1] oznacza:
..x. (2) (indeksujemy od zera, jak zwykle)
x... (0)
...x (3)
.x.. (1)
(po co taka reprezentacja? upraszcza napisanie algorytmu znajdującego).
No i zadanie algorytmu to znalezienie takiej tablicy, która będzie odpowiadała odpowiedniemu rozmieszczeniu hetmanów.
Najpierw wstawiamy pierwszego hetmana na pierwsze miejsce, później drugiego tak żeby nie atakował pierwszeg, później trzeciego tak żeby nie atakował poprzednich dwóch (lub wracamy do ustawiania pierwszego, jesli trzeciego się tak nie da ustawić) itd:
void place_queens(vector<int> queens, int ndx) {
int dim = queens.size(); // szerokość/wysokość szachownicy
// założenie `indukcyjne` - hetmani [0; ndx) są poprawnie ustawieni
if (ndx == queens.size()) {
print_board(queens); // rozmieściliśmy wszystkich hetmanów, pozostaje wypisać rozwiązanie
} else { // ustawiamy n+1tego hetmana
for (int col = 0; col < dim; col++) { // próbujemy wszystkich kolumn
bool col_ok = true; // niezbyt ładna ta zmienna, ale niech juz będzie
for (int prev = 0; prev < ndx; prev++) { // sprawdzamy czy po postawieniu nie zaatakujemy któregoś poprzedniego
if (col == queens[prev] || abs(col - queens[prev]) == ndx - prev) {
col_ok = false; break;
}
}
if (col_ok) { // skoro kolumna jest `nieatakowana`...
queens[ndx] = col; // ...ustawiamy tam hetmana...
place_queens(queens, ndx + 1); // ...i sprawdzamy dalej
}
}
}
}
void n_queens(int n) {
vector<int> queens(n);
place_queens(queens, 0);
}
print_board to pomocnicza funkcja rysująca planszę (ale u Ciebie może robić cokolwiek innego z każdym rozwiązaniem):
void print_board(vector<int> queens) {
for (int row = 0; row < queens.size(); row++) {
for (int col = 0; col < queens.size(); col++) {
printf("%c", queens[row] == col ? 'x' : '.');
} printf("\n");
} printf("---\n");
}
- Rejestracja:około 12 lat
- Ostatnio:około 10 lat
- Postów:161
0
Dzięki Panowie za pomysły. Trochę mi się już rozjaśniło. Wrzucam jednak treść zadania: http://4programmers.net/Pastebin/2474.
Co wy na to? Jeszcze bardziej zakręcone co nie?
- Rejestracja:ponad 19 lat
- Ostatnio:2 miesiące
0
Witam, właśnie bawię się algorytmem węgierskim i mam problem przy "wykreślaniu" zer, mógłby ktoś podpowiedzieć jak to najłatwiej zrobić? Z góry dzięki :)
btw. załóż nowy temat na przyszłość, ten już ma rozwiązanie.
- Rejestracja:ponad 19 lat
- Ostatnio:2 miesiące
1
vector<vector<unsigned> > Tb(N,vector<unsigned>(N,0));
vector<bool> DeletedRow(N),DeletedCol(N);
// Jeżeli MSM ma racje i problemem jest algorytm to ...
while(true)
{
vector<unsigned> Row(N),Col(N);
for(unsigned y=0;y<N;++y) if(!DeletedRow(y)) for(unsigned x=0;x<N;++x) if((!DeletedCol(x))&&(!Tb[y][x])) { ++Row(y); ++Col(x); }
vector<unsigned>::iterator R=max_element(Row.begin(),Row.end()),C=max_element(Col.begin(),Col.end());
if(*R>*C) DeletedRow[R-Row.begin()]=true;
else if(*C) DeletedCol[C-Col.begin()]=true;
else break;
}
edytowany 3x, ostatnio: _13th_Dragon
- Rejestracja:prawie 16 lat
- Ostatnio:4 miesiące
0
@_13th_Dragon - myślę że chodziło bardziej o to w jaki sposób najprościej wykreślić wszystkie zera jak najmniejszą liczbą linii.
To dokładnie odpowiada szukaniu minimum vertex cover w grafie dwudzielnym, ale nie wiem czy taka redukcja łapie się pod prosty sposób (i raczej nie jest optymalne wykonywanie całej roboty od zera za każdym razem) ;).
edit: większość opisów algorytmu w sieci jest widocznie kierowana do humanistów, bo ten punkt jest kwitowany wykreśl zera jak najmniejszą ilością linii i ani słowa o metodzie. Jak na razie, znalazłem coś takiego:
Draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix obtained from step 3 by adopting the following procedure:
Mark all the rows that do not have assignments.
Mark all the columns (not already marked) which have zeros in the marked rows.
Mark all the rows (not already marked) that have assignments in marked columns.
Repeat steps 5 (i) to (iii) until no more rows or columns can be marked.
Draw straight lines through all unmarked rows and marked columns.
edytowany 3x, ostatnio: msm
Zwyczajnie wykreślasz jedną linią jak najwięcej zer w pionie lub w poziomie. Powtarzasz to w pętli nie licząc już wykreślonych. Dodałem kod wyżej - tak na wszelki wypadek.
Dzięki za informację, jeśli takie zachłanne podejście faktycznie działa to chyba aż zaimplementuje go dla poszerzenia horyzontów.
Ja bym powiedział - wielomianowe. Poza tym wyżej masz gotową implementacje, no chyba że ci chodzi o cały algorytm węgierski.