Exista vre-un algoritm polinomial pentru aflarea unui ciclu hamiltonian de cost minim intr-un graf dens(sau complet) ?

Nu. Putem presupune ca graful e complet pentru ca putem adauga muchii cu cost infinit. Asa ca TSP intr-un graf complet e la fel de dificil ca TSP intr-un graf arbitrar.

Esti sigur ca nu e NP-hard? Eu am interpretat enuntul astfel: avem un graf in care fiecare nod are o culoare si vrem sa gasim un drum de la x la y cu un numar minim de culori. Din enunt graful pare planar, ceea ce poate schimba dificultatea problemei (although I'm skeptical about that). Daca graful e general, reducere de la Set Cover pare plauzibila: elementele (from the set cover instances) sunt noduri in graf si seturile sunt culorile. Mai precis, in afara de cele doua noduri speciale x si y, pentru fiecare element a_i si fiecare set S_j care contine elementul a_i, avem un nod v_{i, j} de culoare j. Nodul v_{i, j} (2 <= i <=  n - 1) este conectat cu v_{i - 1, k} for all k, nodul x este conectat cu nodurile v_{1, k}, si y este conectat cu nodurile v_{n, k}. Ceva de genul acesta pare sa mearga, I did not check it myself though.

Gentoo. Cand l-am instalat prima data, era una dintre putinele distributii care aveau suport pentru PowerPC. Foarte flexibil si stabil.

The Apartment (http://www.imdb.com/title/tt0053604/)

Matching http://en.wikipedia.org/wiki/Matching
Probabil ca nu (algoritmi pe grafuri se fac dintr-a 11a nu?).

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.

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.

Este necesar sa fie minim drumul?

Nu e necesar sa pui 0.

Pai cam aceeasi solutie ca si pentru subsirul de lungime maxima.

Mai precis, fie s = s_1 .. s_n si t = t_1 .. t_m sirurile initiale. Fie din[ i ][ j ] = costul maxim al unui subsir al sirurilor s_1 .. s_i si t_1 .. t_j. O recurentza e cam asa (cred):

din[ i ][ 0 ] = din[ 0 ][ j ] = 0
din[ i ][ j ] = max(0, din[ i - 1 ][ j - 1 ] + cost(s_i), din[ i ][ j - 1 ], din[ i - 1 ][ j ]), daca s_i = t_j
           = max(0, din[ i ][ j - 1 ], din[ i - 1 ][ j ]), altfel

N.B.: ma refeream la faptul ca daca o litera nu are cost unic, notiunea de cost al unui subsir nu e bine definita.

Later edit: OK, mi-am dat seama ce vrei sa spui.

Probabil ca fiecare litera are cost unic (altfel problema nu e bine definita, de ex ab poate avea cost 101). Un exemplu mai clar e bacd, adb cu costuri b : 100, a, c, d : 1. Ideea de DP e foarte similara totusi.

Dijkstra calculeaza drumurile minime. Daca folosesti Dijkstra pornind din fiecare nod, cel mai costisitor drum pe care il gasesti e distanza maxima dintre oricare 2 noduri. "Roata" (http://en.wikipedia.org/wiki/Wheel_graph wheel graph) cu 7 noduri este un contraexemplu: un ciclu de lungime 6 cu un nod in centru conectat cu toate nodurile de pe ciclu. Sa zicem ca fiecare muchie are cost 1. Distanta maxima intre oricare 2 varfuri este 2. Dar drumul de cost maxim are cost 6.

Nu-mi dai un exemplu pentru care pica Dijkstra aplicat pt fiecare nod ?

Nu imi dau seama exact la ce te referi. Vrei sa modifici algoritmul lui Dijkstra astfel incant sa aleaga la fiecare pas nodul cu distantza temporara maxima?

Scuze, ar fi trebuit sa postez mai explicit. Ma refeream la cazul in care la fiecare pas gasesti un augmenting path folosind BFS. Nu stiu daca merge in general, dar cred ca poti sa demonstrezi ca merge in cazul in care capacitatile sunt 0 sau 1.

@Lucian: Cred ca in cazul in care capacitatile sunt 0/1, numarul de muchii folosite e intotdeauna acelasi numarul de muchii folosit de algoritmul propus de tine (i.e., la fiecare pas gasesti un augmenting path folosind BFS) este egal cu numarul minim de muchii in orice flux maxim. Am crezut pentru un moment ca muchiile au capacitati 0 sau 1 pentru ca ai spus ca taietura minima are un numar minim de muchii. Mi-am dat seama apoi ce vroiai sa spui

@Marius: nu merge intotdeaua sa adaugi |E| + 1 (cel putin, nu-mi dau seama cum o sa construiesti un flux maxim in vechea retzea folosind un flux maxim in noua retzea)

Capacitatile sunt arbitrare sau doar 0/1?

Bellman-Ford, Dijkstra, etc. construiesc deja arborele drumurilor minime de la sursa catre orice alt varf. Este suficient sa stochezi predecesorul fiecarui nod.

In plus, depinde si ce costuri sunt pe muchii. Dijkstra merge doar pe grafuri cu costuri non-negative.

1. Cu putina algebra. Daca vrei sa simplifici calculele, poti sa schimbi sistemul de coordonate astfel incat unul din cercuri sa aiba centrul in origine.

2. Google is your friend. De ex, http://local.wasp.uwa.edu.au/~pbourke/geometry/polyarea/

3. Ditto. Pagina aceasta de ex. descrie the method of rotating calipers (nu imi mai amintesc daca algoritmul are un nume, eu il numesc asa pentru ca foloseste rotating calipers ca sa afle convex hull-ul (infasurarea convexa?))
http://www.iro.umontreal.ca/~plante/compGeom/algorithm.html

Message preview mergea bine in versiuni mai vechi de Safari (ultima versiune de Safari pre-Leopard cel putin). Sunt cateva diferentze intre Safari 3.1 pe Os X Tiger si Leopard, dar deocamdata bugul e prezent in ambele.

Sau

Cod:

sort(v.begin(), v.end(), greater<int>());

Erik Demaine proves P=NP
http://www.youtube.com/watch?v=VqeF98GGiXQ

Poti sa folosesti memset daca vrei sa initializezi fiecare element cu o constanta.

Pentru grafuri planare, cel mai bun algoritm deterministic e O(n) (Cheriton-Tarjan). Pentru grafuri generale, cel mai bun algoritm deterministic e O(m alpha(n, m)) (alpha -- inverse Ackerman function) (Chazelle).

Hmm, video-ul acela si-ar fi putut expune punctul de vedere si intr-un limbaj "PG 13". Vorbesc despre copii si copilarie, after all.