Ugrás a tartalomhoz

auction algorithm

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

auction algorithm (tsz. auction algorithms)

  1. (informatika) Az aukciós algoritmus (angolul: auction algorithm) egy hatékony és intuitív módszer az optimális hozzárendelési problémák (pl. gépek–feladatok, munkások–munkák, eladók–vevők) megoldására. Főként lineáris hozzárendelési problémák esetén használják, ahol az a cél, hogy az elemek egy halmazát optimálisan rendeljük hozzá egy másik halmaz elemeihez úgy, hogy a teljes nyereség maximális legyen (vagy a költség minimális).


🌍 Háttér – hozzárendelési probléma

Adott:

  • Egy n × n-es költségmátrix: minden c(i, j) azt jelenti, hogy mennyi a költsége, ha az i-edik szereplőt (pl. munkás) hozzárendeljük a j-edik elemhez (pl. feladat).
  • Cél: minden szereplőt pontosan egy feladathoz rendelni úgy, hogy az összköltség minimális legyen.


🧠 Az algoritmus alapötlete

Az aukciós algoritmus egy iteratív, decentralizált módszer, amelyet Dimitri P. Bertsekas dolgozott ki a 1980-as években.

Az ötlet lényege, hogy az egyének (pl. munkások) licitálnak a feladatokra, amelyeket a legjobbnak tartanak. A feladatok ára idővel növekszik a kereslet hatására. Ez a piaci mechanizmus – kereslet-kínálat – vezérli a hozzárendelést.


🧱 Fő fogalmak

  • Árak (p(j)): minden feladathoz tartozik egy ár, amely változik a licitek hatására.
  • Haszon (u(i,j)): az i-edik munkás számára a j feladat haszna c(i,j) - p(j) (ha költség-minimalizálás a cél, akkor -c(i,j) - p(j)).
  • Legjobb feladat: az a feladat, amihez a legnagyobb hasznot társítja az adott munkás.
  • Második legjobb: a második legnagyobb hasznot nyújtó feladat.


🔁 Algoritmus lépései (személy-orientált verzió):

  1. Inicializálás: minden feladat ára p(j) = 0. Nincs hozzárendelés.

  2. Amíg van nem hozzárendelt munkás:

    • Vegyél egy i munkást, aki nincs még hozzárendelve.

    • Számítsa ki minden j feladatra a hasznot: u(i,j) = c(i,j) - p(j).

    • Válassza ki a legjobb (j*) és második legjobb feladatot (j').

    • Tegyen licitet: növelje a j* feladat árát az alábbi mértékben:

      p(j*) := p(j*) + (u(i,j') - u(i,j*)) + ε

      (Ez biztosítja, hogy legalább ε-vel több legyen az új legjobb haszon.)

    • Rendelje i-t a j* feladathoz. Ha más munkás volt ott, az felszabadul.

  3. Ismétlés, amíg minden munkás egy feladathoz van rendelve.


🔧 Paraméterek

  • ε (epsilon): kis pozitív szám, amely biztosítja a stabilitást és elkerüli az árak oszcillációját. Ha ε → 0, akkor az algoritmus közelít az optimálishoz.


📊 Példa

Tegyük fel, hogy van 3 munkás és 3 feladat, a költségmátrix:

    F1 F2 F3
M1  9  2  7
M2  6  4  3
M3  5  8  1

A cél, hogy minden munkást egy feladathoz rendeljünk, úgy, hogy az összköltség minimális legyen.

Az aukciós algoritmus szerint:

  • Minden munkás kiszámolja, melyik feladat éri meg neki legjobban az aktuális árak szerint.
  • Licitet tesz a legjobb feladatra, az ár nő.
  • Az árnövekedés kiszorítja az ott lévő másik munkást (ha volt).
  • A folyamat ismétlődik, amíg mindenki kap valamit.


✅ Előnyök

  • Párhuzamosítható: mivel a munkások döntései függetlenek.
  • Skálázható: nagy méretű hozzárendelési problémákra is jól működik.
  • Decentralizált szemlélet: jól alkalmazható disztribuált rendszerekben.
  • Nem igényli a teljes mátrix tárolását egyszerre.


❌ Hátrányok

  • Az árak lassan konvergálhatnak, ha ε túl kicsi.
  • Sok iteráció szükséges a nagy pontosság eléréséhez.
  • Nem mindig olyan gyors, mint a magyar algoritmus kis n esetén.


🆚 Aukciós algoritmus vs. Magyar algoritmus

Tulajdonság Aukciós algoritmus Magyar algoritmus
Decentralizált Igen Nem
Párhuzamosítható Igen Nem
Átlagos futásidő O(n³), de jól skáláz O(n³)
Stabilitás ε mellett Igen N/A
Pontosság (ε → 0) Optimális megoldás Optimális megoldás


📚 Alkalmazási területek

  • Robotika: több robot feladat-hozzárendelése.
  • Távközlés: sávszélesség allokáció.
  • Szállítmányozás, logisztika: jármű-hozzárendelés.
  • Felhő alapú rendszerek: erőforrás allokáció.


🧮 Matematikai háttér

A hozzárendelési probléma egy lineáris programozási feladat:

  • Változók: x(i,j) ∈ {0,1}, ha i-t j-hez rendeljük.
  • Cél: min ∑∑ c(i,j) * x(i,j)
  • Feltételek: minden i-hez pontosan egy j, és fordítva.

A dualitáselmélet szerint léteznek ár-változók (p(j)), melyek optimalizálása révén megoldható a probléma. Az aukciós algoritmus ezt a duális problémát is figyelembe veszi.


🧑‍💻 Implementációs vázlat (pszeudokód):

initialize prices p[j] = 0
while there exists unassigned agent i:
    for each job j:
        compute utility u(i,j) = value(i,j) - p[j]
    find best job j*, second best j'
    bid = u(i,j') - u(i,j*) + ε
    p[j*] += bid
    assign i to j*, unassign previous agent if needed

🧩 Variánsok

  • Diszkrét árakkal: integer-áras aukció, fix epsilon.
  • Kontinuus árakkal: finomabb, lassabb konvergencia.
  • Csak részleges hozzárendelésekre is kiterjeszthető.
  • Kapacitáskorlátos verzió: egy feladathoz több munkás rendelhető.


🏁 Összefoglalás

Az aukciós algoritmus egy rugalmas, intuitív és hatékony módszer az optimális hozzárendelés problémájára, különösen nagy méretű vagy elosztott rendszerekben. Bár nem mindig a leggyorsabb, de párhuzamosíthatósága és gyakorlati teljesítménye miatt számos valós alkalmazásban előnyös lehet.


További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=auction_algorithm&oldid=3495402”