B&B

[•paliuca]

Cum s-ar face urmatoarea problema cu Branch and Bound ? Am cautat pe google insa nu am gasit nimic concret:

Pe un mal sunt N oameni si N canibali. Ei vor sa treaca un rau cu o barca ce are o capacitate de K persoane. Gasiti o modalitate de a-i trece pe toti pe celelalt mal astfel incat nici pe mal nici in barca sa nu fie la un moment dat mai multi canibali decat oameni . Barca nu trebuie sa traverseze goala.

[•Cosmin]

Starile in problema ta sunt (i, j, k) - i e numarul de canibali de pe malul 0, j e nr de oameni de pe malul 0, k e 0 sau 1 dupa cum barca este pe malul 0 sau 1. (evident pe malul 1 vor fi N - i canibali si N - j oameni).

Acum problema cere determinarea unui drum minim de la starea (N, N) la starea (0, 0). Poti sa faci un bfs pentru a gasi solutia, sau daca O(N*N*k) e prea mult poti sa incerci un A* search sau poti daca vrei neaparat si un Branch and Bound.

[•byndrsn]

Este necesar sa fie minim drumul?

[•paliuca]

Nu trebuie sa fie minim si trebuie sa fie neaparat cu branch and bound . Partea proasta ii ca nu stiu cum sa-mi definesc o metrica sa aleg la fiecare pas ceva optim

[•byndrsn]

Poti sa incerci greedy selection, e.g. un dfs in care vizitezi cel mai "promitzator" succesor al fiecarui nod. De exemplu, dintre toate tranzitiile valide dintr-un nod poti alege tranzitia catre nodul (i, j, k) cu i + j minim sau cu |i - j| minim sau o combinatie a celor doua.

[•paliuca]

Am inteles in principiu, intrebarea mea e daca se termina algoritmul ? Cand ajung pe malul 1 iara trebuie sa fac o alegere si mi se pare destul de confuz ce conditie sa pun sau cum sa fac .

Pentru n = 12 si k = 4 si conditia i + j minim care ar fi primii pasi ? (sa ma prind cum merge)

[•byndrsn]

Daca K este par (si >= 4), lucrurile sunt mai simple. Cand K este >= 4, poti sa pui in barca un numar egal de oameni si canibali: succesorii nodului (i, i, 0) sunt (i - a, i - a, 1), unde a = 1, 2, ..., min(K / 2, i); succesorii nodului (i, i, 1) sunt (i + a, i + a, 0), unde a = 1, 2, .., min(K / 2, N - i).

Din fiecare nod (i, i, 0) poti alege sa trimiti greedy cat mai multi oameni/canibali (maximizezi a). Din fiecare nod (i, i, 1) poti alege sa trimiti inapoi cat mai putini oameni/canibali (minimizezi a). Pentru N = 12, K = 4, primii pasi sunt cam asa:

Primul nod e (12, 12, 0) si poti alege tranzitzia (12, 12, 0) -> (10, 10, 1) (alegi sa trimitzi nr maxim de oameni/canibali, i.e.,  2 din fiecare). In nodul (10, 10, 1), poti alege tranzitia (10, 10, 1) -> (11, 11, 0) (alegi sa trimitzi inapoi nr minim de oameni/canibali, i.e., 1 din fiecare). And so on. Modulo neatentzie, drumul arata cam asa:

(12, 12, 0) -> (10, 10, 1) -> (11, 11, 0) -> (9, 9, 1) -> (10, 10, 0) -> (8, 8, 1) -> (9, 9, 0) -> (7, 7, 1) -> (8, 8, 0) -> (6, 6, 1) -> (7, 7, 0) -> (5, 5, 1) -> (6, 6, 0) -> (4, 4, 1) -> (5, 5, 0) -> (3, 3, 1) -> (4, 4, 0) -> (2, 2, 1) -> (3, 3, 0) -> (1,1, 1) -> (2, 2, 0) -> (0, 0, 1)

Pentru K >= 4, poti gasi intotdeauna o solutie de genul acesta pentru ca numarul de oameni/canibali de pe malul 0 scade monoton dupa fiecare drum dus-intors. (i.e., nu e nevoie de backtracking).

Acesta este un exemplu in care alegi dintre toti succesorii care minimizeaza |i - j| pe cel (sau unul dintre cei) care minimizeaza i + j. In general, ideea e cam aceeasi: Esti in nodul (i, j, k). Calculezi succesorii lui (i, j, k), e.g., toate nodurile (i', j', 1 - k) in care poti ajunge din (i, j, k). Dintre nodurile acestea, alegi pe cel care minimizeaza i' + j' (sau alt criteriu). Daca nodul (i, j, k) nu are succesori, faci backtracking.

[•paliuca]

Multumesc, mi-a iesit  .

[•mordred]

pff, facusem la un moment dat in grafica c++ o animatie pt problema cu canibalii, cum trec raul etc