Блог

Я пытаюсь решить следующую проблему:

• автомобиль едет из пункта назначения в другой
• мы пытаемся добраться до точки B из точки A
• пункты назначения представляют собой графики местоположений с продолжительностью (в часах) маршрута от начала до пункта назначения в каждой вершине
• в каждый возможный час события «E» могут происходить в любом месте. Это известно заранее. Например: в пункте назначения D1 произойдет событие в час h = 0, h = 1, h = 4. То же самое, например, для других пунктов назначения.
• мы пытаемся добраться из точки A в точку B таким образом, чтобы она встречала минимальное количество событий. т.е. мы пытаемся избежать прибытия в место, где в это время будет происходить «событие»
• на самом деле нас не волнует общая продолжительность поездки, если она меньше заданного общего времени (например, 100 часов)
• мы можем ждать на месте в одном и том же месте сколь угодно долго

Я могу решить эту проблему с помощью динамического программирования, но, похоже, сложность для этого довольно велика, так как в каждом возможном пункте назначения я тестирую все другие возможные пункты назначения в качестве следующего шага, плюс все возможное время ожидания на месте (например, поездка в город D после ожидания 1 часа, переходв город D после ожидания 2 часов и т. Д.).

Есть ли более разумный способ решить эту проблему? Я думаю, тот факт, что «события» не имеют определенной структуры, усложняет задачу. В идеале я бы сначала выяснил все возможные маршруты от A до B, а затем каким-то образом добавил знания о событиях