Zabójczy problem z szoferem
W teorii gier problem zabójczego szofera jest matematycznym problemem pościgu , w którym hipotetyczny biegacz, który może poruszać się tylko powoli, ale jest bardzo zwrotny, walczy z kierowcą pojazdu mechanicznego, który jest znacznie szybszy, ale znacznie mniej zwrotny, który próbuje go przegonić. Zakłada się, że zarówno biegacz, jak i kierowca nigdy się nie męczą. Pytanie do rozwiązania brzmi: w jakich okolicznościach i przy użyciu jakiej strategii kierowca samochodu może zagwarantować, że zawsze może dogonić pieszego, albo pieszy może zagwarantować, że będzie mógł w nieskończoność wymykać się samochodowi?
Problem jest często używany jako niesklasyfikowane proxy dla obrony przeciwrakietowej i innych celów wojskowych, umożliwiając naukowcom publikowanie na ten temat bez wpływu na bezpieczeństwo. [ potrzebne źródło ]
Problem ten został zaproponowany przez Rufusa Isaacsa w raporcie z 1951 roku dla RAND Corporation oraz w książce Differential Games .
Problem zabójczego szofera jest klasycznym przykładem gry różniczkowej rozgrywanej w czasie ciągłym w ciągłej przestrzeni stanów . Rachunek wariacyjny i metody ustalania poziomów mogą być używane jako ramy matematyczne do badania rozwiązań problemu. Chociaż problem jest określany jako problem rekreacyjny, jest ważnym problemem modelowym dla matematyki używanym w wielu zastosowaniach w świecie rzeczywistym.
Dyskretna wersja problemu została opisana przez Martina Gardnera (w jego książce Mathematical Carnival , rozdział 16), w której radiowóz o prędkości 2 ściga zboczeniec o prędkości 1 na prostokątnej siatce, gdzie radiowóz, ale nie oszust jest ograniczony nie wykonywać skrętów w lewo ani zawracać.
Zobacz też
- Rachunek wariacyjny
- Metoda ustawiania poziomów
- Problem pościgu za Apoloniuszem
- Problem anioła Conwaya , kolejna gra matematyczna, w której potężny i zwrotny przeciwnik walczy z bardzo zaradnym, ale mniej potężnym wrogiem
- Gra Księżniczka i potwór
- ^ R. Isaacs, Gry pościgowe , RAND Corporation (1951)
- ^ R. Isaacs, Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization , John Wiley & Sons, New York (1965), PP 349–350.
Linki zewnętrzne
- Historia problemu zabójczych szoferów , prezentacja na Kolokwium poświęconym 60-leciu prof. Pierre'a Bernharda.
- Analityczne studium przypadku gry w zabójczego szofera
- Zabójcza gra w szofera. Obliczanie zbiorów poziomów funkcji wartości
- Problem zabójczego szofera