bridge and torch problem

Üdvözlöm, Ön a bridge and torch problem szó jelentését keresi. A DICTIOUS-ban nem csak a bridge and torch problem szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a bridge and torch problem szót egyes és többes számban mondani. Minden, amit a bridge and torch problem szóról tudni kell, itt található. A bridge and torch problem szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. Abridge and torch problem és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.

Angol

Főnév

bridge and torch problem (tsz. bridge and torch problems)

  1. (informatika) A Bridge and Torch Problem (magyarul: híd és fáklya probléma) egy klasszikus logikai optimalizálási feladvány, amit gyakran alkalmaznak mesterséges intelligencia, kombinatorika, és állapottér-keresés oktatásában. A cél: minimális idő alatt átjuttatni egy csoport embert egy sötét hídon egyetlen fáklyával, korlátozott szabályok mellett.


🧠 A probléma alapverziója

Feladat:

Négy ember áll egy sötét híd egyik oldalán. Mindannyian át akarnak jutni a híd másik oldalára, de csak egy fáklyájuk van, és a hídon egyszerre legfeljebb ketten mehetnek át.

Minden személy más-más sebességgel halad:

  • A: 1 perc
  • B: 2 perc
  • C: 5 perc
  • D: 10 perc

Szabályok:

  1. A fáklya kötelező: senki sem kelhet át nélküle.
  2. Egyszerre legfeljebb 2 ember lehet a hídon.
  3. Ketten együtt a lassabbik sebességével haladnak.
  4. A fáklyát valakinek mindig vissza kell hoznia.


🎯 Cél:

Mindenki jusson át a túloldalra minimális idő alatt.


🔄 Tipikus rossz megoldás (nem optimális):

  1. A + B átkel (2 perc)
  2. A visszaviszi a fáklyát (1 perc)
  3. C + D átkel (10 perc)
  4. B visszaviszi a fáklyát (2 perc)
  5. A + B újra átkel (2 perc)

🕐 Összesen: 2 + 1 + 10 + 2 + 2 = 17 perc


✅ Optimális stratégia (jobb megoldás):

  1. A + B átkel → 2 perc
  2. A visszaviszi → 1 perc
  3. C + D átkel → 10 perc
  4. B visszaviszi → 2 perc
  5. A + B átkel újra → 2 perc

🕐 Összesen: 2 + 1 + 10 + 2 + 2 = 17 perc

❗Ez ugyanaz, mint a fenti, de valójában ez az optimális megoldás. Más stratégiák hosszabbak lesznek.


🧮 Lehetséges megközelítések

A probléma kis mérete miatt:

  • Teljes állapottér-felépítés lehetséges (minden átjutási kombináció felderítése)
  • Greedy algoritmus nem működik jól, mert a lokálisan legjobb választás nem globálisan optimális
  • Heurisztikus keresés (pl. A*) alkalmazható bonyolultabb verziókra


🧱 Állapottér modellezése

Minden állapot leírható: 

(A, B, C, D, Fáklya helyzete)

Pl. (True, True, False, False, True) azt jelenti: A és B már átjutottak, C és D még nem, a fáklya az új oldalon van.

Az állapottér gráfban az élek a lehetséges mozgások (áthaladások), a csúcsok pedig az egyes állapotok.


🛠 Variánsok

  • Több ember
  • Több fáklya
  • Különböző hídhossz vagy törékeny híd
  • Napszak (fényviszonyok váltakoznak)
  • Veszélyes zónák (pl. túl sok ember egyszerre leszakítja a hidat)


🧩 TL;DR

A Bridge and Torch probléma egy klasszikus időoptimalizálási logikai feladvány, ahol embereket kell átkísérni egy hídon korlátozott fáklyával és mozgási szabályokkal. A cél a minimális összidő, miközben a mozgások kombinációi gondos tervezést igényelnek.


További információk

Enciclo
Wikious
Sapientia
Scientia
Boobota
Anandapedia
Sagapedia
Wikithot