ugrás a tartalomhoz

N számú ember N számú dolgának cserélgetése úgy, hogy a legtöbb csere jöhessen létre.

Zsozsoweb · 2017. Szep. 27. (Sze), 11.04
Sziasztok!
Van egy projektem. Gyakorlatilag a lényegi megvalósítás legelején elakadtam. :(
A feladat: vannak a usereink (N számú) nekik vannak cuccaik (N számú) és minden cucchoz tartozik minimum 1 cserecucc (N számú lehet) amire hajlandók cserélni.

Pl: Van Pisti neki van 1 almája amit körtére cserélne P C=alma CSC=Körte, Gézának van körtéje de, cseresznyére cserélné, G C=Körte CSC= cseresznye és van Lali akinek van cseresznyéje de, almát szeretne érte vagy körtét. L C=cseresznye CSC= alma || körte.

Itt ugye Lali cserélhetne Gézával, Lalinak lesz körtéje Gézának cserkója frankó de, mi van Pistivel?

Pisti cseréljen Gézával körtét almára majd az almát cserkóra Lacival. mindenki örül.

Ez így egyszerű de nagy számokkal, hogyan? Bocsánat ha nem elég érthető.

phpval szeretnék dolgozni ha van megoldás.
Köszönöm a figyelmeteket!
WZS
‹ Programnyelv váltás Saját számlázó program írása ›
 ■
1

Első ránézésre ez egy

Endyl · 2017. Szep. 27. (Sze), 11.57
Első ránézésre ez egy irányított gráfban leghosszab kör megkeresése problémának tűnik (persze lehet, hogy tévedek/nem jól tudom a magyar szakszavakat). Fejből nem tudok rá hasznos implementációt, de én ilyen témában keresgélnék (vagy akár így; követelményektől függően).
3

Én erősen kétlem, hogy ez

inf · 2017. Szep. 28. (Cs), 02.42
Én erősen kétlem, hogy ez ciklikus gráf lenne, vagy bárhol lennének benne körök.
5

P -[alma]-> L -[cseresznye]-> G -[körte]-> P

Endyl · 2017. Szep. 28. (Cs), 13.42
Például: P -[alma]-> L -[cseresznye]-> G -[körte]-> P és kész a kör :) De a G -[körte]-> L -[cseresznye]-> G is kör, csak rövidebb. Ezért kell a legnagyobbat keresni, hogy ne csak az egymással cserélni tudók cseréljenek, hanem adott esetben többen is.
6

Ha így nézzük, akkor ja,

inf · 2017. Szep. 28. (Cs), 21.43
Ha így nézzük, akkor ja, mégis igazad van. :-)
2

Grafélmélet

Poetro · 2017. Szep. 27. (Sze), 12.00
Szerintem ez leginkább a gráfelméletbe tartozik. Vannak pontjaid (emberek), azok között felírhatsz utakat (mit szeretne), majd ezek közül azokat az utakat az utakat veszed, amik a legtöbb feltételt kielégítik.
4

.

inf · 2017. Szep. 28. (Cs), 03.34
|   | -[a]-> |   | -[cs]-> |   |
| P |        | L |         | G |
|   | <-[k]- |   | <-[k]-  |   |


Magát a problémát szerintem úgy a legegyszerűbb megoldani, hogy megnézed az igényeket és a felajánlásokat, és eltérő előjellel összeadod őket. Először csak az olyanokat, amiknél 1:1 termék van, a maradékon a többiek osztozhatnak. Ebből nagyjából kijön, hogy mi az, ami ténylegesen megoldható.

pl:
P: +a-k
G: +k-cs
L: +cs-(a|k)
->
+a-(a|k)
->
.


A tranzakcióknál azt érdemes fejben tartanod, hogy több dolog van, amik ellent mondhatnak egymásnak:
- a legtöbb feltétel teljesüljön (P, G és L is elégedett legyen)
- egy emberen a lehető legkevesebb tranzakció fusson át (L-nak ne kelljen 2 tranzakciót is végrehajtani), különösen, ha a végén nem kapja meg azt, amit akart
- a legkevesebb tranzakciót használd fel (3 emberre 2 tranzakció lenne a legkevesebb, de a probléma csak 3 tranzakcióval volt megoldható)

Ezeknek gondolom vannak korlátaik, pl senki nem fog napi ezer tranzakciót végrehajtani, ha árumozgatás is van, stb...

Nem hiszem, hogy találsz kész általános megoldást a problémára, ezekből próbálj elindulni, aztán fejleszteni egy sajátot.