Я пытаюсь решить задачу оптимизации, это должно быть сделано с использованием кратчайшего пути графа.Прямо сейчас я застрял, пытаясь смоделировать проблему в виде графика.
Проблема (может быть расширена для n человек, я сделаю пример с n = 3): три парня хотят пересечь реку, скажем, A, B и C. У них есть лодка, и только два из них могут покататься на ней одновременно.Каждый из них может совершить поездку в одиночку со следующим временем:
- A: 40 минут
- B: 30 минут
- C: 40 минут
Если два человека путешествуют вместе, они берут время самого медленного, например, если А и В идут вместе, им требуется 40 минут, чтобы пересечь реку.Затем один из них должен забрать лодку обратно, и это займет X минут, поэтому, если A и B сойдутся вместе, B сможет вернуть лодку обратно, прибавив 30 минут к общему времени.Я хочу найти последовательность минимального времени, необходимого, чтобы перевести всех ребят на другую сторону.
Я думал, что A, B, C, F должны быть вершиной моего графа, а F - конечной точкой.и ребра должны быть временем, но теперь я совершенно уверен в том, как установить связь между ними, чтобы потом найти кратчайший путь.